基于夹角约束的改进型BPA算法研究.doc

 基于夹角约束的改进型 BPA 算法研究# 5 10 15 20 25 30 35 摘要：本文研究了 BPA 算法基本思想，介绍了 BPA 算法的关键技术。在经典 BPA 算法三 角剖分的基础上进行了改进，对滚球过程中生成的新三角形进行约束，对 BPA 算法的半径 选择展开了进一步研究，针对实际的点云数据给出了较好的经验值，并通过改变ρ的大小实 现了简单有效的避免产生孔洞方法。 关键词：三角剖分；BPA 算法；夹角约束； 中图分类号：TP247+.5 Modified BPA arithmetic based on inclined angle restriction LU Qing, YANG Ankang, ZHU Hao, LIU Jingnan (School of Automation, Southeast University, Nanjing 210096) Abstract: In this paper, basic idea and key technology of BPA arithmetic is discussed. This paper improves the triangulation of the classic BPA arithmetic, restricts the new trangle which generaed during the procedure of ball rolling, develops further study on radius selection of BPA arithmetic, gives better emporocal value towards practical point cloud data and realizes simple and effective method to avoid pore generation through changingρvalue. Key words: triangulation; BPA arithmetic; inclined angle restriction 0 引言 剖分问题在上世纪中后期开始受到人们广泛的关注，并有了一系列关于三角剖分的研究 成果[1]。从剖分对象的类别来看，剖分问题大致可分为两种：一种是对给定区域进行三角剖 分，另一种是对给定点集进行剖分。从剖分的维度来划分的话，可以分为二维平面上的三角 剖分，三维空间的三角剖分以及更高维次的剖分。二维平面上的三角剖分算法相对成熟，各 种方法和解决成果已经可以很好的解决剖分问题。特别是以 1934 年由俄国数学家提出的 Delaunay 三角剖分[2]为代表，因为该三角剖分与贪婪算法不同，其实现过程必须满足自身的 约束条件，所以可得到很好的剖分结果。相较于二维平面下的三角剖分，三维空间中的三角 剖分方法发展相对缓慢。Choi[3]提出了直接形成三维空间散乱点集的拓扑关系的方法。之后 的 Marching Cube[4]法是应用最为广泛的方法之一。另一种被广泛使用的方法是 BPA 算法[5]。 这种方法因为操作简单，每个点的操作复杂度并不随着点云数量的增加而增加，并可控制圆 环的大小以协调剖分的时间和精度，因此有很高的实际应用价值。本文基于 BPA 算法讨论 三维点云三角剖分的策略。 1 BPA 算法介绍 1.1  BPA 算法基本思想 BPA 算法的英文全称为 Ball-pivoting algorithm，是 Bernardini 提出的一种新颖的三角剖 分的算法[5]。BPA 算法的主要思想为：如果一个被用户设定好的?? 值作为半径的圆，在碰 -1-  40 45  到三个点之前都没有碰到其它的点，那么这三个点就形成一个三角形。从一个种子三角形开 始，BPA 算法绕着一条边进行移动（如它以一个三角形的一条边为轴线，绕着此轴线进行 转动）直到它碰到另一个点，形成另外一个三角形。这个过程一直持续到所有的边都被作为 主轴转动过为止。然后在从另一个种子三角形开始，重复上述过程。直到没有未被当作轴线 的边为止。BPA 算法相较于其它算法，需要的内存空间相对较少，并且在时间上非常高效， 且重构的效果鲁棒性强。 1.2  BPA 三角剖分算法 假设 M 是三维物体的表面，S 是 M 的采样点集。假设现在 S 的采样密度足够大，可 以保证半径为?? 的球不能在不碰到采样点的情况下通过。将滚动过程中碰到的点连接入已 经建立联系的包络中，这就是 BPA 算法的基本原理。三维空间中，通过放置一个半径为?? 50 的球来连接三个采样点作为开始。保持这个球与三个点中的两个相连，并让该球绕着这两点 组成的这条边进行转动，直到球碰到另一个点。如图