1Greg HumphreysCS445: Intro GraphicsUniversity of Virginia, Fall 2004Subdivision SurfacesModeling• How do we ... Represent 3D objects in a computer? Construct 3D representations quickly/easily? Manipulate 3D representations efficiently?Different representations for different types of objects3D 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 Skeleton Application specificEquivalence of Representations• Thesis: Each fundamental representation has enough expressivepower to model the shapeof any geometric object It is possible to perform all geometric operations with anyfundamental representation!• Analogous to Turing-Equivalence: All computers today are turing-equivalent,but we still have many different processorsComputational Differences• Efficiency Combinatorial complexity Space/time trade-offs Numerical accuracy/stability• Simplicity Ease of acquisition Hardware acceleration Software creation and maintenance• Usability Designer interface vs. computational engine3D 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 Skeleton Application specific2Surfaces• What makes a good surface representation? Accurate Concise Intuitive specification Local support Affine invariant Arbitrary topology Guaranteed continuity Natural parameterization Efficient display Efficient intersectionsH&B Figure 10.46Subdivision Surfaces• Properties: Accurate Concise Intuitive specification Local support Affine invariant Arbitrary topology Guaranteed continuity Natural parameterization Efficient display Efficient intersectionsPixarSubdivision• How do you make a smooth curve?Zorin & SchroederSIGGRAPH 99 Course NotesSubdivision Surfaces• Coarse mesh & subdivision rule Define smooth surface as limit ofsequence of refinementsZorin & SchroederSIGGRAPH 99 Course NotesSubdivision SurfacesBase Mesh3Limit SurfaceKey Questions• How to refine the mesh? Aim for properties like smoothness• How to store the mesh? Aim for efficiency for implementing subdivision rulesZorin & SchroederSIGGRAPH 99 Course NotesLoop Subdivision Scheme• Mesh refinement Refine each triangle into 4 triangles bysplitting each edge and connecting new verticesZorin & SchroederSIGGRAPH 99 Course NotesLoop Subdivision Scheme• New vertex positions Choose locations for new vertices as weighted average oforiginal vertices in local neighborhoodZorin & SchroederSIGGRAPH 99 Course NotesWhat if vertex does not have degree 6?Loop Subdivision Scheme• Rules for extraordinary vertices and boundaries:Zorin & SchroederSIGGRAPH 99 Course NotesLoop• How to choose β? Analyze properties of limit surface Interested in continuity of surface and smoothness Involves calculating eigenvalues of matrices» Original Loop» Warren4Loop Subdivision SchemeZorin & SchroederSIGGRAPH 99 Course NotesLimit surface has provable smoothness properties!Subdivision Schemes• There are different subdivision schemes Different methods for refining topology Different rules for positioning vertices» Interpolating versus approximatingZorin & Schroeder, SIGGRAPH 99 , Course NotesSubdivision SchemesZorin & SchroederSIGGRAPH 99 Course NotesSubdivision SchemesZorin & SchroederSIGGRAPH 99 Course NotesThe Limit Surface• Move each vertex to the limit surface Special “final” subdivision rule:• Compute limit surface tangents Center vertex weight=0 Neighbor vertices (must sum to zero):Key Questions• How refine mesh? Aim for properties like smoothness• How store mesh? Aim for efficiency for implementing subdivision rulesZorin & SchroederSIGGRAPH 99 Course Notes5Polygon Meshes• Mesh Representations Independent faces Vertex and face tables Adjacency lists Winged-EdgeIndependent Faces• Each face lists vertex coordinates Redundant vertices No topology informationVertex and Face Tables• Each face lists vertex references Shared vertices Still no topology informationAdjacency Lists• Store all vertex, edge, and face adjacencies Efficient topology traversal Extra storagePartial Adjacency Lists• Can we store only some adjacency relationshipsand derive others?Winged Edge• Adjacency encoded in edges All adjacencies in O(1) time Little extra storage (fixed records) Arbitrary polygons6Winged Edge• Example:Triangle Meshes• Relevant properties: Exactly 3 vertices per face Any number of faces per vertex• Useful adjacency structure for Loop subdivision: Do not represent edges explicitly Faces store refs to vertices and neighboring faces Vertices store refs to adjacent faces and verticesSummary• Advantages: Simple method for describing complex surfaces Relatively easy to implement Arbitrary topology Local support Guaranteed continuity Multiresolution• Difficulties: Intuitive specification Parameterization
View Full Document