Fast low-memory streaming MLS reconstruction of point-sampled surfaces

ABSTRACT

We present a simple and efficient method for reconstructing triangulated surfaces from massive oriented point sample datasets. The method combines streaming and parallelization, moving least-squares (MLS) projection, adaptive space subdivision, and regularized isosurface extraction. Besides presenting the overall design and evaluation of the system, our contributions include methods for keeping in-core data structures complexity purely locally output-sensitive and for exploiting both the explicit and implicit data produced by a MLS projector to produce tightly fitting regularized triangulations using a primal isosurface extractor. Our results show that the system is fast, scalable, and accurate. We are able to process models with several hundred million points in about an hour and outperform current fast streaming reconstructors in terms of geometric accuracy.

REFERENCES

• 1: Approximating Bounded, Non-Orientable Surfaces from Points, Proceedings of the Shape Modeling International 2004, p.243-252, June 07-09, 2004 [doi>10.1109/SMI.2004.13]
• 2: M. Alexa and A. Adamson. On normals and projection operators for surfaces defined by point sets. In Symposium on Point-Based Graphics, 2004.
• 3: 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
• 4: Rémi Allègre , Raphaëlle Chaine , Samir Akkouche, A streaming algorithm for surface reconstruction, Proceedings of the fifth Eurographics symposium on Geometry processing, July 04-06, 2007, Barcelona, Spain
• 5: 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]
• 6: Nina Amenta , Yong Joo Kil, Defining point-set surfaces, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 7: N. Aspert, D. Santa-cruz, and T. Ebrahimi. M.E.S.H.: Measuring errors between surfaces using the hausdorff distance. In IEEE International Conference on Multimedia, pages 705--708, 2002.
• 8: Matthew Bolitho , Michael Kazhdan , Randal Burns , Hugues Hoppe, Multilevel streaming for out-of-core surface reconstruction, Proceedings of the fifth Eurographics symposium on Geometry processing, July 04-06, 2007, Barcelona, Spain
• 9: T. Boubekeur, W. Heidrich, X. Granier, and C. Schlick. Volume-surface trees. Computer Graphics Forum, 25(3):399--406, 2006.
• 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: Paolo Cignoni , Claudio Montani , Claudio Rocchini , Roberto Scopigno, External Memory Management and Simplification of Huge Meshes, IEEE Transactions on Visualization and Computer Graphics, v.9 n.4, p.525-537, October 2003 [doi>10.1109/TVCG.2003.1260746]
• 12: 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]
• 13: Tamal K. Dey , Joachim Giesen , James Hudson, Delaunay based shape reconstruction from large data, Proceedings of the IEEE 2001 symposium on parallel and large-data visualization and graphics, October 22-23, 2001, San Diego, California
• 14: Tamal K. Dey , Samrat Goswami, Provable surface reconstruction from noisy samples, Computational Geometry: Theory and Applications, v.35 n.1, p.124-141, August 2006 [doi>10.1016/j.comgeo.2005.10.006]
• 15: Tamal K. Dey , Jian Sun, An adaptive MLS surface for reconstruction with guarantees, Proceedings of the third Eurographics symposium on Geometry processing, July 04-06, 2005, Vienna, Austria
• 16: V. Fiorin, P. Cignoni, and R. Scopigno. Out-of-core MLS reconstruction. In CGIM, pages 27--34, 2007.
• 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: Gaël Guennebaud , Markus Gross, Algebraic point set surfaces, ACM Transactions on Graphics (TOG), v.26 n.3, July 2007
• 19: C.-C. Ho, F.-C. Wu, B.-Y. Chen, Y.-Y. Chuang, and M. Ouhyoung. Cubical marching squares: Adaptive feature preserving surface extraction from volume data. Computer Graphics Forum, 24(3):537--546, 2005.
• 20: 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
• 21: Michael Kazhdan , Matthew Bolitho , Hugues Hoppe, Poisson surface reconstruction, Proceedings of the fourth Eurographics symposium on Geometry processing, June 26-28, 2006, Cagliari, Sardinia, Italy
• 22: Michael Kazhdan , Allison Klein , Ketan Dalal , Hugues Hoppe, Unconstrained isosurface extraction on arbitrary octrees, Proceedings of the fifth Eurographics symposium on Geometry processing, July 04-06, 2007, Barcelona, Spain
• 23: Ravikrishna Kolluri, Provably good moving least squares, ACM Transactions on Algorithms (TALG), v.4 n.2, p.1-25, May 2008 [doi>10.1145/1361192.1361195]
• 24: Ravikrishna Kolluri , Jonathan Richard Shewchuk , James F. O'Brien, Spectral surface reconstruction from noisy point clouds, Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing, July 08-10, 2004, Nice, France [doi>10.1145/1057432.1057434]
• 25: D. Levin. Geometric Modeling for Scientific Visualization, chapter Mesh-independent surface interpolation. Springer, 2003.
• 26: Peter Lindstrom, Out-of-core simplification of large polygonal models, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.259-262, July 2000 [doi>10.1145/344779.344912]
• 27: J. Manson, G. Petrova, and S. Schaefer. Streaming surface reconstruction using wavelets. In Symposium on Geometry processing, 2008.
• 28: 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
• 29: 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
• 30: Yutaka Ohtake , Alexander Belyaev , Hans-Peter Seidel, A Multi-scale Approach to 3D Scattered Data Interpolation with Compactly Supported Basis Functions, Proceedings of the Shape Modeling International 2003, p.153, May 12-15, 2003
• 31: R. Pajarola. Stream-processing points. In IEEE Visualization, page 31, 2005.
• 32: Mark Pauly , Markus Gross , Leif P. Kobbelt, Efficient simplification of point-sampled surfaces, Proceedings of the conference on Visualization '02, October 27-November 01, 2002, Boston, Massachusetts
• 33: P. Reuter, P. Joyot, J. Trunzler, T. Boubekeur, and C. Schlick. Surface reconstruction with enriched reproducing kernel particle approximation. In Symposium on Point-Based Graphics, pages 79--88, 2005.
• 34: S. Schaefer and J. Warren. Dual marching cubes: Primal contouring of dual grids. Computer Graphics Forum, 24(2):195--203, 2005.
• 35: G. M. Treece, R. W. Prager, and A. H. Gee. Regularised marching tetrahedra: improved iso-surface extraction. Computers & Graphics, 23(4):583--598, 1999.

INDEX TERMS

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