随着三维建模技术的快速发展，基于散乱点云的曲面重建技术在逆向工程、文物保护、工业制造、计算机辅助设计与制造、虚拟现实和科学计算可视化等领域得到了广泛应用^[1-2]。目前，曲面重建方法主要分为3类^[3]：基于Delaunay三角化的曲面重建^[4-7]、隐式曲面重建^[8-10]和区域生长法曲面重建^[11-17]。其中，区域生长法曲面重建以一个种子三角形为初始网格，根据一定的拓扑准则获取第三点以延伸三角形网格，直至遍历所有点，得到重建表面。该方法具有思路简单、时间复杂度低、能够处理较大规模点云等优点。常用算法有滚球算法(ball pivoting algorithm, BPA)^[11-13]、内在属性驱动算法(intrinsic property driven, IPD) ^[14-15]、包围球算法^[16]、流行网格生长算法^[17]等。

BPA算法^[11]自1999年诞生以来，因其易实现、过程较直观等优点而备受国内外学者关注。但该算法要求：(1)点云附有准确、一致性的法向信息，(2)点云足够均匀。对于要求(1)，现有较为成熟的点云法向估计及一致性调整算法，例如文献[18-20]提出的算法可以准确计算出一致性的点云法向信息，能满足BPA算法的要求。对于要求(2)，一种解决方式是在获取点云数据时，要求其必须足够均匀，但这显然不是一种有效的方式；另一种解决方式是拓展原算法的适用性，使其能更好地重建非均匀点云。针对第二种解决方式，国内外众多学者作了大量研究。文献[21]提出了一种分级限制滚球算法，通过估计最小半径、迭代三角化等过程，可以自适应生成与α-shape算法同等效果的三角形网格，但其只适用于二维点云，不能处理三维点云。文献[22]针对BPA算法重建非均匀点云易产生孔洞的问题，将BPA算法和径向基函数算法相结合，先采用径向基函数在孔洞区域增加新点，然后应用BPA算法重建，虽能修补部分孔洞，但大大增加了时间消耗和内存开销。文献[1, 23]采用可变滚球半径改进BPA算法，能够处理一定程度的非均匀点云，但可变滚球半径需要在重建之前手动设置，不具有自适应性。文献[24]提出了一种结合Delaunay和BPA的网格重建优化算法，当因点云间距大于滚球直径接触不到第三点时，应用Delaunay算法实现滚球在三维空间的旋转以及半径的递增，从另一个方向滚动以选取第三点，但在点云间距大于滚球直径的区域要进行局部Delaunay剖分，计算更加耗时，并且半径初值需要人工选取。文献[25]通过由小到大输入多个滚球半径来改进BPA算法，但滚球半径的选取没有任何先验信息，需要人工多次尝试，才有可能选择出较优的组合，虽然该算法重建效果较好，但人工选取滚球半径无效率可言。

针对BPA算法及其改进算法在处理非均匀点云时不具有自适应性、不能很好地重建其模型且效率低下等问题，本文定义了一种点云内在属性因子(intrinsic property factor of point cloud, IPFPC)，并分析其性质，结合拓展边长等信息自适应确定滚球半径，提出了一种自适应滚球算法(self-adaptive ball pivoting algorithm，SaBPA)，以克服原始BPA算法不擅长处理非均匀点云的缺点。

1 BPA算法及其缺陷

BPA算法是一种经典的曲面重建算法。该算法从一个种子三角形开始，用户先定义一个半径为r的滚球；然后，将滚球沿着种子三角形的某条边滚动(沿着边滚动时始终保持与该边的两个端点接触)，直到接触到下一个点时停止滚动；最后，通过判断该滚球内是否包含其他点来确定是否将该边与该点构成新的三角形。不断循环上述过程，直到将所有点都包含在三角形网格中，完成重建工作。由于其需要用户预先定义滚球半径r，所以处理不均匀点云非其所长。

BPA算法的曲面重建过程包含三角形选取和三角形网格拓展两步。

1) 种子三角形选取。种子三角形用于三角形网格初始化。一个良好的种子三角形需要满足3个条件：（1）该三角形位于点云表面；（2）构成三角形的3个顶点尽量避开可能存在粗差和异常值的点；（3）种子三角形要尽量接近等边三角形。算法具体步骤为：

（1）随机选取一个没有被用于曲面重建的点p。

（2）从点p的邻域中选取两个点p_a、p_b。

（3）构造一个原始三角形△pp_ap_b。

（4）对△pp_ap_b进行相容性检测，满足则继续下一步，否则返回步骤（1）。

（5）当滚球球心位于三角面外侧、球面与3个顶点接触时，判断滚球内是否含有其他点：若没有，则将该三角形作为种子三角形输出；若有，则返回步骤（1）。

2) 三角形网格拓展。该步骤主要是为拓展边获取第三点，构造候选三角形，然后对候选三角形进行相容性检测，并给出相应的处理方法。算法具体步骤为：

（1）检测边的可拓展性，将不可拓展的边标记为内边。

（2）基于给定的滚球半径r确定候选点。

（3）从候选点中选取较优点作为拓展边的第三点，构造三角形，得到候选三角形。

（4）对候选三角形进行相容性检测，若满足条件，则参与构网，否则删除该候选三角形。

（5）不断重复步骤（1）~（4），直到所有边都不可拓展为止，然后修补三角形网格中的孔洞，输出三角形网格。

在原始BPA算法中，滚球半径r是用户在重建之前定义的，具有全局不变性。如果点云不均匀，则在采样点间距大于2r的区域会产生孔洞，二维空间情形如图 1所示。

从图 1(a)可知，当点云数据均匀时，应用BPA算法可以很好地重建出点云表面模型；但当点云数据不均匀时（见图 1(b)），难以确定一个合适的滚球半径来重建出高质量的三维模型。需要对BPA算法中滚球半径的自适应取值问题进行研究，使其具备重建非均匀点云数据的能力。

2 改进的BPA算法

针对BPA算法不适用于重建非均匀点云的缺点，根据拓展边长以及IPFPC，本文设计了一种自适应确定滚球半径的方法，以增强BPA算法的实用价值。

2.1 IPFPC定义

IPFPC是一个无量纲的比值，如图 2所示，定义为拓展边两个顶点参与构网的网格中所有网格边长与拓展边长之间的比值，记为μ_i(如图 2所示i=1, 2…5)，计算公式为：

$\mu = L'/L $

(1)

式中，L'、L分别为网格边长和拓展边长。

由图 2和IPFPC的定义可知，根据每条拓展边IPFPC的均值μ以及该拓展边长L，可概略地知道该拓展边周围的潜在网格边长L' ≈ k · μ · L(k为大于零的常数)，故可根据三角形外接球半径与3条边长之间的关系实现滚球半径的自适应选取。

2.2 SaBPA算法

SaBPA算法主要是对原始BPA算法中滚球半径的选取方法进行改进，其余重建步骤和原始BPA算法相近，滚球半径是根据拓展边长和IPFPC确定的，具有自适应性。

三角形外接球半径与3条边长间的关系为：

$r = \frac{{abc}}{{\sqrt {\left( {a + b + c} \right)\left( {a + b - c} \right)\left( {a - b + c} \right)\left( {b + c - a} \right)} }} $

(2)

式中，r为外接球半径；；a、b、c分别为三角形的3条边长。

由§2.1可知，拓展边周围的潜在网格边长L' ≈ k · μ · L，则可根据式(2)及拓展边长、潜在网格边长概略计算得到滚球半径值：

$r = \frac{{{k^2}{{\bar \mu }^2}}}{{\sqrt {\left( {2k\bar \mu + 1} \right) \cdot \left( {2k\bar \mu - 1} \right)} }}L $

(3)

以均匀点云兔为例，应用数理统计方法对IPFPC进行统计分析，共获得数据14 551组，其中最大值为3.80，最小值为0.09，平均值μ，接近于1，所以为了简化计算，将拓展边长记为μL，则式(3)变为：

$r = \frac{{{k^2}}}{{\sqrt {\left( {2k + 1} \right) \cdot \left( {2k - 1} \right)} }}\bar \mu L $

(4)

通过分析式(4)中函数的性质可知，当$k \in \left({1/2, \sqrt 2 /2} \right]$时，r(k)单调递减；当$k \in \left[{\sqrt 2 /2, + \infty } \right)$时，r(k)单调递增，所以当$k = \sqrt 2 /2$时，r(k)取得最小值，此时滚球半径0.5μL。

若r取值较小，可能使得滚球搜索范围内不存在第三点，产生孔洞；若r取值较大，可能使得滚球搜索范围较大，产生冗余三角形。当k的取值为函数r(k)最小值点的两倍时，即k=1.5，此时滚球半径大约为拓展边长的6.4μ倍，已足够确保其搜索范围内含有第三点，并且不会使得搜索范围过大，故k有效取值范围为$\left({\sqrt 2 /2, 1.5} \right]$，同时也通过多次实验分析验证了该取值范围的有效性。k可以为一个在区间$\left({\sqrt 2 /2, 1.5} \right]$内不断改变的量，也可以是该区间内的一个定值。在本文算法中，为减少计算量，将k视为一个定值，设定k=1.5。

在自适应BPA算法中，重建过程也主要分为选取种子三角形和拓展三角形网格两个步骤。其中，种子三角形选取步骤和原始BPA算法无太大区别；但在三角形网格拓展步骤中，滚球半径值不再是固定不变的，而是根据式(4)计算得到。算法流程如图 3所示。

2.3 重建质量评价方法

目前，对于点云曲面重建质量的评价方法主要是人工目视法，即通过人眼观察重建曲面的好坏，鲜有定量的评价方法。本文依据重建曲面的表面积提出一种定量的评价方法，即表面积统计法。

首先，根据海伦公式计算出每个重建三角形的面积S_i，计算公式为：

${S_i} = \sqrt {{p_i}\left( {{p_i} - {a_i}} \right)\left( {{p_i} - b{}_i^{}} \right)\left( {{p_i} - {c_i}} \right)} $

(5)

式中，a_i、b_i、c_i为第i个重建三角形的3个边长值；p_i为该三角形的半周长(p_i=(a_i+b_i+c_i) 2)。

然后，计算重建曲面的表面积S'：

最后，通过分析重建表面积S'来评价重建曲面质量的高低。

在点云理论表面积值已知时，可通过分析重建表面积S'与理论表面积S之间的差值，即ΔS=S'-S，评价曲面重建结果的好坏。结合人工目视法，当重建曲面中无明显孔洞或冗余三角形时，ΔS值越接近0，代表重建结果越好；并且，当ΔS值为正时，代表重建曲面表面积大于理论值，重建结果中可能含有冗余三角形；当ΔS值为负时，代表重建曲面表面积小于理论值，重建结果中可能含有孔洞。

在点云理论表面积值未知时，可通过计算不同算法重建出的曲面的表面积，并结合人工目视法分析其差异，评价曲面重建质量。

3 点云重建实验与分析

为测试本文提出的SaBPA算法的效果，在Windows7系统Intel(R) Core(TM) i7-4790M CPU 3.60 GHz RAM (8.0 GB)硬件环境下，结合vs2013、Geomagic Studio软件对曲面重建质量和效率进行测试分析。首先，对均匀点云进行重建，评价其重建质量，并将其重建表面积作为点云理论表面积；然后，对均匀点云进行非均匀降采样，随之分别应用BPA算法、文献[25]算法和SaBPA算法重建其曲面，将重建表面积与理论表面积作对比，以分析各算法对非均匀点云曲面重建的适用性。

3.1 均匀点云重建

分别应用BPA算法、文献[25]算法和SaBPA算法对均匀点云龙、兔进行曲面重建，并应用表面积统计法结合人工目视法评价曲面重建质量。其中，BPA算法和文献[25]算法通过人工多次试选滚球半径r，选取其中重建结果最好的进行实验。3种算法重建结果如图 4所示，半径值、半径选取耗时、算法运行耗时及曲面重建表面积统计情况分别如表 1~3所示。

对于均匀点云，从图 4(c)可知，SaBPA算法能重建出高质量的点云表面；从图 4(a)和图 4(b)可知，当滚球半径选取合适时，BPA算法和文献[25]算法也能重建出良好的结果。

从表 1~3可知，BPA算法和文献[25]算法在选取滚球半径时需要人工试选，没有任何先验信息，效率较低，而SaBPA算法可根据拓展边长和IPFPC等信息自适应确定滚球半径，提高了算法的自动化程度，并且耗时与选定半径之后的BPA算法和文献[25]算法相当。

从图 4可知，应用3种算法重建出的均匀点云表面都比较平滑，都具有较高的重建质量；从表 1~3可知，3种算法重建出的曲面表面积也基本相同，重建质量相当。综上可以认为，表面积统计法和人工目视法对于点云曲面重建质量评价具有相同的结果和趋势。

此外，从表 1~3还可以看出，当点云数据量较大时，例如龙点云，重建时需要消耗大量时间，为了提高重建效率，一种行之有效的方式是先对海量点云进行特征保留的降采样^[26-28]，然后重建。

3.2 非均匀点云重建

首先，应用文献[26]算法对原始龙、兔点云进行非均匀降采样，降采样后龙、兔点云中点的个数分别为69 465和8 584，耗时分别为350 s和6 s，如图 5所示；然后，分别应用BPA算法、文献[25]算法和SaBPA算法对非均匀点云进行曲面重建，重建结果如图 6~8所示，半径选取方式、耗时及曲面重建表面积统计情况分布如表 4~6所示。

从图 5(a)可知，原始点云比较均匀且密集。经非均匀降采样之后，如图 5(b)所示，在特征区域（如龙点云的龙头、龙爪以及兔点云的兔耳、兔尾），点云较密集，而在非特征区域(如龙点云的龙身以及兔点云的兔身)，点云较稀疏。

从图 6可知，应用BPA算法对非均匀点云进行曲面重建，当滚球半径选取较小时，如图 6(a)、图 6(d)所示，会导致重建失败，其原因是在点云稀疏区域拓展三角形网格时，在其滚球范围内不包含第三点，无法进行三角形延伸，导致重建失败；当滚球半径选取较大时，如图 6(c)、图 6(f)所示，会导致重建结果中含有大量冗余三角形，其原因是在点云密集区域拓展三角形网格时，在其滚球范围内会包含较多不应与当前点构成拓扑关系且满足三角形网格拓展准则的点，使得重建结果中含有冗余三角形；当滚球半径选取中间值时，如图 6(b)、图 6(e)所示，重建结果在点云密集区域会有少量冗余三角形，在点云稀疏区域会出现孔洞。

从图 7可知，应用文献[25]算法对非均匀点云进行曲面重建，当选取多个较合适的滚球半径进行重建时，会使得重建结果逼近相应均匀点云的重建结果(如图 4(b)所示)；但滚球半径的选取需要经过人工进行多次尝试，针对不同点云，其最适取值组合不同，不具有自适应性，在实际应用中处理较为耗时。

从图 8可知，应用SaBPA算法对非均匀点云进行曲面重建可得到良好的重建结果，非常逼近相应均匀点云的重建结果(如图 4(c)所示)，且无需人工干预。针对不同点云，能根据IPFPC和拓展边长相对合理地自适应确定滚球半径，既不会使第三点搜索范围过小而出现孔洞，也不会使搜索范围过大而产生冗余三角形。

对比表 1~3和表 4~6可知，相对于降采样之前的重建效率，3种算法均有较大程度提高，并且文献[25]算法和SaBPA算法没有损害重建质量；但对于滚球半径的确定，文献[25]算法需要人工试选，而SaBPA算法可自适应确定，所以在重建过程整体耗时上，SaBPA算法远少于文献[25]算法。

从表 5~6还可知，当文献[25]算法中的滚球半径值组合选取相对合理时，其重建非均匀点云的表面积值和SaBPA算法重建的值基本相当；从表 4可知，BPA算法重建非均匀点云表面积值随着滚球半径的改变具有较大程度的变化。为更好地分析和评价3种算法重建出的非均匀点云曲面的质量，以各自算法重建出的均匀点云表面积值为理论值，统计重建的非均匀点云表面积与理论值间的差值，结果如表 7所示。

从表 7可知，应用BPA算法重建非均匀点云时，滚球半径选取过小，例如龙点云r=0.2 cm和兔点云r=0.4 cm，重建表面积比基准值分别少了81.6 cm²和31.4 cm²，对应图 6(b)、图 6(e)中重建曲面也出现了较多孔洞；滚球半径选取过大，例如龙点云r=0.3 cm和兔点云r=0.7 cm，重建曲面表面积比基准值分别多了20.0 cm²和10.6 cm²，对应图 6(c)、图 6(f)中重建曲面也出现了较多冗余三角形，所以应用BPA算法难以重建出高质量的非均匀点云表面。

应用文献[25]算法重建非均匀点云，滚球半径组合选取合理时，重建表面积值与理论值间差值较小，可在一定程度上重建非均匀点云，但合理的滚球半径组合确定耗时多。

应用SaBPA算法重建非均匀点云，重建表面积值与理论值间的差值很接近，重建结果质量高。

4 结语

本文针对BPA算法不适用于非均匀点云曲面重建的问题，提出了一种根据IPFPC自适应确定滚球半径的改进算法——SaBPA算法，并依据重建曲面表面积与点云表面积理论值间的差值，提出了一种曲面重建质量定量评价方法。

SaBPA算法根据拓展边长和IPFPC等信息自适应地确定滚球半径，进行第三点的选取和曲面的重建，实现了BPA算法中滚球半径的自适应确定，克服了BPA算法不适用于非均匀点云曲面重建的缺点。实验结果验证了SaBPA算法的有效性，依据人工目视法和本文所提的表面积统计法对重建曲面进行质量评价，证明了SaBPA算法可高质量地重建出非均匀点云表面。但在曲面重建质量定量评价时，一般难以得到确切的原始点云表面积理论值，故该评价方法的有效性有待进一步验证。