3D Landschaften
Christoph Thöns

Konzepte:

Datenstruktur zur Verwaltung der Höhenlinien

Die Höhenlinien werden zur Laufzeit und im Programmeigenen XML-Dateiformat als Baumstruktur gehalten. Dabei werden die Höhenlinien so angeordnet, dass eine Höhenlinien A die innerhalb einer anderen Höhenlinie B liegt, Kind der Höhenlinie B ist.

Beispiel:


Hier sind die Höhenlinien 2 und 3 Kinder von Höhenlinie 1. 4 ist wiederum Kind von 3. Damit ergibt sich also folgender Baum:


Bei der Triangulierung wird immer der Bereich zwischen einem Höhenlinienpolygon und dessen Kinderpolygonen innerhalb der Baumstruktur mit Dreiecken gefüllt. Da die Verschachtelung der Polygone im XML-Format explizit vorgegeben ist, können somit auch Überhänge dargestellt werden. Ein Beispiel:



Hier ist die Basis des Baumstammes der Vaterknoten des oberen Endes des Stammes und die Basis des Blattwerks wiederum Kind des oberen Endes des Baumstammes, wodurch der Überhang entsteht.

Dateiformat

Eine XML Datei im programmeigenen Format besteht aus einer Materialiendefinition, einer Reihe von Höhenlinien und ggf. Straßen. Hier ein Beispiel:

<terrain>
   <materials>  
       <material name="skyscraper" texture="skyscraper.jpg">
           <ambient r="1.0" g="1.0" b="1.0" a="1.0"/>
           <specular r="1.0" g="1.0" b="1.0" a="1.0"/>
       </material> 
       ...
   </materials>

   <contour altitude="0.0" material="terrain" shape="-11.0222225 -2.0000005 …" shapeVertexCount="23">
       <contour altitude="1.6" shape="-7.4222226 -4.6222224 …" shapeVertexCount="19"/>
   </contour>
  
   … 
   <street scale="4.2" translate="-37,-28" shape="2.60036,5.07643 ..."/>
</terrain>

Materialien können über die typischen Parameter des Beleuchtungsmodells wie Ambient-  und Specular- Farbe definiert werden. Die Verwendung von Texturen und Fragment- bzw. Vertex Shadern ist aber auch möglich (dazu später mehr). Für jede Höhenlinie ist ihre Höhe über der XZ-Ebene im Attribut altitide angegeben werden. Die Eckpunkte des Polygons stehen im shape-Attribut und die Anzahl der Eckpunkte im shapeVertexCount-Attribut. Optional kann im material-Attribut eines der im Materials-Bock definierten Materialien angegeben werden. Wenn keine Material angeben wurde, wird das Material der übergeordneten Höhenlinie weiterverwendet.

Straßen werden genauso als Eckpunkte eines Polygons im shape-Attribut angegeben. Eine Straße kann über das scale-Attribut skaliert, und über das translate-Attribut verschoben werden, um sie an das Terrain anzupassen.

Shader

Moderne Grafikkarten bieten die Möglichkeit, Teile der Grafikpipeline die früher fest verdrahtet waren durch kleine Programme zu ersetzen. Offensichtlich wird dadurch die Flexibilität der Hardware enorm gesteigert. Es gibt momentan zwei Arten von Shadern, genannt Vertex- und Fragment Shader (oder Pixelshader im DirectX jargon). Ein Vertex Shader Programm wird einmal für jeden einzelnen Vertex der Geometrie ausgeführt. Dadurch kann man z.B. eine Wasseroberfläche die Wellen schlägt berechnen, was durch eine Matrixoperation auf den Vertices alleine nicht machbar wäre. Ein Fragment Shader Programm wird dagegen für jedes Pixel das auf den Bildschirm gezeichnet wird ausgeführt. So kann man z.B. Holz und Marmor Texturen berechnen, die beliebig vergrößerbar sind und trotzdem nicht an Qualität verlieren. 

Die Implementierung verwendet einen solchen Fragment Shader um die Textur der Landschaft zu berechnen. Der Shader bekommt fester Farben für bestimmte Höhenniveaus (also Z-Werte) übergeben. Zwischen diesen Niveaus werden die Farben linear interpoliert. Dabei werden die konkreten Farbwerte für die Höhenniveaus als Parameter übergeben. So kann man z.B. unterschiedlich Gebirgszüge unterschiedlich einfärben. Die Materialdefinition für diesen Shader in der XML-Datei sieht wie folgt aus:

 

<material name="terrain" vertexshader="phong.vert" fragmentshader="phong.frag">

   <parameter name="h1" type="float" value="1.3"/>

   <parameter name="h2" type="float" value="2.9"/>

   ...  

   

   <parameter name="cl1" type="vec4" value="0.0 0.0 1.0 1.0"/>

    ...

</material>

Dabei geben die h Parameter die Höhenniveaus und die cl Parameter die zugehörigen Farben an.

Kameras

Die Implementierung bietet die Möglichkeit, zwischen 2 Kameras umzuschalren (Taste K).

Übersichtskamera

Hier blickt die Kamera immer auf denselben Punkt und kann mit der Maus um diesen Punkt rotiert werden. Die Kamera folgt immer der Bewegung der First Person  Ansicht, deren Augpunkt als fokussierter Punkt verwendet wird. Außerdem kann man mit dem Mausrad frei herein- und hinauszoomen, was eine Übersicht über das Gelände erlaubt (insofern das Clipping mitspielt) aber auch die nähere Umgebung sichtbar machen kann.

First Person Ansicht

Diese Kamera stellt das Terrain aus der Sicht einer Person dar, die durch die Landschaft läuft. Die Blickrichtung kann durch drücken und halten der linken Maustaste verändert werden und man kann sich mit Hilfe der Pfeiltasten in alle Richtungen bewegen, wobei sich die Kamera beim Drücken der vorwärts Taste immer in Richtung der aktuellen Blickrichtung bewegt.

Die Kamera schwebt momentan fix in gleich bleibender Höhe über dem Boden. Dadurch wirkt die Bewegung noch relativ starr und man kann keine Abhänge herunterfallen, sondern kommt sofort unten an. Es gibt auch eine rudimentäre Kollisionserkennung. Hierbei wird geprüft, ob sich ein Eckpunkt der Geometrie der Landschaft innerhalb einer Kugel um den Augpunkt befindet, und die Bewegung ggf. gestoppt. Der zweite Teil der Kollisionserkennung würde darin bestehen, zu prüfen ob die Kugel eines der Dreiecke der Landschaft schneidet. Dies zu implementieren blieb jedoch keine Zeit.

Wenn die First Person Kamera nicht aktiv ist, wird eine Art Avatar in die Landschaft an der Stelle gezeichnet, an der sich der Betrachter  gerade befindet. Dieser besteht aus einer Pyramide, deren Spitze im Augpunkt liegt und deren Basisfläche praktisch das Bild das die Person auf dem Bildschirm sieht repräsentiert. Schneidet die Fläche z.B. einen Teil der Landschaft, wird die vordere Clipping-Ebene der Kamera geschnitten und es kommt zu unerwünschten Effekten. Außerdem wird eine Halbtransparente blaue Kugel um den Augpunkt gezeichnet, die die Kollisionskugel repräsentiert, in die also kein Eckpunkt der Geometrie der Landschaft eindringen sollte. Der Avatar dient hauptsächlich der Veranschaulichung und Fehlersuche.

Straßen

Straßen liegen als einfaches Polygon vor und werden einfach auf die Landschaft projiziert. Dazu wird für jeden Endpunkt des Straßenpolygons dessen Höhe über dem Boden bestimmt (genaueres dazu im Implementierungsteil dieser Dokumentation). Dann kann es allerdings noch vorkommen, daß Kanten des Straßenpolygons die Dreiecke der Landschaft durchstoßen. Um dies zu verhindern,  werden die einzelnen Segmente des Straßenpolygons in Teilstrecken unterteilt, wenn sie auf die XZ-Ebene projeziert eine Kante eines Dreiecks der Landschaft schneiden. Wird ein solcher Schnittpunkt festgestellt, so wird das entsprechende Segment des Polygons in zwei Teilsegment aufgespalten, für die dann wiederum rekursiv die Schnittprüfung stattfindet.

Nach diesen Verarbeitungsschritten passt sich der Umriss der Straße wie gewünscht an den Höhenverlauf der Landschaft an. Es genügt jedoch noch nicht, das so entstandene Polygon einfach zu triangulieren, weil die so entstehenden Dreiecke dann immer noch die Dreiecke der Landschaft durchstoßen können. Dies geschieht z.B. wenn ein Vertex der Landschaft auf die XZ-Ebene projiziert komplett innerhalb des Straßenpolygons liegt. Die Dreieckt die diesen Scheitelpunkt enthalten, schneiden dann häufig die Dreiecke der Triangulierung des Straßenpolygons.

Zur Lösung des Problems muß die Triangulierung des Straßenpolygons alle Kanten der Landschaft enthalten, die innerhalb des Straßenpolygons liegen. Die erweist sich in der Praxis als zu komplex als das es im Zeitrahmen dieses Projekts umsetzbar wäre. Der Nächste Abschnitt stellt allerdings eine Näherung vor, die die bessere Ergebnisse liefert.

Delaunay Triangulierung des Staßenpolygons

Der Algorithmus zu Triangulierung von Polygonen neigt dazu, so genannte Fächer (Fans) zu produzieren, also viel aneinandergrenzende Dreiecke, die einen Punkt gemeinsam haben. Dadurch entstehen viele spitze Dreiecke mit einem sehr kleinem Innenwinkel. Dadurch stimmen die Kanten der Dreiecke meistens nicht mit den Kanten der Landschaft überein wodurch sich Straße und Landschaft durchstoßen sich. Um dies zu verbessern, wurde versucht die Triangulierung mit Hilfe des Edge Flipping Algorithmus in eine Delauney Triangulierung umzuwandeln, die Dreiecke mit gleichmäßigen Innenwinkeln erzeugt. Die Hoffnung ist, das die Kanten der Dreicke der Straße danach mehr den Kanten der Dreiecke der Landschaft entsprechen, zumal das Staßenpolygon an den Überscheidungsstellen mit den Dreiecken der Landschaft wie im letzten Abschnitt beschrieben in kleine Teilstücke aufgeteilt werden, was die Ausrichtung begünstigen sollte.

Die Implementierung ist leider aus Zeitgründen noch nicht ganz Fehlerfrei, aber kann beim Vergleich mit dem Ergebnis ohne den weiteren Verarbeitungsschritt schon an manchen stellen Verbesserungen sehen.

 Einfach trianguliertes Straßenpolygon

 Delaunay trianguliertes Straßenpolygon