1Subdivision SurfacesTom FunkhouserPrinceton UniversityCOS 426, Spring 2006Modeling• How do we ... Represent 3D objects in a computer? Acquire computer representations of 3D objects? Manipulate computer representations of 3D objects? Analyze computer representations of 3D objects?Different representations for different types of objects and operations3D 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 specific3D 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 specificSurfaces• 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.46Polygon Meshes• How should we represent a mesh in a computer? Efficient traversal of topology Efficient use of memory• Mesh Representations Independent faces Vertex and face tables Adjacency lists Winged-EdgeZorin & Schroeder, SIGGRAPH 99, Course Notes2Polygon Meshes• How should we represent a mesh in a computer? Efficient traversal of topology Efficient use of memory• Mesh Representations Independent faces Vertex and face tables Adjacency lists Winged-EdgeZorin & Schroeder, SIGGRAPH 99, Course NotesIndependent Faces• Each face lists vertex coordinatesIndependent Faces• Each face lists vertex coordinates Redundant vertices No topology informationVertex and Face Tables• Each face lists vertex references Shared verticesVertex and Face Tables• Each face lists vertex references Shared vertices Still no topology informationAdjacency Lists• Store all vertex, edge, and face adjacencies Efficient topology traversal3Adjacency 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 polygonsWinged Edge• Example:3D 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 specificGerry’s GamePixar4Surfaces• 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• How do you make a smooth curve?Zorin & SchroederSIGGRAPH 99 Course NotesSubdivision Surfaces• Coarse mesh & subdivision rule Define smooth surface as limit of sequence of refinements Zorin & SchroederSIGGRAPH 99 Course NotesKey Questions• How refine mesh? Aim for properties like smoothness• How store mesh? Aim for efficiency for implementing subdivision rulesZorin & SchroederSIGGRAPH 99 Course NotesLoop Subdivision Scheme• How refine mesh? Refine each triangle into 4 triangles by splitting each edge and connecting new vertices Need rules for “even / odd” (white / black) verticesZorin & SchroederSIGGRAPH 99 Course NotesLoop Subdivision Scheme• How position new vertices? Choose locations for new vertices as weighted average of original vertices in local neighborhoodZorin & SchroederSIGGRAPH 99 Course NotesWhat if odd vertex only touches one triangle?Odd: Even:What if even vertex does not have degree 6?5Loop 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» Warren))cos((224183851nnπβ+−= =>=3316383nnnβLoop 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 Notes6Subdivision Surfaces• Properties: Accurate Concise Intuitive specification Local support Affine invariant Arbitrary topology Guaranteed continuity Natural parameterization Efficient display Efficient intersectionsPixarSubdivision Surfaces• Advantages: Simple method for describing complex surfaces Relatively easy to implement Arbitrary topology Local support Guaranteed continuity Multiresolution• Difficulties: Intuitive specification Parameterization IntersectionsKey Questions• How refine mesh? Aim for properties like smoothness• How store mesh? Aim for efficiency for implementing subdivision rulesZorin & SchroederSIGGRAPH 99 Course NotesTriangle 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 verticesAssignment 3• Interactive editing of subdivision surfaces Loop subdivision scheme Partial adjacency list mesh representation Interactive vertex draggingAssignment 3• Edit coarse mesh while display subdivided mesh7Assignment 3• Store hierarchy of meshes Full triangle mesh at every level Vertices store references to counterparts one level up and one level down Enables efficient re-positioning of mesh vertices afterinteractive draggingLevel i Level i+1SummaryAccurate No YesConcise No YesIntuitive specification No NoLocal support Yes YesAffine invariant Yes YesArbitrary
View Full Document
Unlocking...