Abstract:

Constrained Delaunay Triangulation (CDT) has significant practical applications in geographic information systems, 3D modeling, and engineering simulation. However, when large-scale datasets are involved, its construction process still faces challenges such as insufficient parallel efficiency, high topological update overhead, and strong platform dependency. To address these issues, a parallel constrained Delaunay triangulation algorithm based on compute shaders was proposed. Centered on the compute shader execution model, the proposed approach leveraged the fine-grained thread parallelism and high-throughput memory architecture of GPUs to achieve full-process parallelization of the CDT mesh construction workflow. In terms of algorithm implementation, the initial Delaunay triangulation was first generated through point set discretization and parallel Voronoi diagram construction. Subsequently, to meet the intersection-detection and local-reconstruction requirements during the insertion of constrained edges, a dynamic data-layout strategy based on a two-stage prefix sum was proposed to achieve compact storage and efficient indexing of intersection information. Based on this, two core data structures were designed: a dynamic intersecting-edge storage table and a dynamic constraint influence-domain index table. These were used to rapidly locate candidate edges intersecting with constraint edges and the affected triangular regions, respectively, thereby transforming the traditional global search process into local index access and significantly reducing memory access overhead. To address thread conflicts and consistency-maintenance issues in parallel topology updates, an adaptive parallel edge-flip mechanism based on local consistency was proposed. Using constraint edges as the driving unit, this mechanism confined the edge-flip process to independent thread domains. Concurrency-safe updates were achieved through atomic operations and lightweight locks, while a double-buffered queue was employed to facilitate the dynamic propagation and convergence of invalid edges, effectively avoiding concurrency issues such as redundant flips, write conflicts, and out-of-order adjacencies. Experimental results demonstrated that, for datasets containing millions of points and largescale constrained-edge sets, the proposed algorithm achieved significant improvements in computational efficiency compared to traditional serial methods and existing GPU parallel implementations, while exhibiting excellent stability and adaptability on real-world geospatial data. The research findings validated the application potential of the parallel CDT network construction method based on compute shaders in cross-platform geometric computation and high-performance graphics processing.

Key words: constrained Delaunay triangulation, compute shader, GPU, parallel computing, data structure