Computing Curves and Surfaces from Points

Geometric models represent the shape and structure of objects. The mathematical description of geometric models is fundamental for processing virtual objects on digital computers. There are applications in a variety of fields such as industrial design, architecture, geology, medicine, physical simulation, education and entertainment. Many different representations have been created due to the varying demands in the respective fields. In this thesis, we focus on the rather new point-based representations, where curves and surfaces are described by unstructured point samples which are located on or close to the shapes they define. A point-based geometry representation can be considered a sampling of a continuous curve or surface. A variety of advantages result from the minimal consistency constraints, e.g. restructuring is particularly simple and efficient. However, during shape processing, shape modelling and rendering we need to associate a continuous curve or surface with the input points, in order to access and maintain a consistent model. Inspired by the MLS surface, we present an implicit definition of smooth curves and surfaces defined by points. The implicit function is composed of the local centroid of the input points and a tangent frame, allowing us to describe manifolds of arbitrary dimension. The evaluation can be performed locally by only considering a small subset of the points, when using compactly supported functions for weighting the input points. Our implicit definition allows to gain higher order information about the surface. We show how to compute the gradient and curvature for a location of the shape. We present stable and easy to implement algorithms that allow to locally interrogate the shape. Projection operators - including an orthogonal version - and ray intersection operators efficiently compute points of the manifold. We detail how to employ the ray-surface intersection algorithm for ray casting or ray tracing and discuss corresponding efficiency aspects. We also discuss how to effectively apply spatial data-structures in the context of point-based representations. To further speed up rendering, we present an adaptive sampling strategy that exploits both image- and object space coherence. Despite of the relatively time-consuming ray-surface intersection operator, this allows to interactively investigate the point set surface. In order to take into consideration to the varying complexity of a shape, a feature adaptive approach is required. We suggest to attach individual weighting functions to each sample rather than averaging local scales directly. By using ellipsoidal weighting functions, we also address local anisotropic sampling that adjusts to the principal curvatures of the surface. We modify the basic definition of closed surfaces, also allowing to represent bounded surfaces. Additionally, requiring that any point on the surface is close to the local centroid of the input points yields smooth boundaries. We compare this definition to alternatives and discuss the details and parameter choices. We also show that surfaces might as well be globally non-orientable. Finally, we enhance our manifold definition, also enabling us to describe the more general class of piecewise smooth surfaces - still in the setting of point-based representations. Inspired by cell complexes, we model surface patches, curve segments and points and glue them together based on explicit connectivity information