Abstract: 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.

Key words: incremental, inserting, Delaunay triangulation

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

关键词: 增量, 插入法, 三角剖分