面向GPU的Delaunay三角剖分网格细化算法研究

The development of science and technology has stimulated the booming of the digital data industry such as digital earth, digital oceans, and digital medical care, and the number of the spatial data acquired by people grows geometrically. How to generate quality Delaunay mesh for massive data is a significant problem for spatial analysis and visualization field. Delaunay refinement algorithm can be used to generate triangular meshes which satisfy guaranteed bounds on angles, edge lengths, the number of triangles, and the grading of triangles from small to large size. Recently the graphic processing unit (GPU) with its enormous parallel computing power has been used widely in many disciplines for general purpose computation. However, there is no existing GPU algorithm for Delaunay refinement problem. In this project, we will focus on three aspects： (1)We will propose a new Delaunay refinement algorithm based on GPU to generate high quality triangular meshes for input data. (2)Since GPU uses a massively parallel architecture with hundreds to thousands of processing elements to execute thousands to millions of threads simultaneously, common issues in parallel programming such as cooperation among threads, memory management, conflicting data access, racing conditions, and synchronizations become more serious problems. Our research will focus on all the problems mentioned above. (3)We will build a 2D GPU mesh generator/library by integrating the algorithms and implementations proposed in this project and with other existing work accomplished by us before. This generator should be numerically robust and run up to two orders of magnitude faster than the fastest sequential algorithm and can be used for many applications. The accomplishment of this project will provide new insights into the research for computing geometry problems based on the GPU.

科技的发展带动了数字地球、海洋和医疗等大数据产业的蓬勃发展，使人们获取的空间数据呈几何级数增长，如何实现海量数据的高质量的Delaunay三角网格的高速构建，是当前空间数据分析及可视化等领域亟需解决的重要问题之一。为了高速处理海量数据，面向GPU的计算几何算法的研究已经展开，但在网格生成方面，仍缺少比较成熟的算法与实现。针对上述问题，本项目从GPU体系结构特点出发，重点研究以下内容：(1)设计高效的Delaunay三角网格细化算法，以生成高质量的网格；(2)研究GPU算法在并行优化中的诸多关键技术，如内存管理、并行粒度控制和线程间竞争关系处理等，以充分发挥GPU优势，提高算法运行速度；(3)建立面向GPU的三角网格生成库，该库具有极高的稳定性和可移植性，生成的各种网格可应用于数值计算、图形学等领域进行科学计算。本项目的完成将为研究计算几何其它相关问题的GPU算法提供新的思路和实践经验。

本项目研究面向GPU的三角剖分网格生成算法，以实现海量数据的高质量的三角网格的高速构建。项目研究着眼于利用GPU生成网格的两个核心问题，其一是寻求并行插入大量增量点的方式方法，其二是合理优化GPU代码以发挥GPU优势，提高算法运行速度。在研究过程中，努力探索如何将传统的串行及并行的计算几何核心算法部署在GPU上，利用GPU高度并行的多线程和强大计算能力进行高效的计算。并在此基础上，研究GPU算法在并行优化中的诸多关键技术，如内存管理、并行粒度控制和线程间竞争关系处理等。项目研究成果主要表现在如下几方面：1. 提出了一种Delaunay三角剖分网格的细化算法。在处理增量点问题时采取了并行插入后续统一删除冗余点的方法。将不同通途的操作归一化为统一的边翻转操作使大量线程的工作变得相同且独立，以大大提升并行计算的效率。此外,我们定义了增量点的正交关系以减少并行插入增量点时的依赖关系，进一步加快计算时间。实验结果表明，我们的算法运行速度比知名的Triangle软件快几十倍。2. 提出了若干利用GPU这种特殊架构的计算设备进行几何计算的设计原则和技术。总的设计原则是尽量使用类型统一且相互无依赖的数据集合，以及采用尽可能少的分支跳转与循环。结合本项目解决的关键科学问题，我们提出了与硬件结构相匹配的几何数据结构、内存管理方法、粗细粒度并重的并行粒度动态调整方法、多线程间的竞争与同步的方法，并设计和实现了几个计算几何中常用的predicates操作。3. 建立了一个面向GPU的三角网格生成库，该库具有极高的稳定性和可移植性，生成的各种网格可应用于数值计算、图形学等领域进行科学计算。综上所述，本项目的完成将为研究计算几何其它相关问题的GPU算法提供新的思路和实践经验。本项目按照原定研究计划及目标完成了相关研究内容，共发表学术论文9篇，其中SCI期刊5篇、EI期刊1篇，授权发明专利1项，授权软件著作权2项。