Cengiz Öztireli1
1ETH Zürich
It is one of the main goals of Computer Graphics in particular, and science in general, to understand and mimic the complexity in the real world. Over the past decades, it has been proven that the mathematical structures of manifolds, andstochastic point patterns result in accurate and efficient computational representa- tions for the geometric complexity of the world, and modeling these structures with meshless methods offers a versatile and unified treatment. In this thesis, we develop techniques and algorithms to tackle the fundamental problems of meshless sampling and reconstruction of manifolds and point patterns.
The acquired data sampled from manifold surfaces of objects is often noisy, corrup- ted with outliers, and sparse in some parts of the surface. It is thus very challenging to generate accurate reconstructions of the underlying surface. The first problem we address is the generation of robust, and sharp feature and high frequency de- tail preserving reconstructions of point sampled manifolds. Due to the common smoothness assumption, most approximation methods, when directly applied to the manifold surface reconstruction problem, can only generate smooth surfaces without such features, and are significantly affected by outliers. We propose to reformulate the moving least squares based point set surface reconstruction methods in the framework of local kernel regression, which enables us to incorporate methods from robust statistics to arrive at a feature preserving and robust point set surface definition. The new implicit surface definition can preserve fine details and all types of sharp features with controllable sharpness, has a simple analytic form, is robust to outliers and sparse sampling, and efficient and simple to compute. Since the definition is continuous, it is amenable to further processing without any special treatment.
The accuracy of the reconstruction of a surface is necessarily determined by the density and distribution of the points sampled from it. It is thus essential to ensure a dense enough sampling for faithful reconstructions. On the other hand, typical datasets can be massive and redundant in some parts with billions of points, which significantly degrades the performance of the reconstruction algorithms. Hence, finding optimal sampling conditions for a given reconstruction method is essential for efficient and accurate reconstructions. We propose new simplification and resampling algorithms that result in accurate reconstructions while minimizing redundancy. The algorithms are out-of-core, efficient, simple to implement, feature sensitive, and generate high quality blue noise distributions. They utilize a new measure that quantifies the effect a point has on the definition of a manifold, if it is added to the set defining the manifold, by considering the change in the Laplace-Beltrami spectrum. We derive an approximation of this measure by a novel technique that combines spectral analysis of manifolds and kernel methods. Although the measure is conceptually global, it requires only local computations, making the algorithms time and memory efficient.
Not all structures of the real world admit a deterministic manifold form. Indeed, many structures, from the distribution of trees in a forest or pores in a piece of Swiss cheese to those of molecular particles or movements of humans in a crowd are best modeled in a distributional sense by stochastic point patterns. Reconstruction of such patterns from given example distributions is thus of utmost importance. To achieve this, we first propose a new unified analysis of point distributions based on a kernel based approximation of the pair correlation function (PCF). This analysis shows that the PCF is sufficient for unique determination and discrimination of most point patterns, and that there is a quantifiable relation between patterns depending on a new measure of their irregularity. Following this analysis, we propose the first algorithms that can synthesize point distributions with characteristics matching those of provided examples, by minimizing a certain distance between the PCFs. Our first algorithm is a generalized dart throwing method that accepts or rejects added points depending on the PCF. The second gradient descent based algorithm takes the output of the first algorithm, and moves the points so as to minimize the distance between the target PCF and the PCF of the final output point set. The resulting point distributions have the characteristics of the target patterns to be reconstructed.
Links:
PDF