1Subdivision SurfacesThomas FunkhouserPrinceton UniversityC0S 426, Fall 2000Course SyllabusI. Image processingII. RenderingIII. ModelingIV. AnimationImage Processing(Rusty Coleman, CS426, Fall99)Modeling(Dennis Zorin, CalTech)Animation(Angel, Plate 1)Rendering(Michael Bostock, CS426, Fall99)2Course SyllabusI. Image processingII. RenderingIII. ModelingIV. AnimationImage Processing(Rusty Coleman, CS426, Fall99)Modeling(Dennis Zorin, CalTech)Animation(Angel, Plate 1)Rendering(Michael Bostock, CS426, Fall99)Modeling• How do we ...Represent 3D objects in a computer?Construct 3D representations quickly/easily?Manipulate 3D representations efficiently?Different representations for different types of objects33D Object Representations• Raw data VoxelsPoint cloudRange imagePolygons• SurfacesMeshSubdivisionParametricImplicit• SolidsOctreeBSP treeCSGSweep• High-level structuresScene graphSkeletonApplication specificEquivalence of Representations• Thesis:Each fundamental representation has enoughexpressive power to model the shapeof any geometric objectIt is possible to perform all geometric operations withany fundamental representation!• Analogous to Turing-Equivalence:All computers today are turing-equivalent,but we still have many different processors4Computational Differences• EfficiencyCombinatorial complexity (e.g. O( n log n ) )Space/time trade-offs (e.g. z-buffer)Numerical accuracy/stability (degree of polynomial)• SimplicityEase of acquisitionHardware accelerationSoftware creation and maintenance• UsabilityDesigner interface vs. computational engine3D Object Representations• Raw dataVoxelsPoint cloudRange imagePolygons• Surfaces Mesh!Subdivision"Parametric#Implicit• Solids$Octree%BSP tree&CSG'Sweep• High-level structures(Scene graph)Skeleton*Application specific5Surfaces• What makes a good surface representation?+Accurate,Concise-Intuitive specification.Local support/Affine invariant0Arbitrary topology1Guaranteed continuity2Natural parameterization3Efficient display4Efficient intersectionsH&B Figure 10.46Subdivision Surface• Properties:5Accurate6Concise7Intuitive specification8Local support9Affine invariant:Arbitrary topology;Guaranteed continuity<Natural parameterization=Efficient display>Efficient intersectionsPixar6Subdivision• 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 Notes7Key Questions• How refine mesh?@Aim for properties like smoothness• How store mesh?AAim for efficiency for implementing subdivision rulesZorin & SchroederSIGGRAPH 99 Course NotesLoop Subdivision Scheme• How refine mesh?BRefine each triangle into 4 triangles bysplitting each edge and connecting new verticesZorin & SchroederSIGGRAPH 99 Course Notes8Loop Subdivision Scheme• How position new vertices?CChoose locations for new vertices as weighted averageof original vertices in local neighborhoodZorin & SchroederSIGGRAPH 99 Course NotesLoop Subdivision Scheme• Different rules for boundaries:Zorin & SchroederSIGGRAPH 99 Course Notes9Loop Subdivision SchemeZorin & SchroederSIGGRAPH 99 Course NotesLimit surface has provable smoothness properties!Subdivision Schemes• There are different subdivision schemesDDifferent methods for refining topologyEDifferent rules for positioning vertices» Interpolating versus approximatingZorin & SchroederSIGGRAPH 99 Course Notes10Subdivision SchemesZorin & SchroederSIGGRAPH 99 Course NotesSubdivision SchemesZorin & SchroederSIGGRAPH 99 Course Notes11Key Questions• How refine mesh?FAim for properties like smoothness• How store mesh?GAim for efficiency for implementing subdivision rulesZorin & SchroederSIGGRAPH 99 Course NotesPolygon Meshes• Mesh RepresentationsHIndependent facesIVertex and face tablesJAdjacency listsKWinged-Edge12Independent Faces• Each face lists vertex coordinatesLRedundant verticesMNo topology informationVertex and Face Tables• Each face lists vertex referencesNShared verticesOStill no topology information13Adjacency Lists• Store all vertex, edge, and face adjacenciesPEfficient topology traversalQExtra storagePartial Adjacency Lists• Can we store only some adjacency relationshipsand derive others?14Winged Edge• Adjacency encoded in edgesRAll adjacencies in O(1) timeSLittle extra storage (fixed records)TArbitrary polygonsWinged Edge• Example:15Triangle Meshes• Relevant properties:UExactly 3 vertices per faceVAny number of faces per vertex• Useful adjacency structure for Loop subdivision:WDo not represent edges explicitlyXFaces store refs to vertices and neighboring facesYVertices store refs to adjacent faces and verticesAssignment 4• Interactive editing of subdivision surfacesZLoop subdivision scheme[Partial adjacency list mesh representation\Interactive vertex dragging16Assignment 4• Edit coarse mesh while display subdivided meshAssignment 4• Store hierarchy of meshes]Full triangle mesh at every level^Vertices store references to counterpartsone level up and one level down_Enables efficient re-positioning of mesh vertices afterinteractive draggingLevel i Level i+117Summary• Advantages:`Simple method for describing complex surfacesaRelatively easy to implementbArbitrary topologycSmoothness guaranteesdMultiresolution• Difficulties:eIntuitive
View Full Document
Unlocking...