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

作     者：陈国军 李震烁 陈昊祯 

作者机构：中国石油大学(华东)青岛软件学院计算机科学与技术学院 

出 版 物：《图学学报》 (Journal of Graphics)

年 卷 期：2024年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 081104[工学-模式识别与智能系统] 080203[工学-机械设计及理论] 0802[工学-机械工程] 0835[工学-软件工程] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Delaunay三角剖分 计算着色器 GPU 并行计算 Voronoi图 

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