期刊文献+

面向并行的动态增量式Delaunay三角剖分算法 被引量:6

Parallelism-Oriented Dynamic Incremental Delaunay Triangulation Algorithm
下载PDF
导出
摘要 三角剖分是计算机图形学中的重要话题。并行三角剖分算法的发展对传统三角剖分算法提出了新需求,其中之一即是给定一个点数不断增大的点集,实现对该点集三角剖分的快速增量更新。虽然现今已有一些增量三角剖分算法,但都无法支持新增点落入原有三角剖分之外的情况。为解决此问题,提出了三角剖分的外扩技术,基于插入法设计了增量三角剖分算法TID。该算法能够支持任意次、任意数量、任意位置点的增量添加。TID算法能够对任意分布的点集均给出唯一三角剖分结果。对TID算法的性能评估表明,TID算法比现有算法具有更高的计算效率,且增量功能引入的额外开销较小。此外,该算法已成功作为局地三角剖分算法用于并行三角剖分算法中。 Delaunay triangulation is a main topic in computer graphics. Various types of new requirements have appeared during the development of parallel triangulation algorithms, e.g., updating the triangulation incrementally given a set of increasing points. Existing incremental triangulation algorithms do not support for inserting points outside of the triangulation. This paper proposes the expansion of triangulation and designs an incremental triangulation algorithm TID(truly incremental Delaunay) supporting for inserting any number of points with any distribution into an existing triangulation for any time. TID is designed to produce a unique triangulation result for any distribution of points. Experimental evaluation results on TID show that TID has higher computational efficiency than existing algorithms and introduces low computational overhead. In addition, TID has already been used in parallel triangulation algorithm as local triangulation algorithm.
作者 杨昊禹 刘利 张诚 于灏 YANG Haoyu;LIU Li;ZHANG Cheng;YU Hao(Ministry of Education Key Laboratory for Earth System Modeling,Department of Earth System Science,Tsinghua University,Beijing 100084,China)
出处 《计算机科学与探索》 CSCD 北大核心 2020年第1期140-148,共9页 Journal of Frontiers of Computer Science and Technology
基金 国家重点研发计划Nos.2016YFA0602203,2017YFC1501903~~
关键词 增量 插入法 三角剖分 incremental inserting Delaunay triangulation
  • 相关文献

参考文献1

二级参考文献23

共引文献59

同被引文献63

引证文献6

二级引证文献13

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部