TetGen, a Delaunay-Based Quality Tetrahedral Mesh Generator

TLDR

TetGen is a C++ program that generates high‑quality tetrahedral meshes for numerical methods, addressing the theoretical and practical challenges of mesh quality and targeting researchers and developers in mesh generation. This article presents the essential algorithms and techniques used to develop TetGen. TetGen employs Delaunay‑based algorithms—incremental and constrained Delaunay insertion, edge‑recovery, and constrained Delaunay refinement—alongside an efficient mesh data structure, enhanced local operations, and filtered exact predicates to construct quality tetrahedral meshes. TetGen robustly handles arbitrary complex 3D geometries, operates quickly in practice, and its freely available source code is demonstrated through experimental examples and comparisons with other software.

Abstract

TetGen is a C++ program for generating good quality tetrahedral meshes aimed to support numerical methods and scientific computing. The problem of quality tetrahedral mesh generation is challenged by many theoretical and practical issues. TetGen uses Delaunay-based algorithms which have theoretical guarantee of correctness. It can robustly handle arbitrary complex 3D geometries and is fast in practice. The source code of TetGen is freely available. This article presents the essential algorithms and techniques used to develop TetGen. The intended audience are researchers or developers in mesh generation or other related areas. It describes the key software components of TetGen, including an efficient tetrahedral mesh data structure, a set of enhanced local mesh operations (combination of flips and edge removal), and filtered exact geometric predicates. The essential algorithms include incremental Delaunay algorithms for inserting vertices, constrained Delaunay algorithms for inserting constraints (edges and triangles), a new edge recovery algorithm for recovering constraints, and a new constrained Delaunay refinement algorithm for adaptive quality tetrahedral mesh generation. Experimental examples as well as comparisons with other softwares are presented.