Date post: | 06-Apr-2015 |
Category: |
Documents |
Upload: | lulu-eberts |
View: | 103 times |
Download: | 0 times |
Streaming von Meshes
Mesh: Gesamtheit der Vertex- und Dreicksarrays eines Polygons
Streambarer Mesh: Mesh dessen Daten nicht in ihrer Gesamtheit im Hauptspeicher vorhanden sein müssen, um sie zu verarbeiten
Was versteht man darunter ?
Normale Darstellung von Meshes: Arrays von floats für die Vertexdaten, Array von Indizes auf die Vertexdaten für die Flächendaten
Je komplexer das Polygon wird desto mehr Daten müssen abgelegt werden: mehrere Gigabyte Vertizedaten und mehrere Gigabyte Flächendaten
Motivation
Um nur einzelne Teile des Meshes zu verwenden ohne alles zu dereferenzieren müssen Maßnahmen an Aufbau und Anordnung der Meshdaten vorgenommen werden
Motivation
Es gibt immer die Möglichkeit der Speicherung der Daten auf externem Speicher (z.B Festplatte)
Algorithmen die darauf arbeiten nennt man Out-of-core
Verschiedene Möglichkeiten: Zerteilen des Meshes, externe Datenstrukturen, „Dreieckssuppe“, Streaming
Vorrausetzungen
Simples Verfahren, welches große Meshes in kleinere Abschnitte unterteilt
Aber: dazu muss zunächst für den Cut dereferenziert werden
Mesh-Cutting
Ähnlicher Ansatz wie Mesh Cutting: Aufteilung in sog. Cluster
Nutzung dieser Aufteilung um je nach aktuellem Bedarf zu pagen
Externe Datenstrukturen
Umgeht die Problematik der indizierten Daten indem man eben keine Indizes verwendet
Dreiecke werden nacheinander von der Platte in den Speicher geholt
Beziehungen werden rekonstruiert oder einfach ignoriert
„Dreieckssuppe“
Jedoch: Wieder initiales dereferenzieren aller indizierten Daten notwendig
Ergo wie die anderen Varianten nicht die Lösung des Problems
„Dreieckssuppe“
Einführung einer neuen Information: Finalisierung
Ist ein Vertex finalisiert wird er nicht länger für die Berechnungen benötigt
Ist ein vertex finalisiert kann er also aus dem Hauptspeicher entfernt werden
Streambare Meshes
Im Standardformat für Meshes werden keine Anforderungen daran gestellt wo die Vertices der einzelnen Dreiecke abgelegt werden
Für die anfänglichen Meshes praktisch, heute jedoch problematisch, da keine bekannten Ordnungen existieren
Bisherige Anordnung
Um die Güte der Streambarkeit einer Meshindexanordnung zu bestimmen brauchen wir Anhaltswerte
Dreicksabstand : gibt an wieviele Dreiecke sich zwischen der ersten und der letzten Referenzierung des Vertex‘ sind
Definition Streambarkeit
Vertexabstand: maximal Indexdifferenz zwischen den Vertices eines Dreiecks
Dreiecks- Vertexweite: maximale Anzahl die zwischen erstem und letztem Element von Vertexreferenz oder Dreiecksreferenz stehen
Skip: Anzahl der Vertices welche die Indexreihefolge umgehen
Definition Streambarkeit
Demonstration der Gütewerte
Bereits erwähnt: kennzeichnung der Finalisierung
Daraus ergibt sich die Menge der aktuell bearbeiteten Vertices, nämlich alle die zwischen Einführung und Finalisierung stehen
Die maximale Anzahl bildet die Frontweite des Meshes
Definition Streaming Meshes
Es gibt 2 Arten von streambaren Meshes: Pre- und Post-Order
Pre-Order: Vertex kommt vor allen Dreickecken die aud ihn referenzieren an
Post-Order: Vertex kommt nach allen Dreicken die auf ihn referenziern an
Pre- und Post-Order
Darzustellendes Polygon:
Original Darstellung
Pre- und Post-Order
Pre- und Post-Order
Pre-Order Post-Order
Vertexkompakt: jeder Vertex ist vom vorhergehenden oder nachfolgenden Dreieck referenziert
Dreieckskompakt: letzter benötigter Vertex ist direkt davor oder danach im Stream zu finden
Kompakt: beide Kompaktheitsformen
Kompaktheit im Stream
Schritt 1: Trennung von Vertex- und Dreiecksdaten
Soll eine Anordnung von Indices nicht erhalten bleiben sondern umsortier kann diese verworfen werden
Vertices müssen jedoch den auf sie referenzierenden Dreicken zugeordnet werden können
Erzeugung von Streammeshes
Schritt 2: Zuweisung von Keys für Dreicke t und zugehörigen Vertices v
Wir erhalten zwei Datein mit Datensätzen <kv, v, d ,x ,y ,z> und <kt, v1, v2, v3>
Erzeugung von Streammeshes
Schritt 3: Sortierun und Anordnen der Datensätze in einen streambaren Datensatz
Für pre-Order nach Dreiecken
Für Post-Order nach Vertices
Verschiedene techniken zum Anordnen
Erzeugung von Streammeshes
Wenn die Streamgüte des alten Layouts gut genug ist kann man einen Streambaren Mesh erhalten indem man einfach die Datensätze anpasst und Finalisierung vorsieht
Indizierten Mesh verschachteln
Gerade bei hohem skip-Wert bietet sich Kompaktierung an
Dadurch kann leicht Pre-Order erreicht werden: Sortierung der Vertices und Einfügen eines Dreiecks sobald alle dafür nötigen Vertices bereits vorher eingefügt wurden
Kompaktierung
Post-order: Einfügen der Dreiecke jeweils wenn ein Vertex dafür benötigt wird und vor dem besagten Vertex
Kompaktierung
Simple Sortierung der keys nach einer räumlichen Ausrichtung also x, y oder z danach Orientierung entweder an Vertices oder Dreiecken und erzeugen eines kompakten Meshes
Alternativ aber ähnlich: Sortierung nach topologischen Richtlinien
Räumliche Anordnung
Ordnung nach minimaler Weite und Abstand: da diese Werte die Güte der Streambarkeit angeben der natürlichste Ansatz
Aber: das Trennen der Vertices und die Bildung von passenden Reihenfolgen erweist sich als NP-hartes Problem
Spectral Sequencing
Daher: Heuristiken werden benötigt
Beliebt dafür ist das Spectral Sequencing: Aufteilung in Cluster, umordnen dieser per ACE-Clusterformatierung gut geformte Teile
Dadurch wird ein ausreichend gutes gesamtbild erzeugt
Spectral Sequencing
Benötigte Zeiten für die Formatierungsmethoden
I/O-effizientes Arbeiten da durch die Formatierung des Meshes die Dreicke sobald sie im Speicher eintreffen gerendert werden können und alle finalisierten Vertices aus dem Speicher entfernt werden können um Platz zu sparen
Arbeiten mit Streammeshes
Nachteil: kein Mitführen von Informationen wie Valennzen, Inzidenzen und andere topologische Merkmale
Dafür gibt es den Spezialfall von Streammeshes die sogeanntnen „Processing Sequences“
Arbeiten mit Streammeshes
Zudem bietet das Sequenzielle Format der Streammeshes eine gute Möglichkeit für Komprimierung der Daten
Normale Meshkompression benötigt Zugriff auf den Raum in zufälliger Folge, was beim Streamen nicht möglich ist
Daher: eigene Kompression welche die Daten on-the-fly beim Streamen packt
Kompression
Durch einfaches Umformatieren wird es ermöglicht auch mit wenig Speicher grosse Modelle zu rendern welche aufgrund der Datenmengen sonst nicht möglich wären
Nicht an spezifisches Format gebunden, auch Standardformate können bei passenden Abständen genutzt werden (z.B. PLY, OBJ)
Nutzen der Streammeshes
Einfache Formatierungsmethoden können auch direkt in einem Stream geschrieben werden
Manche Ideen wie Ordnungserhaltende Kompression und die Kompaktierung der Meshanordung können auch an anderen Orten Anwendung finden
Nutzen der Streammeshes