Advances in 3D scanning technology have provided an essential means for acquiring information about surfaces and shapes in the real world and have played an important role in fields ranging from the humanities (e.g. cultural preservation) to the sciences (e.g. medical imaging). This research contributes to this trend by developing algorithms for reconstructing 3D models from the raw data returned by today's acquisition modalities. The challenges focused on in this work are two-fold: First, to be useful in practice, the algorithms must be able to process huge datasets, often too large to be able to fit into the working memory of an application. Second, the algorithms must be designed to be versatile, capable of adapting to the varying and non-uniform data returned by the different scanners.
To address these challenges, the investigators reduce the problem of surface reconstruction to the solution of a Poisson equation which can be solved over an octree adapted to the scanned data. Specifically, this research makes three separate contributions. First, it describes a novel algorithm for solving the global Poisson system in a local manner, providing a solver that only requires a small subset of the system to be maintained in working memory at any given time. Second, it presents a novel data-structure that enables streaming traversal through an octree, making it possible to process high-resolution data that is too large to fit into memory. And third, using a finite elements formulation, it generalizes a method for model fitting that allows functions to be fit to data sampled using non-point primitives, extending the breadth of acquisition modalities supported by the reconstruction algorithm.
The goal of this project was to design a program that takes as its input a set of 3D points, sampled from a model, and outputs the surface fitting the points. This task of surface reconstruction is fundamental in transforming the points returned by commodity scanners into a virtual model that can be rendered, explored, and interacted with on a computer. The project successfully met its goals, developing the Poisson Reconstruction technique, and resulted in the following outcomes: Research on Poisson Reconstruction has resulted in 5 publications directly related to reconstruction, as well 5 other publications in related domains of image- and geometry-processing, all in top peer-reviewed journals. The effectiveness of the Poisson Reconstruction method, combined with its ease of use have made it a standard yard-stick against which subsequent reconstruction methods compare themselves. The seminal work related to this project, "Poisson Surface Reconstruction", has been cited nearly 1000 times since its initial publication. The code and executables for the reconstruction have been publicly released -- made freely available to all users, without restriction. The Poisson Reconstruction method has been integrated into numerous software packages, both in and out of the computer graphics community. The code for the Poisson Reconstruction algorithm received the first SGP Software Award.
