曲面散乱点集的组合三角剖分法

Combinatorial triangulations for surface unorganized points

曲面散乱点集的三角剖分广泛应用于三维重建领域.为了更加快速、准确的完成曲面重建,提出了一种组合三角剖分法.此方法将整个剖分过程分为三个步骤:首先借鉴分治算法的思想将整个点集进行区域划分,以降低其拓扑结构的复杂性;之后在各个小区域内依据异侧准则、法向量夹角最大准则、域值距离准则和最小内角最大准则进行直接三角剖分;最后根据三维Delaunay空球准则进行各区域边界的连接,从而完成剖分.实验结果表明,组合法可以准确、快速的实现曲面散乱点集的三角剖分.

Triangulations for surface unorganized points have been applied to 3-D reconstruction widely. In order to reconstruct surface precisely and fast, a combinatorial triangulations method is proposed in this paper. The process was divided into 3 steps： firstly, all unorganized points were carved up into many small regions by partition algorithms and the topological structure of the whole points set was predigested by this step ; secondly, direct triangulations were carried out in these small regions according to the different side rule, the angle of two normal vectors maximized rule, the threshold distance rule and the internal minimal angle maximized rule; finally, different regions were connected by the 3-D Delaunay eircumsphere rule. Experimental results show that surface unorganized points can be triangulated by combinatorial triangulations precisely and fast.