Geodätische Kurven für die Verarbeitung von punktbasierten Modelle

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