1Overview of3D Object RepresentationsTom FunkhouserPrinceton UniversityCOS 426, Spring 2006Introduction• What is computer graphics? Imaging = representing 2D images Rendering = constructing 2D images from 3D models Modeling = representing 3D objects Animation = simulating changes over timeCourse 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? Acquire computer representations of 3D objects? Manipulate computer representations of 3D objects? Analyze computer representations of 3D objects?Stanford Graphics LaboratoryH&B Figure 10.463D ObjectsHow can this object be represented in a computer?3D ObjectsThis one?H&B Figure 10.4623D ObjectsHow about this one?Stanford Graphics Laboratory3D ObjectsThis one?Lorensen3D ObjectsThis one?H&B Figure 9.93D ObjectsThis one?3D Object Representations• A computational representation of geometry can be viewed as a language or a data structure• The choice of 3D object representation can have great impact on algorithms Data structures determine algorithms!abcdef1237456abcdefgObjectabcdef1234567Binary Spatial PartitionBinary Tree3D Object Representations• Desirable properties Accurate Concise Easy acquisition Intuitive editing Local support Affine invariant Arbitrary topology Guaranteed validity Guaranteed continuity Natural parameterization Efficient display Efficient intersectionsPolygonal Mesh33D Object Representations• Raw data Point cloud Range image Polygon soup• Surfaces Mesh Subdivision Parametric Implicit• Solids Voxels BSP tree CSG Sweep• High-level structures Scene graph Application specificPoint Cloud• Unstructured set of 3D point samples Acquired from range finder, computer vision, etcHoppeHoppeMicroscribe-3DPolhemusRange Image• Set of 3D points mapping to pixels of depth image Acquired from range scannerBrian CurlessSIGGRAPH 99 Course #4 NotesRange Image Tesselation Range SurfaceCyberwareStanfordPolygon Soup• Unstructured set of polygons Created with interactive modeling systems? Larson3D Object Representations• Raw data Point cloud Range image Polygon soup• Surfaces Mesh Subdivision Parametric Implicit• Solids Voxels BSP tree CSG Sweep• High-level structures Scene graph Application specificMesh• Connected set of polygons (usually triangles) May not be closedStanford Graphics Laboratory4Subdivision Surface• Coarse mesh & subdivision rule Define smooth surface as limit of sequence of refinements Zorin & SchroederSIGGRAPH 99 Course NotesParametric Surface• Tensor product spline patchs Each patch is parametric function Careful constraints to maintain continuityFvDFH Figure 11.44x = Fx(u,v)y = Fy(u,v)z = Fz(u,v)uvImplicit Surface• Points satisfying: F(x,y,z) = 0Polygonal ModelImplicit ModelBill LorensenSIGGRAPH 99Course #4 Notes3D Object Representations• Raw data Point cloud Range image Polygon soup• Surfaces Mesh Subdivision Parametric Implicit• Solids Voxels BSP tree CSG Sweep• High-level structures Scene graph Application specificVoxels• Uniform grid of volumetric samples Acquired from CAT, MRI, etc.FvDFH Figure 12.20Stanford Graphics LaboratoryBSP Tree• Binary space partition with solid cells labeled Constructed from polygonal representationsabcdef1237456abcdefgObjectabcdef1234567Binary Spatial PartitionBinary TreeNaylor5CSG• Hierarchy of boolean set operations (union, difference, intersect) applied to simple shapesFvDFH Figure 12.27H&B Figure 9.9Sweep• Solid swept by curve along trajectoryRemoval Path Sweep ModelBill LorensenSIGGRAPH 99Course #4 Notes3D Object Representations• Raw data Point cloud Range image Polygon soup• Surfaces Mesh Subdivision Parametric Implicit• Solids Voxels BSP tree CSG Sweep• High-level structures Scene graph Application specificScene Graph• Union of objects at leaf nodesBell Laboratoriesavalon.viewpoint.comApplication SpecificApo A-1(Theoretical Biophysics Group,University of Illinois at Urbana-Champaign)Architectural Floorplan(CS Building, Princeton University)Taxonomy of 3D RepresentationsDiscrete ContinuousCombinatorialFunctionalParametric ImplicitTopological Set Membership Voxels,Point setsMeshSubdivisionBSP TreeCell ComplexBezierB-SplineAlgebraicNaylor3D Shape6Equivalence of Representations• Thesis: Each fundamental representation has enough expressive power to model the shape of any geometric object It 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• Efficiency Combinatorial complexity (e.g. O( n log n ) ) Space/time trade-offs (e.g. z-buffer) Numerical accuracy/stability (degree of polynomial)• Simplicity Ease of acquisition Hardware acceleration Software creation and maintenance• Usability Designer interface vs. computational engineComplexity vs. Verbosity TradeoffVerbosity / InaccuracyComplexity / Accuracypixels/ voxelspiecewise linear polyhedralow degree piecewise non-linearsingle general functionsSummary• Raw data Point cloud Range image Polygon soup• Surfaces Mesh Subdivision Parametric Implicit• Solids Voxels BSP tree CSG Sweep• High-level structures Scene graph Application
View Full Document
Unlocking...