Improved Pivoting Ball Algorithm for Nonuniform Point Cloud Data

Abstract

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

CLC Number:

TP391.9

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.

References

[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.