Drahtgitterlandschaft

Objekte im virtuellen 3 dimensionalen Raum mittels Dreiecken zu moddelieren und zu berechnen ist eine weit verbreitete Technik und kann als quasi als Standard bezeichnet werden.  Möchte man diese Objekte aber in einer weitläufigen Landschaft platzieren, kommt oft die Frage auf, wie diese nun eigentlich dargestellt werden soll. Es gibt die verschiedensten Ansätze und endlose Abhandlungen im Netz, doch auch hier hat sich das Modell der Unterteilung einer Landschaft in kleine - oder große - Dreicke durchgesetzt. Die Beschreibung einer solchen Landschaft wird dabei in der Regel in einer einfachen 2 dimensionalen Höhenkarte vorliegen.

Eine Herrausforderung bei der Darstellung großer Landschaften in einem Drahtgittermodell, welches durch die vielen Dreiecke gebildet wird, ist die Anzahl der notwendigen Dreiecke. Da dies die Performance - also die Geschwindigkeit - mit der die Landschaft dargestellt werden kann negativ beeinflusst umso mehr Dreiecke eine Landschaft benötigt, müssen Optimierungspotentiale ausgeschöpft werden.

LOD 

Ein sehr wirkungsvolles Mittel ist die Anwendung von sogenannten LOD (LevelOfDetail) Verfahren. Dabei wird die Landschaft nicht durch eine gleichmäßige Verteilung von Dreiecken gleicher Größe beschrieben, sondern von “unregelmäßigen” Dreiecksstrukturen. Einen aus meiner Sicht guten Allgorythmus beschreibt ein Papier von Peter Lindstrom und Valerio Pascucci. Unter dem Titel “Visualization of Large Terrains Made Easy” haben Sie 2001 ihren SOAR (Stateless One-pass Adaptive Refinement) Allgorythmus und eine Beispielimplementierung veröffentlicht. Leider sind die Quellenverweise im Internet nicht mehr auffindbar. Den (vermutlich nicht mehr funktionierenden) Link auf den Artikel werde ich aber dennoch hier platzieren.

Für unser Projekt werde ich diese Ideen aufgreifen und eine PSP Version dieses Allgorythmus implementieren. Der Vorteil: Ebene Flächen in der Landschaft werden durch so wenige Dreiecke wie möglich und sehr stark zerklüftete Flächen mit so vielen Dreiecken wie notwendig repräsentiert. Im Folgenden werde ich kurz die Theorie des Algorythmus erklären und die Implementierung zeigen.

Die Grundidee
Es wird zunächst immer davon ausgegangen, dass die 3D Landschaft durch eine 2D Karte mit quadratischen Abmessungen einer Potenz von 2 abgebildet wird. Die Seiten können somit immer ganzzahlig durch 2 geteilt werden. Beispiele wären Flächen von 64×64 oder 256×256 oder gar 1024×1024. In einem ersten Schritt wird eine solche Fläche nun in 4 Dreiecke aufgeteilt. Diese werden durch die 4 Eckpunkte und den Mittelpunkt der Landschaft gebildet.

In den nun folgenden Schritten wird jeweils ein solches Dreieck als Startpunkt genutzt und für sich selbst betrachtet.
Das Refinement
In den folgenden Schritten wird das Dreick nun in 2 neue gleichgroße Dreiecke aufgeteilt. Diese werden wiederum in jeweils 2 neue Dreiecke aufgeteilt. Das ganze (auch refinement genannt) wird nun rekursiv solange wiederholt bis es entweder nicht mehr geht, weil die kleinste Teilungseinheit erreicht ist, oder bis ein bestimmter Schwellwert erreicht ist.
Zur Vereinfachung ist das ganze hier auchnochmal kurz visualisiert:

Schön zu sehen ist, wie die Dreicke immer kleiner werden. Solange es keine Definition eines Schwellwertes gibt, wird diese Vorgehensweise am Ende dazu führen, dass wir ein komplett gleichmäßiges sehr feines Drahtgittermodell erreichen. Das bedeutet, dass wir diesen Schwellenwert nun Näher betrachten müssen.
Der Schwellenwert soll es ermöglichen zu unterscheiden ob ein gegebenes Dreieck geteilt werden soll, oder nicht.

Dazu eine kleine Überlegung:
Wenn wir eine Linie über das Gelände spannen, dann hat diese am Anfang und am Ende einen festen Höhenwert. Der Höhenwert in der Mitte der Linie kann einfach liniear bestimmt werden und ist die hälfte des Höhenunterschiedes der beiden Punkte. Setzt man nun einen Punkt in die Mitte dieser Linie und bestimmt dessen wirkliche Höhe wird dieser Wert in der Regel von dem Linear ermittelten Wert abweichen.  Diese Abweichung bzwl dieser Fehlerwert, soll unser Schwellenwert sein. Unterschreitet diese Abweichung einen bestimmten Wert, ist es nicht notwendig die Linie/das Dreieck wirklich zu teilen.

Dreiecke
Nachdem der Allgorythmus zur Aufteilung nun klar ist, soll am Ende natürlich ein möglichst gleichmäßiges Dreiecksband (Triangle Strip) heraus kommen. Das bedeutet dass wir zu der Zeit zu der wir das Refinement durchführen die Liste der Punkte zusammenstellen müssen, aus der sich dann das Dreiecksband ergibt.  Das ganze sei hier anhand einer Grafik aus dem Papier von P. Lindstrom und V.Pascucci veranschaulicht.

Einen solchen “Streifen” gilt es nun zu Erstellen.
Bisher haben wir davon gesprochen die Landschaft in “imaginäre” Dreiecke aufzuteilen und diese nach und nach zu Teilen. Dabei besteht jedes Dreieck aus 3 Punkten.  Bei diesen 3 Punkten interessieren uns für die Aufteilung nur die X und Y Position. Die höhe ist dabei ledoglich für die Schwellenwertbetrachtung von Bedeutung. Da die Aufteilung der Punkte in x und y Richtung gleichmäßig ist und immer den selben Abstand zu einander haben müssen wir die eigentlichen Koordinaten der Punkte gar nicht betrachten. Vielmehr können wir jeden Punkt über einen index Wert addressieren. Das hat 2 Vorteile.
1: Wir sparen Speicherplatz und Rechenleistung da Mehrfachnennungen der Indexwerte leicher zu handhaben sind als die komplexen Punkte die immer aus mind. 3 Zahlen (x, y, z) bestehen.
2: Wir können das Dreiecksband aus einer Liste einfacher Indexwerte aufbauen.
Das Dreicksband hat die Eigenschaft, dass die ersten 3 Punkte ein komplettes Dreieck beschreiben. Danach benötigt as nur noch einen weitern Punkt um ein erneutes Dreieck aufzuspannen. Das machen wir uns hier zunutze. Das bedeutet der erste Punkt ist eben ein Eckpunkt unseres Ausgangsdreieckes (vor dem Refinement). Während der nun folgenden Teilung der Dreiecke werden die Punkte immer dann, wenn ein Dreick nicht mehr geteilt werden kann an die Liste angefügt. Da die “Drehrichtung” der Punkte dabei immer gleich bleiben muss um fortlaufend Dreiecke zu erzeugen, müssen hin und wieder “blinde” Dreiecke eingefügt werden.

Bild aus dem original Papier zur Veranschaulichung der Richtung in der die Punkte in der Liste stehen müssen um ein fortlaufendes Dreiecksband zu erreichen.

Zusammenfassung
Die Grundüberlegungen des Verfahrens sind nun erläutert. In dem Papier werden noch weitere Verfahren zum verringern der Anzahl der notwendigen Dreiecke zum Darstellen dieser Landschaft ausgeführt. Darauf gehen wir vielleicht zu einem Späteren Zeitpunkt ein. Zunächst haben wir aber alles beisammen um aus der trockenen Theorie wieder handfeste Praxis in Form von Programmzeilen für die PSP werden zu lassen.