Boundary recovery after 3D Delaunay tetrahedralization without adding extra nodes

In this paper, we investigate boundary recovery, the problem that has troubled researchers ever since Delaunay-based methods were applied to generate mesh. There are a number of algorithms for boundary recovery already and most of them depend heavily on adding extra nodes. In this paper, we make an effort to seek a method to recover boundaries without using extra nodes. It was noted that some previous algorithms imposed artificial boundary constraints on a meshing problem at the recovering stage; we first try to discard these artificial constraints and thus make things easier. Then a new method is proposed by which the boundaries can be recovered by means of two operations: (1) creating a segment in the mesh and (2) removing a segment from the mesh. Both operations are special cases of a general local transformation called small polyhedron reconnection operation. The method works well when coupled with the sphere-packing method proposed by the first author. If the mesh sizing function is suitable, a good configuration of nodes will be created accordingly by the sphere-packing method and the boundary can be recovered by the local transformation presented here without inserting extra nodes. Copyright q 2007 John Wiley & Sons, Ltd.