TU Darmstadt ULB TUprints

# Computing Curves and Surfaces from Points

### Adamson, Anders (2008)Computing Curves and Surfaces from Points. Technische Universität DarmstadtPh.D. Thesis, Primary publication

 Preview
Kapitel1-4 - PDF

 Preview
Kapitel5-7 - PDF

 Preview
Kapitel8-10 - PDF

Item Type: Ph.D. Thesis
Type of entry: Primary publication
Title: Computing Curves and Surfaces from Points
Language: English
Referees: Encarnaç~ao José Luis; Prof. Dr.-Ing. Dr. h.c. mult., Hon. Prof. Dr. e. h. ; Gross, Prof. Dr. Markus
Advisors: Alexa, Prof. Dr.- Marc
Date: 17 October 2008
Place of Publication: Darmstadt
Date of oral examination: 12 July 2007
Abstract:

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.

Alternative Abstract:
Alternative AbstractLanguage

Geometrische Modelle repräsentieren die Form und Struktur von Objekten. Ihre mathematische Beschreibung ist Grundlegend für die Verarbeitung von virtuellen Objekten auf digitalen Computern. Die Arbeit befasst sich mit der punktbasierten Repräsentation, bei der Kurven und Flächen durch Punkte definiert werden, die auf oder nahe der beschriebenen Form liegen. Dabei werden keine Nachbarschaftsbeziehungen zwischen den Punkten gespeichert. Hierin unterscheidet sich dieser Ansatz von den vorherrschenden Geometriebeschreibungen, zu denen NURBS, Unterteilungsflächen und Polygonale Netze zählen. Eine Reihe von Vorteilen resultiert aus der Tatsache, dass die Punkte beliebig verteilt sein können, ohne dass eine Struktur unter den Punkten erforderlich ist. Zum einen können Punktwolken, die durch 3D-Scanner bereitgestellt werden direkt verwendet werden. Im Gegensatz dazu stellt sich die vollständige Rekonstruktion der Konnektivität aufwändig dar, da globale Ansätze (z.B. 3D-Delaunay Triangulierung) benötigt werden. Ein weiterer Vorteil liegt in der einfachen Restrukturierung der Modelle, welches das Hinzufügen und Entfernen von Punkten beinhaltet. Dieses kommt vor allem in vorwiegend dynamischen Szenarien zum tragen. Um von den Vorteilen der einfachen Beschreibung zu profitieren und um gleichzeitig auf konsistente Modelle zugreifen und diese konsistent halten zu können, ist es erforderlich, eine kontinuierliche Kurve oder Fläche mit den Eingabepunkten zu assoziieren. Inspiriert von Moving Least Squares (MLS) Flächen wird eine einfache implizite Definition von Kurven und Flächen entwickelt. Die resultierenden Kurven und Flächen sind glatt und differenzierbar. Ihre Auswertung ist lokal, d.h. zum Zwecke der effizienten Verarbeitung, muss lediglich eine Teilmenge der Eingabepunkte berücksichtigt werden. Desweiteren wird gezeigt, wie Information höherer Ordnung berechnet werden kann und wie man Berandungen, nicht-orientierbare Flächen und scharfe Kanten und Ecken erhält.

German
Uncontrolled Keywords: Computational geometry, Surface modeling, Surface representation, Point set surfaces, Ray tracing
URN: urn:nbn:de:tuda-tuprints-8931