1Overview of3D Object RepresentationsThomas 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 such representationsquickly and/or automatically with a computer?Manipulate 3D objects with a computer?Different methods for different object representations33D ObjectsHow can this object be represented in a computer?3D ObjectsThis one?H&B Figure 10.4643D ObjectsHow about this one?Stanford Graphics Laboratory3D ObjectsThis one?Lorensen53D ObjectsThis one?H&B Figure 9.93D ObjectsThis one?6Representations of Geometry• 3D Representations provide the foundations for Computer Graphics, Computer-Aided GeometricDesign, Visualization, Robotics• They are languages for describing geometrySemantics Syntaxvalues data structuresoperations algorithms• Data structures determine algorithms!3D Object Representations• Raw dataPoint cloudRange imagePolygon soup• SurfacesMeshSubdivisionParametricImplicit• SolidsVoxelsBSP treeCSGSweep• High-level structuresScene graphSkeletonApplication specific7Point Cloud• Unstructured set of 3D point samplesAcquired from range finder, computer vision, etcHoppeHoppeRange Image• Set of 3D points mapping to pixels of depth imageAcquired from range scannerBrian CurlessSIGGRAPH 99 Course #4 NotesRange Image Tesselation Range Surface8Polygon Soup• Unstructured set of polygonsCreated with interactive modeling systems?Larson3D Object Representations• Raw dataPoint cloudRange imagePolygon soup• SurfacesMeshSubdivisionParametricImplicit• SolidsVoxelsBSP treeCSGSweep• High-level structures Scene graph!Skeleton"Application specific9Mesh• Connected set of polygons (usually triangles)#May not be closedStanford Graphics LaboratorySubdivision Surface• Coarse mesh & subdivision rule$Define smooth surface as limit ofsequence of refinementsZorin & SchroederSIGGRAPH 99 Course Notes10Parametric Surface• Tensor product spline patchs%Careful constraints to maintain continuityFvDFH Figure 11.44Implicit Surface• Points satisfying: F(x,y,z) = 0Polygonal ModelImplicit ModelBill LorensenSIGGRAPH 99Course #4 Notes113D Object Representations• Raw data&Point cloud'Range image(Polygon soup• Surfaces)Mesh*Subdivision+Parametric,Implicit• Solids-Voxels.BSP tree/CSG0Sweep• High-level structures1Scene graph2Skeleton3Application specificVoxels• Uniform grid of volumetric samples4Acquired from CAT, MRI, etc.FvDFH Figure 12.20Stanford Graphics Laboratory12BSP Tree• Binary space partition with solid cells labeled5Constructed from polygonal representationsabcdef1237456abcdefgObjectabcdef1234567Binary Spatial PartitionBinary TreeNaylorCSG• Hierarchy of boolean set operations (union,difference, intersect) applied to simple shapesFvDFH Figure 12.27H&B Figure 9.913Sweep• Solid swept by curve along trajectoryRemoval Path Sweep ModelBill LorensenSIGGRAPH 99Course #4 Notes3D Object Representations• Raw data6Point cloud7Range image8Polygon soup• Surfaces9Mesh:Subdivision;Parametric<Implicit• Solids=Voxels>BSP tree?CSG@Sweep• High-level structuresAScene graphBSkeletonCApplication specific14Scene Graph• Union of objects at leaf nodesBell Laboratoriesavalon.viewpoint.comSkeleton• Graph of curves with radiiStanford Graphics LaboratorySGI15Application 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 VoxelsMeshSubdivisionBSP TreeCell ComplexBezierB-SplineAlgebraicNaylor16Equivalence of Representations• Thesis:DEach fundamental representation has enoughexpressive power to model the shapeof any geometric objectEIt is possible to perform all geometric operations withany fundamental representation!• Analogous to Turing-Equivalence:FAll computers today are turing-equivalent,but we still have many different processorsComputational Differences• EfficiencyGCombinatorial complexity (e.g. O( n log n ) )HSpace/time trade-offs (e.g. z-buffer)INumerical accuracy/stability (degree of polynomial)• SimplicityJEase of acquisitionKHardware accelerationLSoftware creation and maintenance• UsabilityMDesigner interface vs. computational engine17Complexity vs. Verbosity TradeoffVerbosity / InaccuracyComplexity / Accuracypixels/ voxelspiecewise linear polyhedralow degree piecewise non-linearsingle general functionsSummary• Raw dataNPoint cloudORange imagePPolygon soup• SurfacesQMeshRSubdivisionSParametricTImplicit• SolidsUVoxelsVBSP treeWCSGXSweep• High-level structuresYScene graphZSkeleton[Application
View Full Document
Unlocking...