《基于夹角约束的改进型 BPA 算法研究.doc》由会员分享，可在线阅读，更多相关《基于夹角约束的改进型 BPA 算法研究.doc（7页珍藏版）》请在三一文库上搜索。
1、精品论文基于夹角约束的改进型 BPA 算法研究鲁清，杨安康，朱昊，刘京南（东南大学自动化学院，南京 210096）5摘要：本文研究了 BPA 算法基本思想，介绍了 BPA 算法的关键技术。在经典 BPA 算法三 角剖分的基础上进行了改进，对滚球过程中生成的新三角形进行约束，对 BPA 算法的半径选择展开了进一步研究，针对实际的点云数据给出了较好的经验值，并通过改变的大小实 现了简单有效的避免产生孔洞方法。10关键词：三角剖分；BPA 算法；夹角约束；中图分类号：TP247+.5Modified BPA arithmetic based on inclined angle restriction
2、LU Qing, YANG Ankang, ZHU Hao, LIU Jingnan15(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
3、 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 effective20method to avoid pore generation through changingvalue.Key words: triangulation; BPA arithmetic; incli
4、ned angle restriction0引言剖分问题在上世纪中后期开始受到人们广泛的关注，并有了一系列关于三角剖分的研究25成果1。从剖分对象的类别来看，剖分问题大致可分为两种：一种是对给定区域进行三角剖 分，另一种是对给定点集进行剖分。从剖分的维度来划分的话，可以分为二维平面上的三角 剖分，三维空间的三角剖分以及更高维次的剖分。二维平面上的三角剖分算法相对成熟，各 种方法和解决成果已经可以很好的解决剖分问题。特别是以 1934 年由俄国数学家提出的 Delaunay 三角剖分2为代表，因为该三角剖分与贪婪算法不同，其实现过程必须满足自身的30约束条件，所以可得到很好的剖分结果。相较于二维
5、平面下的三角剖分，三维空间中的三角 剖分方法发展相对缓慢。Choi3提出了直接形成三维空间散乱点集的拓扑关系的方法。之后的 Marching Cube4法是应用最为广泛的方法之一。另一种被广泛使用的方法是 BPA 算法5。 这种方法因为操作简单，每个点的操作复杂度并不随着点云数量的增加而增加，并可控制圆环的大小以协调剖分的时间和精度，因此有很高的实际应用价值。本文基于 BPA 算法讨论35三维点云三角剖分的策略。1BPA 算法介绍1.1BPA 算法基本思想BPA 算法的英文全称为 Ball-pivoting algorithm，是 Bernardini 提出的一种新颖的三角剖 分的算法5。 B
6、PA 算法的主要思想为：如果一个被用户设定好的 r 值作为半径的圆，在碰基金项目：高等学校博士学科点专项科研基金（20090092110052）作者简介：鲁清(1987-) 男，硕士，主要研究方向：检测技术与自动化装置通信联系人：刘京南（1955-），男，教授，博导，主要研究方向：检测技术与自动化装置. E-mail: - 7 -40到三个点之前都没有碰到其它的点，那么这三个点就形成一个三角形。从一个种子三角形开始，BPA 算法绕着一条边进行移动（如它以一个三角形的一条边为轴线，绕着此轴线进行 转动）直到它碰到另一个点，形成另外一个三角形。这个过程一直持续到所有的边都被作为 主轴转动过为止。然
7、后在从另一个种子三角形开始，重复上述过程。直到没有未被当作轴线 的边为止。BPA 算法相较于其它算法，需要的内存空间相对较少，并且在时间上非常高效，45且重构的效果鲁棒性强。1.2BPA 三角剖分算法假设 M 是三维物体的表面，S 是 M 的采样点集。假设现在 S 的采样密度足够大，可以保证半径为 r 的球不能在不碰到采样点的情况下通过。将滚动过程中碰到的点连接入已 经建立联系的包络中，这就是 BPA 算法的基本原理。三维空间中，通过放置一个半径为 r50的球来连接三个采样点作为开始。保持这个球与三个点中的两个相连，并让该球绕着这两点 组成的这条边进行转动，直到球碰到另一个点。如图 1 中所示
8、，然后将这个新的点放入当前 的网格中，并继续沿着当前的网格进行重复的操作，直到所有的点都被触及到，即完成了三 角剖分过程。ylksijosskkckrs i s jmcijo xngts o55图 1 BPA 算法加入新点过程Fig.1 Process of adding new point to BPA arithmetic2基于夹角约束的 BPA 三角剖分算法2.1 夹角约束BPA 算法高效的核心思想在于它是“一次性完成的”：首先选取三个种子点组成种子60三角形，然后以其中的一条边为轴进行滚动。在滚动的过程中碰到的第一个点作为新的网格 中的点，将其与轴线相连接，以扩大其边界。这种贪婪算法的
9、思想是保证 BPA 算法时间复 杂度低的基础，即“碰到即连接”。但是这种时间复杂度的降低却存在一些不可避免的问题。如图 2 所示，假设 A、B、C、D、E 这五个空间中存在的点，从得到好的三角剖分的结 果来说，应该将 A 点加入网格中，形成网格。而 B、C、D、E 这四点形成的三角形均存在65问题。值得说明的是，在这里 D 和 E 属于不同问题的两个顶点。其中，E 点为与已经存在 的三角形基本属于同一个平面，但其夹角很小，在实际的剖分中应对其优化或者舍弃这一点； 而 D 点位于与已存在的三角形几乎垂直的平面上，与轴边所形成的角度也很小。在实际过 程中，因为采样偏差的原因，很可能存在像 E 这样
10、的点，同时也可能出现因为噪声和错误 采样，产生 D 点那样的噪声点。C 点与 E 点情况类似，同样可能由于采样的偏差所导致。70而 B 点的出现可能是因为此处采样点空缺，或曲面在此处曲率有较大的转折，或者 B 点属于物体的另一部分空间结构。ADECB图 2 BPA 算法滚动过程中存在的问题Fig.2 Problems in BPA arithmetic rolling process7580859095100因此，我们可以得出结论为：好的三角剖分应尽量将 A 点加入新的剖分网格中，而避免将 B、C、D、E 此类点加入已有的网格中。下面对这几种情况进行具体分析讨论。对于 B 点，BPA 算法可以
11、将其排除在网格之外，因为当 A 点存在的情况下，球在碰到 B 点之前会先碰到 A 点，所以 A 点有比 B 点更高的优先级。但是对于 C、D、E 三点，球在 一次滚动的过程中会在碰到 A 点之前先碰到他们，并把他们直接加入网格之中形成新的边 界。这样，所形成的网格会存在较多的条状三角形。这种畸形的三角形会导致后续实物加工 时走刀的复杂度增加，从而给逆向工程的实现带来困难。特别的，当 D 点存在时，一个原 本较为平坦的曲面会因为噪点 D 的存在而出现拓扑上较为复杂的曲面，这对后续的加工来 说更是一个难题。因此，应根据问题点所具有的共性，建立一个合理的判据，在一次滚球过程中建立新的 拓扑边时进行判
12、断，从而将存在问题的拓扑连接排除掉，得到更好更优的三角剖分结果。对 C、D 和 E 点的情况进行进一步分析可以发现，在这三种情况下，均存在一些共性， 如：由于存在一条较短边或较小角，导致三角形的面积均较小；此外，C、D、E 这三点到 轴线边的垂线段长度均较短；无一例外的，由 C、D、E 即新组成的三角形中至少又一个角 为接近 0 度的角。根据这些共性进行进一步分析可以得到以下结论。(1) 面积约束：虽然图 2 中所示的 C、D、E 三点与轴线构成三角形后的面积较小，但 不能否认存在面积较大的情况。例如当轴线段本身长度较长时，虽然高线较短，但面积却并 非特别小；此外，对面积的判定阈值较难选取，因
13、为点云数据的稀疏程度可能存在不一致的 地方，用单一判据很难进行全局范围内的好的约束。(2) 垂线段长度：利用点到线的距离进行判断虽然可以避免轴线段长度不同所带来的影 响，但对于点云密度分布不均匀的情况仍然不能得到一个很好的判定结果。此外，求取垂线 段的长度即意味着求取垂足，而垂足的求取将需要联立一个二元一次方程组进行求解。这在 计算上并非最优。(3) 夹角大小：相对于前面两个判别条件，夹角的大小鲁棒性更强。因为它不仅与轴线 段的长度无关，也与垂线段的长度没有关系，而只与三角形本身的形状有关系。而这种能够 直观反映三角形形状的变量正是能够反映较为规整的三角形的变量。此外，已知三角形的三 个顶点计
14、算夹角非常简单，只需利用余弦定理，进行五次乘法运算和两次加法运算即可得到。综上所述，我们将夹角判据作为判据，来对一次滚球过程中的新点的选取进行约束，以 期得到更好的三角剖分结果。具体做法为：设当前的半径为 r 的球位于三角形V0V1V2 上，其中V0V1 作为轴，球绕其转动。在滚动105110的过程中，具体实现为首先选取以V0V1 的中点为球心，以 2 r 为半径的球，为了方便计算，可以将此球以中心在球心，而边长为 2 r 的立方体代替。求取出此立方体内的子序列后，将 子序列中的点与中心进行连线，求取欧式距离。并按两个三角形的面间夹角大小进行点的排 序，设这里的点集为 p1 , p2 , p3
15、 L pn ，其中，夹角大小满足 pi p j , i j 。然后计算 pi 点与边V0V1 所形成的三角形的三个角的夹角。因为是在三维空间中，所以实际上 pi ，V0 和V1 这三个点的坐标均为三维向量。不妨记为：r pi = ( px , py , pz ) rV0 = (V0 x ,V0 y ,V0 z )(1) r计算向量之间的夹角余弦值：rr V1 = (V1x ,V1 y ,V1z ) cospi ,V0= ( px , py , pz ) (V0 x ,V0 y ,V0 z ) r r coscospi ,V1r rV0 ,V1= ( px , py , pz ) (V1x ,V
16、1 y ,V1z )= (V0 x ,V0 y ,V0 z ) (V1x ,V1 y ,V1z )(2)115120125130设定阈值q ，若三者余弦的绝对值有任何一个值大于阈值q ，则认为该三角形不满足约束条件，将 pi 点抛弃，继而进行下一个点的寻找，直到找到一个满足夹角约束的点，从而 结束一次滚球过程。通过这种方法，可以改善用 BPA 算法进行三角剖分中存在的问题，进一步改善所生成 的三角网格的质量。如图 3 所示。(a) BPA 算法三角剖分结果局部图(b) 加入夹角约束的三角剖分结果局部图(a) Topography of triangulation result(b) Topog
17、raphy of triangulation with inclined angle restriction图 3 有无夹角约束下的实验效果Fig.3 Testing effect with and without inclined angle restriction需要指出的是，这里的夹角约束能够改善三角网格非最优的情况，但并不能使得剖分的结果达到完全的最优。要具有 Delaunay 三角剖分所具有的最大化最小角最优性质，必须对 生成的整个三角网格进行全局 LOP 优化。而这将大大增加整个三角剖分的时间。在实际工 程中，这种优化并不总是利大于弊的，因此，此处仅是利用夹角的约束条件进行局部优化
18、改 善，并未进行全局优化。这种局部优化仅仅在生成新三角网格之前进行三次夹角判断，其复 杂度为 O(1) ，这种判断并未增加算法的总体时间复杂度。2.2 滚球半径Bernardini 在文献5中给出的滚球半径 r 的限制条件为足够大，以保证能够在采样点最 稀疏的情况下使得球可以同时碰触到三个顶点。但在实际情况中，存在着更加复杂的情况需135140145150155160要考虑。由于在 BPA 算法的实现过程中，需要计算点的子序列，即以某轴线段的中点为球心， 半径为 2 r 的球所包含的所有点，进行该步骤的计算是为了能够在以此线段为转动轴的下一 次转动中碰触到的点只有这些点。显而易见的，这些点必然
19、是在欧式空间上与该转轴非常邻 近的点。但是，得到子集后还需要进行判断，新加入的点能否与转轴形成满足条件的三角形， 同时要计算点与轴线所得到的三角形和原三角形所形成的面夹角，并对点集按照此夹角进行排序。并且为了计算下一次转动，还需要计算新的三角形所在的半径为 r 的球的球心，这 些均需要进行复杂的几何计算。特别是加入夹角约束后，还需要进行角度的判断。因此，当r 增大的时候，从均匀分布的三维空间点的层面上考虑，包入球的点集的个数将会呈 O(n3 ) 的速度增长，也使得算法执行的总时间上大大增加，如图 4 所示。虽然如此，在实际的操作 过程中，较大的滚球半径往往在总体的剖分时间上消耗更少。这是因为虽
20、然每个点需要计算 的子序列数增多了，但是由于点云数据是在三维平面下的，因此大的滚球半径意味着一次滚 动过程中，一个点的拓扑关系的建立会伴随着许多其它点的忽略。这些被忽略的点因为被包 含在了新建立的三角形里面，所以不再参与三角剖分的过程，因此从总体上看，大的滚球半 径意味着需要进行剖分的点云数据成倍数的减少，从而使得三角剖分的总时间下降。图 4 滚球半径对计算时间的影响Fig.4 Influence of radius of rolling ball to calculation time因为滚球半径设置过大，会使得以 MN 线段为轴线进行一次滚球的过程中首先碰到 P点，而并非位置处于更下方但距
21、离 MN 更近的 A、B、C、D 四点，所产生的影响即 P 点与 MN 线段组成新的三角形，且此三角形永久性存在。而 A、B、C、D 四点则因为处于已经 建立的三角形的内部而再无机会参与到三角剖分之中。这种大半径下的 BPA 算法是有利有 弊的。优点在于由于半径较大，使得总体三角剖分的时间大大降低，从而实时性上得到提高 和加强；而缺点在于由于半径的增大，使得 BPA 算法的颗粒度变大，丢失了一些重要的细 节信息，所重构出的曲面较为粗糙，不能反映实际物体的细节特征。如图 5 所示：(a) 大半径剖分效果图(b) 小半径剖分效果图(a) Effect drawing of smooth radiu
22、s subdivision(b) Effect drawing of minor radius subdivision图 5 不同滚球半径剖分效果对比Fig.5 Comparison between different rolling ball radius subdivisions图 5 中，（a）图为滚球半径较大时得到的剖分效果图，（b）图为滚球半径较小时得到的165170175180185190剖分效果图。从图中可以看出，在鼻子上，用大的滚球半径进行 BPA 操作与较小半径时得到的结果基本一致。此时大半径的滚球半径在平坦区域可以更加快速的得到剖分结果，且剖 分效果与小半径下剖分效果无差。
23、但在鼻子的边缘区域，由于滚球半径过大，从而导致在一 次的滚动过程中跳过了过多的点，而这些点恰好是鼻子边缘的细节部分，此时大半径的滚球 半径因为颗粒度太大从而导致剖分效果相比小半径下的效果要差，造成了细节信息的大量丢 失。因此，滚球半径 r 的选择非常重要。若半径过小，则光顺的表面会产生较多的小的孔 洞，若半径 r 过大，则会因为每次滚球时进行过多次的复杂计算而使得总体剖分时间增加。 通过比较讨论，我们认为在采样频率一致，得到的点云数据密度较一致时，选取点云间最短 距离的 1.5 至 2 倍作为滚球半径较为合适。但当点云密度不一致时，则应着重考虑密集点云 处，适当降低滚球半径。由于小半径所产生的
24、孔洞，可以在后面的进一步迭代中进行改善。 下面将对迭代下的情况进行进一步的讨论说明。2.3 滚球迭代BPA 算法的初衷是进行三角剖分。在时间复杂度较低的情况下，放弃最优化，得到一个较好的三角剖分结果。但是由于半径 r 的限制，加上实际采样的过程中不可避免的会产 生一些点云的错误与丢失，因此在滚球的过程中会不可避免的产生一些较小的孔洞。这些孔 洞的产生原因多是由于局部点云数据的分布所引起的。特别是在细节较多，点云密度不一致的三维数据集中，单一的半径 r 在剖分上会有局 限，产生孔洞不可避免。如图 6 中(a)所示为实际 lady 头像在半径 r 较小时的剖分结果，可 以看到，由于鼻孔处缺少点云数
25、据，因此在滚球过程中不可避免的产生孔洞。(b)图为在(a)图的基础上将滚球半径 r 增大一倍后，进行二次迭代的剖分效果图。可以看到，通过增大半径，可以明显的减少孔洞的产生。(a) 小半径下剖分效果(b) 大半径下剖分效果(a) Subdivision effect with minor radius(b) Subdivision effect with smooth radius图 6 增大 BPA 半径迭代前后效果示意图Fig.6 Comparison between before and after increase BPA radius iteration195值得提出的是，第二次增大滚
26、球半径并不意味着剖分上的重复操作和时间上的成倍增加。因为在第一次滚球过程中对每条边均设置了状态：活跃边、边界边、冻结边。在第一次 BPA计算的过程中，活跃态的边通过滚球不断进行被改变为冻结态，当算法计算结束时， 只有实际的处于点云集合边缘的边和构成孔洞的边仍然处于边界态，其它所有边均处于冻结 态。由于第二次增大滚球半径后的计算是在第一次 BPA 的基础上进行的，所以对第二次时 的计算可直接从边界态的边开始进行，因此在计算时间上不会成倍数关系。此外，两次迭代间的半径变化不易过大。因为虽然在较小半径值下剖分得到的三角形仍200然存在，但很有可能当大幅增大滚球半径后，原来的边界边会在滚动过程中碰到过
27、远的点。从而产生二义性的三角拓扑结构。如图 7 所示。其中，(a)图为较小半径下进行 BPA 算法的 局部示意图，此时，得到由加粗边界而围成的孔洞。在进行迭代操作时，若滚球半径过大， 则会在建立了 AB 边后，进行下一次滚动时首先碰到 C 点。此时，将建立以点 A、B、C 为 顶点的三角形，并将此结果纳入剖分结果中，这将导致二义性的产生，如图(b)所示。因此， 实际情况下半径的增大应根据点云数据一次剖分后孔洞的尺寸大小来进行确定。CB A2052103结论(a) 小半径产生的空洞(b)使用大半径 BPA 时产生二义性(a) Pore generated with small radius(b)
28、 Ambiguity generated by using large radius BPA图 7 剖分二义性Fig.7 Subdivision ambiguity215220225本文介绍了三维点云三角剖分算法中的 BPA 算法。在此基础上对算法进行了改进，增 加了夹角判据，对滚球过程中新点的选择进行约束，以避免大量“长条”（slide）的产生； 研究了滚球半径的选择策略，给出了实用的 r 的经验值；对采样密度不均匀的点云数据用 BPA 算法处理时遇到的问题进行了讨论；在研究 r 的取值后对迭代过程进行了说明。通过 上述改进使得生成的三角形会向优化过的 Delaunay 三角形靠拢，能够更好
29、的表现出三维物 体的实际形态，而且可以简单有效的避免产生孔洞。参考文献 (References)1 周晓云，朱心雄, 散乱数据点三角剖分方法综述J. 工程图学学报， 1993，14（1）：48-54.2 Fang T, L Piegl. Algorithm for Delaunay triangulation and convex-hull computation using a sparse matrixJ. Computer-Aided Design, 1992, 24(8): 425-436.3 ChoiB. Triangulation of scattered date in 3D s
30、paceJ. Computer-Aided Design, 1988, 20(5): 239-248.4 Lorensen W E, Cline H E. Marching cubes: A high resolution 3D surface construction algorithmJ. ComputerGraphics, 1987, 21(4): 163-169.5 Bernardini F. The ball-pivoting algorithm for surface reconstructionJ. IEEE Transactions on Visualization and Computer Graphics, 1999, 5(4): 349-359.