Robust reconstruction of watertight 3D models from non-uniformly sampled point clouds without normal information

ABSTRACT

We present a new volumetric method for reconstructing watertight triangle meshes from arbitrary, unoriented point clouds. While previous techniques usually reconstruct surfaces as the zero level-set of a signed distance function, our method uses an unsigned distance function and hence does not require any information about the local surface orientation. Our algorithm estimates local surface confidence values within a dilated crust around the input samples. The surface which maximizes the global confidence is then extracted by computing the minimum cut of a weighted spatial graph structure. We present an algorithm, which efficiently converts this cut into a closed, manifold triangle mesh with a minimal number of vertices. The use of an unsigned distance function avoids the topological noise artifacts caused by misalignment of 3D scans, which are common to most volumetric reconstruction techniques. Due to a hierarchical approach our method efficiently produces solid models of low genus even for noisy and highly irregular data containing large holes, without loosing fine details in densely sampled regions. We show several examples for different application settings such as model generation from raw laser-scanned data, image-based 3D reconstruction, and mesh repair.

REFERENCES

• 1: Marc Alexa , Johannes Behr , Daniel Cohen-Or , Shachar Fleishman , David Levin , Claudio T. Silva, Point set surfaces, Proceedings of the conference on Visualization '01, October 21-26, 2001, San Diego, California
• 2: Nina Amenta , Marshall Bern , Manolis Kamvysselis, A new Voronoi-based surface reconstruction algorithm, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.415-421, July 1998 [doi>10.1145/280814.280947]
• 3: Nina Amenta , Sunghee Choi , Ravi Krishna Kolluri, The power crust, Proceedings of the sixth ACM symposium on Solid modeling and applications, p.249-266, May 2001, Ann Arbor, Michigan, United States [doi>10.1145/376957.376986]
• 4: {BC02} Boissonnat J.-D., Cazals F.: Smooth surface reconstruction via natural neighbour interpolation of distance functions. Comput. Geom. 22, 1--3 (2002), 185--203.
• 5: Yuri Boykov , Vladimir Kolmogorov, Computing Geodesics and Minimal Surfaces via Graph Cuts, Proceedings of the Ninth IEEE International Conference on Computer Vision, p.26, October 13-16, 2003
• 6: Yuri Boykov , Vladimir Kolmogorov, An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Vision, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.26 n.9, p.1124-1137, September 2004 [doi>10.1109/TPAMI.2004.60]
• 7: Fausto Bernardini , Joshua Mittleman , Holly Rushmeier , Cláudio Silva , Gabriel Taubin, The Ball-Pivoting Algorithm for Surface Reconstruction, IEEE Transactions on Visualization and Computer Graphics, v.5 n.4, p.349-359, October 1999 [doi>10.1109/2945.817351 ]
• 8: {BNK02} Borodin P., Novotni M., Klein R.: Progressive gap closing for mesh repairing. In Advances in Modelling, Animation and Rendering, Vince J., Earnshaw R., (Eds.). Springer Verlag, July 2002, pp. 201--213.
• 9: Stephan Bischoff , Darko Pavic , Leif Kobbelt, Automatic restoration of polygon models, ACM Transactions on Graphics (TOG), v.24 n.4, p.1332-1352, October 2005 [doi>10.1145/1095878.1095883]
• 10: J. C. Carr , R. K. Beatson , J. B. Cherrie , T. J. Mitchell , W. R. Fright , B. C. McCallum , T. R. Evans, Reconstruction and representation of 3D objects with radial basis functions, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.67-76, August 2001 [doi>10.1145/383259.383266]
• 11: Brian Curless , Marc Levoy, A volumetric method for building complex models from range images, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.303-312, August 1996 [doi>10.1145/237170.237269]
• 12: Tamal K. Dey , Samrat Goswami, Tight cocone: a water-tight surface reconstructor, Proceedings of the eighth ACM symposium on Solid modeling and applications, June 16-20, 2003, Seattle, Washington, USA [doi>10.1145/781606.781627]
• 13: {DMGL02} Davis J., Marschner S. R., Garr M., Levoy M.: Filling holes in complex surfaces using volumetric diffusion. In 3DPVT (2002), pp. 428--438.
• 14: Mathieu Desbrun , Mark Meyer , Peter Schröder , Alan H. Barr, Implicit fairing of irregular meshes using diffusion and curvature flow, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.317-324, July 1999 [doi>10.1145/311535.311576]
• 15: {EBV05} Esteve J., Brunet P., Vinacua A.: Approximation of a variable density cloud of points by shrinking a discrete membrane. Comput. Graph. Forum 24, 2 (2005), 791--807.
• 16: Jihad El-Sana , Amitabh Varshney, Controlled simplification of genus for polygonal models, Proceedings of the 8th conference on Visualization '97, p.403-ff., October 18-24, 1997, Phoenix, Arizona, United States
• 17: Shachar Fleishman , Daniel Cohen-Or , Cláudio T. Silva, Robust moving least-squares fitting with sharp features, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 18: Igor Guskov , Zoë J. Wood, Topological noise removal, No description on Graphics interface 2001, p.19-26, June 07-09, 2001, Ottawa, Ontario, Canada
• 19: Hugues Hoppe , Tony DeRose , Tom Duchamp , John McDonald , Werner Stuetzle, Surface reconstruction from unorganized points, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.71-78, July 1992
• 20: Alexander Hornung , Leif Kobbelt, Hierarchical Volumetric Multi-view Stereo Reconstruction of Manifold Surfaces based on Dual Graph Embedding, Proceedings of the 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, p.503-510, June 17-22, 2006 [doi>10.1109/CVPR.2006.135]
• 21: Tao Ju, Robust repair of polygonal models, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 22: Michael Kazhdan, Reconstruction of solid models from oriented point sets, Proceedings of the third Eurographics symposium on Geometry processing, July 04-06, 2005, Vienna, Austria
• 23: Vladimir Kolmogorov , Yuri Boykov, What Metrics Can Be Approximated by Geo-Cuts, Or Global Optimization of Length/Area and Flux, Proceedings of the Tenth IEEE International Conference on Computer Vision (ICCV'05) Volume 1, p.564-571, October 17-20, 2005 [doi>10.1109/ICCV.2005.252]
• 24: William E. Lorensen , Harvey E. Cline, Marching cubes: A high resolution 3D surface construction algorithm, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.163-169, July 1987
• 25: Herve Lombaert , Yiyong Sun , Leo Grady , Chenyang Xu, A Multilevel Banded Graph Cuts Method for Fast Image Segmentation, Proceedings of the Tenth IEEE International Conference on Computer Vision (ICCV'05) Volume 1, p.259-265, October 17-20, 2005 [doi>10.1109/ICCV.2005.13]
• 26: Boris Mederos , Nina Amenta , Luiz Velho , Luiz Henrique de Figueiredo, Surface reconstruction from noisy point clouds, Proceedings of the third Eurographics symposium on Geometry processing, July 04-06, 2005, Vienna, Austria
• 27: Fakir S. Nooruddin , Greg Turk, Simplification and Repair of Polygonal Models Using Volumetric Techniques, IEEE Transactions on Visualization and Computer Graphics, v.9 n.2, p.191-205, April 2003 [doi>10.1109/TVCG.2003.1196006]
• 28: Yutaka Ohtake , Alexander Belyaev , Marc Alexa , Greg Turk , Hans-Peter Seidel, Multi-level partition of unity implicits, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 29: 3D Scattered Data Approximation with Adaptive Compactly Supported Radial Basis Functions, Proceedings of the Shape Modeling International 2004, p.31-39, June 07-09, 2004 [doi>10.1109/SMI.2004.1]
• 30: {PMG04} Pauly M., Mitra N., Guibas L.: Uncertainty and variability in point cloud surface data. In Eurographics Symposium on Point-Based Graphics (2004).
• 31: Steven M. Seitz , Charles R. Dyer, Photorealistic Scene Reconstruction by Voxel Coloring, Proceedings of the 1997 Conference on Computer Vision and Pattern Recognition (CVPR '97), p.1067, June 17-19, 1997
• 32: Carlos E. Scheidegger , Shachar Fleishman , Cláudio T. Silva, Triangulating point set surfaces with bounded error, Proceedings of the third Eurographics symposium on Geometry processing, July 04-06, 2005, Vienna, Austria
• 33: {SLS*06} Sharf A., Lewiner T., Shamir A., Kobbelt L., Cohen-Or D.: Competing fronts for coarse-to-fine surface reconstruction. In Eurographics (2006), p. to appear.
• 34: G. Vogiatzis , P. H. S. Torr , R. Cipolla, Multi-View Stereo via Volumetric Graph-Cuts, Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05) - Volume 2, p.391-398, June 20-26, 2005 [doi>10.1109/CVPR.2005.238]
• 35: Zoë Wood , Hugues Hoppe , Mathieu Desbrun , Peter Schröder, Removing excess topology from isosurfaces, ACM Transactions on Graphics (TOG), v.23 n.2, p.190-208, April 2004 [doi>10.1145/990002.990007]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling