3D triangulation?

Question

Programming

Hey!
I do not know how to solve the problem with 3D triangulation. Do not send me immediately to Google, I have already been there, but there are still questions. Let me first describe my problem.
As input, I get the "skeleton" of a 3D object, consisting of lines. I need to triangulate this volume. Sounds simple, but I haven't found a solution.
Let's say I got the "skeleton" of the object, it is immediately worth noting that the object can be "convex", this is the essence of the problem. I need to fill this volume with tetrahedra, and there is no goal of achieving a large segmentation. The picture below shows the "skeleton" (left) and what should come out (right).

In order to fill the volume of the "skeleton" with tetrahedra, it is necessary to create additional edges. The picture below shows how this should work.

It is in the creation of new edges that the problem lies. Since the figure can be "convex", a new edge can be built outside the required volume, as a result of which we will get an incorrect object.

Is there any algorithm? Is it possible to do this using some libraries (eg OpenGL or DirectX)?

Answer 1

In general, this is how it is done.
Let the figure be given by a set of triangular faces with a known orientation. An even number of faces converge in each edge (for example, a figure of two tetrahedra glued along an edge is possible), and when going around any edge, the orientations of the faces converging in it alternate (for example, there are faces ABC, BAD, ABE, BAF). Even if there are no such strange edges in the original model, they can appear at an intermediate stage.
Select any two faces with the following properties:
- they have a common edge AB;
- when bypassing this edge, they are sequential
- the internal angle between these faces is less than 180 degrees.
Such borders will always be found. Let it be ABC and BAD.
Consider the tetrahedron ABCD. Let's check if it has other vertices inside. If not, we will replace the faces ABC and BAD with CAD and BCD (thus cutting out ABCD from the model). If there is, we take the vertex E of them, which is closest to the face ABC, and replace the face ABC with three faces ABE, AEC, EBC.
After that, we look at the faces, and if it turns out that some face occurs twice with opposite orientations (ABC and ACB), we discard both copies.
The process is repeated until all edges disappear.
Everything.

Answer 2

Delaunay triangulation generalizes to cases of any dimension.

Answer 3

The source code of various triagulation algorithms and links to scientific articles on this topic can be viewed at the link: geuz.org/gmsh/. In my opinion, gmsh is a very good mesher.

Answer 4

Save in STL format, which is only made of triangles. In general, you can choose the quality of the conversion. A rectangle is always split into two triangles. The result of the coordinates of the points of the triangles can be obtained in text format.