Implicit Surfaces & Solid Representations3D Object Representations3D Object Representations3D Object RepresentationsImplicit SurfacesImplicit SurfacesImplicit SurfacesImplicit SurfacesImplicit Surface PropertiesImplicit Surface PropertiesImplicit Surface PropertiesImplicit Surface PropertiesImplicit Surface PropertiesComparison to Parametric SurfacesImplicit Surface RepresentationsImplicit Surface RepresentationsImplicit Surface RepresentationsAlgebraic SurfacesAlgebraic SurfacesAlgebraic SurfacesAlgebraic SurfacesAlgebraic SurfacesAlgebraic SurfacesImplicit Surface RepresentationsVoxelsVoxelsVoxelsVoxelsVoxelsVoxel StorageImplicit Surface RepresentationsBasis functionsRadial Basis FunctionsBlobby ModelsBlobby ModelsBlobby ModelsBlobby Model of FaceBlobby Model of FaceBlobby Model of FaceBlobby Model of HeadBlobby Model of HeadBlobby Model of HeadBlobby ModelsVariational Implicit SurfacesVariational Implicit SurfacesImplicit Surface SummarySummary3D Object RepresentationsSolid ModelingMotivation 1Motivation 2Motivation 33D Object RepresentationsVoxelsVoxelsVoxel ProcessingVoxel Boolean OperationsVoxel DisplayVoxel DisplayVoxel DisplayVoxel DisplayVoxelsVoxelsQuadtrees & OctreesQuadtree ProcessingQuadtree Boolean Operations3D Object RepresentationsBSP TreesBSP Trees3D Object RepresentationsConstructive Solid Geometry (CSG)CSG AcquisitionCSG AcquisitionCSG Boolean OperationsCSG Display & Analysis3D Object RepresentationsSweepsSweepsSweepsSummaryImplicit Surfaces & Solid Representations COS 4263D Object Representations • Desirable properties of an object representation Easy to acquire Accurate Concise Intuitive editing Efficient editing Efficient display Efficient intersections Guaranteed validity Guaranteed smoothness etc. Large Geometric Model Repository Georgia Tech3D Object Representations • Desirable properties of an object representation Easy to acquire Accurate Concise Intuitive editing Efficient editing Efficient display Efficient intersections Guaranteed validity Guaranteed smoothness etc. Large Geometric Model Repository Georgia Tech3D 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 specificImplicit Surfaces • Represent surface with function over all space KazhdanImplicit Surfaces • Surface defined implicitly by function KazhdanImplicit Surfaces • Surface defined implicitly by function: f (x, y, z) = 0 (on surface) f (x, y, z) < 0 (inside) f (x, y, z) > 0 (outside) f(x,y) = 0 on curve f(x,y) < 0 inside f(x,y) > 0 outside TurkImplicit Surfaces • Normals defined by partial derivatives normal(x, y, z) = normalize(∂f /∂x, ∂f /∂y, ∂f /∂z) Normals Tangents Curvatures BloomenthalImplicit Surface Properties (1) Efficient check for whether point is inside Evaluate f(x,y,z) to see if point is inside/outside/on Example: ellipsoid H&B Figure 10.10 1),,(222−++=zyxrzryrxzyxfImplicit Surface Properties (2) Efficient surface intersections Substitute to find intersections Ray: P = P0 + tV Sphere: |P - O|2 - r 2 = 0 Substituting for P, we get: |P0 + tV - O|2 - r 2 = 0 Solve quadratic equation: at2 + bt + c = 0 where: a = 1 b = 2 V • (P0 - O) c = |P0 - C|2 - r 2 = 0 P0 V O P r P’Implicit Surface Properties (3) Efficient boolean operations (CSG) How would you implement: Union? Intersection? Difference? Union Difference BloomenthalImplicit Surface Properties (4) Efficient topology changes Surface is not represented explicitly! BourkeImplicit Surface Properties (4) Efficient topology changes Surface is not represented explicitly! BloomenthalComparison to Parametric Surfaces • Implicit Efficient intersections & topology changes • Parametric Efficient “marching” along surface & rendering BloomenthalImplicit Surface Representations • How do we define implicit function? f(x,y,z) = ?Implicit Surface Representations • How do we define implicit function? Algebraics Voxels Basis functions OthersImplicit Surface Representations • How do we define implicit function? Algebraics Voxels Basis functions OthersAlgebraic Surfaces • Implicit function is polynomial f(x,y,z)=axd+byd+czd+dxd-1y+dxd-1z +dyd-1x+... H&B Figure 10.10 1),,(222−++=zyxrzryrxzyxfAlgebraic Surfaces • Most common form: quadrics f(x,y,z)=ax2+by2+cz2+2dxy+2eyz+2fxz+2gx+2hy+2jz+k • Examples Sphere Ellipsoid Torus Paraboloid Hyperboloid MenonAlgebraic Surfaces • Higher degree algebraics Cubic Quartic Degree sixAlgebraic Surfaces • Equivalent parametric surface Tensor product patch of degree m and n curves yields algebraic function with degree 2mn Bicubic patch has degree 18!Algebraic Surfaces • Intersection Intersection of degree m and n algebraic surfaces yields curve with degree mn Intersection of bicubic patches has degree 324!Algebraic Surfaces • Function extends to infinity Must trim to get desired patch (this is difficult!)Implicit Surface Representations • How do we define implicit function? Algebraics Voxels Basis functionsVoxels • Regular array of 3D samples (like image) Samples are called voxels (“volume pixels”) www.volumegraphics.comVoxels • Example isosurfaces Princeton University SUNY Stoney BrookVoxels • Regular array of 3D samples (like image) Applying reconstruction filter (e.g. trilinear) yields f(x,y,z) Isosurface at f(x,y,z) = 0 defines surface 2.3 1.2 0.3 0.2 1.7 0.4 -0.5 -0.9 0.9 0.1 -0.7 -1.7 0.2 -0.8 -1.4 -2.5Voxels • Iso-surface extraction algorithm e.g., Marching cubesVoxels • Iso-surface extraction algorithm e.g., Marching cubes (15 cases)Voxel Storage • O(n3) storage for n x n x n grid 1 billion voxels for 1000 x 1000 x 1000Implicit Surface Representations • How do we define implicit function? Algebraics Voxels Basis functionsBasis functions • Implicit function is sum of basis functions Example: τ−++=−−211200),(1),(0)(PPdbPPdbeaeaPfP0 P1 PRadial Basis Functions • Blobby molecules • Meta
View Full Document
Unlocking...