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.