Isotopic Reconstruction of Surfaces with Boundaries

Home People Research Publications

Abstract. We present an algorithm for the reconstruction of a surface with boundaries (including a non-orientable 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 alpha-complex of a sample of the surface. No other post-processing 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), 1371--1382. 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 alpha-complex 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. Surface reconstruction on Moai. From left to right: input point data, alpha-complex with sliver tetrahedra (red), final surface after sliver peeling. 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. tetrahedron T peeling T through e 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 2-2 flat tetrahedra (see paper for definition). Algorithms for Closed Surfaces There are three steps for our algorithm on closed surfaces. ReConstruct(P) 1) Compute alpha-complex K=C(P); 2) While there is a peelable tetrahedron in K, peel it top-down; 3) Output the resulting 2-complex. Surfaces with Boundaries and Extension to Non-Uniform Sampled Point Data We use collar extension to handle surfaces with boundaries, and we also extend our algorithm to non-uniform sampled point data. See our paper for details. Some Results on Uniform Sampling Some Results on non-Uniform Sampling The Peel software based on this result is available.