-
随着三维建模技术的快速发展，基于散乱点云的曲面重建技术在逆向工程、文物保护、工业制造、计算机辅助设计与制造、虚拟现实和科学计算可视化等领域得到了广泛应用[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算法不擅长处理非均匀点云的缺点。
-
BPA算法是一种经典的曲面重建算法。该算法从一个种子三角形开始，用户先定义一个半径为r的滚球；然后，将滚球沿着种子三角形的某条边滚动(沿着边滚动时始终保持与该边的两个端点接触)，直到接触到下一个点时停止滚动；最后，通过判断该滚球内是否包含其他点来确定是否将该边与该点构成新的三角形。不断循环上述过程，直到将所有点都包含在三角形网格中，完成重建工作。由于其需要用户预先定义滚球半径r，所以处理不均匀点云非其所长。
BPA算法的曲面重建过程包含三角形选取和三角形网格拓展两步。
1) 种子三角形选取。种子三角形用于三角形网格初始化。一个良好的种子三角形需要满足3个条件：（1）该三角形位于点云表面；（2）构成三角形的3个顶点尽量避开可能存在粗差和异常值的点；（3）种子三角形要尽量接近等边三角形。算法具体步骤为：
（1）随机选取一个没有被用于曲面重建的点p。
（2）从点p的邻域中选取两个点pa、pb。
（3）构造一个原始三角形△ppapb。
（4）对△ppapb进行相容性检测，满足则继续下一步，否则返回步骤（1）。
（5）当滚球球心位于三角面外侧、球面与3个顶点接触时，判断滚球内是否含有其他点：若没有，则将该三角形作为种子三角形输出；若有，则返回步骤（1）。
2) 三角形网格拓展。该步骤主要是为拓展边获取第三点，构造候选三角形，然后对候选三角形进行相容性检测，并给出相应的处理方法。算法具体步骤为：
（1）检测边的可拓展性，将不可拓展的边标记为内边。
（2）基于给定的滚球半径r确定候选点。
（3）从候选点中选取较优点作为拓展边的第三点，构造三角形，得到候选三角形。
（4）对候选三角形进行相容性检测，若满足条件，则参与构网，否则删除该候选三角形。
（5）不断重复步骤（1）~（4），直到所有边都不可拓展为止，然后修补三角形网格中的孔洞，输出三角形网格。
在原始BPA算法中，滚球半径r是用户在重建之前定义的，具有全局不变性。如果点云不均匀，则在采样点间距大于2r的区域会产生孔洞，二维空间情形如图 1所示。
图 1 二维情形下BPA算法
Figure 1. BPA in 2D Situation
从图 1(a)可知，当点云数据均匀时，应用BPA算法可以很好地重建出点云表面模型；但当点云数据不均匀时（见图 1(b)），难以确定一个合适的滚球半径来重建出高质量的三维模型。需要对BPA算法中滚球半径的自适应取值问题进行研究，使其具备重建非均匀点云数据的能力。
-
针对BPA算法不适用于重建非均匀点云的缺点，根据拓展边长以及IPFPC，本文设计了一种自适应确定滚球半径的方法，以增强BPA算法的实用价值。
-
IPFPC是一个无量纲的比值，如图 2所示，定义为拓展边两个顶点参与构网的网格中所有网格边长与拓展边长之间的比值，记为μi(如图 2所示i=1, 2…5)，计算公式为：
图 2 IPFPC示意图
Figure 2. Schematic Diagram of IPFPC
$$\mu = L'/L $$ (1) 式中，L'、L分别为网格边长和拓展边长。
由图 2和IPFPC的定义可知，根据每条拓展边IPFPC的均值μ以及该拓展边长L，可概略地知道该拓展边周围的潜在网格边长L' ≈ k · μ · L(k为大于零的常数)，故可根据三角形外接球半径与3条边长之间的关系实现滚球半径的自适应选取。
-
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所示。
图 3 改进算法流程图
Figure 3. Flowchart of the Improved Algorithm
-
目前，对于点云曲面重建质量的评价方法主要是人工目视法，即通过人眼观察重建曲面的好坏，鲜有定量的评价方法。本文依据重建曲面的表面积提出一种定量的评价方法，即表面积统计法。
首先，根据海伦公式计算出每个重建三角形的面积Si，计算公式为：
$${S_i} = \sqrt {{p_i}\left( {{p_i} - {a_i}} \right)\left( {{p_i} - b{}_i^{}} \right)\left( {{p_i} - {c_i}} \right)} $$ (5) 式中，ai、bi、ci为第i个重建三角形的3个边长值；pi为该三角形的半周长(pi=(ai+bi+ci) 2)。
然后，计算重建曲面的表面积S'：
$$S' = \mathop \sum \nolimits {S_i} $$ 最后，通过分析重建表面积S'来评价重建曲面质量的高低。
在点云理论表面积值已知时，可通过分析重建表面积S'与理论表面积S之间的差值，即ΔS=S'-S，评价曲面重建结果的好坏。结合人工目视法，当重建曲面中无明显孔洞或冗余三角形时，ΔS值越接近0，代表重建结果越好；并且，当ΔS值为正时，代表重建曲面表面积大于理论值，重建结果中可能含有冗余三角形；当ΔS值为负时，代表重建曲面表面积小于理论值，重建结果中可能含有孔洞。
在点云理论表面积值未知时，可通过计算不同算法重建出的曲面的表面积，并结合人工目视法分析其差异，评价曲面重建质量。
-
为测试本文提出的SaBPA算法的效果，在Windows7系统Intel(R) Core(TM) i7-4790M CPU 3.60 GHz RAM (8.0 GB)硬件环境下，结合vs2013、Geomagic Studio软件对曲面重建质量和效率进行测试分析。首先，对均匀点云进行重建，评价其重建质量，并将其重建表面积作为点云理论表面积；然后，对均匀点云进行非均匀降采样，随之分别应用BPA算法、文献[25]算法和SaBPA算法重建其曲面，将重建表面积与理论表面积作对比，以分析各算法对非均匀点云曲面重建的适用性。
-
分别应用BPA算法、文献[25]算法和SaBPA算法对均匀点云龙、兔进行曲面重建，并应用表面积统计法结合人工目视法评价曲面重建质量。其中，BPA算法和文献[25]算法通过人工多次试选滚球半径r，选取其中重建结果最好的进行实验。3种算法重建结果如图 4所示，半径值、半径选取耗时、算法运行耗时及曲面重建表面积统计情况分别如表 1~3所示。
图 4 均匀点云重建结果图
Figure 4. Results of Uniform Point Cloud Reconstruction
表 1 BPA算法重建均匀点云统计表
Table 1. Statistics of Uniform Point Cloud Reconstructed by BPA Algorithm
点云 点数/个 半径值/cm 耗时/s 重建表面积/cm2 半径选取 算法运行 龙 434 866 r = 0.1 未知 535 710.8 兔 35 947 r = 0.2 未知 9 572.4 表 2 文献[25]算法重建均匀点云统计表
Table 2. Statistics of Uniform Point Cloud Reconstructed by Reference [25] Algorithm
点云 点数/个 半径值/cm 耗时/s 重建表面积/cm2 半径选取 算法运行 龙 434 866 r = 0.1, 0.2 未知 544 712.0 兔 35 947 r = 0.2, 0.4 未知 11 575.9 表 3 SaBPA算法重建均匀点云统计表
Table 3. Statistics of Uniform Point Cloud Reconstructed by SaBPA Algorithm
点云 点数/个 半径值/cm 耗时/s 重建表面积/cm2 龙 434 866 自适应值 558 708.5 兔 35 947 自适应值 12 566.4 注：耗时项包含半径选取和算法运行两项 对于均匀点云，从图 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]，然后重建。
-
首先，应用文献[26]算法对原始龙、兔点云进行非均匀降采样，降采样后龙、兔点云中点的个数分别为69 465和8 584，耗时分别为350 s和6 s，如图 5所示；然后，分别应用BPA算法、文献[25]算法和SaBPA算法对非均匀点云进行曲面重建，重建结果如图 6~8所示，半径选取方式、耗时及曲面重建表面积统计情况分布如表 4~6所示。
图 5 点云示意图
Figure 5. Diagram of Point Cloud
图 6 BPA算法重建非均匀点云结果图
Figure 6. Results of Non-uniform Point Cloud Reconstructed by BPA Algorithm
图 8 SaBPA算法重建非均匀点云结果图
Figure 8. Results of Non-uniform Point Cloud Reconstructed by SaBPA
表 4 BPA算法重建非均匀点云统计表
Table 4. Statistics of Non-uniform Point Cloud Reconstructed by BPA Algorithm
表 5 文献[25]算法重建非均匀点云统计表
Table 5. Statistics of Non-uniform Point Cloud Reconstructed by Reference [25] Algorithm
点云 点数/个 半径值/cm 耗时/s 重建表面积/cm2 半径选取 算法运行 龙 69 465 r =0.1, 0.2, 0.3 未知 33 718.1 兔 8 584 r =0.2, 0.4, 0.7 未知 3 561.2 表 6 SaBPA算法重建非均匀点云统计表
Table 6. Statistics of Non-uniform Point Cloud Reconstructed by SaBPA Algorithm
点云 点数/个 半径值/cm 耗时/s 重建表面积/cm2 龙 69 465 自适应值 37 712.4 兔 8 584 自适应值 4 563.9 注：耗时项包含半径选取和算法运行两项 从图 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 非均匀点云重建表面积与理论值间差值统计表/cm2
Table 7. Differences Between Non-uniform Point Cloud Reconstructed Surface Area and Its Theoretical Value/cm2
点云 BPA算法 文献[25]算法 SaBPA算法 龙 -375.0
(r=0.1)-81.6
(r=0.2)20.0
(r=0.3)6.1
(r=0.1, 0.2, 0.3)3.9 兔 -335.0
(r=0.2)-31.4
(r=0.4)10.6
(r=0.7)-14.7
(r=0.2, 0.4, 0.7)-2.5 从表 7可知，应用BPA算法重建非均匀点云时，滚球半径选取过小，例如龙点云r=0.2 cm和兔点云r=0.4 cm，重建表面积比基准值分别少了81.6 cm2和31.4 cm2，对应图 6(b)、图 6(e)中重建曲面也出现了较多孔洞；滚球半径选取过大，例如龙点云r=0.3 cm和兔点云r=0.7 cm，重建曲面表面积比基准值分别多了20.0 cm2和10.6 cm2，对应图 6(c)、图 6(f)中重建曲面也出现了较多冗余三角形，所以应用BPA算法难以重建出高质量的非均匀点云表面。
应用文献[25]算法重建非均匀点云，滚球半径组合选取合理时，重建表面积值与理论值间差值较小，可在一定程度上重建非均匀点云，但合理的滚球半径组合确定耗时多。
应用SaBPA算法重建非均匀点云，重建表面积值与理论值间的差值很接近，重建结果质量高。
-
本文针对BPA算法不适用于非均匀点云曲面重建的问题，提出了一种根据IPFPC自适应确定滚球半径的改进算法——SaBPA算法，并依据重建曲面表面积与点云表面积理论值间的差值，提出了一种曲面重建质量定量评价方法。
SaBPA算法根据拓展边长和IPFPC等信息自适应地确定滚球半径，进行第三点的选取和曲面的重建，实现了BPA算法中滚球半径的自适应确定，克服了BPA算法不适用于非均匀点云曲面重建的缺点。实验结果验证了SaBPA算法的有效性，依据人工目视法和本文所提的表面积统计法对重建曲面进行质量评价，证明了SaBPA算法可高质量地重建出非均匀点云表面。但在曲面重建质量定量评价时，一般难以得到确切的原始点云表面积理论值，故该评价方法的有效性有待进一步验证。
A New Self-adaptive Ball Pivoting Algorithm Driven by an Intrinsic Property Factor of Point Cloud
-
摘要: 采用滚球算法（ball pivoting algorithm，BPA）重建非均匀点云时会产生较多孔洞或冗余三角形，对此先定义一种点云内在属性因子，提出了一种自适应BPA算法，并用重建曲面表面积定量评价曲面重建质量。首先，根据点云法向、位置、点间距离、关系等信息选取3个恰当的孤立点，构建种子三角形；其次，计算每条拓展边的点云内在属性因子，并结合拓展边长等信息，自适应地确定滚球半径r；最后，将半径为r的滚球沿着拓展边滚动，选取合适的第三点拓展三角形网格。采用龙、兔点云进行曲面重建实验，实验结果表明，无论是均匀点云还是非均匀点云，此算法均能自适应地重建出点云表面模型，重建过程无需人工干预，算法稳健、高效，重建结果质量较高。Abstract: To solve the shortcoming that there will be some holes and/or redundant triangles when non-uniform point cloud is reconstructed by BPA(ball pivoting algorithm), a new self-adaptive ball pivoting algorithm is proposed. The improved algorithm is driven by an intrinsic property of point cloud, which is initially proposed. And according to the reconstructed surface area, a new method of surface reconstruction quality evaluation is also proposed. Firstly, three isolated points are selected to build a seed triangle, according to the points' vectors, position, spacing, connection and so on. Then, the radius r of the pivoting ball is adaptively calculated based on the intrinsic property of point cloud and front edge length. Finally, a suitable third point is selected by pivoting the ball of radius r around the front edge, to expand the triangulation. Experiments on Dragon and Bunny point cloud show that the proposed algorithm can adaptively reconstruct the surface of both uniform and non-uniform point cloud.Moreover, it is robust, efficient and needs no manual intervention. The reconstructed surface is of high-quality according to the proposed method of surface reconstruction quality evaluation.
-
图 6 BPA算法重建非均匀点云结果图
Figure 6. Results of Non-uniform Point Cloud Reconstructed by BPA Algorithm
图 8 SaBPA算法重建非均匀点云结果图
Figure 8. Results of Non-uniform Point Cloud Reconstructed by SaBPA
表 1 BPA算法重建均匀点云统计表
Table 1. Statistics of Uniform Point Cloud Reconstructed by BPA Algorithm
点云 点数/个 半径值/cm 耗时/s 重建表面积/cm2 半径选取 算法运行 龙 434 866 r = 0.1 未知 535 710.8 兔 35 947 r = 0.2 未知 9 572.4 
下载: 导出CSV
表 2 文献[25]算法重建均匀点云统计表
Table 2. Statistics of Uniform Point Cloud Reconstructed by Reference [25] Algorithm
点云 点数/个 半径值/cm 耗时/s 重建表面积/cm2 半径选取 算法运行 龙 434 866 r = 0.1, 0.2 未知 544 712.0 兔 35 947 r = 0.2, 0.4 未知 11 575.9
下载: 导出CSV
表 3 SaBPA算法重建均匀点云统计表
Table 3. Statistics of Uniform Point Cloud Reconstructed by SaBPA Algorithm
点云 点数/个 半径值/cm 耗时/s 重建表面积/cm2 龙 434 866 自适应值 558 708.5 兔 35 947 自适应值 12 566.4 注：耗时项包含半径选取和算法运行两项
下载: 导出CSV
表 4 BPA算法重建非均匀点云统计表
Table 4. Statistics of Non-uniform Point Cloud Reconstructed by BPA Algorithm
下载: 导出CSV
表 5 文献[25]算法重建非均匀点云统计表
Table 5. Statistics of Non-uniform Point Cloud Reconstructed by Reference [25] Algorithm
点云 点数/个 半径值/cm 耗时/s 重建表面积/cm2 半径选取 算法运行 龙 69 465 r =0.1, 0.2, 0.3 未知 33 718.1 兔 8 584 r =0.2, 0.4, 0.7 未知 3 561.2
下载: 导出CSV
表 6 SaBPA算法重建非均匀点云统计表
Table 6. Statistics of Non-uniform Point Cloud Reconstructed by SaBPA Algorithm
点云 点数/个 半径值/cm 耗时/s 重建表面积/cm2 龙 69 465 自适应值 37 712.4 兔 8 584 自适应值 4 563.9 注：耗时项包含半径选取和算法运行两项
下载: 导出CSV
表 7 非均匀点云重建表面积与理论值间差值统计表/cm2
Table 7. Differences Between Non-uniform Point Cloud Reconstructed Surface Area and Its Theoretical Value/cm2
点云 BPA算法 文献[25]算法 SaBPA算法 龙 -375.0
(r=0.1)-81.6
(r=0.2)20.0
(r=0.3)6.1
(r=0.1, 0.2, 0.3)3.9 兔 -335.0
(r=0.2)-31.4
(r=0.4)10.6
(r=0.7)-14.7
(r=0.2, 0.4, 0.7)-2.5
下载: 导出CSV
-
[1] 胡思兰, 周明全, 税午阳, 等.一种改进Ball Pivoting的散乱点云数据重建算法[J].系统仿真学报, 2015, 27(10):2446-2452 http://d.old.wanfangdata.com.cn/Periodical/xtfzxb201510033 Hu Silan, Zhou Mingquan, Shui Wuyang, et al. Improved Ball Pivoting Algorithm for Nonuniform Point Cloud Data[J]. Journal of System Simulation, 2015, 27(10):2446-2452 http://d.old.wanfangdata.com.cn/Periodical/xtfzxb201510033 [2] 孙殿柱, 魏亮, 李延瑞, 等.基于局部样本增益优化的α-shape曲面拓扑重建[J].机械工程学报, 2016, 52(3):136-142 http://d.old.wanfangdata.com.cn/Periodical/jxgcxb201603022 Sun Dianzhu, Wei Liang, Li Yanrui, et al. Surface Reconstruction with α-shape Based on Optimization of Surface Local Sample[J]. Journal of Mechanical Engineering, 2016, 52(3):136-142 http://d.old.wanfangdata.com.cn/Periodical/jxgcxb201603022 [3] 李国俊.基于Delaunay细化的散乱点云曲面重建研究[D].郑州: 信息工程大学, 2015 Li Guojun. Research on Surface Reconstruction Base on Delaunay Refinement from Scattered Point Clouds[D]. Zhengzhou: Information Engineering University, 2015 [4] 李国俊, 李宗春, 孙元超, 等.利用Delaunay细分进行噪声点云曲面重建[J].武汉大学学报·信息科学版, 2017, 42(1):123-129 http://ch.whu.edu.cn/CN/abstract/abstract5645.shtml Li Guojun, Li Zongchun, Sun Yuanchao, et al.Using Delaunay Refinement to Reconstruct Surface from Noisy Point Clouds[J]. Geomatics and Information Science of Wuhan University, 2017, 42(1):123-129 http://ch.whu.edu.cn/CN/abstract/abstract5645.shtml [5] 张剑清, 李彩林, 郭宝云.基于切平面投影的散乱数据点快速曲面重建算法[J].武汉大学学报·信息科学版, 2011, 36(7):757-762 http://ch.whu.edu.cn/CN/abstract/abstract595.shtml Zhang Jianqing, Li Cailin, Guo Baoyun. A Fast Surface Reconstruction Algorithm for Unorganized Points Based on Tangent Plane Projection[J]. Geomatics and Information Science of Wuhan University, 2011, 36(7):757-762 http://ch.whu.edu.cn/CN/abstract/abstract595.shtml [6] 何华, 李宗春, 李国俊, 等.散乱点云的自适应α-shape曲面重建[J].计算机应用, 2016, 36(12):3394-3397 http://d.old.wanfangdata.com.cn/Periodical/jsjyy201612028 He Hua, Li Zongchun, Li Guojun, et al. Surface Reconstruction for Scattered Point Clouds with Adaptive α-shape[J]. Journal of Computer Applications, 2016, 36(12):3394-3397 http://d.old.wanfangdata.com.cn/Periodical/jsjyy201612028 [7] 贾军辉, 黄明, 刘祥磊.基于三维狄洛尼三角网的曲面重建算法[J].测绘学报, 2018, 47(2):281-290 http://d.old.wanfangdata.com.cn/Periodical/chxb201802017 Jia Junhui, Huang Ming, Liu Xianglei. Surface Reconstruction Algorithm Based on 3D Triangulation[J]. Acta Geodaetica et Cartographica Sinica, 2018, 47(2):281-290 http://d.old.wanfangdata.com.cn/Periodical/chxb201802017 [8] 刘涛, 高媛, 秦品乐, 等.基于点云增强优化的泊松重建算法[J].计算机应用研究, 2018, 35(2):940-943 http://d.old.wanfangdata.com.cn/Periodical/jsjyyyj201803063 Liu Tao, Gao Yuan, Qin Pinle, et al. Improved and Optimized Poisson Reconstruction Algorithm Based on Point Cloud Library[J]. Journal of Computer Applications, 2018, 35(2):940-943 http://d.old.wanfangdata.com.cn/Periodical/jsjyyyj201803063 [9] Carr J C, Beatson R K, Cherrie J B, et al. Reconstruction and Representation of 3D Objects with Radial Basis[C]. The 28th Annual Conference on Computer Graphics and Interactive Techniques, New York, USA, 2001 [10] 符华年, 刘兴虎, 李俊峰.基于地面激光点云数据的NURBS曲面重建[J].测绘地理信息, 2017(4):17-19 http://d.old.wanfangdata.com.cn/Periodical/chxxygc201704004 Fu Huanian, Liu Xinghu, Li Junfeng. NURBS Surface Reconstruction Based on Terrestrial LiDAR Point Cloud[J]. Journal of Geomatics, 2017(4):17-19 http://d.old.wanfangdata.com.cn/Periodical/chxxygc201704004 [11] Bernardine F, Mittleman J, Holly R.The Ball-Pivoting Algorithm for Surface Reconstruction[J]. IEEE Transactions on Visualization and Computer Graphics, 1999, 5(4):349-359 doi: 10.1016-j.ins.2011.07.017/ [12] 李晶晶, 范大昭, 耿弘毅, 等.城市点云的区域生长三角网构建方法[J].测绘科学技术学报, 2016, 33(1):65-70 http://d.old.wanfangdata.com.cn/Periodical/chxyxb201601014 Li Jingjing, Fan Dazhao, Geng Hongyi, et al. Triangular Mesh Construction for City Points Based on Region Growing[J]. Journal of Geomatics Science and Technology, 2016, 33(1):65-70 http://d.old.wanfangdata.com.cn/Periodical/chxyxb201601014 [13] 余松, 王彦坤.基于滚球法的面要素聚合[J].测绘科学, 2017, 42(10):138-141 http://d.old.wanfangdata.com.cn/Periodical/chkx201710023 Yu Song, Wang Yankun. Polygon Cluster Based on Rolling Sphere Method[J]. Science of Surveying and Mapping, 2017, 42(10):138-141 http://d.old.wanfangdata.com.cn/Periodical/chkx201710023 [14] Lin Hongwei, Chiew L T, Wang Guojin. A Mesh Reconstruction Algorithm Driven by an Intrinsic Property of a Point Cloud[J]. Computer-Aided Design, 2004, 36(1):1-9 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=93d2ffa80afc46fb595e565d3bc2b471 [15] Long Chengjiang, Zhao Jianhui, Yuan Zhiyong, et al. Improvements on IPD Algorithm for Triangular Mesh Reconstruction from 3D Point Cloud[C]. The First International Conference on Multimedia Information Networking and Security, Wuhan, China, 2009 [16] Diangelo L, Distefano P, Giaccari L. A New Mesh-Growing Algorithm for Fast Surface Reconstruction[J].Computer-Aided Design, 2011, 43(6):639-650 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=90194fda80f8cca37a7d43be7be036db [17] Huang J, Menq C H. Combinatorial Manifold Mesh Reconstruction and Optimization from Unorganized Points with Arbitrary Topology[J].Computer-Aided Design, 2002, 34(2):149-165 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=2fb056a062c7b495dc0a44c6d334898e [18] 何华, 李宗春, 闫荣鑫, 等.引入曲面变分实现点云法矢一致性调整[J].测绘学报, 2018, 47(2):275-280 http://d.old.wanfangdata.com.cn/Periodical/chxb201802016 He Hua, Li Zongchun, Yan Rongxin, et al. On the Consistent Normal Vector Adjustment of Point Cloud Using Surface Variation[J]. Acta Geodaetica et Cartographica Sinica, 2018, 47(2):275-280 http://d.old.wanfangdata.com.cn/Periodical/chxb201802016 [19] Sun Jiuai, Smith M, Smith L, et al. Examining the Uncertainty of the Recovered Surface Normal in Three Light Photometric Stereo[J]. Image and Vision Computing, 2007, 25(7):1073-1079 doi: 10.1016/j.imavis.2006.04.024 [20] 刘健.可修正的点云一致定向[D].大连: 大连理工大学, 2014 Liu Jian. Mendable Consistent Orientation of Point Clouds[D]. Dalian: Dalian University of Technology, 2014 [21] Esdras M, Luiz V, Helio L. Restricted BPA: Applying Ball-Pivoting on the Plane[C]. The 17th Brazilian Symposium on Computer Graphics and Image Processing, Curitiba, Brazil, 2004 [22] Hussein A. A Hybrid System for Three-Dimensional Objects Reconstruction from Point-Clouds Based on Ball Pivoting Algorithm and Radial Basis Functions[C]. The 9th WSEAS International Conference on Computers, Athens, Hellenic, 2005 [23] 杨光.改进的BPA算法研究及其在三维表面重建中的应用[D].杭州: 浙江工业大学, 2008 Yang Guang. Research on the BPA Algorithm and the Application on the 3D Surface Reconstruction[D]. Hangzhou: Zhejiang University of Technology, 2008 [24] Bharti S, Kamaldeep K. Optimization of Mesh Reconstruction Using Delaunay and Ball Pivoting Algorithm[J]. International Journal of Research in Engineering and Advanced Technology, 2013, 1(2):1-7 [25] Digne J. An Analysis and Implementation of a Parallel Ball Pivoting Algorithm[J]. Image Processing on Line, 2014(4):149-168 [26] 李国俊, 李宗春, 侯东兴.基于Delaunay三角化的噪声点云非均匀采样[J].计算机应用, 2014, 34(10):2922-2924 http://d.old.wanfangdata.com.cn/Periodical/jsjyy201410033 Li Guojun, Li Zongchun, Hou Dongxing. Delaunay-Based Non-uniform Sampling for Noisy Point Cloud[J]. Journal of Computer Applications, 2014, 34(10):2922-2924 http://d.old.wanfangdata.com.cn/Periodical/jsjyy201410033 [27] 张雨禾, 耿国华, 魏潇然, 等.保留几何特征的散乱点云简化算法[J].计算机辅助设计与图形学学报, 2016, 28(9):1420-1427 http://d.old.wanfangdata.com.cn/Periodical/jsjfzsjytxxxb201609003 Zhang Yuhe, Geng Guohua, Wei Xiaoran, et al. Point Clouds Simplification with Geometric Feature Reservation[J]. Journal of Computer-Aided Design and Computer Graphics, 2016, 28(9):1420-1427 http://d.old.wanfangdata.com.cn/Periodical/jsjfzsjytxxxb201609003 [28] 付永健, 李宗春, 何华, 等.基于K-近邻拟合平面点云简化算法[J].北京测绘, 2017(S1):86-90 http://www.cnki.com.cn/Article/CJFDTotal-BJCH2017S1022.htm Fu Yongjian, Li Zhongchun, He Hua, et al. Point Cloud Simplification Based on K-neighbors Fitting Plane[J]. Beijing Surveying and Mapping, 2017(S1):86-90 http://www.cnki.com.cn/Article/CJFDTotal-BJCH2017S1022.htm -
点击查看大图
图(8) / 表(7)
计量
- 文章访问数: 1389
- HTML全文浏览量: 189
- PDF下载量: 96
- 被引次数: 0
