Bilkent University
Department of Computer Engineering
CS590/690 SEMINAR
Parallel Constrained Delaunay Tetrahedralization
Ziya Erkoc
MS Student
(Supervisor: Asst. Prof. Eray Tüzün)
Computer Engineering Department
Bilkent University
Abstract: Constrained Delaunay Tetrahedralization (CDT) algorithms are widely used in various practical settings. We aim to develop an algorithm that can tetrahedralize large objects faster or using less memory depending on the selected mode. We achieve this by following the divide-and-conquer paradigm. Specifically, our algorithm receives the input mesh as input, partitions it into several parts according to a user-defined parameter, tetrahedralize each piece separately, and combine the tetrahedralized parts to obtain the final tetrahedral mesh. In the base case, we use TetGen because it generates quality tetrahedra efficiently. The algorithm consists of Input Partitioning, Surface Closure, and Mergestages. When the Parallel Processing mode is enabled, we apply multi-threading to speed up, while for the Memory Requirement Reduction mode, we reduce the memory footprint by using single-thread and intermediate files. The experimental results show that our algorithm can provide significant speedup or memory requirement reduction over TetGen. At the same time, it can tetrahedralize large objects that TetGen cannot. Besides, in some cases, it can even create higher quality tetrahedral mesh than TetGen. Hence, it can be used as an alternative tetrahedralization tool when TetGen cannot tetrahedralize a large model due to its high memory requirement, to speed up the tetrahedralization, or to increase the tetrahedral mesh quality. In this regard, our algorithm is a divide-and-conquer extension to the sequential CDT algorithm, TetGen.
DATE: 22 November 2021, Monday @ 16:30 Zoom