面向并行的动态增量式Delaunay三角剖分算法*

摘要：

三角剖分是计算机图形学中的重要话题.并行三角剖分算法的发展对传统三角剖分算法提出了新需求,其中之一即是给定一个点数不断增大的点集,实现对该点集三角剖分的快速增量更新.虽然现今已有一些增量三角剖分算法,但都无法支持新增点落入原有三角剖分之外的情况.为解决此问题,提出了三角剖分的外扩技术,基于插入法设计了增量三角剖分算法TID.该算法能够支持任意次、任意数量、任意位置点的增量添加.TID算法能够对任意分布的点集均给出唯一三角剖分结果.对TID算法的性能评估表明,TID算法比现有算法具有更高的计算效率,且增量功能引入的额外开销较小.此外,该算法已成功作为局地三角剖分算法用于并行三角剖分算法中.

关键词：增量、插入法、三角剖分

所属期刊栏目：14

分类号：TP391.41(计算技术、计算机技术)

资助基金：The National Key Research and Development Program of China under Grant Nos. 2016YFA0602203, 2017YFC1501903 国家重点研发计划

在线出版日期：2020-01-18（万方平台首次上网日期，不代表论文的发表时间）

页数：共9页

页码：140-148