How to get the boundary of delaunay triangulation

Question

I'm implementing tunnel detection algorithm in the paper "Computing Geometry-aware Handle and Tunnel Loops in 3D Models".

Before the actual tunnel detection, the input needs to be preprocessed, as mentioned in paper Section 5

"In order to apply the algorithm for persistence, we assume that the input surface M is presented with a simplicial complex K which tessellates the convex hull of M and M is a subcomplex of K. This means that we have the explicit simplicial representations for both inside space I and outside space O."

My input is a triangular closed surface mesh, from the above quote, my understanding is that I should:

1.Read in the the surface mesh, perform a delaunay 3d algorithm using the points of the surface mesh. The output of this step is a tetrahedron mesh.

2.From step1, I can somehow get the boundary surface(boundary in terms of same boundary as input surface mesh), exterior triangles and interior triangles.

The author of the paper actually posted a video on Youtube illustrating the steps mentioned above.

My question is: In step2, how can I get the surface and exterior triangles from tetrahedron mesh? During delaunay triangulation 3d, all it needs are the point clouds(ie. positions of points).

I've tried constructing the initial surface mesh's SDF and try to find the surface from tetrahedron using SDF, but this has proved to be not ideal.

Can someone give me some hint? Or am I heading a wrong direction?

Answer 1

Unless the original surface mesh triangles are used by the resultant tet mesh, it is imposible (improbable) to obtain the original boundary surface (unless of course, original boundary surface was a convex hull). The original surface mesh triangles can only be encoded into the resultant tet grid, if boundary tetrahedron faces retain the original tessellation. The Delaunay method you use to generate the tet mesh (Non-constrained) does not do this. Non-constrained Delaunay methods may edge flip, thus loosing the original surface tessellation.

Non-constrained Delaunay methods always produce a convex hull (of the original pointset... 2D and 3D), so it sounds like the routine is working (you would get a convex hull back), but its the method used to generate the tet grid which prevents what you want in this case.

So unfortunately, in this case you cannot since the tet mesh was created using Delaunay, and not Constrained-Delaunay.

Alternative methods to construct unstructured grids such as Constrained-Delaunay and Advancing front use the original surface mesh as boundary conditions and so can retain/encode the original surface mesh which can be extracted using the method outlined below to obtain the original boundary surface tessellation.

If using one of the other methods for generating a tet mesh which preserve/encode the boundary surface into the tet faces, you can obtain a boundary surface of a tet mesh by identifying which tet faces are used once in a tet mesh of shared vertices. These by definition are the triangles of the tet mesh boundary surface.

All 'interior' faces will be used by at most two tetrahedrons. All 'exterior' (boundary surface) faces will be used only once.

1. Share the vertices of the tet mesh.

2. Create a list of all the triangles (faces) in the tet mesh (each tet has 4 faces, and since tet mesh uses shared vertices, each tet will have 4 vertices).

3. Create a list of vertex usage wrt to triangles. i.e a list of vertices for each triangle.

4. Most triangles should have 6 vertices used (3 unique vertices, so 3 pairs). The triangles which have 3 vertices (no duplicate vertex indexes) have no adjacent tet and so are boundary triangles.

5. Rebuild a triangle surface using just the boundary triangles.

Robustness is important, any cavities within the tet mesh will also be identified as boundary surfaces, however ime you can be quite liberal with equality tolerance when sharing vertices (checking which vertices are equal).