Reconstructive geometry

This thesis "Reconstructive Geometry" presents a new collision detection algorithm, a novel approach to generative modeling, and an innovative shape recognition technique. All these contributions are centred around the questions "how to combine acquisition data with generative model descriptions" and "how to perform this combination efficiently". Acquisition data - such as point clouds and triangle meshes - are created e.g. by a 3D scanner or a photogrammetric process. They can describe a shape's geometry very well, but do not contain any semantic information. With generative descriptions it's the other way round: a procedure describes a rather ideal object and its construction process. This thesis builds a bridge between both types of geometry descriptions and combines them to a semantic unit. An innovative shape recognition technique, presented in this thesis, determines whether a digitized real-world object might have been created by a given generative description, and if so, it identifies the high-level parameters that have been passed to the generative script. Such a generative script is a simple JavaScript function. Using the generative modeling compiler "Euclides" the function can be understood in a mathematical sense; i.e. it can be differentiated with respect to its input parameters, it can be embedded into an objective function, and it can be optimized using standard numerical analysis. This approach offers a wide range of applications for generative modeling techniques; parameters do not have to be set manually - they can be set automatically according to a reasonable objective function. In case of shape recognition, the objective function is distance-based and measures the similarity of two objects. The techniques that are used to efficiently perform this task (space partitioning, hierarchical structures, etc.) are the same in collision detection where the question, whether two objects have distance zero, is answered. To sum up, distance functions and distance calculations are a main part of this thesis along with their application in geometric object descriptions, semantic enrichment, numerical analysis and many more.