July 2004

BACK

* N.B.:

1. Following the classification of Mencl and Muller, "Interpolation and Approximation of Surfaces from 3D Scattered Data Points," State of the Arts Reports, Eurographics, pp. 51-67, 1998.
    
2. This is a "high-level" classification where some methods are really part of more than one class.

Implicit (Level set based) methods

• Applicable to various inputs from which a (signed) volumetric distance field is grown

• Typically uses an Eulerian grid to simulate distance propagation (voxel-based).
   
  • Mathematical Morphology
     
  • Level sets are traced (e.g., polygonized with the Marching Cube algorithm or some variant)
     
• Usually requires a notion of "outside" versus "inside" so that a particular level set (the zero level-set) will approximate the surface M.
   
  • For example oriented tangent planes from which a signed distance map can be computed (Hoppe et al., SIGGRAPH 1992; Curless & Levoy, SIGGRAPH 1996)
     
• Extension: Can be combined with a surface under tension model (alike a snake or active surface) which is evolved (shrunk) from "outside" the initial dataset (alike a shrinking balloon or minimum bounding box containing all inputs). The tension in the model provides smoothness of the final result.
  • Zhao et al., 2001.

Incremental Surface Propagation

• Build-up an interpolating mesh using surface-oriented properties of the input sample points.
   
• Also called "Advancing front triangulation:" another propagation scheme, but 2D this time, intrinsic to the surface M to be approximated.
   
• Early paper by Boissonnat (1984): Pick a short edge; iteratively extend from this edge a mesh by attaching triangles at the boundaries of the surface M*.
   

Recent papers:

• Ball Pivoting Algorithm (BPA), Bernardini et al. @ IBM, 1999.
   
  • Main assumption:
    Samples are distributed over the entire surface with a spatial frequency greater than or equal to some application-specified minimum.
     
  • Advantage: Computing a 3D Delaunay triangulation can be prohibitively expensive and can lead to numerical instability.
     
  • Parameter: radius r of the ball. Starting from a seed triangle, the ball pivots around successive edges until it hits another point, such that no other point is included in the ball.
     

• Projection (or Umbrella) based:
   
  1. Main ingredient: Build a local surface patch at a sample point, an umbrella made of incident polygons which plays the role of a discrete topological disk.
      
  2. Merge the umbrellas into a global mesh.
      
• Gopi and Krishnan, 2000:
   
  • A local Delaunay-neighborhood (triangulation dual of Voronoi) is built, as an
    "umbrella" around each sample point.
     
  • Final mesh is determined by projection of each of these umbrella.
     
  • Requirements on local sampling density; closest (allowed) distance between layers; and normal deviation between any pair of triangles sharing a vertex (smoothness; angle < 90 deg.).
     
• Udo Adamy et al., "Surface Reconstruction Using Umbrella Filters," 2000 and 2002.
  

Spatial subdivision

• Subdivision of a bounding volume surrounding the input data followed by combinatorially selecting cells related to the shape of the point set.
   
• Most algorithms in this category are based on the Delaunay tetrahedrization (or its dual Voronoi diagram).
   

• Sculpting approach: Delaunay tetrahedra are progressively eliminated according to a geometric criterion such as area of a triangular face; Boissonnat, 1984; Veltkamp, 1995 (adapts to variable sampling densities, but cannot handle holes or surfaces with boundaries); Attali, 1997 (r-regular sample set introduced).
   
• 3D Alpha-shapes (H. Edelsbrunner et al., 1994): a subset of the Delaunay tetrahedrization: keep only faces having associated Maximal (Delaunay) ball radius smaller than the global parameter alpha.
   
• Voronoi poles and the medial axis: Amenta et al., Dey et al., since 1998.

BACK

Last Updated: July 13, 2004