# How to get the boundary of delaunay triangulation

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?

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).

• Hi lfgtm, thanks for the detailed explanation. I think what you meant is somewhat similar to this stackoverflow.com/questions/66607716/… post. I've tried looping through all the tetra faces and looking for duplicates. What I end up with(the faces only used once) is the convex hull of delaunay mesh. But what I want are the triangle faces similar to the original input triangular mesh. Mar 6, 2023 at 16:28
• @veggieg Yes, it is the same principle. Very important that the vertices are shared in order to determin shared/adajcent tet faces. Mar 6, 2023 at 17:43
• Apologies, I understand your question better now, if you do not use the surface mesh as boundary conditions for constructing the tet grid, you would stand a good chance of loosing the triangle information with the resultant tet mesh. non-constrained Delaunay methods may edge flip so the original triangle edges would no longer be encoded into the resultant tet mesh. In which case there is no way to obtain the original surface mesh unless the surface mesh triangles form part of the tet faces. Have updated answer. Mar 6, 2023 at 17:51
• Thank you for the update. I don't know about constrained delaunay triangulation before, if this help save the surface information it would be much easier. But most popular libraries only support non-constrained delaunay triangulation. Or, I could also try the SDF algorithm, but the precision is still a problem. Mar 9, 2023 at 16:39
• @veggieg you could also look into "Advancing front" instead of constrained delaunay. There are also hybrid approaches which utliise traits from multiple methods for tet grid generation. Mar 9, 2023 at 16:53