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

Combinatorial triangulations for surface unorganized points

作　　者：于舒春[1] 臧希喆[1] 赵杰[1] 蔡鹤皋[1] 

机构地区：[1]哈尔滨工业大学机器人研究所,哈尔滨150080

出　　处：《哈尔滨工业大学学报》2008年第11期1722-1725,共4页Journal of Harbin Institute of Technology

基　　金：国家高技术研究发展计划资助项目(2001AA422250);长江学者和创新团队发展计划资助项目

摘　　要：曲面散乱点集的三角剖分广泛应用于三维重建领域.为了更加快速、准确的完成曲面重建,提出了一种组合三角剖分法.此方法将整个剖分过程分为三个步骤:首先借鉴分治算法的思想将整个点集进行区域划分,以降低其拓扑结构的复杂性;之后在各个小区域内依据异侧准则、法向量夹角最大准则、域值距离准则和最小内角最大准则进行直接三角剖分;最后根据三维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.

关 键 词：散乱点集 三角剖分 三维重建 分治算法 

分 类 号：TP242[自动化与计算机技术—检测技术与自动化装置]