Surface mesh reconstruction
from unorganized point clouds
Spatial subdivision methods using or referring to the Medial Axis
Voronoi Filtering: Poles and the MA (Amenta et al.)
Claim to fame: 1st algorithm in 3D with provable guarantees of
reconstruction (interpolation through the right vertices).
Intuitive notion: featureless areas (remote from the MA) can be
reconstructed with fewer samples.
Since some Voronoi vertices can be arbitrarily close to the surface M
irrespective of the sampling density, poles are introduced. It
is shown that as density augments, for a smooth continuous surface (no
boundaries), poles will remain away from the surface (alternatively
close the theoretical MA).
The (crust) algorithm in a nutshell, 1998:
Pass 1: Compute the 3D Voronoi diagram of the sample points, S.
Poles: For each sample point s, pick the
farthest vertex v of its Voronoi cell, and the farthest vertex v' such
that angle vsv' exceeds 90 degrees.
Pass 2: Compute the Delaunay tessellation of the sample points
augmented with the poles, the Voronoi vertices chosen in the second
(Voronoi filtering) Keep a triangle only if the 3 vertices are sample
points s in S.
NB: Will work if the poles were well situated on each side of the
unknown surface M.
(Normal filtering) Remove a triangle T if the angle difference between
the normal to T and the vector to the pole p+ at a vertex of T is too
large (parameter theta).
(Trimming) Orient triangles and poles (inside and outside) consistently
to retrieve a piecewise-linear manifold without boundary.
Alternatives to steps 3, 4 and 5, 2000:
A co-cone defines an umbrella for a sample point made of small Delaunay
triangles defining a relatively flat disk-like neighborhood centered at
the sample point.
The power crust and power shape:
Label poles as outer or inner poles and output the power diagram faces
separating the cells of outer and inner poles == power crust
== approximate surface mesh M*
Output the triangulation faces connecting inside poles == power
shape == approximate interior MA
NB: Power distance of point x in R^3 from a (weighted) point p: pi_p(x)
= | x - p|² - r² , where r is a weight (here taken as the
radius of the associated polar ball (maximal or Delaunay ball).
Sampling criterion based on the distance to MA:
Let the Local Feature Size at a point p on M, denoted
LFS(p), be the Euclidean distance from p to the nearest point of the MA.
LFS(p) <= smallest radius of MA associated to p.
LFS(p) is 1-Lipschitz: i.e., LFS(p) <= LFS(q) + |pq|
, for any 2 points p and q on M.
Set S is an r-sample of M if no point p on M is farther than
"r . LFS(p)" from a point of S.
This is valid only for regular (smooth) manifolds, i.e., r should
be positive and in practice cannot be too small.
Works well in 2D: in particular a smooth curve is perfectly
reconstructed (interpolated) for r <= 0.25 .
Breaks down in 3D because Voronoi vertices can be arbitrarily close to
the surface: this is why poles are introduced. Then, the crust is
guaranteed to be topologically equivalent to M if r
<= 0.06 .
Key element of the algorithm(s) : distinguish outer from inner
Done iteratively starting with those for which a high
confidence is available (triangular face part of the convex hull for
example: i.e., Voronoi cell shooting off to infinity).
Inner and outer polar balls should intersect shallowly.
Near sharp corners this criterion may fail: a test on how
skinny (elongated) a voronoi cell is permits to avoid rounding off
corners (user-supplied parameter).
Noisy sampling: when points lie near but not on the surface,
not all Voronoi cells are well shaped (i.e., elongated or
Examples and details: http://www.cs.utexas.edu/users/amenta/powercrust/welcome.html
Petitjean and Boyer, 2001: Regular and
non-regular point sets
Requires sufficiently dense samplings.
Regularity of a point set should be decided on the basis of points
alone, not the a priori unknown shape (e.g., via
Theoretical values of r are not useful in practical
applications' particularly for CAD-like objects with sharp edges which
would require infinite density (to avoid a heuristic like above).
Dey et al., 2003: Tight cocone: A water-tight Surface
Output of the power crust is not a triangulated surface (i.e.,
made of polygons) and it may introduce extra points (near corners).
It fails when the sampling is not uniform and dense.
Construct an approximate MA once a closed (tight)
surface is built (using the cocone algorithm and a hole detection and
NEXT: CoCone algorithm.
Last Updated: June 30, 2004