


People Research Publications 
Abstract.
We present an algorithm for the reconstruction of a surface with boundaries
(including a nonorientable one) in three dimensions from a sufficiently dense
sample. It is guaranteed that the output is isotopic to the unknown sampled
surface. No previously known algorithm guarantees isotopic or homeomorphic
reconstruction of surfaces with boundaries. Our algorithm is surprisingly
simple. It peels slivers greedily from an alphacomplex of a sample of the
surface. No other postprocessing is necessary. We provide several experimental
results from an implementation of our basic algorithm and also a modified
version of it. Paper: T. K. Dey, K. Li., E. A. Ramos, and R. Wenger. Isotopic Reconstruction of Surfaces with Boundaries. Proc. Sympos. Geom. Processing 2009 (SGP09), special issue of Computer Graphics Forum, Vol. 28, No. 5 (2009), 13711382. Software: Peel software Our algorithm takes as input a point cloud P (sufficiently dense) sampled from a smooth surface M (with or without boundaries), and output a Delaunay mesh from those sample points in P. The output is isotopy equivalent to the original surface M. The idea is that we first construct an alphacomplex K from P, then peel off all the tetrahedra from it to get a surface that is isotopic to M. We show this process on 3D model Moai in the following image.
Peeling a tetrahedron Let T be a tetrahedron in K, and T has edge e and t1, t2 are two triangles of T incident to e. We say T is peelable by e if no triangle other than t1, t2 is incident to T in K. A new complex K' is obtained by peeling T (removing {T,e,t1,t2}) from K, denoted K(e)>K'. Note that a peeling doesn't delete any vertex of K.
Canonical Peeling Sequence Two edge sequences {e_i} and {g_i} by which K is peeled are compatible if for any e (in {e_i}) and g (in {g_i}) that peel the same tetrahedron in K, either e=g or e and g are vertex disjoint. For example, as shown in the next picture, {e_2, e_1} and {e_3, e_2} are compatible, but not with {e_4, e_1}
We show in our paper that there exist a canonical peeling sequence of tetrahedra from K, induced by a deformation retraction of B(P), which is the union of balls of radius alpha at all points of P. We call this deformation retraction: Normal Retraction. Normal Retraction When a Voronoi vertex is swept over as B(P) retracts, two Voronoi edges go out of B(P), corresponding to that a sliver is peeled off from C(P), which is the Delaunay triangulation restricted to B(P). Equivalently, each peeling from C(P) is associated with a Voronoi vertex going out of B(P). Note that initially C(P)=K before the normal retraction. The sequence of simplices, {s_1,s_2,...,s_n}, removed from C(P) as C(P) transforms to Del_M(P), induces the canonical peeling sequence for C(P). We also show that all tetrahedra peeled are 22 flat tetrahedra (see paper for definition). Algorithms for Closed Surfaces There are three steps for our algorithm on closed surfaces. ReConstruct(P) 1) Compute alphacomplex K=C(P); 2) While there is a peelable tetrahedron in K, peel it topdown; 3) Output the resulting 2complex. Surfaces with Boundaries and Extension to NonUniform Sampled Point Data We use collar extension to handle surfaces with boundaries, and we also extend our algorithm to nonuniform sampled point data. See our paper for details. Some Results on Uniform Sampling
Some Results on nonUniform Sampling
The Peel software based on this result is available. 