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

Delaunay triangulation partitioning processing algorithm based on compute shaders

作　　者：陈国军[1] 李震烁 陈昊祯 CHEN Guojun;LI Zhenshuo;CHEN Haozhen(Qingdao Institute of Software,College of Computer Science and Technology,China University of Petroleum(East China),Qingdao 266580,China)

机构地区：[1]中国石油大学(华东)青岛软件学院、计算机科学与技术学院,山东青岛266580

出　　处：《图学学报》2025年第1期159-169,共11页Journal of Graphics

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

关 键 词：DELAUNAY三角剖分 计算着色器 GPU 并行计算 VORONOI图 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术] TP18[自动化与计算机技术—计算机科学与技术]