Mesh Parametrisierung

Katja Bühler, Mathematische Methoden der Computergrahik

Papers:

• MAPS – Multiresolution Adaptive Parametrization of SurfacesA. Lee, W. Swelden, P. Schröder, L. Cowsar, D. Dobkin Siggraph 1998

• Hierarchical Parametrizations of Triangulated SurfacesK. Hormann, G. Greiner, Swen Campagna

Wozu Parametrisieren?

Surface fitting: Parametrische glatte Flächen approximieren 3D Datenpunkte

Texture Mapping: Farbinformation / Texturen werden über Parametergebieten definiert und auf die Fläche abgebildet.

Morphing / Mesh editingRemeshing: Die Triangulierung eines Meshes wird so

verändert, dass ein Mesh eine Unterteilungshierarchie (subdivision connectivity) besitzt.(z.B. i.A. nicht der Fall für 3D Scanner Output) Parametrisierung erlaubt adaptives Remeshing ohne die subdivision connectivity zu verlieren.

Beispiel für Parametrisierungen

Arten von Parametrisierungsalgorithmen?

• 1. Ansatz: Direkte Abbildung des Meshes in die Ebene. Dieses Parameter-Mesh kann mittels Optimierungsalgorithmen verbessert werden

• 2. Ansatz: Eng verbunden mit Vereinfachungs-algorithmen:– Zwei “Schulen”:

• Klassische Multiresolution Darstellungen• Sequenzielle Vereinfachung (PMs)

• Optimale Parametrisierung:– Hängt stark von der Anwendung ab, z.B. Minimierung der

#Dreiecke, Minimierung des Approximationsfehlers, Minimierung der Verzerrung.

Allgemeine Problemstellung

• Gegeben: – Ein Dreiecks-Mesh, d.h. eine Menge von Punkten pi

und dazugehörigen Dreiecken Ti im R3. – Ein Parametergebiet G im R2.

• Gesucht:– Parameterwerte (ui,vi) aus G für jeden Punkt pi, so

daß die Topologie des Meshes erhalten bleibt. D.h. die den Dreiecken Ti entsprechenden Dreiecke ti im Parametergebiet dürfen sich nicht überlappen.

Lokale Parametrisierung

• Parametrisierung der Nachbarschaft W0,…,Wn eines Referenzknotens V durch “Plätten” der Nachbarschaft.

• Die Abbildung hat folgende Eigenschaften– || wi – vi || = || Wi – Vi || – Winkel zum Nachbarknoten im “geplättete” Dreieck:

n

jj

ii

0

Globale Parametrisierung

• Komplexes Problem!– Direkte Abbildung einer gerümmten Fläche in die

Ebene ist immer mit Verzerrungen verbunden. – Manche Algorithmen zerstückeln die Fläche– Was soll erhalten werden? (Flächeninhalt, Winkel,

geodätische Krümmung……)– Optimierungsalgorithmen finden bezüglich

vorgegebener Randwerte optimale Parametrisierungen.

Hierarchische Parametrizierungen

• Nutzen Mesh-Hierarchien aus, um “gute” Parametrisierungen zu erhalten.

• Idee: Gute Parametrisierungen lassen sich für weniger komplexe Meshes leichter berechnen und dann auf die feineren Levels übertragen.

• Wichtige Fragestellung: Wie berechne ich sinnvoll die Parameter und deren zusammenhänge in den einzelnen Levels?

Hierarchical ParametrizationsHormann et al.

• Relativ simples Paper• Idee:• Verwende Progressive Meshes um ein gute

Anfangsmesh für den Optimierungsprozess zu bekommen und ihn so zu beschleunigen.

Hormann – Algorithmus 1

• Berechne alle Hierarchie-Levels.• Bei jedem Half Edge Collaps berechne

außerdem die baryzentrischen Koordinaten des eliminierten Punktes bezüglich der lokalen Parametrisierung des umgebenden Dreiecks.

• Speichere baryzentrische Koordinaten und Index des Mutterdreiecks.

Hormann – Algorithmus 2

• Parametrisierung:– Beginne mit dem gröbsten Mesh und berechne eine

optimale Parametrisierung– Verwende die gespeicherten baryzentrischen

Koordinaten um die fehlenden Dreiecke in das nächst feineren Level einzufügen.

– Nehme diese Parametrisierung als Anfangswert für die Optimierung des nächstfeineren Levels, usw.

Hormann - Ergebnisse

MAPS – Multiresolution Adaptive Parametrization of Surfaces Lee et. al.

• Ähnlicher Ansatz wie bei Hormann

• Mesh-Hierarchie basiert auf einem Algorithmus von Dobkin und Kirkpatrick (DK), der eine maximale Anzahl von O(log N) Levels garantiert.

Um was geht’s genau?

• Gegeben: Irreguläre Triangulierungen von Mannigfaltigkeiten vom Geschlecht 2, z.B. Daten aus einem Laserscanner, oder Ergebnis des Marching Cubes-Algorithmus,….

• Gesucht:“Glatte, schöne Parametrisierung” des original Meshes

• Ansatz:– Hierarchische Vereinfachung induziert eine Parametrisierung

des originalen Meshes über einer kleinen Anzahl von Dreiecken im Parameterraum

– Verbesserung der Parametrisierung durch hierarchisches Glätten basierend auf Loop-Subdivision.

Aufbau der Mesh-Hierarchie:Der DK-Algorithmus

• Ein Vereinfachungschrittbesteht daraus, soviele Knoten wie möglich mit minimaler Valenz zu eliminieren.

• Originalalgorithmus verwendet topologische Information um die Knoten zu bestimmen.

• Hier: Priority Queue, die geometrische und topolgische Information enthält.

Der DK-Algorithmus

1. Setze alle Knoten unmarkiert

2. Bestimme zufällig einen unmarkiert Knoten mit Valenz < 12

3. Entferne den Knoten und retrianguliere das entstandene Loch.

4. Markiere die Knoten der Nachbarschaft des entfernten Knotens.

5. Wiederhole Schritt 2.-4. solange bis kein Knoten mehr entfernt werden kann.

Verbesserung des DK-Algorithmus- Auswahl der Knoten

• Die zufällige Auswahl der Knoten kann ersetzt werden durch eine Priority Queue, die die Krümmung der Nachbarschaft eines Knotens mit in den Entscheidungsprozess einbezieht.

• Zuerst werden die Knoten mit Valenz < 12 ausgewählt, die eine “flache” Umgebung haben.

• Dadurch können wesentlich mehr Knoten entfernt werden (~1/4 statt mindestens 1/24)

Verbesserung des DK-Algorithmus- Retriangulierung

• Abbildung der Nachbarschaft auf die Ebene mit Hilfe einer konformen Abbildung (winkeltreu, minimale metrische Verzerrung, bijektiv)

• Retriangulierung in der Ebene mit “Constrained Delaunay Triangulation”

DK Mesh - Hierarchie

Parametrisierung

• Beginne mit einer Parametrisierung des feinsten Meshes

• Falls ein Punkt einen Vereinfachungsschritt überlebt, bleibt auch seine Parametrisierung bestehen

• Falls ein Punkt entfernt wird, so wird er bezüglich des Dreiecks parametrisiert, in dem er liegt.

• Früher entfernte Punkte werden ebenfalls entsprechend reparametrisiert.

Probleme

• Die Abbildung der einzelnen Knoten in das Parametergebiet führt nicht unbedingt zu einer Triangulierung, wenn die Knoten verbunden werden – Dreiecke können z.B. auch auf nicht-konvexe Gebiete abgebildet werden. Gerade Verbindung führen zu überlappenden gebieten

• Lösungen:– Unterteile das Mesh in den problematischen Gebieten weiter,

oder– Führe Dreiecksflips durch.

Tagging and Feature Lines

• Die Nachbarschaft wird entlang der Feature Line in zwei Bereiche aufgeteil und getrennt retrianguliert.

Uniform Remeshing

• Baue eine 1:4 Unterteilungshierarchie des Parametergebietes auf.

• Bestimme, in welchem Dreieck eines Levels ein Knoten liegt.

• Verwende baryzentrischen Koordinaten bezüglich des original Dreiecks um die Position des neuen Knotens im Mesh zu bestimmen.

Glätten der Parametrisierung

• Problem: Parametrisierung geht nicht glatt über die Kanten der Basis-Dreiecke

• Lösung: Verwende Modifizierte (flache) Loop Subdivision.

• Details siehe Paper…..

Adaptive Remeshing

• Problem: Normalerweise wirde die komplette Hierarchie eines Meshes aufgebaut und dann werden einzelne Äste des Meshes abgeschnitte.

• Hier: Verfeinerung im Remeshing-Prozess findet nur statt, wenn der Abstand zum “Mutter”-Dreieck eine bestimmten Wert übersteigt.

Ergebnisse

Ergebnisse