Surface mesh reconstruction
from unorganized point clouds
Spatial subdivision methods using or referring to the Medial Axis
Summary on regularity
Regularity based on distance to a certain medial axis was introduced by
Amenta et al. (and further used by Dey et al.) in
order to be able to derive proofs on the quality of the potential
reconstruction (and conditions necessary to be met, e.g. on
Petitjean and Boyer were critical of an approach based on an unknown
continuous MA and thus introduced the DMA, and formalize a notion of
regularity based on the distance to the DMA and an extension (to 3D) of
Gabriel graphs (subcomplex of Delaunay tessellations).
Comments: The above are not general enough to tackle precisely
non-regular samplings, which are commonly encountered in practice.
In particular, when two distinct surface patches come close to each
other, s.t. that this distance is similar to the sampling radius, the
above methods must introduced a posteriori heuristics to try
to fix locally the mesh.
Negative curvature sampled patches and nearly flat patches create
problems (a tiny maximal ball can always be fitted between 4 sample
points nearly on an equatorial plane).
The notion of a hole in the data is not always well characterized; but,
in practice, there are holes in the scans ... and this should probably
be recognized as such, rather than filled-in in some ad'hoc manner. The
power-crust of Amenta et al. addresses this issue however
(pairs of inner and outer polar balls which intersect
"deeply" are significant of holes and removed from the
None of these recent methods refer or use the original definition of
the medial axis (by Blum; circa 1962).
Degenerate configurations are bypassed. Is this reasonable? probably.
Is it desirable? probably not. CAD-like objects and uniform samplings
are useful. Higher order symmetries (although unstable) are also useful
for recognition purposes (e.g., a sphere ought to be
represented by a single point: its center).
Non-smooth surfaces and objects are in theory rejected. Again, is this
desirable in applications?
Last Updated: July 8, 2004