Surface mesh reconstruction
from unorganized point clouds
Surface Reconstruction based on a Dynamical System
J. Giesen and M. John, "Surface Reconstruction Based on a
Dynamical System." Proceedings of the 23rd Annual Conference of
the European Association for Computer Graphics (Eurographics), Computer
Graphics Forum 21, (2002) 363-371.
J. Giesen and M. John, The Flow Complex: A Data Structure for Geometric
Modeling. Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete
Algorithms (SODA), (2003) 285-294.
Other references here.
Study the critical points of the distance function
(using the Voronoi diagram and dual Delaunay tesselation of point
sets) --- Theorem 1:
The critical points of the distance function h (from points of the
input dataset) are the intersection of Voronoi objects
and their dual Delaunay objects.
Study critical points of Morse functions as studied by Edelsbrunner et al. (aka Alpha-shapes
and computational topology).
Use of Voronoi/Delaunay objects:
For point samples, critical points are characterized at the
intersection of Voronoi objects with their dual Delaunay objects.
Driver of a point x: Consider the lowest dimensional
Voronoi object which contains x; let sigma be the dual Delaunay object.
The driver of x is then the closest point to x on sigma.
x is part of a Voronoi cell, sigma is the dual Delaunay vertex, i.e.,
a sample point p. The driver of x is the sample p.
x is part of a Voronoi face or shock sheet, sigma is the dual Delaunay
edge: the driver of x is the A_1^2-2 locus.
x is part of a Voronoi edge or shock curve, sigma is the dual Delaunay
triangle (thru the 3 samples sharing the Voronoi edge): the driver of x
is the A_1^3-2 locus.
x is part of a Voronoi vertex, sigma is the dual Delaunay tetrahedron;
the driver of x is x for a regular tet.
Stable manifold of a critical point s of the
vector distance function h (to the boundary, inputs): is
given by the integral curves ending at s (i.e., the
set of all ponts that flow into s).
Stable manifold of a critical point of index 0 (minimum) is the
critical point itself (e.g., a sample input point).
Stable manifold of a critical point of index 1 (saddle
point at the intercept of a Delaunay edge and Voronoi face; i.e.,
an A_1^2-2 shock sheet source) is the Delaunay edge.
NB: The union of all such stable manifolds is what they call the (3D)
Gabriel graph, different from the definition of Petitjean and Boyer,
but directly equivalent to the 2D definition.
Stable manifold of a critical point of index 2 (saddle
point at the intercept of a Delaunay face F and Voronoi edge; i.e.,
an A_1^3-2 shock curve source for acute triangle configurations) is
constructed as a polygon contained in the Delaunay faces F which all
flow into s.
Stable manifold of a critical point of index 3 (local
maximum, a sink for the flow; i.e., an A_1^4-4) is a
region bounded by multiple adjacent stable manifolds of index 2,
bounded by a circuit of Delaunay edges, i.e., stable
manifolds of index 1.
NB: There is an error in the above right figure: one saddle point is
missing for the central Delaunay edge.
NB: the driver d corresponds to an A_1^2-2 candidate; the
critical point s is necessarily an A_1^3-2 for an acute
triangular configuration of three generators; s' corresponds to
an A_1^3-2 for an obtuse configuration s.t. the shock sheet which flows
outward of it, leads to s and the associated Voronoi edge (or
A_1^3 shock curve).
The blue dot s is an A_1^3-2
with all flows inward. The green dots
correspond to A_1^3-2's with one outward flow (sheet). Red dots are input point generators (samples)
which are connected by Delaunay edges creating the outward boundary of
the stable manifold of s.
NB: The green dot on the LHS of the blue s is not correct as drawn,
since its associated triplet of generators form an acute triangle.
Given a finite set of points in R^3, the stable flow complex of the
point set is given by the simplicial complex built by the Gabriel graph
(Delaunay edges) and the triangulated surface whose points flow into
index 2 saddles.
The stable manifolds of the local maximum of the distance function h associated
with a finite set of points P in R^3 are the bounded regions of the
Notes (re-interpretation in the language of shock graphs and scaffolds):
Step 3: Computes the set of A_1^3-2's (i.e., isolated
sources of shock curves).
Step 5: Acute triangle interpolant associated to a shock curve with a
valid shock source.
Step 13: This is a valid shock source for a sheet, i.e., an
Steps 13 and 14: Produce a triangle with vertices given by a pair of
input points (which share a Delaunay edge, i.e., for which
there is a well-defined A_1^2-2) and the Delaunay triangle circumcenter
Steps 15 to 24: Produce a triangle (or polygon) for input pairs which
do not have a well-defined critical point (i.e., without an
A_1^2-2 shock source), by iteratively triangulating neighboring
Delaunay faces via associated shock curve sources for obtuse
configurations (i.e., with one outward sheet flow towards s).
With this procedure, we end-up with a complex which is typically larger
than the desired mesh, M*.
NB: The above is a sytematic triangulation process; there are no
constraints derived from sampling conditions or from surface-related
configurations (e.g., more the two stable manifolds may be
attached to the same Delaunay edges).
Iteratively remove parts of the flow complex which locally are
non-manifold: i.e., such that the associated Gabriel (Delaunay)
edge has more than 2 surface patches (3 or more stable manifolds of
index 2) through it.
Ordered removal: For a given edge with 3 or more surface patches thru
it, remove the one which has minimum distance between its index 2
critical point s and its associated index 3 maximum (i.e.,
with minimum distance between the A_1^3-2 and its closest A_1^4-4 sink).
Stop removals when all Delaunay edges have at most 2 surface patches
Remaining "problem:" resolve topological non-regularities.
NB: Nearby patches which are connected: separate these (heuristic
based? unclear in the paper how this is done).
Extension to shape partitioning and matching in:
T.K. Dey, J. Giesen and S. Goswami, "Shape Segmentation and
Matching with Flow Discretization." Proceedings of the 8th
International Workshop on Algorithms and Data Structures (WADS),
Lecture Notes in Computer Science 2748, (2003) 25-36.
Relationships with alpha-shapes:
T. K. Dey, J. Giesen and M. John, "Alpha-Shapes and Flow Shapes
are Homotopy Equivalent." Proceedings of the 35rd Annual ACM
Symposium on the Theory of Computing (STOC), (2003) 493-502
Extension to the power diagram in:
J. Giesen and M. John, "Computing the Weighted Flow Complex."
Proceedings of the 8th International Fall Workshop Vision, Modeling,
and Visualization (VMV), (2003) 235-243.
Theorem 1: The critical points of h = Min pi_p(x) are the intersection
points of the power objects and their dual Delaunay objects (where
pi_p(x) = |x-p|² - r², the power distance).
This work is very close in spirit to the work on shock graphs and
scaffold. Although they do not mention medial axes, we can consider
that this work is related to two of the previous classes: distance
based (level-sets) and partition-based (Voronoi/Delaunay).
NB: I met Giesen last year at the Workshop on surface meshing at DIMACS
and told him that their work was very closely related to ours. He did
not know of shock graphs and scaffold at the time. In their most recent
papers they do mention one of our papers (shock scaffolds, IWVF 2001),
but only as a method to compute the MA, and they seem unaware of
previous work on 2D shapes.
Last Updated: July 8, 2004