3D Object RepresentationJason LawrenceCS445: GraphicsAcknowledgment: slides by Misha Kazhdan, Allison Klein, Tom Funkhouser,Adam Finkelstein and David Dobkin3D Object Representation• How do we ...oRepresent 3D objects in a computer?oConstruct such representations quickly and/or automatically with a computer?oManipulate 3D objects with a computer?Different methods for different object representations3D ObjectsHow can this object be represented in a computer?3D ObjectsThis one?H&B Figure 10.463D ObjectsHow about this one?Stanford Graphics Laboratory3D ObjectsThis one?H&B Figure 9.93D ObjectsThis one?Representations of Geometry• 3D Representations provide the foundations foroComputer GraphicsoComputer-Aided Geometric DesignoVisualizationoRobotics• They are languages for describing geometry! data structures ! ! algorithms• Data structures determine algorithms!3D Object Representations• Raw dataoPoint cloudoRange imageoPolygon soup• SurfacesoMeshoSubdivision oParametricoImplicit• SolidsoVoxelsoBSP treeoCSGoSweep• High-level structuresoScene graphoSkeletonoApplication specificPoint Cloud• Unstructured set of 3D point samplesoAcquired from range finder, random sampling, particle system implementations, etcHoppeHoppePoint Cloud• Unstructured set of 3D point samplesoAcquired from range finder, random sampling, particle system implementations, etcHoppeHoppeCan associate colors/normals/etc. to the pointsRange Image• An image storing depth instead of coloroAcquired from structured range scannersBrian CurlessSIGGRAPH 99 Course #4 NotesRange Image Tesselation Range SurfacePolygon Soup• Unstructured set of polygonsoCreated with interactive modeling systems, combining range images, etc. Larson3D Object Representations• Raw dataoPoint cloudoRange imageoPolygon soup• SurfacesoMeshoSubdivision oParametricoImplicit• SolidsoVoxelsoBSP treeoCSGoSweep• High-level structuresoScene graphoSkeletonoApplication specificMesh• Connected set of polygons (usually triangles)oMay not be closedStanford Graphics LaboratorySubdivision Surface• Coarse mesh & subdivision ruleoDefine smooth surface as limit of sequence of refinements Zorin & SchroederSIGGRAPH 99 Course NotesParametric Surface• Tensor product spline patchesoCareful use of constraints to maintain continuityFvDFH Figure 11.44Implicit Surface• Points satisfying: F(x,y,z) = 0Polygonal ModelImplicit ModelBill LorensenSIGGRAPH 99Course #4 Notes3D Object Representations• Raw dataoPoint cloudoRange imageoPolygon soup• SurfacesoMeshoSubdivision oParametricoImplicit• SolidsoVoxelsoBSP treeoCSGoSweep• High-level structuresoScene graphoSkeletonoApplication specificVoxels• Uniform grid of volumetric samplesoAcquired from CT, MRI, etc.FvDFH Figure 12.20Stanford Graphics LaboratoryBSP Tree• Binary space partition with solid cells labeledoConstructed from polygonal representationsabcdef1237456abcdefgObjectabcdef1234567Binary Spatial PartitionBinary TreeNaylorCSG• Hierarchy of boolean set operations (union, difference, intersect) applied to simple shapesFvDFH Figure 12.27H&B Figure 9.9Sweep• Solid swept by curve along trajectoryStephen ChenneyU WisconsinSweep• Solid swept by curve along trajectoryoCurve may be arbitraryoSweep polygon may deform (scale, rotate) with respect to the path orientationStephen ChenneyU Wisconsin3D Object Representations• Raw dataoPoint cloudoRange imageoPolygon soup• SurfacesoMeshoSubdivision oParametricoImplicit• SolidsoVoxelsoBSP treeoCSGoSweep• High-level structuresoScene graphoSkeletonoApplication specificScene Graph• Union of objects at leaf nodesBell Laboratoriesavalon.viewpoint.comSkeleton• Graph of curves with radiiStanford Graphics LaboratorySGIApplication SpecificApo A-1(Theoretical Biophysics Group,University of Illinois at Urbana-Champaign)Architectural FloorplanEquivalence of Representations• Thesis:oEach fundamental representation has enough expressive power to model the shape of any geometric objectoIt is possible to perform all geometric operations with any fundamental representation!• Analogous to Turing-Equivalence:oAll computers today are Turing-equivalent, but we still have many different processorsComputational Differences• EfficiencyoCombinatorial complexityoSpace/time trade-offsoNumerical accuracy/stability• SimplicityoEase of acquisitionoHardware acceleration• UsabilitySurfaces• What makes a good surface representation?oConciseoLocal supportoAffine invariantoArbitrary topologyoGuaranteed continuity oNatural parameterizationoEfficient displayoEfficient intersectionsH&B Figure 10.46Surfaces• What makes a good surface representation?oConciseoLocal supportoAffine invariantoArbitrary topologyoGuaranteed continuity oNatural parameterizationoEfficient displayoEfficient intersectionsNot Local SupportSurfaces• What makes a good surface representation?oConciseoLocal supportoAffine invariantoArbitrary topologyoGuaranteed continuity oNatural parameterizationoEfficient displayoEfficient intersectionsSurfaces• What makes a good surface representation?oConciseoLocal supportoAffine invariantoArbitrary topologyoGuaranteed continuity oNatural parameterizationoEfficient displayoEfficient intersectionsTopological GenusEquivalencesSurfaces• What makes a good surface representation?oConciseoLocal supportoAffine invariantoArbitrary topologyoGuaranteed continuity oNatural parameterizationoEfficient displayoEfficient intersectionsSurfaces• What makes a good surface representation?oConciseoLocal supportoAffine invariantoArbitrary topologyoGuaranteed continuity oNatural parameterizationoEfficient displayoEfficient intersectionsA Parameterization(not necessarily natural)Surfaces• What makes a good surface representation?oConciseoLocal supportoAffine invariantoArbitrary topologyoGuaranteed continuity oNatural parameterizationoEfficient displayoEfficient
View Full Document
Unlocking...