TU Darmstadt / ULB / TUbiblio

Computing Curves and Surfaces from Points

Adamson, Anders (2007)
Computing Curves and Surfaces from Points.
Technische Universität Darmstadt
Dissertation, Erstveröffentlichung

Kurzbeschreibung (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.

Typ des Eintrags: Dissertation
Erschienen: 2007
Autor(en): Adamson, Anders
Art des Eintrags: Erstveröffentlichung
Titel: Computing Curves and Surfaces from Points
Sprache: Englisch
Referenten: ç~ao José Luis; Prof. Dr.-Ing. Dr. h.c. mult., Hon. Prof. Dr. e. h. ; Gross, Prof. Dr. Markus
Berater: Alexa, Prof. Dr.- Marc
Publikationsjahr: 22 November 2007
Ort: Darmstadt
Datum der mündlichen Prüfung: 12 Juli 2007
URL / URN: urn:nbn:de:tuda-tuprints-8931
Kurzbeschreibung (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.

Alternatives oder übersetztes Abstract:
Alternatives AbstractSprache

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.

Deutsch
Freie Schlagworte: Computational geometry, Surface modeling, Surface representation, Point set surfaces, Ray tracing
Zusätzliche Informationen:

131 p.

Sachgruppe der Dewey Dezimalklassifikatin (DDC): 000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik
Fachbereich(e)/-gebiet(e): 20 Fachbereich Informatik
20 Fachbereich Informatik > Graphisch-Interaktive Systeme
Hinterlegungsdatum: 17 Okt 2008 09:22
Letzte Änderung: 21 Nov 2023 09:45
PPN:
Referenten: ç~ao José Luis; Prof. Dr.-Ing. Dr. h.c. mult., Hon. Prof. Dr. e. h. ; Gross, Prof. Dr. Markus
Datum der mündlichen Prüfung / Verteidigung / mdl. Prüfung: 12 Juli 2007
Export:
Suche nach Titel in: TUfind oder in Google
Frage zum Eintrag Frage zum Eintrag

Optionen (nur für Redakteure)
Redaktionelle Details anzeigen Redaktionelle Details anzeigen