Real-Time Shape Acquisition with Sensor-Specific Precision

The core idea in this project is to capture the shape of physical objects in real time, with guaranteed precision, and to reconstruct the shape boundaries with minimal geometry. An example application is to let untrained users acquire shapes using emerging mobile sensing devices such as Google`s Project Tango. The user moves the sensor around the object, guided by immediate visual feedback on the input sampling quality. The output is a topologically clean mesh consisting of just the vertices required to represent its features to the desired approximation. The real- time reconstruction enables numerous geometry-processing applications to be taken online, such as shape retrieval/matching, harvesting real-world geometry into a cloud, perspective photo correction, interactive modeling, augmented reality, physics simulation, or fabrication. The upcoming shift from expensive high-quality 3D scanners to ubiquitous commodity mobile sensors yields less precise samples, but large amounts as they arrive at high update rates of several times per second. However, this poses the challenge that state-of-the-art methods to process point clouds cannot keep up with these high data rates. For example, reconstructing the connectivity of an object that is dynamically scanned would require a speed-up of around two orders of magnitude. Achieving such a speedup would open up several new possibilities. In this project, we propose to achieve this by improving several stages of the surface-reconstruction pipeline, according to the following goals: Locality: Most importantly, surface reconstruction should not be treated as a global problem. This is possible since we show that the required locality depends on the local feature size. In turn, this allows for efficient parallelization. Processing ease: We want to allow operating directly on manifolds instead of point clouds, which greatly simplifies further processing such as the steps described below. We show that this can be achieved by reconstructing the topology of features before their geometry. Noise tolerance: Less precisely sampled data motivates us to better exploit the (prior known) statistical noise properties of the sensor. Instead of just smoothing the samples for visual plausibility, this permits faithful reconstruction within the measured error of the specific sensing device. Proper sampling density: At near-under-sampled features, estimating the tangent space may fail when assuming an isotropic neighborhood around samples, resulting in topological deficiencies. On the other hand, oversampled features contain redundant geometry, which requires simplification before transmitting it over low-bandwidth mobile channels. Therefore, a tightly bound sampling condition needs to be defined in order to both reconstruct and represent features sampled as sparsely as possible, but as densely as required.

The main result of our project are ground-breaking results in both curve and surface reconstruction. Fundamental results: We proved that a smooth curve in a plane can be reconstructed from much fewer unstructured points than believed before. This is a highly significant theoretical result compared to the previous state of the art established about 20 years ago. Our proof is supported by a novel criterion designed in this project. Furthermore, we developed an algorithm which is able to sample unstructured points on a smooth planar curve such that this criterion is fulfilled. These fundamental results should further fuel development in curve and surface reconstruction. Ground-breaking performance: We also achieved a ground-breaking result on using deep learning in surface reconstruction that greatly improves the current gold standard in surface reconstruction used in the graphics community. We expect our new method to also be very useful to users of surface reconstruction outside the research field, and are currently developing a web service for general usage. The basic advances of applying the deep learning approach should be applicable to many more aspects of reconstruction, such as color, light, or missing data. Relevant algorithm speed-up: We developed a k-nearest neighbors algorithm that runs in parallel on the GPU with much increased performance by sorting the points first in a grid. K-nearest neighbor finding is an important problem in many other computer science research fields since many methods rely on finding a specific number of points that are nearest in 3D space to a given coordinate. Thus, our new fast method is very relevant to a broader community. Real-world application: We developed a new research instrument to accurately measure the error of multiple sensor devices. We aggregate these errors in the form of x/y/z deviations of the sampled point coordinates as device-specific statistics. This allows us to compute the coefficients of probability density functions that specify with which probability and how near the original point is from the measured sample. We used the results to minimize an energy functional in order to increase the reconstruction accuracy of noisy curves and silhouettes of 3D models acquired from commodity sensor devices. Surface simplification: Using the fundamental results mentioned in the beginning enabled us to resample point clouds representing smooth curves with many fewer points. This inspired ongoing work to apply our new sampling condition also to surfaces, in order to simplify triangle meshes such that fewer triangles are required to represent an object while still representing the features in the same - adjustable - quality, regardless of their size.