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