Delaunay triangulation partitioning processing algorithm based on compute shaders

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

Abstract

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

CLC Number:

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

Figures/Tables 14

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

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

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)

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

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

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)

Fig. 7 The original point that needs to be deleted

Fig. 8 Explanation diagram of judgment conditions

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)

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

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

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

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

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

References 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.