Implementierung:
Übersicht über den Quelltext:
Die folgende Aufstellung soll eine Übersicht über die Quelltextdateien geben, um den Einstieg in den Quelltext zu erleichtern:| Einsprungpunkte | |
| Terrain_main.java | Leitet eine Klasse von der Applet ab und stellt eine main-Methode bereit. |
| Terrain.java | Eigentlicher Einsprungpunkt. Kümmert sich um die OpenGL Events, führt die Initialisierungen durch und koordiniert den Rendervorgang. |
| Resourcen Management | |
| ContourManger.java | Verantwortlich für das Laden und verwalten der Höhenlinien. |
| ShaderManager.java | Verantwortlich für die Verwaltung der geladenen Shader. |
| TextureManager.java | Verantwortlich für die Verwaltung der geladenen Texturen. |
| Texture.java | Repräsentiert eine einzelne Textur. |
| ContourLine.java | Repräsentiert eine einzelne Höhenlinie eines ContourManagers. |
| Material.java | Repräsentiert ein Material. |
| Street.java | Repräsentiert eine Straße. |
| Kameras | |
| CenteredCamera.java | Implementiert eine Kamera, die immer auf eine festen Punkt blickt und sich mit der Maus um diesen Punkt drehen lässt. |
| FirstPersonCamera.java | Implementiert eine Kamera, die die Szene aus Sicht einer Preson darstellt. |
| Geometrie | |
| Triangulation.java | Stellt verschiedene Methoden zur Triangulierung von Polygonen mit und ohne Löchern bereit. |
| Geometry.java | Stellt diverse Methoden bereit. z.B. Umkreismittelpkt. eines Dreiecks, Schnittpunkt zweier Strecken, Punkt-in-Polygon-Test, Bestimmung der Normalen eins Polyeders für das Beleuchtungsmodell, usw. |
| Vector3.java | Repräsentiert einen 3-dimensionalen Vektor und stellt einige Operation bereit, wie z.B. Skalar- und Kreizprodukt |
| Verschiedenes | |
| Tools.java | Enthält kleinere Hilfmethoden wie: Erzeugung einer Liste um benachbarte Dreiecke zu bestimmen (Adjacency Information) und Konstruktion der konvexen Hülle eines Polygons |
| SVGImport.java | Importiert Höhenlinien aus den polygon-Tags einer SVG-Datei |
| resources/phong.frag | Implementiert den Shader für die Landschaft |
Triangulierung der Höhenlinien
Polygone mit einem Loch
Der einfachste Fall ist eine Höhenlinie, die genau eine untergeordnete Höhenlinie hat. Hier wird mit einer beliebigen Kante zwischen dem inneren und dem äußeren Polygon begonnen, die keine weitere Kante der beiden Polygone schneidet. Dann kann man als nächsten Punkt den Nachbarpunkt auf den äußeren oder dem inneren Polygon wählen. Die Implementierung wählt hier die Möglichkeit die die kürzere Kante erzeugt um kleinere Dreiecke zu erhalten.
Polygone mit mehreren Löchern
Höhenlinien mit mehr als einer verschachtelten Höhenlinie sind wesentlich schwieriger zu triangulieren. Die Implementierung verwendet den Ansatz, das Polygon der konvexen Hülle der verschachtelten Höhenlinien zu bestimmen (in der unteren Abbildung blau eingezeichnet). Zwischen diesem und dem Elternpolygon wird dann wie im vorherigen abschnitt beschrieben trianguliert. Danach werden die Löcher bestimmt, die innerhalb der Konvexen Hülle übrig geblieben sind. Diese sind wiederum Polygone, die mit dem Bresenham Scan Algorithms (siehe unten) trianguliert werden.
 |
 |
Höhe über dem Boden bestimmten
Zu Platzierung der Kamera in gleich bleibender Höhe über dem Boden in der First Person Ansicht und um den Straßenverlauf and die Landschaft anzupassen wird die Höhe über einem bestimmten Punkt der Landschaft in der XZ-Ebene benötigt. Dazu wird das Höhenlinienpolygon innerhalb des Baumes bestimmt, das diesen Punkt enthält, so dass keines der Kindpolygone den Punkt ebenfalls enthält. Danach werden nur die Dreiecke durchlaufen, die den Bereich zwischen dem gefundenen Polygon und dessen Kindpolygonen triangulieren. Ist das Dreieck an der gesuchten XZ-Position gefunden, wird die Höhe durch Lineare Interpolation bestimmt. Durch dieses Vorgehen kann die Zahl der zu durchlaufenden Dreiecke wesentlich reduziert werden.SVG Import
Beim SVG Import müssen die Polygone der Höhenlinien, die in der SVG-Datei "nebeneinander" liegen, in den Baum der Datenstruktur eingereiht werden. Hierzu wird der Punkt-in-Polgygon-Test häufig verwendet. Für jedes neue Polygon wird überprüft, ob es innerhalb des momentan betrachteten bereits bekannten Polygons liegt und nicht in einem seiner Kinderpolygone liegt. Ist dies der Fall, so wird das neue Polygon an dieser Stelle in den Baum eingeordnet. Es muss allerdings noch überprüft werden, ob Kinder des neuen Vaterpolygons innerhalb des neuen Polygons liegen. Ist dies der Fall, werden diese dem neuen Polygon untergeordnet.
 |
| SVG-Datei in Dia |
Verwendete Standardalgorithmen:
Im Folgenden werden allgmein bekannte Algorithmen kurz erläutert, die in der Implementierung Anwendung finden. Teilweise wurden diese selbst implementiert, teilweise wurde nur die Beispielimplementierung angepasst. Zu jedem Algorithmus ist die verwendete Quelle angegeben. Die Algorithmen sollen hier nicht tiefergehend erklärt werden, sondern es soll nur die zu Grunde liegende Idee dargestellt werden. Weitere Details bieten die Links zu den jeweiligen Quellen.
Konvexe Hülle: Graham Scan
Beim Graham Scan wird zunächst der Punkt mit der niedrigsten Y-Koordinate (im 2-dimensionalen) bestimmt (a). Dann werden die übrigen Punkte nach dem Winkel ihrer Verbindungsstrecken mit dem niedrigsten Punkt sortiert (b). Verbindet man nun der Reihe nach die so sortierten Punkte, erhält man bereits ein Polygon, das eine Art Hülle um die Punktwolke darstellt (c).
Jetzt müssen aus diesem Polygon noch die Ecken entfernt werden, die nicht konvex sind, bei denen also der links liegende Winkel < 180° ist. Das übrig bleibende Polygon ist dann die konvexe Hülle der Punktwolke.
Quelle:http://www.inf.fh-flensburg.de/lang/algorithmen/geo/graham.htm
Triangulierung eines einfachen Polygons: Ear Clipping
Eine Ecke eines einfachen Polygons heißt Ohr, wenn die Strecke zwischen den beiden Nachbarecken komplett im Inneren des Polygons liegt. Jedes Polygon (das kein Dreieck ist) hat mindestens 2 Ohren.
 |
| Einfaches Polygon mit genau 2 Ohren |
In jedem Schritt kann also ein Ohr zur Liste der erzeugten Dreiecke hinzugefügt und aus dem Ursprungspolygon entfernt werden. Das entstehende Polygon hat wieder mindestens 2 Ohren.
Quelle: http://cgm.cs.mcgill.ca/~godfried/teaching/cg-projects/97/Ian/twoears.html
Punkt im Polygon: Algorithmus aus Gamasutra
Hinweis: Gamasutra ist ein Onlinemagazin für Entwickler von Videospielen auf der immer wieder Artikel zu verschiedensten Themen veröffentlich werden. Die Seite erfordert eine kostenlose Anmeldung.
Der Algorithmus teilt die Ebene wie in der unteren Abbildung gezeigt anhand der Koordinaten des zu untersuchenden Punktes in vier Quadranten ein. Dann werden die Ecken des Polygons der Reihe nach durchlaufen. Immer wenn bei Übergang von einer Ecke des Polygons zur nächste die Grenze zwischen zwei Quadranten im Urzeigersinn überschritten wird, wird ein interner Zähler um eins erhöht. Bei einer Überschreitung im Gegenurzeigersinn wird der Zähler dagegen um eins verringert. Zu beginn wird der Zähler mit null initialisiert. Hat der Zähler nach dem Durchlaufen aller Punkt den Wert +4 oder -4, liegt der Punkt innerhalb des Polygons. Der Fall das ein Übergang von einem zum übernächsten Quadrant stattfindet, also z.B. von I nach III, muss gesondert behandelt werden, ist aber ähnlich einfach.
Beispiel:
Hier passiert beim Übergang von Punkt 1 zu 2 und Punkt 2 zu 3 nichts, da keine Grenzen überschritten werden. Zwischen Punkt 3 und 4 findest eine Überschreitung der Grenze zwischen Quadrant I und II im Urzeigersinn statt. Der Zähler wird also um 1 erhöht. Beim Übergang zwischen 4 und 5 findet dagegen ein Übergang zwischen Quadrant II und I im Gegenurzeigersinn statt. Der Zähler wird also wieder um 1 verringert. Sind alle restlichen Punkte durchlaufen, bleibt der Zähler bei +4 stehen, und somit liegt der Punkt im Polygon.
Quelle: http://www.gamasutra.com/features/20000210/lander_01.htm
Delaunay Triangulierung: Edge Flipping
Eine Triangulierung heißt Delaunay Triangulierung, wenn kein anderer Punkt innerhalb des Umkreises eines jeden Dreiecks der Triangulierung liegt. Der Edge Flipping Algorithmus geht von einer gegebenen Triangulierung aus und stellt das Delaunay Kriterium her, indem die gemeinsame Kante zwischen jeweils zwei benachbarten Dreiecken gekippt wird (Flipping). Es lässt sich beweisen, dass die beiden Dreiecke danach das Kriterium erfüllen.Beispiel:
Links sieht man zwei benachbarte Dreiecke, wobei der markierte Punkt innerhalb des Umkreises des roten Dreiecks liegt. Somit verstoßen die Dreiecke also gegen das Delaunay Kriterium. Rechts sind die Dreiecke mit gekippter gemeinsamer Kante abgebildet. Jetzt erfüllen beide Dreiecke das Kriterium.
In der Praxis ist die Implementierung etwas aufwändiger, weil z.B. die Nachbarschaft eines Dreiecks erst bestimmt werden muss und beim Kippen der Kante der Umlaufsinn der Dreiecke erhalten bleiben muss. Außerdem ist es oft schwer, das Delaunay Kriterium mit bloßem Auge zu prüfen. Zur vereinfachten Bestimmung der Nachbarschaften wird eine Adjazenliste verwendet. Es wird vorab eine Liste generiert, die pro Dreieck drei Indizes enthält, pro Kante des Dreiecks einer. Die Indizes zeigen dabei auf auf die entsprechende Kante des angrenzenden Dreiecks.
Quelle: Diverse. z.B. Wikipedia Artikel zur Delaunay-Triangulation.