Bilkent University
Department of Computer Engineering


Memory-efficient Constrained Delaunay Tetrahedralization of Large Three-dimensional Triangular Meshes


Ziya Erkoç
Master Student
(Supervisor: Prof. Dr. Uğur Güdükbay )
Computer Engineering Department
Bilkent University

Abstract: We propose a divide-and-conquer algorithm that can solve the Constrained Delaunay Tetrahedralization (CDT) problem. It consists of three stages: Input Partitioning, Surface Closure, and Merge. We first partition the input into several pieces to reduce the problem size. We apply 2D Triangulation to close the open boundaries to make new pieces watertight. Each piece is then sent to TetGen [Hang Si, "TetGen, a Delaunay-Based Quality Tetrahedral Mesh Generator", ACM Transactions on Mathematical Software, Vol. 41, No. 2, Article No. 11, 36 pages, January 2015] for processing. We finally merge each tetrahedral mesh to calculate the final solution. In addition, we apply post-processing to remove vertices we introduced during the input partitioning stage to preserve the input triangles. An alternative approach that does not insert new vertices and eliminates the need for post-processing is also possible but not robust. The benefit of our method is that it can reduce memory usage or increase the speed of the process. It can even tetrahedralize meshes that TetGen cannot do due to the memory's insufficiency. We also observe that this method can increase the overall tetrahedral mesh quality.


DATE: 19 July 2022, Tuesday @ 10:45 Zoom