gCDT: A Highly Parallel GPU Algorithm for Large-Scale Constrained Delaunay Triangulation

摘要

2D constrained Delaunay triangulation (CDT) is a key component in CAD, visualization, and scientific computing. We present a highly parallel GPU-based method capable of computing CDTs on inputs with millions of vertices, while efficiently and robustly enforcing arbitrary valid constraints. On benchmarks with complex constraints, 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-flipping scheme and a constraint-handling algorithm with predictable parallel behavior, enabling stable performance even on adversarial and difficult configurations.