The reconstruction of large three-dimensional meshes
Michael Kazhdan, Matthew Bolitho · 2010
Surface reconstruction is the process of creating virtual three-dimensional representations of real-world objects using data obtained from 3D scanners. The traditional challenges of surface reconstruction arise from the uncertain nature of input data. Inaccuracies in scanning devices create noisy data. Point sampling is often non-uniform. And, accessibility constraints during the scanning process may leave some regions of the surface devoid of data. Robustly constructing a surface in the presence of these data anomalies is a difficult problem. In addition, surface reconstruction methods have recently encountered a new challenge resulting from developments in 3D scanning techniques. New scanning technologies have driven a dramatic increase in the size of datasets available for surface reconstruction, with datasets now exceeding one billion point samples. As a result, space and time efficiency have become critical in the development of effective reconstruction algorithms, and the design of streaming and parallel techniques has become indispensable. In this dissertation we describe a new technique for surface reconstruction, based on the solution to a Poisson equation. Our approach is designed to meet the multiple challenges of modern datasets. The method is robust to the types of noise found in real-world data, allowing the reconstruction of high quality surfaces. Despite formulating surface reconstruction as a global problem, we also show that our method can be implemented using only local updates which allows extremely large reconstruction problems to be solved in a streaming manner. We also exploit current industry trends towards multi-core and parallel computing by presenting a parallel implementation of our method that is able to dramatically reduce the time taken to produce highly detailed reconstructions. We demonstrate the practicality of our method on several of the largest reconstruction datasets available to date.