On converting sets of tetrahedra to combinatorial and PL manifolds

We investigate the problem of removing singularities from a non-manifold tetrahedral mesh so as to convert it to a more exploitable manifold representation. Given the twofold combinatorial and geometrical nature of a 3D simplicial complex, we propose two conversion algorithms that, depending on the targeted application, modify either its connectivity only or both its connectivity and its geometry. In the first case, the tetrahedral mesh is converted to a combinatorial 3-manifold, whereas in the second case it becomes a piecewise linear (PL) 3-manifold. For both the approaches, the conversion takes place while using only local modi. cations around the singularities. We outline sufficient conditions on the mesh to guarantee the feasibility of the approaches and we show how singularities can be both identified and removed according to the configuration of their neighborhoods. Furthermore, besides adapting and extending surface-based approaches to a specific class of full-dimensional simplicial complexes in 3D, we show that our algorithms can be implemented using a flexible data structure for manifold tetrahedral meshes which is suitable for general applications. In order to exclude pathological configurations while providing sound guarantees, the input mesh is required to be a sub-complex of a combinatorial ball; this makes it possible to assume that all the singularities are part of the mesh boundary. (C) 2009 Elsevier B.V. All rights reserved.