1Greg HumphreysCS445: Intro GraphicsUniversity of Virginia, Fall 2003Subdivision SurfacesGreg HumphreysUniversity of VirginiaCS 445, Fall 2003Modeling• How do we ...D Represent 3D objects in a computer?D Construct 3D representations quickly/easily?D Manipulate 3D representations efficiently?Different representations for different types of objects3D Object Representations• Raw dataD VoxelsD Point cloudD Range imageD Polygons• SurfacesD MeshD Subdivision D ParametricD Implicit• SolidsD OctreeD BSP treeD CSGD Sweep• High-level structuresD Scene graphD SkeletonD Application specificEquivalence of Representations• Thesis:D Each fundamental representation has enough expressive power to model the shape of any geometric objectD It is possible to perform all geometric operations with any fundamental representation!• Analogous to Turing-Equivalence:D All computers today are turing-equivalent, but we still have many different processors2Computational Differences• EfficiencyD Combinatorial complexityD Space/time trade-offsD Numerical accuracy/stability• SimplicityD Ease of acquisitionD Hardware accelerationD Software creation and maintenance• UsabilityD Designer interface vs. computational engine3D Object Representations• Raw dataD VoxelsD Point cloudD Range imageD Polygons• SurfacesD MeshD Subdivision D ParametricD Implicit• SolidsD OctreeD BSP treeD CSGD Sweep• High-level structuresD Scene graphD SkeletonD Application specificSurfaces• What makes a good surface representation?D AccurateD ConciseD Intuitive specificationD Local supportD Affine invariantD Arbitrary topologyD Guaranteed continuity D Natural parameterizationD Efficient displayD Efficient intersectionsH&B Figure 10.46Subdivision Surfaces• Properties:D AccurateD ConciseD Intuitive specificationD Local supportD Affine invariantD Arbitrary topologyD Guaranteed continuity D Natural parameterizationD Efficient displayD Efficient intersectionsPixar3Subdivision• How do you make a smooth curve?Zorin & SchroederSIGGRAPH 99 Course NotesSubdivision Surfaces• Coarse mesh & subdivision ruleD Define smooth surface as limit of sequence of refinements Zorin & SchroederSIGGRAPH 99 Course NotesBase Mesh Limit Surface4Key Questions• How refine mesh?D Aim for properties like smoothness• How store mesh?D Aim for efficiency for implementing subdivision rulesZorin & SchroederSIGGRAPH 99 Course NotesLoop Subdivision Scheme• How refine mesh?D Refine each triangle into 4 triangles by splitting each edge and connecting new verticesZorin & SchroederSIGGRAPH 99 Course NotesLoop Subdivision Scheme• How position new vertices?D Choose locations for new vertices as weighted average of original 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 Notes5Loop• How to choose β?D Analyze properties of limit surfaceD Interested in continuity of surface and smoothnessD 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 schemesD Different methods for refining topology D Different rules for positioning vertices » Interpolating versus approximatingZorin & Schroeder, SIGGRAPH 99 , Course NotesSubdivision SchemesZorin & SchroederSIGGRAPH 99 Course Notes6Subdivision SchemesZorin & SchroederSIGGRAPH 99 Course NotesKey Questions• How refine mesh?D Aim for properties like smoothness• How store mesh?D Aim for efficiency for implementing subdivision rulesZorin & SchroederSIGGRAPH 99 Course NotesPolygon Meshes• Mesh RepresentationsD Independent facesD Vertex and face tablesD Adjacency listsD Winged-EdgeIndependent Faces• Each face lists vertex coordinatesD Redundant verticesD No topology information7Vertex and Face Tables• Each face lists vertex referencesD Shared verticesD Still no topology informationAdjacency Lists• Store all vertex, edge, and face adjacencies D Efficient topology traversalD Extra storagePartial Adjacency Lists• Can we store only some adjacency relationshipsand derive others? Winged Edge• Adjacency encoded in edgesD All adjacencies in O(1) timeD Little extra storage (fixed records)D Arbitrary polygons8Winged Edge•Example:Triangle Meshes• Relevant properties:D Exactly 3 vertices per faceD Any number of faces per vertex• Useful adjacency structure for Loop subdivision:D Do not represent edges explicitlyD Faces store refs to vertices and neighboring facesD Vertices store refs to adjacent faces and verticesSummary• Advantages:D Simple method for describing complex surfacesD Relatively easy to implementD Arbitrary topologyD Local supportD Guaranteed continuityD Multiresolution• Difficulties:D Intuitive specification D ParameterizationD
View Full Document
Unlocking...