skip to main content
10.5555/1281991.1282002acmotherconferencesArticle/Chapter ViewAbstractPublication PagessgpConference Proceedingsconference-collections
Article

A streaming algorithm for surface reconstruction

Published: 04 July 2007 Publication History

Abstract

We present a streaming algorithm for reconstructing closed surfaces from large non-uniform point sets based on a geometric convection technique. Assuming that the sample points are organized into slices stacked along one coordinate axis, a triangle mesh can be efficiently reconstructed in a streamable layout with a controlled memory footprint. Our algorithm associates a streaming 3D Delaunay triangulation data-structure with a multilayer version of the geometric convection algorithm. Our method can process millions of sample points at the rate of 50k points per minute with 350 MB of main memory.

References

[1]
{ACA06} Allègre R., Chaine R., Akkouche S.: A Dynamic Surface Reconstruction Framework for Large Unstructured Point Sets. In Proc. IEEE/Eurographics Symposium on Point-Based Graphics (2006), pp. 17--26. 7, 8
[2]
{ACA07} Allègre R., Chaine R., Akkouche S.: A Flexible Framework for Surface Reconstruction from Large Point Sets. Computers & Graphics 31, 2 (2007). 8
[3]
{Ame99} Amenta N.: The Crust Algorithm for 3D Surface Reconstruction. In Proc. Symposium on Computational Geometry (1999), pp. 423--424. 2, 3, 10
[4]
{BHGS06} Boubekeur T., Heidrich W., Granier X., Schlick C.: Volume-Surface Trees. In Proc. Eurographics (2006), pp. 399--406. 7
[5]
{BMR*99} Bernardini F., Mittleman J., Rushmeier H., Silva C., Taubin G.: The Ball-Pivoting Algorithm for Surface Reconstruction. IEEE Transactions on Visualization and Computer Graphics 5, 4 (1999), 349--359. 1, 7
[6]
{CG06} Cazals F., Giesen J.: Delaunay Triangulation based Surface Reconstruction: Ideas and Algorithms. In Effective Computational Geometry of Curves and Surfaces (2006), Boissonnat J.-D., Teillaud M., (Eds.). 1, 2
[7]
{CGA} http://www.cgal.org. 6
[8]
{Cha03} Chaine R.: A Geometric Convection Approach of 3-D Reconstruction. In Proc. Symposium on Geometry Processing (2003), pp. 218--229. 2, 7
[9]
{CL96} Curless B., Levoy M.: A Volumetric Method for Building Complex Models from Range Images. Computer Graphics (Proc. SIGGRAPH) 30 (1996), 303--312. 7
[10]
{Dev02} Devillers O.: The Delaunay hierarchy. Internat. J. Found. Comput. Sci. 13, 2 (2002), 163--180. 8
[11]
{Dey04} Dey T. K.: Curve and surface reconstruction. Chapter in Handbook of Discrete and Computational Geometry, Goodman and O' Rourke eds., CRC press, 2nd edition (2004). 1
[12]
{DGH01} Dey T. K., Giesen J., Hudson J.: Delaunay-based Shape Reconstruction from Large Data. In Proc. IEEE Symposium in Parallel and Large Data Visualization and Graphics (2001), pp. 19--27.
[13]
{DT03} Devillers O., Teillaud M.: Perturbations and Vertex Removal in a 3D Delaunay Triangulation. In Proc. ACM-SIAM Symposium on Discrete Algorithms (2003), pp. 313--319. 5
[14]
{Ede02} Edelsbrunner H.: Surface Reconstruction by Wrapping Finite Point Sets in Space. In Ricky Pollack and Eli Goodman Festscrift (2002), Aronov B., Basu S., Pach J., M. Sharir S.-V., (Eds.), Springer-Verlag, pp. 379--404. 2
[15]
{GJ03} Giesen J., John M.: The Flow Complex: A Data Structure for Geometric Modeling. In Proc. ACM-SIAM Symposium on Discrete Algorithms (2003), pp. 285--294. 2
[16]
{GKS00} Gopi M., Krishnan S., Silva C. T.: Surface Reconstruction based on Lower Dimensional Localized Delaunay Triangulation. In Proc. Eurographics (2000), pp. 363--371. 1
[17]
{IL05} Isenburg M., Lindstrom P.: Streaming Meshes. In Proc. IEEE Visualization Conference (2005), pp. 231--238. 1, 6
[18]
{ILGS03} Isenburg M., Lindstrom P., Gumhold S., Snoeyink J.: Large Mesh Simplification using Processing Sequences. In Proc. IEEE Visualization (2003), pp. 465--472. 1
[19]
{ILS05} Isenburg M., Lindstrom P., Snoeyink J.: Streaming Compression of Triangle Meshes. In Proc. Symposium on Geometry Processing (2005), pp. 111--118. 1
[20]
{ILSS06} Isenburg M., Liu Y., Shewchuk J., Snoeyink J.: Streaming Computation of Delaunay Triangulations. ACM Transactions on Graphics (Proc. SIGGRAPH) 25, 3 (2006), 1049--1056. 1, 3
[21]
{KBH} Kazhdan M., Bolitho M., Hoppe H.: Poisson surface reconstruction. In Proc. Symposium on Geometry Processing, pp. 61--70. 7
[22]
{Kol05} Kolluri R.: Provably good moving least squares. In Proc. ACM-SIAM Symposium on Discrete Algorithms (2005), pp. 1008--1017.
[23]
{LJ05} Liu Y., J. Snoeyink: A comparison of five implementations of 3D Delaunay tessellation. In Combinatorial and Computational Geometry (2005), Goodman J. E., Pach J., Welzl E., (Eds.), vol. 52 of MSRI Publications, Cambridge, pp. 435--453. 1
[24]
{OBS05} Ohtake Y., Belyaev A. G., Seidel H.-P.: An integrating approach to meshing scattered point data. In Proc. ACM Symposium on Solid and Physical Modeling (2005), pp. 61--69. 1, 7, 8
[25]
{Paj05} Pajarola R.: Stream-Processing Points. In Proc. IEEE Visualization (2005), pp. 239--246. 1
[26]
{RCG*04} Rocchini C., Cignoni P., Ganovelli F., Montani C., Pingi P., Scopigno R.: The Marching Intersections Algorithm for Merging Range Images. The Visual Computer 20, 2--3 (2004), 149--164. 7
[27]
{SFS05} Scheidegger C. E., Fleishman S., Silva C. T.: Triangulating point set surfaces with bounded error. In Proc. Symposium on Geometry Processing (2005), pp. 63--72. 7, 8
[28]
{She97} Shewchuk J. R.: Delaunay Refinement Mesh Generation. PhD thesis, Technical Report CMU-CS-97-137, School of Computer Science, Carnegie Mellon University, Pittsburgh, Pennsylvania, 1997. 4
[29]
{WK03} Wu J., Kobbelt L.: A Stream Algorithm for the Decimation of Massive Meshes. In Proc. Graphics Interface (2003), pp. 185--192. 1
[30]
{ZOF01} Zhao H.-K., Osher S., Fedkiw R.: Fast Surface Reconstruction using the Level Set Method. In Proc. IEEE Workshop on Variational and Level Set Methods in Computer Vision (VLSM) (2001), pp. 194--202. 2

Cited By

View all
  • (2009)Fast low-memory streaming MLS reconstruction of point-sampled surfacesProceedings of Graphics Interface 200910.5555/1555880.1555893(15-22)Online publication date: 25-May-2009
  • (2008)Streaming surface reconstruction using waveletsProceedings of the Symposium on Geometry Processing10.5555/1731309.1731324(1411-1420)Online publication date: 2-Jul-2008

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Other conferences
SGP '07: Proceedings of the fifth Eurographics symposium on Geometry processing
July 2007
273 pages
ISBN:9783905673463

Sponsors

  • EUROGRAPHICS: The European Association for Computer Graphics

Publisher

Eurographics Association

Goslar, Germany

Publication History

Published: 04 July 2007

Check for updates

Author Tags

  1. geometric convection
  2. streaming Delaunay triangulation
  3. streaming surface reconstruction

Qualifiers

  • Article

Conference

SGP '07
Sponsor:
  • EUROGRAPHICS
SGP '07: Geometry processing
July 4 - 6, 2007
Barcelona, Spain

Acceptance Rates

SGP '07 Paper Acceptance Rate 21 of 74 submissions, 28%;
Overall Acceptance Rate 64 of 240 submissions, 27%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 18 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2009)Fast low-memory streaming MLS reconstruction of point-sampled surfacesProceedings of Graphics Interface 200910.5555/1555880.1555893(15-22)Online publication date: 25-May-2009
  • (2008)Streaming surface reconstruction using waveletsProceedings of the Symposium on Geometry Processing10.5555/1731309.1731324(1411-1420)Online publication date: 2-Jul-2008

View Options

View options

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media