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

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

摘要/Abstract

摘要：

Delaunay三角剖分是一种经典的计算几何算法，在众多领域中有着广泛地使用，随着实际需求的不断提高，现有的Delaunay三角剖分算法已不能满足大规模数据的需求，为此，提出了一种基于计算着色器的并行Delaunay三角剖分方法，该方法通过纹理缓存将点集数据输入到计算着色器中，并利用计算着色器加速Delaunay三角剖分，同时在现有方法的基础上提出动态插入法解决点集在离散空间中的重映射问题。此外，为了能够让显存有限的GPU构建出远超其显存限制的Delaunay三角网，提出基于计算着色器的分区双向扫描算法，并将点集划分为多个子区域，然后通过扫描各个子区域的方式进行构网。实验结果表明：在相同运行环境下，基于计算着色器的方法与现有的方法相比缩短了构网时间。同时分区双向扫描算法很好地解决了GPU的显存瓶颈问题，能让显存有限的GPU构建出远超其显存容量的Delaunay三角网。

关键词: Delaunay三角剖分, 计算着色器, GPU, 并行计算, Voronoi图

Abstract:

Delaunay triangulation is a classic computational geometry algorithm, which is widely used in many fields. With the increasing demand for practical applications, the existing Delaunay triangulation algorithm have proven inadequate for large-scale data. Therefore, a parallel Delaunay triangulation method based on compute shaders was proposed. This method input point set data into the compute shader through a texture buffer and utilized the compute shader to execute the Delaunay triangulation algorithm. At the same time, a dynamic insertion method was proposed based on the existing method to address the remapping problem of point sets in discrete space. In addition, to enable GPUs with limited video memory to construct Delaunay triangulations that significantly exceeded their video memory limitations, a partitioned bidirectional scanning algorithm based on compute shaders was proposed. This method divided the point set into multiple sub-regions, and then constructed the network by scanning each sub-region. Experimental results indicated that under the same operating environment, the method based on compute shaders shortened the network construction time compared with the existing methods. Moreover, the partitioned bidirectional scanning algorithm effectively solved the GPU memory bottleneck problem, allowing GPUs with limited video memory to construct Delaunay triangulations that far exceeded their video memory capacity.

Key words: Delaunay triangulation, compute shader, GPU, parallel computing, Voronoi diagram

中图分类号:

陈国军, 李震烁, 陈昊祯. 基于计算着色器的并行Delaunay三角剖分算法[J]. 图学学报, 2025, 46(1): 159-169.

CHEN Guojun, LI Zhenshuo, CHEN Haozhen. Delaunay triangulation partitioning processing algorithm based on compute shaders[J]. Journal of Graphics, 2025, 46(1): 159-169.

图/表 14

图1 构网各步骤示意图((a)点集数据；(b)点集的Voronoi图；(c)点集的Delaunay三角剖分)

Fig. 1 Each step of triangulation ((a) Datasets; (b) Voronoi diagram of datasets; (c) Delaunay triangulation of datasets)

图2 重映射导致的构网缺失((a)错误的三角网；(b)正确的三角网)

Fig. 2 Missing triangulation caused by remapping ((a) Error triangulation; (b) Correct triangulation)

图3 动态插入法各步骤示意图((a)确定缺失点的位置；(b)为缺失的数据点添加额外的离散行与离散列；(c)构建三角剖分)

Fig. 3 Each steps of dynamic insertion ((a) Determine the location of missing points; (b) Add additional discrete rows and columns for missing data points; (c) Construct triangulation)

图4 未对边界处理所造成的三角网缺失((a)分区间存在间隙的三角剖分；(b)正确的Delaunay三角剖分)

Fig. 4 Missing triangulation caused by no boundary treatment ((a) Triangulation with gaps between partitions; (b) Correct Delaunay triangulation)

图5 子区域在接收到来自邻近区域边界处的种子点信息后能正确地连接在一起

Fig. 5 Sub regions can be correctly connected together after receiving seed point information from neighboring region boundaries

图6 构建子区域一维Voronoi图各步骤示意图((a)初始状态；(b)完成2次扫描后的状态；(c)点集的一维Voronoi图)

Fig. 6 Schematic diagram of the steps to construct the one-dimensional Voronoi diagram of each sub-region ((a) Datasets; (b) After completing two scans; (c) 1D-Voronoi of datasets)

图7 需要删除的原始点信息

Fig. 7 The original point that needs to be deleted

图8 判断条件说明图

Fig. 8 Explanation diagram of judgment conditions

图9 由子区域Voronoi图转化为Delaunay三角剖分示意图((a)子区域组合而成的完整Voronoi图；(b)由各个子区域的Delaunay三角剖分组合的完整Delaunay三角剖分)

Fig. 9 Transformation from sub-region Voronoi diagram to Delaunay triangulation ((a) A complete Voronoi diagram composed of sub regions; (b) The complete Delaunay triangulation composed of Delaunay triangulations from each subregion)

表1 不同方法所用时间对比/ms

Table 1 Performance of different methods/ms

点集数量/ 10^x	增量插入法	CGAL	CUDA	计算着色器
1	0.3	0.044	15	8
2	3	0.149	19	11
3	139	0.920	23	17
4	11213	10.000	45	25
5	1778960	140.000	54	33
6	>1 day	1557.000	229	108
7	>1 day	22857.000	1101	501

表2 CUDA和计算着色器各阶段用时对比/ms

Table 2 Comparison of CUDA and compute shader/ms

点数/ 10^x	CUDA			计算着色器
点数/ 10^x	导入时间	计算时间	导出时间	导入时间	计算时间	导出时间
4	20.80	3.40	21.90	6.50	6.65	12.50
5	25.50	3.80	27.40	6.80	7.13	20.20
6	102.30	10.60	126.90	38.50	8.67	64.90
7	425.80	35.10	688.90	196.20	10.70	295.04

表3 动态插入法与现有方法用时对比/ms

Table 3 Comparison between dynamic insertion and existing methods/ms

重映射点数量	现有方法	动态插入法
100	255.3	38.2
300	825.6	43.8
500	1148.7	49.2
700	1595.2	56.5
900	2055.8	63.6

表4 点集数量变化对构网时间的影响/ms

Table 4 The effect of the change in the number of datasets/ms

点集数量/ 10^x	一维 Voronoi 生成	二维 Voronoi 生成	构建三角网	修补三角网	耗时总和
2	0.572	1.66	1.84	1.93	5.99
3	0.714	1.68	1.85	2.08	6.32
4	0.719	1.91	2.12	2.01	6.76
5	0.897	2.44	2.32	2.26	7.91
6	0.992	3.22	2.65	2.71	9.58
7	1.020	4.34	5.82	3.56	14.70

表5 分区数量变化对构网时间的影响/ms

Table 5 The effect of the change in the number of partitions/ms

构网各阶段	分区数
构网各阶段	4	16	64	256
横向扫描子区域	8.48	11.29	34.07	131.82
构建一维Voronoi图	1.81	6.10	28.30	102.07
纵向扫描子区域	6.34	12.88	49.90	179.48
构建二维Voronoi图	8.08	25.82	135.40	448.63
构建三角网	542.13	716.95	922.73	1130.42
修补三角网	142.65	140.16	143.45	142.32
耗时总和	709.49	913.20	1313.80	2134.74

参考文献 25

[1]	袁清洌, 吴学群. 结合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).
[2]	MULCHRONE K F. Application of Delaunay triangulation to the nearest neighbour method of strain analysis[J]. Journal of Structural Geology, 2003, 25(5): 689-702.
[3]	童立靖, 李嘉伟. 一种基于改进PointNet++网络的三维手姿估计方法[J]. 图学学报, 2022, 43(5): 892-900.
	TONG L J, LI J W. A 3D hand pose estimation method based on improved PointNet++[J]. Journal of Graphics, 2022, 43(5): 892-900 (in Chinese).
[4]	KANG D S, KIM Y J, SHIN B S. Efficient large-scale terrain rendering method for real-world game simulation[C]// The 1st International Conference on E-Learning and Games. Cham: Springer, 2006: 597-605.
[5]	MAVRIPLIS D J. Adaptive mesh generation for viscous flows using triangulation[J]. Journal of Computational Physics, 1990, 90(2): 271-291.
[6]	NANDURI J R, PINO-ROMAINVILLE F A, CELIK I. CFD mesh generation for biological flows: geometry reconstruction using diagnostic images[J]. Computers & Fluids, 2009, 38(5): 1026-1032.
[7]	DE FLORIANI L, FALCIDIENO B, PIENOVI C. Delaunay-based representation of surfaces defined over arbitrarily shaped domains[J]. Computer Vision, Graphics, and Image Processing, 1985, 32(1): 127-140.
[8]	BOWYER A. Computing Dirichlet tessellations[J]. The Computer Journal, 1981, 24(2): 162-166.
[9]	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.
[10]	ZHOU S, JONES C B. HCPO: an efficient insertion order for incremental delaunay triangulation[J]. Information Processing Letters, 2005, 93(1): 37-42.
[11]	FORTUNE S. A sweepline algorithm for Voronoi diagrams[C]// The 2nd Annual Symposium on Computational Geometry. New York: ACM, 1986: 313-322.
[12]	ŽALIK B. An efficient sweep-line Delaunay triangulation algorithm[J]. Computer-Aided Design, 2005, 37(10): 1027-1038.
[13]	BINIAZ A, DASTGHAIBYFARD G. A faster circle-sweep Delaunay triangulation algorithm[J]. Advances in Engineering Software, 2012, 43(1): 1-13.
[14]	LEE D T, SCHACHTER B J. Two algorithms for constructing a Delaunay triangulation[J]. International Journal of Computer & Information Sciences, 1980, 9(3): 219-242.
[15]	SONG Y, LI M, LIU X. A paralleled Delaunay triangulation algorithm for processing large LIDAR points[J]. ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences, 2022, 10: 141-146.
[16]	NGUYEN C, RHODES P J. TIPP: parallel Delaunay triangulation for large-scale datasets[C]// The 30th International Conference on Scientific and Statistical Database Management. New York: ACM, 2018: 8.
[17]	NAVARRO C, HITSCHFELD-KAHLER N, SCHEIHING E. A parallel GPU-based algorithm for Delaunay edge-flips[EB/OL]. [2024-03-28]. https://scholar.google.com/scholar?hl=zh-CN&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.
[18]	HOFF III K E, KEYSER J, LIN M, et al. Fast computation of generalized Voronoi diagrams using graphics hardware[C]// The 26th Annual Conference on Computer Graphics and Interactive Techniques. New York: ACM, 1999: 277-286.
[19]	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.
[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]	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.
[22]	MOWER J E. Real-time drainage basin modeling using concurrent compute shaders[EB/OL]. [2024-03-28]. https://www.albany.edu/-Jmower/Publications/MowerAC2016_PaperSub.pdf.
[23]	MIHAI C C, LUPU C. Using graphics processing units and compute shaders in real time multimodel adaptive robust control[J]. Electronics, 2021, 10(20): 2462.
[24]	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.
[25]	QI M, CAO T T, TAN T S. Computing 2D constrained Delaunay triangulation using the GPU[C]// ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games. New York: ACM, 2012: 39-46.