Subdivision SurfacesModeling3D Object RepresentationsEquivalence of RepresentationsComputational DifferencesSlide 6SurfacesSlide 8SubdivisionSlide 10Key QuestionsLoop Subdivision SchemeSlide 13Slide 14LoopSlide 16Subdivision SchemesSlide 18Slide 19Slide 20Polygon MeshesIndependent FacesVertex and Face TablesAdjacency ListsPartial Adjacency ListsWinged EdgeSlide 27Triangle MeshesSummaryGreg HumphreysCS445: Intro GraphicsUniversity of Virginia, Fall 2003Subdivision SurfacesGreg HumphreysUniversity of VirginiaCS 445, Fall 2003Modeling•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 dataVoxelsPoint cloudRange imagePolygons•SurfacesMeshSubdivision ParametricImplicit•SolidsOctreeBSP treeCSGSweep•High-level structuresScene graphSkeletonApplication specificEquivalence of Representations•Thesis:Each fundamental representation has enough expressive power to model the shape of any geometric objectIt is possible to perform all geometric operations with any fundamental representation!•Analogous to Turing-Equivalence:All computers today are turing-equivalent, but we still have many different processorsComputational Differences•EfficiencyCombinatorial complexitySpace/time trade-offsNumerical accuracy/stability•SimplicityEase of acquisitionHardware accelerationSoftware creation and maintenance•UsabilityDesigner interface vs. computational engine3D Object Representations•Raw dataVoxelsPoint cloudRange imagePolygons•SurfacesMeshSubdivision ParametricImplicit•SolidsOctreeBSP treeCSGSweep•High-level structuresScene graphSkeletonApplication specificSurfaces•What makes a good surface representation?AccurateConciseIntuitive specificationLocal supportAffine invariantArbitrary topologyGuaranteed continuity Natural parameterizationEfficient displayEfficient intersectionsH&B Figure 10.46Subdivision Surfaces•Properties:AccurateConciseIntuitive specificationLocal supportAffine invariantArbitrary topologyGuaranteed continuity Natural parameterizationEfficient displayEfficient intersectionsPixarSubdivision•How do you make a smooth curve?Zorin & SchroederSIGGRAPH 99 Course NotesSubdivision Surfaces•Coarse mesh & subdivision ruleDefine 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 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 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 surfaceInterested in continuity of surface and smoothnessInvolves calculating eigenvalues of matrices»Original Loop»Warren))cos((224183851nn3316383nnnLoop Subdivision SchemeZorin & SchroederSIGGRAPH 99 Course NotesLimit surface has provable smoothness properties!Subdivision Schemes•There are different subdivision schemesDifferent 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 NotesKey Questions•How refine mesh?Aim for properties like smoothness•How store mesh?Aim for efficiency for implementing subdivision rulesZorin & SchroederSIGGRAPH 99 Course NotesPolygon Meshes•Mesh RepresentationsIndependent facesVertex and face tablesAdjacency listsWinged-EdgeIndependent Faces•Each face lists vertex coordinatesRedundant verticesNo topology informationVertex and Face Tables•Each face lists vertex referencesShared verticesStill no topology informationAdjacency Lists•Store all vertex, edge, and face adjacencies Efficient topology traversalExtra storagePartial Adjacency Lists•Can we store only some adjacency relationshipsand derive others?Winged Edge•Adjacency encoded in edgesAll adjacencies in O(1) timeLittle extra storage (fixed records)Arbitrary polygonsWinged Edge•Example:Triangle Meshes•Relevant properties:Exactly 3 vertices per faceAny number of faces per vertex•Useful adjacency structure for Loop subdivision:Do not represent edges explicitlyFaces store refs to vertices and neighboring facesVertices store refs to adjacent faces and verticesSummary•Advantages:Simple method for describing complex surfacesRelatively easy to implementArbitrary topologyLocal supportGuaranteed continuityMultiresolution•Difficulties:Intuitive specification
View Full Document
Unlocking...