Surface mesh reconstruction
from unorganized point clouds
Spatial subdivision methods using or referring to the Medial Axis
Voronoi Filtering: Cocone (Amenta et al.)
Co-cone in 2D.
|Co-cone in 3D.
Nina Amenta, Sunghee Choi, Tamal Dey and Naveen Leekha, "A
simple algorithm for homeomorphic surface reconstruction," ACM
Symposium on Computational Geometry, 2000, pages 213-222. Submitted
to the International Journal of Computational Geometry and its
Guarantee that the output surface M* is homeomorphic (a
continuous deformation exists preserving the topology) to the object
original surface M.
Claim to fame: 1st published result with such a guarantee.
(old) Assumptions of the previous crust algorithm:
M is smooth (twice-differentiable) manifold without boundary (closed:
topologically like a sphere).
Sampling is dense and uniform enough so that no sample point is too far
(not too close) from the MA; i.e., the distance between samples is
proportional (factor r ) to the (minimum) distance to the MA.
A simpler one-pass algorithm is proposed with the above guarantee as a
(new) Assumptions: Let T be the set of final triangles for M*
T contains all (Delaunay) triangles whose dual Voronoi edges intersect M
--> ensures that T contains a piecewise-linear manifold
homeomorphic to M (T is usually larger).
Each triangle is small: i.e., the radius of its
circumcircle is much smaller than the distance to the MA at its
Triangles in T are flat: i.e., a triangle normal
makes a small angle with the surface normals at their vertices.
Together, conditions 2 and 3 are used to show that any piecewise-linear
manifold extracted from T which spans all samples s must be
homeomorphic to M.
Samples are in general position (no degenerate situations, like
co-spherical or co-linear).
Candidate triangles are selected using the cocone at each sample point:
Consider the farthest Voronoi vertex associated to a sample p: this is
its 1st pole p+.
The line through p and p+ is the estimated normal N to M at p.
For an angle theta (parameter) the co-cone is defined as the
cone complement of the double cone with apex p making an angle pi/2 -
theta with N.
Determine the set of Voronoi edges in Vp that intersect the co-cones at
all 3 of the samples inducing an edge.
The dual triangles of such edges are part of the candidate set T.
From Dey & Goswami, "Tight cocone," 2003.
Problems with practical data, due to undersampling, noise,
The estimated "normals" then may not be in the correct
direction, leading to a wrong choice of triangles.
Procedure BOUNDARY: detect Voronoi cells which are not
long and thin along the estimated normals.
Removing these triangles leaves holes in the mesh.
Tight cocone attempts to fill such
holes by labeling Delaunay tetrahedra as in or out,
based on the initial approximation of the surface. Remove all out
tetrahedra, and take the boundary of the in tetrahedra to
get a surface M* (which is then "water tight", i.e.,
closed). Works well if the undersampling is local.
Last Updated: June 30, 2004