1 - Zhejiang University, China

2 - Zhejiang Sci-Tech University, China

3 - Shenzhen Poisson Software Co., Ltd., China

* - Corresponding Author

Abstract

2D constrained Delaunay triangulation (CDT) is a key component in CAD, visualization, and scientific computing. We present a highly parallel GPU-based method that is capable of computing CDT for inputs with up to 10 million vertices in 0.1 seconds on a NVIDIA GeForce RTX 4090 GPU, while efficiently and robustly enforcing arbitrary valid constraints. Across benchmarks with diverse spatial distributions, our method typically delivers several-fold speedups over the prior state-of-the-art GPU approach and is roughly an order of magnitude faster than widely used CPU implementations. The efficiency stems from an improved parallel edge-flip scheme coupled with a constraint-handling algorithm with provable time complexity, enabling stable performance even in adversarial and worst-case configurations.
 

Letters benchmark: For a scene containing approximately 900K vertices with numerous constraints of varying sizes, gCDT achieves an overall speedup of roughly 25X over the prior state-of-the-art GPU-based CDT algorithm gDel2D [Qi et al. 2013, 2019], while the constraint-processing component is nearly three orders of magnitude faster.

Contents