Surface mesh reconstruction
from unorganized point clouds
Spatial subdivision methods using or referring to the Medial Axis
Regular point sets (Petitjean
Deal with (1) surfaces of arbitrary topology, allowing (2) non-uniform
sampling, and (3) producing models with provable guarantees on the basis
of the point samples only.
Summary (main ideas):
DMA: A discrete version of the MA is proposed to define the
regularity of interpolants (essentially, how far surface polygons are
from the MA):
The proposed DMA boils down to Blum's MA without the medial structure
that intersects or touches the surface interpolants.
NB: This requires we first get a surface interpolant ... (somewhat a
Regularity: an (closed) interpolant (like a triangle) is
regular if the granularity (i.e., maximum local
radius of the interpolants incident at each sample point p) is smaller
than the local thickness (i.e., Euclidean distance
to the DMA).
Granularity is equivalent to the maximum radius for the A_1^3-2's
associated to p used to build interpolants incident at p.
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 point set.
Local characterization of 3D regular point sets: "Suitable
extension of the Gabriel graph to 3D point set."
NB: Recipe in 2D: of all Gabriel neighbors at p (pairs with an
A_1^2-2), keep only the 2 nearest ones.
For 3 points adjacent in a regular interpolant O, 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 complex (3DGC).
The 3DGC is a subcomplex of the Delaunay tessellation of P.
NB: The set of centers of maximal balls of the 3DGC corresponds to the
set of A_1^3-2 shock sources.
The interpolant set O is a subcomplex of the 3DGC.
Minimal granularities: Construction of a regular mesh by
Given an edge Pi Pj in O, pick Pk and Pl
such that the associated 2 triangles have smallest circumcircles.
Start with a known edge in O (e.g., the shortest edge in the Delaunay
Non-regular sets remain problematic: if two surface patches
are such that the DMA is closer than the local granularities, we run
into problems with the above (it leaves holes in the mesh).
Last Updated: July 15, 2004