In dieser Dissertation präsentieren wir computergrafische Verfahren für die Analyse und Verarbeitung von Oberflächen, die durch Punktmengen repräsentiert sind. In den Verfahren spielen geodätische Kurven eine zentrale Rolle. Der erste Teil der Arbeit befasst sich mit dem Berechnen von geodätischen Kurven auf punktbasierten Flächen. Es werden zwei Haupttechniken präsentiert.
Die erste ergibt ein Verfahren zur effizienten Berechnung von Approximationen der geodätischen Kurven. Sie basiert auf einer grafischen Darstellung der Fläche durch den sogenannten erweiterten sphere-of-influence-graph (eSIG). Approximationen der geodätischen Kurven werden als kürzeste Pfade des eSIGs berechnet mit Hilfe von Dijkstra-ähnlichen Algorithmen.
Mit der zweiten Technik werden genauere Approximationen der geodätische Kurven berechnet. Sie ist robust in Bezug auf Rauschen und Ausreißer. Stückweise lineare Approximationen von geodätischen Kurven auf einer punktbasierten Fläche sind dabei als Minima einer geeignet definierten Energiefunktion definiert.
In dieser Arbeit werden zwei Anwendungen geodätischer Kurven entwickelt, (1) die Kompression texturierter punktbasierter Flächen von Geschlecht 0 und (2) die Ähnlichkeitssuche in Datenbanken von punktbasierten 3D-Modellen.
(1) Das hier beschriebene Kompressionsverfahren basiert auf einer sphärischen Repräsentation einer Genus-0 Fläche dargestellt durch eine Menge sogenannter Surfel (eine erweiterte punktbasierte Form). Es behandelt Geometrie, Texturen und andere Flächeneigenschaften in einer einheitlichen Art und Weise. Die Surfel werden auf eine Sphäre abgebildet, wobei die geodätischen Abstände auf der Fläche so gut wie möglich erhalten bleiben. Komplexitätsprobleme werden durch eine Einschränkung der in die Berechnung eingehenden Abstände gelöst. Die resultierende Vektor-bewertete Funktion auf der Sphäre wird dann regelmäßig abgetastet (resampled). Die Komponenten werden dekorreliert durch die Karhunen-Loeve Transformation, dargestellt durch kugelförmige Wavelets und mit dem zerotree Algorithmus kodiert. Der von der Kompression verursachte geometrische Rekonstruktionsfehler ist kleiner als der bei anderen Methoden bei sehr niedrigen Bit-Raten.
(2) Unser System für punktbasiertes Modellretrieval beinhaltet: eine Surfeltechnik für das Umwandeln von polygonalen Netzmodellen (mesh models) in entsprechende surfel-basierte Darstellungen und zwei Formbeschreiber um die Geometrie und die Topologie der punktbasierten Modelle effizient zu vergleichen.
Die Surfeltechnik besteht aus einer Rasterisierung von Polygonen, die den geometrischen Eigenschaften der triangulierten Modelle angepasst ist, so dass die wesentlichen visuellen und geometrischen Eigenschaften im resultierenden surfel-basiertes Modell erhalten bleiben.
Für die erste Formbeschreibung surfel-basierter Flächer wird die Fläche skaliert und aus verschiedenen Blickwinkeln gerendert. Die dabei erzeugten Tiefenpuffer werden Fourier-transformiert und einige der Koeffizienten werden im Outputvektor der Formbeschreibung aufgenommen. Die Formbeschreibung besitzt so eine eingebettete Multiskalen-Darstellung, ist invariant in Bezug auf ähnlichkeitstransformationen und robust in Bezug auf Ausreißer.
Der zweite Formbeschreiber basiert auf geodätischen Kurven und ist für das Abgleichen der Geometrie- und Topologie der punktbasierten Modelle bestimmt. Unsere Technik wählt eine Anzahl gleichmäßig verteilter Bezugspunkte auf der punktbasierten Fläche aus. Dann wird die zugehörige normalisierte geodätische Distanzmatrix berechnet. Die Ähnlichkeit von zwei punkt-basierten Modellen wird durch einen Histogramm-basierten Vergleich der beiden zugehörigen Abstands-Matrizen ermittelt. Diese Technik ist effektiv für den Vergleich von 3D Objekten und invariant bezüglich isometrischer Verformungen.

In this thesis we present a framework for analysis and processing of point set surfaces based on geodesics. The first part deals with computing geodesics on point set surfaces. Two main techniques are presented.
The first technique efficiently computes fast approximations of geodesics. It relies on a graph representation of the surface using an extended sphere of influence graph (eSIG). Approximations of geodesics are computed as shortest paths on the eSIG by using Dijkstra-like algorithms.
The second technique computes accurate approximations of geodesics and is robust with respect to noise and outliers. It is a novel technique, which computes piecewise linear approximations of geodesics on point set surfaces by minimizing an energy function defined for piecewise linear paths.
This thesis presents two surface processing/analysis applications, in which geodesics are used for compression of textured point based surfaces of genus-0, and for point based model retrieval.
The compression scheme described in this thesis is based on a spherical representation of a genus-0 surface represented by a surfel set. It incorporates geometry, texture and other surface attributes in a unified manner. Each surfel, with its attribute vector, is mapped onto a sphere by using a novel and efficient approach for dense surface mapping, which considers rectangular distance matrices. In this approach the geodesic distances between each surfel and a set of key-surfels are optimally preserved in order to improve the resolution and eliminating the need for interpolation that complicates and slows down existing surface unfolding methods. The resulting spherical vector-valued function is then regularly resampled. Its components are decorrelated by the Karhunen-Loève transform, represented by spherical wavelets and encoded using the zerotree algorithm. The compression-induced geometry error is smaller than that of other methods at very low bit-rates.
A system for point based model retrieval is also presented. It comprises: a surfelization technique for converting polygonal mesh models into corresponding surfel based representations, and two shape descriptors for comparing efficiently the geometry and the topology of point based models.
The presented surfelization technique is designed for converting large databases of triangular mesh models into corresponding surfel based representations. It consists of an enhanced triangle rasterization procedure adapted to the geometric features of a triangulated model, which preserves its main visual and geometric characteristics in the resulting surfel based model.
The first shape descriptor focuses on effectively matching the geometry of surfel based models. It is constructed through a pose normalization of surfel based models, and a Fourier analysis of depth-buffer images, which are rendered from different viewpoints. Our depth-buffer image based shape descriptor is able to compare the geometry of several classes of objects. Moreover, it possesses an embedded multi-resolution representation, is invariant with respect to similarity transforms and robust with respect to outliers.
The second shape descriptor is based on geodesics, and is designed for geometry and topology matching of point based models. A normalized geodesic distance matrix is computed from a set of reference points, which are selected randomly on a point set surface. The similarity of two point based models is then computed by comparing the associated distance matrices using a histogram based approach. This technique resulted in being an effective method for the comparison of deformed objects of the same class, since it is invariant with respect to similarity and isometric transformations.