3D ModelingSyllabusWhat is 3D Modeling?Modeling3D Object Representations3D Object Representations3D Object Representations3D Object Representations3D Object Representations3D Object Representations3D Object RepresentationsEquivalence of RepresentationsWhy Different Representations?Modeling Operations3D Object RepresentationsOutlineRange ImageRange ImageTerminologyPoint CloudOutlinePolygonal MeshSubdivision SurfaceParametric SurfaceImplicit SurfaceOutlineVoxelsBSP TreeCSGSweepOutlineScene GraphApplication SpecificTaxonomy of 3D RepresentationsEquivalence of RepresentationsComputational DifferencesUpcoming Lectures3D ModelingCOS 426SyllabusI. Image processingII. ModelingIII. RenderingIV. AnimationImage Processing(Rusty Coleman, CS426, Fall99)Modeling(Dennis Zorin, CalTech)Animation(Angel, Plate 1)Rendering(Michael Bostock, CS426, Fall99)What is 3D Modeling?• Topics in computer graphics Imaging = representing 2D images Rendering = constructing 2D images from 3D models Modeling = representing 3D objects Animation = simulating changes over timeModeling• How do we ... Represent 3D objects in a computer? Acquire computer representations of 3D objects? Manipulate computer representations of 3D objects?Stanford Graphics LaboratoryH&B Figure 10.463D Object RepresentationsHow can this object be represented in a computer?3D Object RepresentationsHow about this one?3D Object RepresentationsThis one?H&B Figure 9.93D Object RepresentationsThis one?H&B Figure 10.463D Object RepresentationsThis one? Stanford Graphics Laboratory3D Object RepresentationsThis one?3D Object Representations• Points Range image Point cloud• Surfaces Polygonal mesh Subdivision Parametric Implicit• Solids Voxels BSP tree CSG Sweep• High-level structures Scene graph Application specificEquivalence of Representations• Thesis: Each 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 Computers and programming languages are Turing-equivalent, but each has its benefits…NaylorWhy Different Representations?• Efficiency for different tasks Acquisition Rendering Manipulation Animation AnalysisData structures determine algorithmsModeling Operations• What can we do with a 3D object representation? Edit Transform Smooth Render Animate Morph Compress Transmit Analyze etc.Digital MichelangeloThouis “Ray” Jones Sand et al.Pirates of the Caribbean3D Object Representations• Desirable properties depend on intended use Easy to acquire Accurate Concise Intuitive editing Efficient editing Efficient display Efficient intersections Guaranteed validity Guaranteed smoothness etc.Outline• Points Range image Point cloud• Surfaces Polygonal mesh Subdivision Parametric Implicit• Solids Voxels BSP tree CSG Sweep• High-level structures Scene graph Application specificRange Image• Set of 3D points mapping to pixels of depth image Acquired from range scannerBrian CurlessSIGGRAPH 99 Course #4 NotesRange Image Tesselation Range SurfaceCyberwareStanfordRange Image• Image: stores an intensity / color alongeach of a set of regularly-spaced rays in space• Range image: stores a depth alongeach of a set of regularly-spaced rays in space• Not a complete 3D description: does notstore objects occluded (from some viewpoint)• View-dependent scene descriptionTerminology• Range images• Range surfaces• Depth images• Depth maps• Height fields• 2½-D images• Surface profiles• xyz maps• …Point Cloud• Unstructured set of 3D point samples Acquired from range finder, computer vision, etcHoppeHoppeMicroscribe-3DPolhemusOutline• Points Range image Point cloud• Surfaces Polygonal mesh Subdivision Parametric Implicit• Solids Voxels BSP tree CSG Sweep• High-level structures Scene graph Application specificPolygonal Mesh• Connected set of polygons (usually triangles)Stanford Graphics LaboratorySubdivision 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 NotesOutline• Points Range image Point cloud• Surfaces Polygonal 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 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 trajectoryRemoval Path Sweep ModelBill LorensenSIGGRAPH 99Course #4 NotesOutline• Points Range image Point cloud• Surfaces Polygonal 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 RepresentationsDiscr ete ContinuousCombinatorialFunctionalParametric ImplicitTopological Set Membership Voxels,Point setsMeshSubdivisionBSP TreeCell ComplexBezierB-SplineAlgebraicNaylor3 D Sh ap eEquivalence of Representations• Thesis: Each fundamental representation has sufficient 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
View Full Document