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

An Algorithm for Triangulating Unorganized Points with Normal

作　　者：董辰世[1] 汪国昭[1] 

机构地区：[1]浙江大学数学系,杭州310027

出　　处：《计算机学报》2005年第6期1000-1005,共6页Chinese Journal of Computers

基　　金：国家自然科学基金(60473130);国家"九七三"重点基础研究发展规划项目基金(2004CB318000)资助.

摘　　要：曲面上散乱点的三角剖分在曲面重建中发挥着重要作用.借助于曲面上的法矢信息和三维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.

关 键 词：曲面重建 散乱点 法矢 DELAUNAY三角剖分 三角网格曲面 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]