Surface Reconstruction from Unorganized Points Using Graph Cut

Abstract:

A new surface reconstruction algorithm is presented for unorganized 3D points in this work. By properly building a graph, the surface is shown to correspond to the minimum s-t cut of the graph. In addition, since our proposed algorithm is based on the three dimensional Delaunay triangulation, it is guaranteed the reconstructed surface is composed by the patches with fine shapes in the Delaunay tetrahedra. Besides, the reconstructed surface can interpolate the input data and can also decimate the outliers automatically through proper adjusting the parameters. The experiments indicate our algorithm is practical and easy to implement.

• Periodical: Advanced Materials Research (Volumes 476-478)
• Pages: 587-591
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.476-478.587
• Online since: February 2012
• Authors: Xiao Ming Wang, Li Min Shi
• Keywords: Graph Cuts, Scattered Points, Surface Reconstruction

References

[1] J. D. Boissonnat. Geometric structures for three dimensional shape representation[J]. ACM Transaction on Graphics, 1984, 3(4): 266–286.

DOI: 10.1145/357346.357349

[2] H. Edelsbrunner and E. P. Mücke. Three-dimensional alpha shapes[J]. ACM Transaction on Graphics, 1994, 13(1): 43–72.

DOI: 10.1145/174462.156635

[3] C. Bajaj, F. Bernardini and G. Xu. Automatic reconstruction of surfaces and scalar fields from 3D scans[C] //Proc. ACM SIGGRAPH, 1995: 109–118.

DOI: 10.1145/218380.218424

[4] Hoppe H. Surface reconstruction from unorganized points[C] //Proc. ACM SIGGRAPH, chicago, 1992: 71-78.

DOI: 10.1145/142920.134011

[5] WHITAKER R. T.: A Level-Set Approach to 3D Reconstruction from Range Data. International Journal of Computer Vision 29, 3 (1998), 203–231.

[6] ZHAO H.-K., OSHER S., FEDKIW R.: Fast Surface Reconstruction Using the Level Set Method. In First IEEE Workshop on Variational and Level Set Methods (2001), p.194–202.

DOI: 10.1109/vlsm.2001.938900

[7] N. Amenta, M. Bern and M. Kamvysselis. A new Voronoi-based surface reconstruction algorithm[C] . Proceedings of ACM SIGGRAPH, 1998: 415-421.

DOI: 10.1145/280814.280947

[8] N. Amenta, S. Choi and R. K. Kolluri. The power crust [C] //Proc. 6th Annu. Sympos. Solid Modeling Applications, 2001: 249–260.

[9] Tamal K. Dey, Samrat Goswami. Tight Cocoon: A Water-tight Surface reconstructor[C].

[10] Kolluri, R., Shewchuk, J. R. and O'Brien, J. F. Spectral surface reconstruction from noisy point clouds[C]. Proc. Eurographics Symposium on Geometry Processing, 2004: 11-21.

DOI: 10.1145/1057432.1057434

[11] L.Ford, D.Fulkerson. Flows in Networks. Princeton University Press, 1962.

[12] Tamal K.Dey, Gang Li, Jian sun. Normal estimation for point clouds: a comparison study for a voronoi based method[C] //Proc. Eurographics Symposium on Point-Based Graphics, 2005: 39-46.

DOI: 10.1109/pbg.2005.194062

[13] Mark Pauly, Richard Keiser, etc. Shape Modeling with Point-Sampled Geometry[C]. Proc. ACM SIGGRAPH, 2003: 641-650.

DOI: 10.1145/1201775.882319

[14] Yuti Boykov, Vladimir Kolmogrov. An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision[J]. IEEE Transactions on PAMI, 2004, 26(9): 1124-1137.

DOI: 10.1109/tpami.2004.60

[15] Information on http://www.cgal.org