11Subdivision SurfacesAdam FinkelsteinPrinceton UniversityC0S 426, Fall 20012Course SyllabusI. Image processingII. RenderingIII. ModelingIV. AnimationImage Processing(Rusty Coleman, CS426, Fall99)Modeling(Dennis Zorin, CalTech)Animation(Angel, Plate 1)Rendering(Michael Bostock, CS426, Fall99)3Course SyllabusI. Image processingII. RenderingIII. ModelingIV. AnimationImage Processing(Rusty Coleman, CS426, Fall99)Modeling(Dennis Zorin, CalTech)Animation(Angel, Plate 1)Rendering(Michael Bostock, CS426, Fall99)4Modeling• How do we ...o Represent 3D objects in a computer?o Construct 3D representations quickly/easily?o Manipulate 3D representations efficiently?Different representations for different types of objects53D Object Representations• Raw datao Voxelso Point cloudo Range imageo Polygons•Surfaceso Mesho Subdivisiono Parametrico Implicit•Solidso Octreeo BSP treeo CSGo Sweep• High-level structureso Scene grapho Skeletono Application specific6Equivalence of Representations• Thesis:o Each fundamental representation has enoughexpressive power to model the shapeof any geometric objecto It is possible to perform all geometric operations withany fundamental representation!• Analogous to Turing-Equivalence:o All computers today are turing-equivalent,but we still have many different processors27Computational Differences• Efficiencyo Combinatorial complexity (e.g. O( n log n ) )o Space/time trade-offs (e.g. z-buffer)o Numerical accuracy/stability (degree of polynomial)• Simplicityo Ease of acquisitiono Hardware accelerationo Software creation and maintenance•Usabilityo Designer interface vs. computational engine83D Object Representations• Raw datao Voxelso Point cloudo Range imageo Polygons• Surfaceso Mesho Subdivisiono Parametrico Implicit•Solidso Octreeo BSP treeo CSGo Sweep• High-level structureso Scene grapho Skeletono Application specific9Surfaces• What makes a good surface representation?o Accurateo Conciseo Intuitive specificationo Local supporto Affine invarianto Arbitrary topologyo Guaranteed continuityo Natural parameterizationo Efficient displayo Efficient intersectionsH&B Figure 10.4610Subdivision• How do you make a smooth curve?Zorin & SchroederSIGGRAPH 99Course Notes11Subdivision Surfaces• Coarse mesh & subdivision ruleo Define smooth surface as limit ofsequence of refinementsZorin & SchroederSIGGRAPH 99Course Notes12Key Questions• How refine mesh?o Aim for properties like smoothness• How store mesh?o Aim for efficiency for implementing subdivision rulesZorin & SchroederSIGGRAPH 99Course Notes313Loop Subdivision Scheme• How refine mesh?o Refine each triangle into 4 triangles bysplitting each edge and connecting new verticesZorin & SchroederSIGGRAPH 99Course Notes14Loop Subdivision Scheme• How position new vertices?o Choose locations for new vertices as weighted averageof original vertices in local neighborhoodZorin & SchroederSIGGRAPH 99Course NotesWhat if vertex does not have degree 6?15Loop Subdivision Scheme• Rules for extraordinary vertices and boundaries:Zorin & SchroederSIGGRAPH 99Course Notes16Loop• How to choose β?o Analyze properties of limit surfaceo Interested in continuity of surface and smoothnesso Involves calculating eigenvalues of matrices» Original Loop» Warren))cos((224183851nnπβ+−==>=3316383nnnβ17Loop Subdivision SchemeZorin & SchroederSIGGRAPH 99Course NotesLimit surface has provable smoothness properties!18Subdivision Schemes• There are different subdivision schemeso Different methods for refining topologyo Different rules for positioning vertices» Interpolating versus approximatingZorin & Schroeder, SIGGRAPH 99 , Course Notes419Subdivision SchemesZorin & SchroederSIGGRAPH 99Course Notes20Subdivision SchemesZorin & SchroederSIGGRAPH 99Course Notes21Key Questions• How refine mesh?o Aim for properties like smoothness• How store mesh?o Aim for efficiency for implementing subdivision rulesZorin & SchroederSIGGRAPH 99Course Notes22Polygon Meshes• Mesh Representationso Independent faceso Vertex and face tableso Adjacency listso Winged-Edge23Independent Faces• Each face lists vertex coordinateso Redundant verticeso No topology information24Vertex and Face Tables• Each face lists vertex referenceso Shared verticeso Still no topology information525Adjacency Lists• Store all vertex, edge, and face adjacencieso Efficient topology traversalo Extra storage26Partial Adjacency Lists• Can we store only some adjacency relationshipsand derive others?27Winged Edge• Adjacency encoded in edgeso All adjacencies in O(1) timeo Little extra storage (fixed records)o Arbitrary polygons28Winged Edge•Example:29Triangle Meshes• Relevant properties:o Exactly 3 vertices per faceo Any number of faces per vertex• Useful adjacency structure for Loop subdivision:o Do not represent edges explicitlyo Faces store refs to vertices and neighboring faceso Vertices store refs to adj acent faces and vertices30Assignment 4• Interactive editing of subdivision surfaceso Loop subdivision schemeo Partial adjacency list mesh representationo Interactive vertex dragging631Assignment 4• Edit coarse mesh while display subdivided mesh32Assignment 4• Store hierarchy of mesheso Full triangle mesh at every levelo Vertices store references to counterpartsone level up and one level downo Enables efficient re-positioning of mesh vertices afterinteractive draggingLevel i Level i+133Subdivision Surfaces• Properties:o Accurateo Conciseo Intuitive specificationo Local supporto Affine invarianto Arbitrary topologyo Guaranteed continuityo Natural parameterizationo Efficient displayo Efficient intersectionsPixar34Summary• Advantages:o Simple method for describing complex surfaceso Relatively easy to implemento Arbitrary topologyo Local supporto Guaranteed continuityo Multiresolution• Difficulties:o Intuitive specificationo Parameterizationo
View Full Document
Unlocking...