一个利用法矢的散乱点三角剖分算法

An Algorithm for Triangulating Unorganized Points with Normal

曲面上散乱点的三角剖分在曲面重建中发挥着重要作用.借助于曲面上的法矢信息和三维Delaunay三角剖分算法,该文给出了一种新的散乱点三角剖分算法.输入一组散乱点以及所在曲面S在这些散乱点处的一致定向的法矢信息,该算法将产生一张插值散乱点的三角网格曲面M,并且曲面M可以近似地看成是曲面S的三角剖分.算法的主要步骤分为两步:首先通过曲面S的一致定向的法矢信息,在曲面S的同一侧添加辅助点,利用这些辅助点来剔除Delaunay三角剖分中产生的不需要的三角片;然后将剩余的三角片连接成一张完整的网格曲面.与基于中轴的三角剖分算法相比,该文算法需要更少和更简单的计算.与局部三角剖分算法相比,该文算法可以更有效地避免重建后的曲面产生自交.该文的算法可用于任意拓扑的光滑曲面重建.

The triangulation of unorganized points on a surface plays a important role for surface reconstruction. This paper presents a novel triangulation algorithm based on the normal information of the surface and the Delaunay triangulation algorithm. Given a group of unorganized points and oriented normal sampled from a surface S , the authors output a triangular mesh M , which pass through the unorganized points and can be treat as the approximation to the triangulation of the surface S . There are two stages in the method. The first step is to use the oriented normal information to generate a group of auxiliary points on one side of the surface S , which is used to remove the triangles from the Delaunay triangulation. Then, the authors connect the remained triangles to form a triangular mesh. There is one primary advantage in the method versus the medial axis: approximating the medial axis is a difficult task whereas the method here requires no such computation. In contrast with the local triangulation algorithm, the algorithm in this paper is more powerful to avoid surface self intersection. This algorithm suit to deal with the smooth surface reconstruction with arbitrary topology. We describe an implementation of it and show example outputs.