Meshless sampling and reconstruction of manifolds and patterns

Abstract

It is one of the main goals of Computer Graphics in particular, and science ingeneral, to understand and mimic the complexity in the real world. Over the pastdecades, it has been proven that the mathematical structures of manifolds, andstochastic point patterns result in accurate and efficient computational representationsfor the geometric complexity of the world, and modeling these structureswith meshless methods offers a versatile and unified treatment. In this thesis,we develop techniques and algorithms to tackle the fundamental problems ofmeshless sampling and reconstruction of manifolds and point patterns.The acquired data sampled from manifold surfaces of objects is often noisy, corruptedwith outliers, and sparse in some parts of the surface. It is thus very challengingto generate accurate reconstructions of the underlying surface. The first problemwe address is the generation of robust, and sharp feature and high frequency detailpreserving reconstructions of point sampled manifolds. Due to the commonsmoothness assumption, most approximation methods, when directly applied tothe manifold surface reconstruction problem, can only generate smooth surfaceswithout such features, and are significantly affected by outliers. We propose toreformulate the moving least squares based point set surface reconstruction methodsin the framework of local kernel regression, which enables us to incorporate methodsfrom robust statistics to arrive at a feature preserving and robust point set surfacedefinition. The new implicit surface definition can preserve fine details and alltypes 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 anyspecial treatment.The accuracy of the reconstruction of a surface is necessarily determined by thedensity and distribution of the points sampled from it. It is thus essential to ensurea dense enough sampling for faithful reconstructions. On the other hand, typicaldatasets can be massive and redundant in some parts with billions of points, whichsignificantly degrades the performance of the reconstruction algorithms. Hence,finding optimal sampling conditions for a given reconstruction method is essential forefficient and accurate reconstructions. We propose new simplification and resamplingalgorithms that result in accurate reconstructions while minimizing redundancy.The algorithms are out-of-core, efficient, simple to implement, feature sensitive,iiiand generate high quality blue noise distributions. They utilize a new measurethat quantifies the effect a point has on the definition of a manifold, if it is addedto the set defining the manifold, by considering the change in the Laplace-Beltramispectrum. We derive an approximation of this measure by a novel technique thatcombines spectral analysis of manifolds and kernel methods. Although the measure isconceptually global, it requires only local computations, making the algorithmstime 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 Swisscheese to those of molecular particles or movements of humans in a crowd are bestmodeled in a distributional sense by stochastic point patterns. Reconstruction of suchpatterns from given example distributions is thus of utmost importance. To achievethis, we first propose a new unified analysis of point distributions based on a kernelbased approximation of the pair correlation function (PCF). This analysis shows thatthe PCF is sufficient for unique determination and discrimination of most pointpatterns, and that there is a quantifiable relation between patterns depending ona new measure of their irregularity. Following this analysis, we propose the firstalgorithms that can synthesize point distributions with characteristics matchingthose of provided examples, by minimizing a certain distance between the PCFs.Our first algorithm is a generalized dart throwing method that accepts or rejectsadded points depending on the PCF. The second gradient descent based algorithmtakes the output of the first algorithm, and moves the points so as to minimize thedistance between the target PCF and the PCF of the final output point set. Theresulting point distributions have the characteristics of the target patterns to bereconstructed.iv