Modeling Surfaces

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

Goals

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

Variety of Representations

• Raw Data
  • point cloud - unstructured 3D point samples
    
  • range image - depth data (acquired from range scanner)
    
  • voxels - uniform grid of sample data (acquired from MRI, CAT, etc)
    
  • unconnected polygons - created interactively?
    
• 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
    

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
    
  • Constructive Solid Geometry (CSG), combine surfaces via union, intersection, difference
    
• Extrusions, any 2D shape that is pulled or swept through 3D space
  • Segmented tubes
    
  • Ruled surfaces - a straight line swept through space
    
  • Surfaces of revolution - a curve rotated about an axis
    
• Curves used to define 3D surfaces
  • Quadrics, 3D analogs of conic sections
    
  • Superquadrics, quadrics extended with "bulge" factors to produce greater variety
    
  • 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
      

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 (based on dot product with light direction)
• Can be calculated per polygon, flat shading, or per vertex, interpolated shading
• Often original surface, if there even was one, is gone, so need some way to make up plausible normals
  • If polygon is planar, can calculate normal as cross product of edge vectors
  • If not, approximate by "averaging" using Newell's method
    
    • this method is numerically "robust": if two vectors are almost parallel, cross product is small, so result may be inaccurate
• Advantages of using vertex normals instead of face normal
  • facilitates clipping
  • facilitates shading of smoothly curved shapes

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

• Polygonal Formats by G. Chappell
• Mesh Data Structures by D. Zorin
• Wavefront OBJ file format for representing polygonal objects
• Tutorial - The Half-Edge Mesh Data Structure
• Marching Cubes Algorithm Tutorial
• A Developer's Survey of Polygonal Simplification Algorithms by D. Luebke
• Quadric-Based Polygonal Surface Simplification by M. Garland
• Superquadrics and their Geometric Properties by A. Jaklic, A. Leonardis, and F. Solina