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.