1SurfacesThomas FunkhouserPrinceton UniversityCOS 426, Spring 20063D Object Representations• Raw data Voxels Point cloud Range image Polygons• Surfaces Mesh Subdivision Parametric Implicit• Solids Octree BSP tree CSG Sweep• High-level structures Scene graph Application specificCurved Surfaces• What makes a good surface representation? Accurate Concise Intuitive specification Local support Affine invariant Arbitrary topology Guaranteed continuity Natural parameterization Efficient display Efficient intersectionsCurved Surface Representations• Polygonal meshes• Subdivision surfaces• Parametric surfaces• Implicit surfaces Parametric Surfaces• Boundary defined by parametric functions: x = fx(u,v) y = fy(u,v) z = fz(u,v)• Example: ellipsoidH&B Figure 10.10φθφθφsinsincoscoscoszyxrzryrx===Parametric Surfaces• Advantages: Easy to enumerate points on surface• Problem: Need piecewise-parametrics surfaces to describe complex shapesuvFvDFH Figure 11.422Parametric Surfaces• Boundary defined by parametric functions: x = fx(u,v) y = fy(u,v) z = fz(u,v)• Example: ellipsoidH&B Figure 10.10φθφθφsinsincoscoscoszyxrzryrx===Parametric Surfaces• Boundary defined by parametric functions: x = fx(u,v) y = fy(u,v) z = fz(u,v)FvDFH Figure 11.42uvxyzuvParametric functions define mapping from (u,v) to (x,y,z):Piecewise Parametric Surfaces• Surface is partitioned into parametric patches:Watt Figure 6.25Same ideas as parametric splines!Parametric Patches• Each patch is defined by blending control pointsSame ideas as parametric curves!FvDFH Figure 11.44Parametric Patches• Point Q(u,v) on the patch is the tensor product of parametric curves defined by the control pointsWatt Figure 6.21Q(u,v)Q(0,0)Q(1,0)Q(0,1)Q(1,1)Parametric Bicubic PatchesPoint Q(u,v) on any patch is defined by combining control points with polynomial blending functions:TTVMUM =4,43,42,41,44,33,32,31,34,23,22,21,24,13,12,11,1),(PPPPPPPPPPPPPPPPvuQWhere M is a matrix describing the blending functionsfor a parametric cubic curve (e.g., Bezier, B-spline, etc.)[]123uuu=U[]123vvv=V3B-Spline PatchesVMUMTSplineBSplineB −− =4,43,42,41,44,33,32,31,34,23,22,21,24,13,12,11,1),(PPPPPPPPPPPPPPPPvuQWatt Figure 6.28 −−−−=−061326102102102112161212161SplineBMBezier PatchesVMUMTBezierBezier =4,43,42,41,44,33,32,31,34,23,22,21,24,13,12,11,1),(PPPPPPPPPPPPPPPPvuQFvDFH Figure 11.42 −−−−=0001003303631331BezierMBezier Patches • Properties: Interpolates four corner points Convex hull Local controlWatt Figure 6.22Bezier Surfaces• Continuity constraints are similar to the ones for Bezier splinesFvDFH Figure 11.43Bezier Surfaces• C0continuity requires aligning boundary curvesWatt Figure 6.26aBezier Surfaces• C1continuity requires aligning boundary curves and derivativesWatt Figure 6.26b4Drawing Bezier Surfaces• Simple approach is to loop through uniformly spaced increments of u and vDrawSurface(void) {for (int i = 0; i < imax; i++) {float u = umin + i * ustep;for (int j = 0; j < jmax; j++) {float v = vmin + j * vstep;DrawQuadrilateral(...);}}}DrawSurface(void) {for (int i = 0; i < imax; i++) {float u = umin + i * ustep;for (int j = 0; j < jmax; j++) {float v = vmin + j * vstep;DrawQuadrilateral(...);}}}Watt Figure 6.32Drawing Bezier Surfaces• Better approach is to use adaptive subdivision:DrawSurface(surface) {if Flat (surface, epsilon) {DrawQuadrilateral(surface);}else {SubdivideSurface(surface, ...);DrawSurface(surfaceLL);DrawSurface(surfaceLR);DrawSurface(surfaceRL);DrawSurface(surfaceRR);}}DrawSurface(surface) {if Flat (surface, epsilon) {DrawQuadrilateral(surface);}else {SubdivideSurface(surface, ...);DrawSurface(surfaceLL);DrawSurface(surfaceLR);DrawSurface(surfaceRL);DrawSurface(surfaceRR);}}Uniform subdivisionAdaptive subdivisionWatt Figure 6.32Drawing Bezier Surfaces• One problem with adaptive subdivision is avoiding cracks at boundaries between patches at different subdivision levelsAvoid these cracks by adding extra vertices and triangulatingquadrilaterals whose neighbors are subdivided to a finer levelCrackWatt Figure 6.33Parametric Surfaces• Advantages: Easy to enumerate points on surface Possible to describe complex shapes• Disadvantages: Control mesh must be quadrilaterals Continuity constraints difficult to maintain Hard to find intersections Curved Surface Representations• Polygonal meshes• Subdivision surfaces• Parametric surfaces• Implicit surfaces Implicit Surfaces• Boundary defined by implicit function: f (x, y, z) = 0• Example: linear (plane) ax + by +cz + d = 0N = (a,b,c)(x,y,z)5Implicit Surfaces• Example: quadricf(x,y,z)=ax2+by2+cz2+2dxy+2eyz+2fxz+2gx+2hy+2jz+k• Common quadric surfaces: Sphere Ellipsoid Torus Paraboloid HyperboloidH&B Figure 10.1001222=−++zyxrzryrxImplicit surface examplesSkin [Markosian99]MaxMan Blobby ObjectImplicit Surface Examples• Voxels describe density at regular sample points Surface may not be described explicitlyVisible Human(National Library of Medicine)SUNY Stoney BrookImplicit Surfaces• Advantages: Easy to test if point is on surface Easy to intersect two surfaces Easy to compute z given x and y• Disadvantages: Hard to describe specific complex shapes Hard to enumerate points on surfaceSummaryAccurate No Yes Yes YesConcise No Yes Yes YesIntuitive specification No No Yes NoLocal support Yes No Yes YesAffine invariant Yes Yes Yes YesArbitrary topology Yes No No YesGuaranteed continuity No Yes Yes YesNatural parameterization No No Yes NoEfficient display Yes No Yes YesEfficient intersections No Yes No NoPolygonalMeshImplicitSurfaceParametricSurfaceSubdivisionSurfaceFeature3D Object Representations• Raw data Point cloud Range image Polygon soup• Surfaces Mesh Subdivision Parametric Implicit• Solids Voxels BSP tree CSG Sweep• High-level structures Scene graph Application specific6Solid Modeling Representations• What makes a good solid representation? Accurate Concise Affine invariant Easy acquisition Guaranteed validity Efficient
View Full Document
Unlocking...