Surface mesh reconstruction
from unorganized point clouds
Spatial subdivision methods using or referring to the Medial Axis
Regular 2D Point Sets
Regular 3D Point sets
"Regular and Non-Regular Point Sets: Properties and
Reconstruction,", S. Petitjean and Edmond Boyer, Computational
Geometry-Theory and Application, volume 19, number 2-3, pp. 101-126,
Paper is available here: http://www.loria.fr/~petitjea/publications.html
Critique of methods based on LFS (and smoothness):
Requires sufficiently dense samplings (which is rarely met in practice).
Regularity of a point set should be decided on the basis of points
alone, not the a priori unknown shape (e.g., via the
LFS, i.e., distance to the unknown MA).
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).
NB: Dey et al. assume for CAD models that ridges are known
and the the surfaces are closed to compute MA of such CAD models.
Deal with (1) surfaces of arbitrary topology, allowing (2) non-uniform
sampling, and (3) producing models with provable guarantees.
The sampling S is from an actual surface M.
The sampling is "proper", i.e., there is enough
samples points in high curvature areas, and try to avoid oversampling
in low curvature areas.
Regular interpolants: Define a discrete equivalent of r-sampling,
based on an analogue for piecewise-linear objects of the MA.
Regularity of a point set can then be decided via the points alone.
When applied to non-regular point sets, one needs to iteratively
determine locally regular configurations of simplices.
Then, more simplices are recovered than needed.
An a posteriori stage based on heuristics is designed to
recover the "interesting part".
NB: No dangling edges allowed in closed interpolants.
O will be assumed to be a closed interpolant of P.
Simplex: Convex hull of a set of affine independent points (e.g.,
a vertex, an edge, a triangle, a tetrahedron, etc.).
Star of a vertex p: set of simplices incident on p.
NB: These are like the maximal (Delaunay) balls of each shock curve
source (A_1^3-2's in 3D) associated to p.
Definition of the MA of an interpolant ("None of the previously
defined MA of piecewise-linear surfaces, mostly based on the Voronoi
diagram, are entirely satisfactory.")
This is Blum's MA without the medial medial structure that
intersects or touches the surface interpolants. On the right above,
the dark triangles represent surface interpolants (i.e., the
samples P,Q,R do not share an interpolant in this particular
The DMA is a "good indicator of the ability of an interpolant to
reconstruct an unknown shape."
2 examples in 2D of how the DMA may differ from the continous MA.
Local thickness is related to the LFS(p) of Amenta et al.
(the Euclidean distance from p to the nearest point of the
In the above examples, C1 and C2 are not part of the interpolant O.
In contra-distinction to Amenta et al. the notion of
regularity introduced here is based on a discrete analogue
to the MA and it can be checked directly from the sample
Let O be a regular interpolant of P.
Thus O is a subset of the Delaunay tessellation of P.
Assume O is a regular 2D point set.
Thus, an edge Pi Pj of a regular interpolant belongs to
the Gabriel graph of the point set, which itself is a subset of
the Delaunay tessellation, such that pairs of points are connected if
the ball having them for diameter is empty (maximal).
NB: The set of centers of maximal balls of the Gabriel graph in 2D
corresponds to the set of A_1^2-2 shock sources.
For regular interpolants, the local granularity at a sample p is
equivalent to the maximum distance between p and any other
point in its neighborhood, i.e., it is a measure of the size
of the neighborhood.
Not all edges of the Gabriel graph correspond to edges of O.
The following proposition permits to discriminate which edges are
Recipe in 2D: of all Gabriel neighbors, keep only the 2 nearest ones.
Assume O is a regular 3D point set.
"Suitable extension of the Gabriel graph to 3D point set:"
For 3 points, Pi, Pj, Pk, consider a ball touching them and
such that its center is also the circumcenter of the circumcircle
through these 3 points. If this ball is maximal (empty of other points)
then construct a 2-simplex (triangle) and triple of 1-simplex (edges)
with vertices Pi, Pj, Pk; this is called the 3D Gabriel
The 3DGC is a subcomplex of the Delaunay tessellation of P.
The interpolant set O is a subcomplex of the 3DGC.
NB: The set of centers of maximal balls of the 3DGC corresponds to the
set of A_1^3-2 shock sources.
Thus, given an edge Pi Pj, pick Pk and Pl such
that the associated 2 triangles have smallest circumcircles.
Remember: Local thickness is the minimum distance to the DMA.
Non-Regular Point Sets
Problem in 3D: The tangent plane at hyperbolic sampled patches (or
negative curvature surfaces) intersects the mesh locally. leading to a
tendency to have flat 4-point configurations --> non-regularity.
Minimal Interpolants (heuristic):
The (m-1)-simplex s2 neighboring an already computed (m-1)-simplex s1
on O is s.t. the granularities at the vertices of s1 AND s2 are minimal
(i.e., the circumballs have minimal radii).
s1 and s2 belong to the Gabriel complex of P.
This ensures the resulting interpolant is a subcomplex of the Gabriel
complex of P, but it typically leaves holes in the mesh.
Implicit idea: the Gabriel complex contains enough simplices (e.g.,
triangles) for reconstruction.
The resulting meshing is not always made of a single manifold (i.e.,
some edges have more than two interpolant through them). Use some
heuristics to simplify the mesh (partial results).
Conclusion (future steps):
Establish a parallel between the DMA and the continuous MA.
Last Updated: July 15, 2004