Multi-level streaming for out-of-core surface reconstruction
Symposium on Geometry Processing 2007.
Out-of-core solution of huge Poisson system to reconstruct 3D scans.
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.
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.