Quad Layout Generation and Symmetric Tilings of Closed Surfaces

Abstract

This thesis concerns two fundamental concepts in surface topology. The first part proposes a solution of the problem of generating an all quadrilateral patch layout on a given surface. We approach the problem from a combinatorial graph optimization point of view. Mainly, finding a nice quad layout of a given surface is equivalent to solving a minimum weight perfect matching problem with additional quad guarantee constraints. The results are of high quality in terms of coarseness and alignment to important features of the geometry which can be used for wide range of applications such as hierarchical subdivision or high order surface fitting. The second part suggests an algorithm to symmetrically generate high genus surfaces suitable for space models of regular maps. It is based on a novel identification in hyperbolic space to derive directly the tubular neighborhood of the edge of a tiling directly the the hyperbolic representation followed by a spring relaxation procedure with intersection-free guarantee. We succeed to produce new embeddings of regular maps ranging from genus 5 to 85.

Diese Dissertation beschäftigt sich mit zwei grundsätzlichen Konzepten in der Oberflächentopologie. Der erste Teil behandelt das Problem, eine gegebene Oberfläche in Vierecksgitter zu pflastern. Ist eine regelmässige Pflasterung gegeben, werden im zweiten Teil Methoden vorgeschlagen, um eine symmetrische geschlossene Oberfläche zu bauen und diese symmetrisch einzubetten. Oberflächepflasterung hat eine breite Reihe von Anwendung in der Computergrafik und Geometrieverarbeitung. Für eine gegebene Oberfläche schlagen wir einen flexiblen Algorithmus vor, welcher autmoatisch Vierecksgitter von hoher Qualität auf dieser Oberfläche erzeugt. Strukturierte Darstellung einer Oberfläche durch Vierecksgitter hat praktische Anwendungen in unterschiedlichen Bereichen, wie Unterteilungsflächen, Approximation von Oberflächen, Kompression und Hierarchien in der finiten Element Methode. Unser Ansatz besteht darin, einen Singularitäten-Graph eines Rahmenfeldes zu konstruieren. Dieses Feld dekodiert die lokalen Strukturen der Geometrie. Das Problem, ein Vierecksgitter auf der Oberfläche zu erzeugen ist damit äquivalent zur Konstruktion eines minimalen gewichteten Matchings mit disjunkten Nebenbedingungen. Das resultierende Vierecksgitter ist von hoher Qualität in dem Sinne, als das es trotz grober Auflösung den lokalen Strukturen der Geometrie folgt. Anwendungen unserer Methode auf Dreiecks- und Vierecksgitter zeigen, dass die Ergebnisse sich mit denen anderer aktueller Methoden messen können. Für eine gegebene reguläre Pflasterung, präziser eine reguläre Karte, führen wir die entsprechende reguläre Oberfläche ein. Diese ist die passendste Oberfläche von hohem Genus, welche die gegebene Pflasterung realisiert. Das Visualisieren regulärer Karten ist ein schwieriges Problem. Alle regulären Karten, bzw. symmetrischen Pflasterungen einer Oberfläche von Genus bis 302 sind algebraisch bereits bekannt. Sie liegen in Form von Symmetriegruppen vor, welche auf den entsprechenden universellen Abdeckungsräumen agieren. Jedoch ist wenig über die geometrischen Realisierungen bekannt, d.h. über das Finden hoch-symmetrischer Einbettungen abgeschlossener Oberflächen und die passenden hoch-symmetrischen Pflasterungen. In dieser Arbeit führen wir einen Algorithmus ein, welcher automatisch räumliche Modelle für einige dieser regulären Karten erstellt und dabei schöne Oberflächen mit sehr hoher Symmetrie erzeugt.