三维物体表面三角划分的快速算法

A Fast Algorithm of Triangulation on 3D Surface

通过三角划分从三维空间点集重建三维表面的方法 ,在实际应用中涉及到的数据量常常很大 ,因此对算法的计算速度有较高的要求 .基于三维重建时物体截面轮廓线序列中的相邻轮廓线基本相似的事实 ,提出了一种物体截面轮廓线点集之间的三角划分的快速算法 .该算法首先寻找轮廓线的控制点 ,并对每两条相邻轮廓线的控制点进行配对 ,然后将这样两条轮廓线之间的三角划分 ,分配在多个小的曲线段对之间进行 ,并且由于事先进行了控制点匹配 ,因此 ,在每个小的区域中就能够进行简化快速的三角划分 .经理论分析和实验 ,该算法与常规的全局优化算法相比 ,在视觉效果上基本一致 ,可在计算时间上却要少得多 。

Triangulation from 3D points set is one of often using ways in which 3D surface is restored. But in practice, it needs to process a huge of data, so it is time consuming. Based on the fact in 3D restoration that most sequential section contours of an object are similar to adjacent ones, a quick method on triangulation between two section contours is proposed in this paper. First, the dominant points of every contour are located, then the dominant points of two contours are matched each other, so the area between two contours is segmented into multi smaller areas. And then triangulation is performed in each small area. Because of the pre matched dominant points, a simple and quick triangulation can be applied. In this paper, the strategy of triangulation we used is:keep the proportion of the numbers of the dots not used on two curves in accordance with that of whole numbers of the dots on the two curves. Analysis by theory and experiments show that the visual effect of this algorithm is almost the same in computing with common global optimizing methods, and it spends much less time. So the algorithm is effective.