Surface mesh reconstruction
from unorganized point clouds
Incremental surface propagation
Implicit (level sets - Eulerian grid)
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.
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
Fig. 2 from Zhao01
Typically uses an Eulerian grid to simulate distance propagation
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.
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
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*.
Ball Pivoting Algorithm (BPA),
Bernardini et al. @ IBM, 1999.
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.
BPA in 2D: (a) A disk of radius r pivots from sample to sample,
connecting them with edges.
(b) If the sampling density is too low, some edges are missed leaving
(c) When the curvature of the manifold, M, is larger than 1/r
some samples are not reachable.
Projection (or Umbrella) based:
Main ingredient: Build a local surface patch at a sample point, an
umbrella made of incident polygons which plays the role of a discrete
Merge the umbrellas into a global mesh.
Gopi and Krishnan, 2000:
A local Delaunay-neighborhood (triangulation dual of Voronoi) is built,
"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.
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
Descartes' analysis of star systems, circa 1644.
S is the sun, epsilon is a star, RQD... is a comet's path.
In blue I added a Delaunay
triangle dual to 3 Voronoi edges.
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
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
Voronoi poles and the medial axis:
Amenta et al., Dey et al., since 1998.
Last Updated: July 13, 2004