Multi-level streaming for out-of-core surface reconstruction

Multi-level streaming for out-of-core surface reconstruction
Matthew Bolitho, Michael Kazhdan, Randal Burns, Hugues Hoppe.
Symposium on Geometry Processing 2007.
Out-of-core solution of huge Poisson system to reconstruct 3D scans.
Abstract: Reconstruction of surfaces from huge collections of scanned points often requires out-of-core techniques, and most such techniques involve local computations that are not resilient to data errors. We show that a Poisson-based reconstruction scheme, which considers all points in a global analysis, can be performed efficiently in limited memory using a streaming framework. Specifically, we introduce a multilevel streaming representation, which enables efficient traversal of a sparse octree by concurrently advancing through multiple streams, one per octree level. Remarkably, for our reconstruction application, a sufficiently accurate solution to the global linear system is obtained using a single iteration of cascadic multigrid, which can be evaluated within a single multi-stream pass. We demonstrate scalable performance on several large datasets.
Hindsights: The streaming algorithm in this paper implements a prolongation-only (i.e. cascadic) multigrid solver over an adaptive 3D octree. In our ISVC 2009 paper, we apply domain decomposition to parallelize this cascadic multigrid computation. Our SIGGRAPH 2008 paper achieves a full V-cycle multigrid as a streaming algorithm, although over a regular grid rather than an adaptive quadtree.
Eurographics Association Copyright Notice
Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than Eurographics must be honored.