基于计算着色器的并行约束Delaunay三角剖分算法

doi:10.11996/JG.j.2095-302X.2026040801

摘要/Abstract

摘要：

约束Delaunay三角剖分(CDT)在地理信息系统、三维建模及工程仿真等领域具有重要应用价值，但在大规模数据场景下，其构建过程仍面临并行效率不足、拓扑更新开销高以及平台依赖性强等问题。为此，提出了一种基于计算着色器的并行约束Delaunay三角剖分算法。以计算着色器执行模型为核心，利用GPU的细粒度线程并行性与高吞吐存储架构，实现CDT构网流程的全流程并行化。在算法实现上，首先通过点集离散化与并行Voronoi图构建生成初始Delaunay三角网；随后，围绕约束边插入过程中的相交检测与局部重构需求，提出一种基于双阶段前缀和的动态数据布局策略，实现相交信息的紧凑存储与高效索引。在此基础上，设计了动态相交边存储表与动态约束影响域索引表两类核心数据结构，分别用于快速定位约束边相交的候选边及受影响三角形区域，从而将传统全局搜索过程转化为局部索引访问，显著降低访存开销。针对并行拓扑更新中的线程冲突与一致性维护问题，提出一种基于局部一致性的自适应并行边翻转机制，以约束边为驱动单元，将边翻转过程限定在独立线程域内，通过原子操作与轻量级锁实现安全的拓扑更新，并结合双缓冲队列实现非法边的动态传播与收敛，有效避免了重复翻转、写冲突及邻接关系失序等并发问题。实验结果表明，在百万级点集及约束条件下，相较于传统串行方法及现有GPU并行实现，该算法在计算效率方面具有显著提升，且在真实地理空间数据上表现出良好的稳定性与适应性。研究结果验证了基于计算着色器的并行CDT构网方法在跨平台几何计算与高性能图形处理中的应用潜力。

关键词: 约束Delaunay三角剖分, 计算着色器, GPU, 并行计算, 数据结构

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

中图分类号:

TP391

陈国军, 孔赟艺, 陈家乐, 宋双双. 基于计算着色器的并行约束Delaunay三角剖分算法[J]. 图学学报, 2026, 47(4): 801-811.

CHEN Guojun, KONG Yunyi, CHEN Jiale, SONG Shuangshuang. Parallel constrained Delaunay triangulation algorithm based on compute shaders[J]. Journal of Graphics, 2026, 47(4): 801-811.

图/表 14

图1 约束Delaunay三角剖分构网过程((a) 点集与约束边集；(b) Voronoi图；(c) DT；(d) CDT)

Fig. 1 Constrained Delaunay triangulation mesh generation process ((a) Point set and constraint set; (b) Voronoi diagram; (c) DT; (d) CDT)

图2 并行约束Delaunay三角剖分算法的整体架构

Fig. 2 The overall architecture of the parallel constrained Delaunay triangulation algorithm

图3 基于Voronoi-Delaunay对偶性的初始三角网构建((a) Voronoi图；(b) DT)

Fig. 3 Construction based on Voronoi-Delaunay duality ((a) Voronoi diagram; (b) DT)

图4 动态相交边存储表

Fig. 4 Dynamic intersection edge table

图5 动态约束影响域索引表

Fig. 5 Dynamic constraint domain index table

图6 并行边翻转操作流程图

Fig. 6 Parallel edge flip operation flowchart

图7 边翻转3种情况((a) 凸四边形且翻转后不再相交；(b) 凸四边形但翻转后仍与约束相交；(c) 凹四边形)

Fig. 7 Three scenarios of edge flipping ((a) Convex quadrilateral and no longer intersects after flipping; (b) Convex quadrilateral but still intersects with the constraint after flipping; (c) Concave quadrilateral)

表1 固定50万约束边改变点数不同方法运行时间对比/ms

Table 1 Comparison of running time of different methods for changing points with fixed 50 w constraints/ms

点集规模(10⁶)	CGAL	GPU-DT	Ours
1.0	12 047	1 014	133.134
1.5	18 493	1 516	143.896
2.0	20 776	1 901	155.214
2.5	28 717	2 318	160.521
3.0	33 293	2 836	167.000
3.5	49 209	3 123	174.326
4.0	67 425	3 541	183.605

图8 不同点集下CGAL与GPU-DT的运行时间和Ours相对于CGAL与GPU-DT的加速情况

Fig. 8 The running time of CGAL and GPU-DT with different points and speedup relative to CGAL and GPU-DT

表2 固定200万点改变约束边数不同方法运行时间对比/ms

Table 2 Comparison of running time of different methods for changing the number of constrained edges with a fixed 200 w points/ms

约束边集规模(10⁵)	CGAL	GPU-DT
2	5 815	1 685	147.390
3	7 796	1 768	149.791
4	11 654	1 817	153.068
5	20 776	1 901	155.214
6	22 794	2 141	157.198
7	28 556	2 223	160.236
8	37 138	2 385	165.346
9	44 696	2 434	167.768
10	56 799	2 501	169.640

图9 不同约束边集下CGAL与GPU-DT的运行时间和Ours相对于CGAL与GPU-DT的加速情况

Fig. 9 The running time of CGAL and GPU-DT with different constraints and speedup relative to CGAL and GPU-DT

图10 CDT构网各阶段的运行时间((a) 固定50万约束边改变点集；(b) 固定200万点集改变约束边数)

Fig. 10 The running time of different steps of the CDT computation ((a) Fixed 50w constraints and varying the number of points; (b) Fixed 200w points and varying the number of constraints)

表3 消融实验结果/ms

Table 3 Results of ablation experiment/ms

约束边集规模(10⁵)	Variant-1	Variant-2	Variant-3	Ours
2	164.517	155.435	152.034	147.390
4	173.290	161.868	159.163	153.068
6	184.508	169.286	163.288	157.198
8	195.390	178.826	170.705	165.346
10	209.078	187.892	180.908	169.640

图11 真实数据集CDT构建示例((a) 澳大利亚地貌数据；(b) 等高线地形数据；(c) 城市建筑群数据)

Fig. 11 CDT results on real-world datasets ((a) Australian topography; (b) Contour map; (c) Urban building dataset)

参考文献 30

[1]	MAHMOUD A H, PORUMBESCU S D, OWENS J D. Dynamic mesh processing on the GPU[J]. ACM Transactions on Graphics, 2025, 44(4): 1-19.
[2]	MIKY Y, KAMEL A, ALSHOUNY A. A combined contour lines iteration algorithm and Delaunay triangulation for terrain modeling enhancement[J]. Geo-Spatial Information Science, 2023, 26(3): 558-576. DOI URL
[3]	袁清洌, 吴学群. 结合Delaunay三角面分离法与搜索球策略的三维曲面重建算法[J]. 图学学报, 2018, 39(2): 278-286. DOI
	YUAN Q L, WU X Q. 3D surfaces reconstruction algorithm via detaching Delaunay triangular mesh and search-ball approach[J]. Journal of Graphics, 2018, 39(2): 278-286 (in Chinese).
[4]	BHATTARAI S, DAHAL K, VICHARE P, et al. Adapted Delaunay triangulation method for free-form surface generation from random point clouds for stochastic optimization applications[J]. Structural and Multidisciplinary Optimization, 2020, 61(2): 649-660. DOI
[5]	LUO Y M, MI Z X, TAO W B. DeepDT: learning geometry from Delaunay triangulation for surface reconstruction[EB/OL]. (2021-05-18)[2025-09-05]. https://ojs.aaai.org/index.php/AAAI/article/view/16327.
[6]	CASTAÑEDA F D, GARCÍA-ACOSTA G, GARZÓN- ALVARADO D A, et al. Design for the additive manufacturing of structural elements with cellular materials using Voronoi diagrams and Delaunay triangulations: biological and structural applications[J]. Mechanics of Advanced Materials and Structures, 2024, 31(27): 9550-9570. DOI URL
[7]	CHEW L P. Constrained Delaunay triangulations[C]// The 3rd Annual Symposium on Computational Geometry. New York: ACM, 1987: 215-222.
[8]	LAWSON C L. Generation of a triangular grid with application to contour plotting[R]. Pasadena: Jet Propulsion Laboratory, 1972.
[9]	BOWYER A. Computing Dirichlet tessellations[J]. The Computer Journal, 1981, 24(2): 162-166. DOI URL
[10]	GUIBAS L, STOLFI J. Primitives for the manipulation of general subdivisions and the computation of Voronoi[J]. ACM Transactions on Graphics, 1985, 4(2): 74-123. DOI URL
[11]	LIN J X, CHEN R Q, YANG C C, et al. Distributed and parallel Delaunay triangulation construction with balanced binary-tree model in cloud[C]// The 15th International Symposium on Parallel and Distributed Computing. New York: IEEE Press, 2016: 107-113.
[12]	ZHOU S, JONES C B. HCPO: an efficient insertion order for incremental Delaunay triangulation[J]. Information Processing Letters, 2005, 93(1): 37-42. DOI URL
[13]	FORTUNE S. A sweepline algorithm for Voronoi diagrams[C]// The 2nd Annual Symposium on Computational Geometry. New York: ACM, 1986: 313-322.
[14]	ŽALIK B. An efficient sweep-line Delaunay triangulation algorithm[J]. Computer-Aided Design, 2005, 37(10): 1027-1038. DOI URL
[15]	BINIAZ A, DASTGHAIBYFARD G. A faster circle-sweep Delaunay triangulation algorithm[J]. Advances in Engineering Software, 2012, 43(1): 1-13. DOI URL
[16]	NAVARRO C, HITSCHFELD-KAHLER N, SCHEIHING E. A parallel GPU-based algorithm for Delaunay edge-flips[EB/OL]. [2025-09-14]. https://scholar.google.com/scholar?hl=zhCN&as_sdt=0%2C5&q=A+parallel+gpu-based+algorithm+for+delaunay+edge-flips&btnG=#d=gs_cit&t=1728983123697&u=%2Fscholar%3Fq%3Dinfo%3AtcrG4K4tgnsJ%3Ascholar.google.com%2F%26output%3Dcite%26scirp%3D0%26hl%3Dzh-CN.
[17]	FISCHER I, GOTSMAN C. Fast approximation of high-order voronoi diagrams and distance transforms on the GPU[J]. Journal of Graphics Tools, 2006, 11(4): 39-60. DOI URL
[18]	RONG G D, TAN T S. Jump flooding in GPU with applications to Voronoi diagram and distance transform[C]// 2006 Symposium on Interactive 3D Graphics and Games. New York: ACM, 2006: 109-116.
[19]	RONG G D, TAN T S, CAO T T, et al. Computing two-dimensional Delaunay triangulation using graphics hardware[C]// 2008 Symposium on Interactive 3D Graphics and Games. New York: ACM, 2008: 89-97.
[20]	CAO T T, TANG K, MOHAMED A, et al. Parallel Banding Algorithm to compute exact distance transform with the GPU[C]// 2010 ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games. New York: ACM, 2010: 83-90.
[21]	CHRISOCHOIDES N. Parallel mesh generation[M]// RUASET A M, TVEITO A. Numerical Solution of Partial Differential Equations on Parallel Computers. Cham: Springer, 2006: 237-264.
[22]	KLEIN R, LINGAS A. A linear-time randomized algorithm for the bounded Voronoi diagram of a simple polygon[C]// The 9th Annual Symposium on Computational Geometry. New York: ACM, 1993: 124-132.
[23]	SHEWCHUK J R. Triangle: engineering a 2D quality mesh generator and Delaunay triangulator[C]// Applied Computational Geometry. Towards Geometric Engineering. Cham: Springer, 1996: 203-222.
[24]	QI M, CAO T T, TAN T S. Computing 2D constrained Delaunay triangulation using the GPU[J]. IEEE Transactions on Visualization and Computer Graphics, 2013, 19(5): 736-748. DOI URL
[25]	COLL N, GUERRIERI M. Parallel constrained Delaunay triangulation on the GPU[J]. International Journal of Geographical Information Science, 2017, 31(7): 1467-1484. DOI URL
[26]	SCHÜTZ M, KERBL B, WIMMER M. Rendering point clouds with compute shaders and vertex order optimization[J]. Computer Graphics Forum, 2021, 40(4): 115-126.
[27]	VA H, CHOI M H, HONG M. Real-time cloth simulation using compute shader in Unity3D for AR/VR contents[J]. Applied Sciences, 2021, 11(17): 8255. DOI URL
[28]	JUNKER A, PALAMAS G. Real-time interactive snow simulation using compute shaders in digital environments[C]// The 15th International Conference on the Foundations of Digital Games. New York: ACM, 2020: 1-4.
[29]	陈国军, 李震烁, 陈昊祯. 基于计算着色器的并行Delaunay三角剖分算法[J]. 图学学报, 2025, 46(1): 159-169. DOI
	CHEN G J, LI Z S, CHEN H Z. Delaunay triangulation partitioning processing algorithm based on compute shaders[J]. Journal of Graphics, 2025, 46(1): 159-169 (in Chinese). DOI
[30]	CGAL. Computational geometry algorithms library[EB/OL]. [2025-09-14]. https://www.cgal.org/.