skip to main content
10.5555/1555880.1555893guideproceedingsArticle/Chapter ViewAbstractPublication PagesgiConference Proceedingsconference-collections
research-article
Free access

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

Published: 25 May 2009 Publication History

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]
A. Adamson and M. Alexa. Approximating bounded, non-orientable surfaces from points. In Shape Modeling International, pages 243--252, 2004.
[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]
M. Alexa, J. Behr, D. Cohen-Or, S. Fleishman, D. Levin, and C. T. Silva. Point set surfaces. In IEEE Visualization, pages 21--28, 2001.
[4]
R. Allègre, R. Chaine, and S. Akkouche. A streaming algorithm for surface reconstruction. In Symposium on Geometry Processing, pages 79--88, 2007.
[5]
N. Amenta, S. Choi, and R. Kolluri. The power crust. In Symposium on Solid Modeling, pages 249--260, 2001.
[6]
N. Amenta and Y. J. Kil. Defining point-set surfaces. ACM Transactions on Graphics, 23(3):264--270, 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]
M. Bolitho, M. Kazhdan, R. Burns, and H. Hoppe. Multilevel streaming for out-of-core surface reconstruction. In Symposium on Geometry processing, pages 69--78, 2007.
[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, and T. R. Evans. Reconstruction and representation of 3D objects with radial basis functions. In Proc. ACM SIGGRAPH, pages 67--76, 2001.
[11]
P. Cignoni, C. Montani, C. Rocchini, and R. Scopigno. External memory management and simplification of huge meshes. IEEE Transactions on Visualization and Computer Graphics, 9(4):525--537, 2003.
[12]
B. Curless and M. Levoy. A volumetric method for building complex models from range images. In Proc. ACM SIGGRAPH, pages 303--312, 1996.
[13]
T. K. Dey, J. Giesen, and J. Hudson. Delaunay based shape reconstruction from large data. In IEEE Symposium on parallel and large-data visualization and graphics, pages 19--27, 2001.
[14]
T. K. Dey and S. Goswami. Provable surface reconstruction from noisy samples. Computational Geometry Theory and Applications, 35(1):124--141, 2006.
[15]
T. K. Dey and J. Sun. An adaptive MLS surface for reconstruction with guarantees. In Symposium on Geometry processing, page 43, 2005.
[16]
V. Fiorin, P. Cignoni, and R. Scopigno. Out-of-core MLS reconstruction. In CGIM, pages 27--34, 2007.
[17]
S. Fleishman, D. Cohen-Or, and C. T. Silva. Robust moving least-squares fitting with sharp features. ACM Transactions on Graphics, 24(3):544--552, 2005.
[18]
G. Guennebaud and M. H. Gross. Algebraic point set surfaces. ACM Transactions on Graphics, 26(3):23, 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]
M. Kazhdan. Reconstruction of solid models from oriented point sets. In Symposium on Geometry Processing, pages 73--82, 2005.
[21]
M. Kazhdan, M. Bolitho, and H. Hoppe. Poisson surface reconstruction. In Symposium on Geometry Processing, pages 61--70, 2006.
[22]
M. Kazhdan, A. Klein, K. Dalal, and H. Hoppe. Unconstrained isosurface extraction on arbitrary octrees. In Symposium on Geometry Processing, pages 125--133, 2007.
[23]
R. Kolluri, Provably good moving least squares. ACM Transactions on Algorithms, 4(2):1--25, 2008.
[24]
R. Kolluri, J. R. Shewchuk, and J. F. O'Brien. Spectral surface reconstruction from noisy point clouds. In Symposium on Geometry Processing, pages 11--21, 2004.
[25]
D. Levin. Geometric Modeling for Scientific Visualization, chapter Mesh-independent surface interpolation. Springer, 2003.
[26]
P. Lindstrom. Out-of-core simplification of large polygonal models. In Proc. ACM SIGGRAPH, pages 259--262, 2000.
[27]
J. Manson, G. Petrova, and S. Schaefer. Streaming surface reconstruction using wavelets. In Symposium on Geometry processing, 2008.
[28]
B. Mederos, N. Amenta, L. Velho, and L. H. de Figueiredo. Surface reconstruction for noisy point clouds. In Symposium on Geometry Processing, pages 53--62, 2005.
[29]
Y. Ohtake, A. Belyaev, M. Alexa, G. Turk, and H.-P. Seidel. Multilevel partition of unity implicits. ACM Transactions on Graphics, 22(3):463--470, 2003.
[30]
Y. Ohtake, A. Belyaev, and H.-P. Seidel. A multi-scale approach to 3D scattered data interpolation with compactly supported basis functions. In Shape Modeling International, page 153, Washington, DC, USA, 2003. IEEE Computer Society.
[31]
R. Pajarola. Stream-processing points. In IEEE Visualization, page 31, 2005.
[32]
M. Pauly, M. H. Gross, and L. Kobbelt. Efficient simplification of point-sampled surfaces. In IEEE Visualization, pages 163--170, 2002.
[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.

Cited By

View all
  • (2017)Processing Large Geometric Datasets in Distributed EnvironmentsLNCS on Transactions on Computational Science XXIX - Volume 1022010.1007/978-3-662-54563-8_6(97-120)Online publication date: 1-Jan-2017
  • (2015)Mont’e ScanJournal on Computing and Cultural Heritage 10.1145/26448238:1(1-23)Online publication date: 25-Feb-2015
  • (2015)A Fast and Robust Framework for Semiautomatic and Automatic Registration of Photographs to 3D GeometryJournal on Computing and Cultural Heritage 10.1145/26295147:4(1-23)Online publication date: 11-Feb-2015
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image Guide Proceedings
GI '09: Proceedings of Graphics Interface 2009
May 2009
257 pages
ISBN:9781568814704

Sponsors

  • The Canadian Human-Computer Communications Society / Société Canadienne du Dialogue Humaine Machine (CHCCS/SCDHM)

Publisher

Canadian Information Processing Society

Canada

Publication History

Published: 25 May 2009

Qualifiers

  • Research-article

Acceptance Rates

GI '09 Paper Acceptance Rate 28 of 77 submissions, 36%;
Overall Acceptance Rate 206 of 508 submissions, 41%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)22
  • Downloads (Last 6 weeks)3
Reflects downloads up to 17 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2017)Processing Large Geometric Datasets in Distributed EnvironmentsLNCS on Transactions on Computational Science XXIX - Volume 1022010.1007/978-3-662-54563-8_6(97-120)Online publication date: 1-Jan-2017
  • (2015)Mont’e ScanJournal on Computing and Cultural Heritage 10.1145/26448238:1(1-23)Online publication date: 25-Feb-2015
  • (2015)A Fast and Robust Framework for Semiautomatic and Automatic Registration of Photographs to 3D GeometryJournal on Computing and Cultural Heritage 10.1145/26295147:4(1-23)Online publication date: 11-Feb-2015
  • (2013)Fast in-place binning of laser range-scanned point setsJournal on Computing and Cultural Heritage 10.1145/2499931.24999356:3(1-19)Online publication date: 5-Aug-2013
  • (2012)Scale robust multi view stereoProceedings of the 12th European conference on Computer Vision - Volume Part III10.1007/978-3-642-33712-3_29(398-411)Online publication date: 7-Oct-2012
  • (2009)A point-based system for local and remote exploration of dense 3D scanned modelsProceedings of the 10th International conference on Virtual Reality, Archaeology and Cultural Heritage10.5555/2384470.2384475(25-32)Online publication date: 22-Sep-2009

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media