一种改进Ball Pivoting的散乱点云数据重建算法

系统仿真学报 ›› 2015, Vol. 27 ›› Issue (10): 2446-2452.

一种改进Ball Pivoting的散乱点云数据重建算法

胡丝兰^1,2, 周明全^1,2, 税午阳^1,2, 武仲科^1,2

1.教育部虚拟现实应用工程研究中心,北京 100875;
2.北京市文化遗产数字化保护重点实验室,北京 100875

收稿日期:2015-06-14 修回日期:2015-07-31 出版日期:2015-10-08 发布日期:2020-08-07
作者简介:胡丝兰(1991-),女,湖南,硕士生,研究方向虚拟现实与可视化技术。
基金资助:
自然科学基金(61202198, 61402042); 中央高校基本科研业务费(2013YB70, 2013YB72); 国家科技支撑计划(2012BAH33F04)

Improved Pivoting Ball Algorithm for Nonuniform Point Cloud Data

Hu Silan^1,2, Zhou Mingquan^1,2, Shui Wuyang^1,2, Wu Zhongke^1,2

1. Engineering Research Center of Virtual Reality and Applications, Beijing 100875, China;
2. Beijing Key Laboratory of Digital Preservation and Virtual Reality for Cultural Heritage, Beijing 100875, China

Received:2015-06-14 Revised:2015-07-31 Online:2015-10-08 Published:2020-08-07

摘要/Abstract

摘要： Ball Pivoting算法主要是用来对点云数据进行表面重建,算法是从一个种子三角形开始的,球沿着这个种子三角形的一个边进行旋转,直到这个球接触到下一个点,该边与该点组成一个三角形。该算法主要的缺点是当点云数据不均匀的时候球在滚动的过程当中不会接触到点,因此会产生洞。提出了一种对散乱点云数据进行重建的改进的Ball Pivoting算法;对初始点云数据构建k-d树,使得搜索区域算法时间效率提高;使用可变半径搜索改进算法,使得算法能够处理不均匀的点云数据而不会产生洞;优化了网格的拓扑结构。实验结果证明该算法相对于Ball Pivoting算法效率高,且不会生成洞,三角网格的拓扑结构好。

关键词: Ball Pivoting三角化, 三角网格, 散乱点云数据, k-d树

Abstract: Ball Pivoting algorithm is mainly used for surface reconstruction of point cloud data, the algorithm starts from a seed triangle, the ball along the seed triangle a side of rotation until the ball is exposed to a point and the edge and the composition of a triangle. The main disadvantage of this algorithm is that when the point cloud data is not uniform when the ball in the rolling process does not contact the point, and therefore will have a hole. A non-uniform point cloud data for improved reconstruction of the Ball Pivoting algorithm of the original point cloud data was proposed to construct k-d tree, allowing searching area algorithm time efficiency; variable radius search algorithm could make the algorithm deal with non-uniform point cloud data and did not produce hole, putting forward the more being a searching area algorithm, to optimize the topology structure of the grid. The experimental results show that the algorithm is efficient and cannot generate the holes and the topological structure of the triangle mesh is better than the Ball Pivoting algorithm.

Key words: Ball Pivoting triangulation, mesh triangular, nonuniform point cloud, k-d tree

中图分类号:

TP391.9

胡丝兰, 周明全, 税午阳, 武仲科. 一种改进Ball Pivoting的散乱点云数据重建算法[J]. 系统仿真学报, 2015, 27(10): 2446-2452.

Hu Silan, Zhou Mingquan, Shui Wuyang, Wu Zhongke. Improved Pivoting Ball Algorithm for Nonuniform Point Cloud Data[J]. Journal of System Simulation, 2015, 27(10): 2446-2452.

参考文献

[1] Cazals F, Giesen J.Delaunay triangulation based surface reconstruction.[M]// Boissonnat J, Teillaud M, editors. Effective computational geometry for curves and surfaces. Math. and visualization. Germany: Springer-Verlag, 2006: 231-76.
[2] Bernardini F, Mittleman J, Rushmeier H, et al. The Ball Pivoting algorithm for surface reconstruction[J]. IEEE Transactions on Visualization and Computer Graphics (S1001-395), 1999, 5(4): 349-359.
[3] Amenta N, Bern M, Kamvysselis M.A new Voronoi-based surface reconstruction algorithm[C]// The Proceeding of Computer Graphics, SIGGRAPH‘98. USA: ACM, 1998: 415-421.
[4] Amenta N, Choi S, Dey TK, et al. A simple algorithm for homeomorphic surface reconstruction[J]. International Journal of Computational Geometry & Applications (S1002-8331), 2002, 12(1/2): 125-141.
[5] Li X, Han CY, Wee WG.On surface reconstruction: a priority driven approach[J]. Computer-Aided Design (S1003-6221), 2009, 41(9): 626-640.
[6] Chang MC, Leymarie FF, Kimia BB.Surface reconstruction from point clouds by transforming the medial scaffold[J]. Computer Vision and Image Understanding (S1002-0708), 2009, 113(11): 1130-1146.
[7] Carr J, Beatson R, Cherrie H, et al. Reconstruction and representation of 3D objects with radial basis functions[C]// SIGGRAPH, 2001. USA: ACM, 2001: 67-76.
[8] Turk G, O’Brien [J]. Modelling with implicit surfaces that interpolate TOG, 2002: 855-73.
[9] Dey Tamal K, Sun Jian.An adaptive MLS surface for reconstruction with guarantees[C]// Proceedings of the Third Eurographics Symposium on Geometry Processing, 2005.
(TALG), 2010, 4(2): 812-78.
[10] Kolluri R.Provably good moving least squares[J]. ACM Transactions on Algorithms (TALG)(S1001-8843),2008, 4(2): 832-73
[11] Kazhdan M, Bolitho M, Hoppe H.Poisson surface reconstruction[C]// Symposium on Geometry Processing, The IEEE Symposium on Parallel and Large-data Visualization and Graphics. USA: IEEE, 2006: 61-70.
[12] Dey TK, Goswami S.Tight cocone: a watertight surface reconstructor[J]. Journal of Computing and Information Science in Engineering (S1002-4688), 2003, 3(4): 302-307.
[13] Dey TK, Goswami S.Provable surface reconstruction from noisy samples[J]. Computational Geometry (S1003-2254), 2006, 35(1/2): 124-141.
[14] Dey TK, Giesen J, Hudson J.Delaunay based shape reconstruction from large data[C]// The Proceeding of The IEEE Symposium on Parallel and Large-data Visualization and Graphics. USA: IEEE, 2001: 19-27.
[15] Amenda N, Choi S, Kolluri R.The power crust[C]// The Proceeding of the ACM Symposium on Solid Modeling and Applications. USA: ACM, 2001: 249-60.
[16] Cohen-Steiner D, Da F.A greedy Delaunay-based surface reconstruction algorithm[J]. Visual Computer (S1002-3386), 2004, 20(1): 4-16.
[17] Gopi M, Krishnan S, Silva C.Surface reconstruction using lower dimensional localized Delaunay triangulation[J]. The Proceeding of Eurographics (S1000-2432), 2000, 19(3): 467-78.
[18] Huang J, Menq CH.Combinatorial manifold mesh reconstruction and optimization from unorganized points with arbitrary topology[J]. Computer Aided Design (S1001-4432), 2002, 34(2): 149-65.