This section gives some general information about TetGen. These are not required in order to use TetGen.
TetGen is written entirely in C++, and it only uses the standard C (ANSI) libraries. Hence the code is easily portable and should be compiled by a popular C++ compilers, such as GNU’s gcc/g++, Intel’s and Mircosoft’s C++ compilers. So far, TetGen has been successfully compiled on all major computer architectures and major operating systems (Unix/Linux, Windows, Mac OS) with both 32-bit and 64-bit versions.
The current version of TetGen contains about 25,000 source lines and 7,000 comment lines. These numbers do not include those of Shewchuk’s robust predicates.
TetGen dynamically allocates memory when it is needed. There is no minimum memory requirement to run TetGen. The maximum memory is only limited by the physical memory available from your system. The more memory you have, the larger the mesh you can generate.
For example, the 32-bit version of TetGen used about 694.5 Mega bytes memory to generate the Delaunay tetrahedralization (DT) of a set of 2,000,000 (two million) points randomly distributed inside a unit cube. This DT has 13,504,899 tetrahedra. This is approximately 364 bytes per vertex or 54 bytes per tetrahedron. In other words, with 4 Giga byte memory, a maximum Delaunay tetrahedralization may be generated by the 32-bit version of TetGen having approximately 11,799,360 (ca. 11 million) vertices or 79,536,431 (ca. 79 million) tetrahedra.
More memory is needed in generating quality tetrahedral meshes. The extra memory is used to store boundary information and working arrays of algorithms. For example, the 32-bit version of TetGen used about 770 Mega bytes memory to generate a quality tetrahedral mesh with 2,000,000 (two million) vertices and 12,237,300 tetrahedra.
So far, the largest quality tetrahedral mesh was generated by the 64-bit version of TetGen. It contains 1,007,700,944 (ca. 1 billion) vertices, and 6,454,556,696 (ca. 6.45 billion) tetrahedra. TetGen used about 905.7 Giga bytes memory on generating this mesh, see Table 2.
When generating Delaunay tetrahedraliations, the worst case running time of TetGen is O(n2), where n is the input number of vertices. However, this only happens for some very special point sets. For most point sets appearing in applications, TetGen runs in almost O(n logn) time, see Table 1.
The CPU time required to obtain the quality tetrahedral mesh is obviously related to the complexity of the geometry and topology of the inputs, as well as the command line switches and parameters specified. Nevertheless, the running time of TetGen increases almost linearly with respect to the output number of mesh elements, see Table 2.
This section gives some practical information regarding the performance of TetGen. In particular, Table 1 and Table 2 report the statistics of some test runs of TetGen. The used version of TetGen was a 64-bit version compiled by GNU gcc/g++ version 4.7.2 with the −O3 (optimization) switch. The used computer was a computer of WIAS (erhard-03) with Intel(R) Xeon(R) Ten-Core 2.40GHz CPU, 1,024 Giga byte memory, and SuSE Linux. The given CPU times exclude the file I/O time. Comparisons of TetGen with other programs are available in paper [24].
Table 1 shows the statistics of TetGen on creating Delaunay tetrahedralizations. Three random point sets of different sizes are used in these tests. They are generated by the tool rbox (command: rbox -D3 xxx) in the program qhull (http://www.qhull.org). It is well known that the Delaunay tetrahedralizations of random point sets have linear complexity. Both memory usage and CPU time of TetGen are quasilinear.
Table 2 shows the statistics of TetGen on creating quality tetrahedral meshes. The input of these tests is a 3d unit cube with 8 vertices and 6 facets described in file cube.smesh. The resulting meshes were generated by using the command: tetgen -pqa# -x1000000 cube.smesh, where “-a#” specifies a very small tetrahedron volume constraint, and “ -x1000000” specifies a user-defined memory allocation size.
volume # of points # of tets used memory CPU time constraint (output) (output) (Mega bytes) (seconds) 1.0×10−7 3,023,518 18,744,549 2,904 126 1.0×10−8 29,412,255 186,090,870 27,599 1,374 1.0×10−9 290,323,148 1,854,336,524 268,781 12,124 5.0×10−10 579,301,396 3,706,331,655 534,386 26,872 2.87×10−10 1,007,700,944 6,454,556,696 927,449 44,261
Table 2: Statistics of TetGen on generating quality tetrahedral meshes.
When running TetGen, errors may happen. In this case, TetGen may fail to generate a mesh. The typical reasons that cause failures of TetGen may be one of the follows:
In most cases TetGen is able to detect the error. If TetGen is running as a standalone program and if an error is detected, then TetGen will report a message that describes the error possibly together with a suggestion to fix it, and terminate. Below is an example of such a message.
Found two segments intersect each other.
1st: [13,7] 1.
2nd: [1114,1113] 1.
A self-intersection was detected. Program stopped.
Hint: use -d option to detect all self-intersections.
If TetGen is running as a library, i.e., it is called inside other program, then the error message will not be seen, and TetGen will throw an error index (integer), which can be catched by the standard C++ exception handler try and catch. A list of error indices and messages are provided in the Appendix.
When TetGen terminates on error, it automatically releases the used memory before terminating itself. This avoids potential memory leak when calling TetGen multiple times.