1//************************************ bs::framework - Copyright 2018 Marko Pintera **************************************//
2//*********** Licensed under the MIT license. See LICENSE.md for full terms. This notice is not to be removed. ***********//
3#include "Utility/BsTriangulation.h"
4#include "Math/BsVector3.h"
5
6// Third party
7#include "TetGen/tetgen.h"
8
9namespace bs
10{
11 TetrahedronVolume Triangulation::tetrahedralize(const Vector<Vector3>& points)
12 {
13 TetrahedronVolume volume;
14 if (points.size() < 4)
15 return volume;
16
17 tetgenio input;
18 input.numberofpoints = (int)points.size();
19 input.pointlist = new REAL[input.numberofpoints * 3]; // Must be allocated with "new" because TetGen deallocates it using "delete"
20 for(UINT32 i = 0; i < (UINT32)points.size(); ++i)
21 {
22 input.pointlist[i * 3 + 0] = points[i].x;
23 input.pointlist[i * 3 + 1] = points[i].y;
24 input.pointlist[i * 3 + 2] = points[i].z;
25 }
26
27 tetgenbehavior options;
28 options.neighout = 2; // Generate adjacency information between tets and outer faces
29 options.facesout = 1; // Output face adjacency
30 options.quiet = 1; // Don't print anything
31
32 tetgenio output;
33 ::tetrahedralize(&options, &input, &output);
34
35 UINT32 numTetrahedra = (UINT32)output.numberoftetrahedra;
36 volume.tetrahedra.resize(numTetrahedra);
37
38 for (UINT32 i = 0; i < numTetrahedra; ++i)
39 {
40 memcpy(volume.tetrahedra[i].vertices, &output.tetrahedronlist[i * 4], sizeof(INT32) * 4);
41 memcpy(volume.tetrahedra[i].neighbors, &output.neighborlist[i * 4], sizeof(INT32) * 4);
42 }
43
44 // Generate boundary faces
45 UINT32 numFaces = (UINT32)output.numberoftrifaces;
46 for (UINT32 i = 0; i < numFaces; ++i)
47 {
48 INT32 tetIdx = -1;
49 if (output.adjtetlist[i * 2] == -1)
50 tetIdx = output.adjtetlist[i * 2 + 1];
51 else if (output.adjtetlist[i * 2 + 1] == -1)
52 tetIdx = output.adjtetlist[i * 2];
53 else // Not a boundary face
54 continue;
55
56 volume.outerFaces.push_back(TetrahedronFace());
57 TetrahedronFace& face = volume.outerFaces.back();
58
59 memcpy(face.vertices, &output.trifacelist[i * 3], sizeof(INT32) * 3);
60 face.tetrahedron = tetIdx;
61 }
62
63 // Ensure that vertex at the specified location points a neighbor opposite to it
64 for(UINT32 i = 0; i < numTetrahedra; ++i)
65 {
66 INT32 neighbors[4];
67 memcpy(neighbors, volume.tetrahedra[i].neighbors, sizeof(INT32) * 4);
68
69 for(UINT32 j = 0; j < 4; ++j)
70 {
71 INT32 vert = volume.tetrahedra[i].vertices[j];
72
73 for (UINT32 k = 0; k < 4; ++k)
74 {
75 INT32 neighborIdx = neighbors[k];
76 if (neighborIdx == -1)
77 continue;
78
79 Tetrahedron& neighbor = volume.tetrahedra[neighborIdx];
80 if (vert != neighbor.vertices[0] && vert != neighbor.vertices[1] &&
81 vert != neighbor.vertices[2] && vert != neighbor.vertices[3])
82 {
83 volume.tetrahedra[i].neighbors[j] = neighborIdx;
84 break;
85 }
86 }
87 }
88 }
89
90 return volume;
91 }
92}