Modeling Surfaces

• How to represent objects for 3D graphics?
• How to construct such representations quickly and/or automatically?
• How to manipulate such representations?
  

Variety of Representations

• Raw Data
  • point cloud - unstructured set of 3D point samples
    
  • range image - depth data (acquired from range scanner)
    
  • unconnected polygons - created interactively?
    
  • voxels - uniform grid of sample data (acquired from MRI, CAT, etc)
    
• Surfaces
  • mesh - connected set of polygons
    
  • subdivision - coarse mesh + subdivision rule
    
  • parametric - geometric equation
    
  • implicit - points satisfying function: F(x, y, z) = 0
    
    
• High-level structures
  • scene graph - union of objects at leaf nodes
    
  • skeleton - graph of curves with radii
    
  • application specific
    

Goals

• Accuracy
• Conciseness
• Intuitive specification
• Affine invariant
• Natural parameterization
• Efficient display
• Efficient intersections
• Arbitrary topology
• Guaranteed continuity
• Local support

Polygon Mesh

• Most basic representation for 3D systems (usually triangles)
• Made up of vertices, edges, and faces
• Order in which vertices are traversed determines direction of normal
  

Normals

• Used to determine surface lighting (amount based on dot product with light direction)
• If polygon is planar, can calculate normal as cross product of edge vectors
• If not, approximate by "averaging" using Newell's method
  
• Can be calculated per polygon, flat shading, or per vertex, interpolated shading

Mathematical Representations of Surfaces

• Implicit or functional form: F(x, y, z) = 0
• Explicit or parametric form: P(u, v) = (X(u, v), Y(u, v), Z(u, v))

Techniques for Generating Surfaces

• Typically start with 2D polygon or curve and extend in 3D
• Polyhedra, any closed collection of planar polygons
  Since many vertices are shared, avoid redundancy by separating vertex, normal, and face data
  • Platonic solids
    
  • Prisms
    
• Extrusions, any 2D shape that is pulled or swept through 3D space
  • Segmented tubes
    
  • Ruled surfaces
    
  • Surfaces of revolution
    
  • Rendering Spline Surfaces
    
    • Can be expensive for high-quality approximation if simply evaluate at each point
    • Evaluate using Horner's rule for factoring reduces multiples to O(n)
    • Approximate by sub-dividing control points based on de Casteljau's geometric construction
    • Approximate using forward differencing reduces to adding pre-computed constants each step
      
• Quadrics, 3D analogs of conic sections
  
• Superquadrics, quadrics extended with "bulge" factors to produce greater variety
  
• Constructive Solid Geometry (CSG), combine above surfaces via union, intersection, difference
  

Tessellating Surfaces

• Goal: generate fewest number of polygons
• Variety of ways to polygonalize ideal surface
• Simplest: given function of surface, sample at given intervals
  

• Marching cubes, divide 3D space into cubes, sample at specific points, connect samples
  

References

• Curved Surfaces by Steve Marchner
• Polygonal Formats by Glenn G. Chappell
• Wavefront OBJ file format for representing polygonal objects
• Tutorial - The Half-Edge Mesh Data Structure
• Marching Cubes by W. Lorensen and H. Cline
• A Developer's Survey of Polygonal Simplification Algorithms by David Luebke
• Quadric-Based Polygonal Surface Simplification by M. Garland