Das Darstellen von Terrain ist ein sehr wichtiges und oft behandeltes Thema in der Computergrafik und in Spielen. Es gibt zahlreiche Algorithmen sowohl für die Erstellung von Höhendaten als auch zum Darstellen des Terrains. In diesem Buch werden Algorithmen vorgestellt, die Höhendaten für realistische Landschaften generieren. Ein wesentlicher Punkt bei der Analyse dieser Algorithmen ist die prozedurale und parametergesteuerte Generierung dieser Daten, welche eine zufällige, anhand von bestimmten Regeln definierte realistische Landschaft liefern. Diese soll ohne weitere Bearbeitung direkt für Spiele verwendbar sein. Im zweiten Teil geht es um die effiziente Darstellung dieser Landschaften. Dafür wird die Technik der Geometrie Clipmaps verwendet, welche eine moderne Art der Berechnung von Landschaften mit einer sehr hohen grafischen Qualität erlaubt. Dabei wird die Technik kurz vorgestellt und danach näher analysiert. Ein für dieses Buch implementiertes, frei skalierbares Referenzprogramm liefert dafür die erforderlichen Messdaten. Es wird untersucht, warum diese Technik vor allem für Spiele interessant ist und welche Vorteile sie bietet. Im dritten und letzten Teil werden Algorithmen und Techniken vorgestellt, welche von Spielen häufig verwendet werden. Beispiele dafür sind Kollisionserkennung, Culling Techniken, Schattenberechnung, Sichtbarkeitstests usw. Analysiert wird dabei, ob und inwiefern diese Algorithmen mit den Geometrie Clipmaps funktionieren und wie sie für Spiele effizient eingesetzt werden können.

Textprobe: Kapitel 4, Geometrie Clipmaps: 4.1, Einführung: Die Approximation von Höhendaten beim Zeichnen ist ein wichtiges Thema für die Echtzeitdarstellung von Landschaften insbesondere bei Außenlevels von Spielen. LOD (Level Of Detail) Algorithmen werden dazu eingesetzt die Terraindaten optimal für das Zeichnen vorzubereiten, um das Terrain mit größt möglichem Detailgrad zu akzeptabler Bildwiederholrate darzustellen. Dazu wurden im Laufe der Zeit zahlreiche unterschiedliche Ansätze entwickelt. Eingeteilt werden diese Algorithmen wie folgt: 1. Irregular meshes: Diese Algorithmen verändern das Gitternetz, das dem Terrain zugrunde liegt. Regionen mit geringeren Details (zum Beispiel ebene Flächen) werden mit weniger Polygonen dargestellt als Regionen, die mehr Details erfordern (zum Beispiel Bergrücken). Ziel dieser Algorithmen ist die Polygonzahl bestmöglich zu minimieren, ohne dass relevante Details des Terrains verschwinden. Vorteil dieser Technik ist die geringe Anzahl an Polygonen, die aber nur durch eine rechenintensive Vorausberechnung ermöglicht werden kann. 2. Bin-tree hierarchies: Die Polygone der Gitternetze werden in einem binären Baum eingeteilt. Anhand dieser Struktur werden dann Areale mit geringerem Detailgrad durch zusammengefasste Polygone dargestellt. 3. Bin-tree regions: Der binäre Baum wird anders als bei den Bin-tree hierarchies nicht über die Achsen des Koordinatensystems erstellt und ermöglicht so eine bessere Approximation der Terraindaten. 4. Tiled blocks: Das Terrain wird in Blöcke eingeteilt (zum Beispiel mit einem Quadtree). Diese Blöcke werden dann in unterschiedlichen Detailstufen gezeichnet. Hauptaufgabe der Algorithmen ist hier die korrekte Anzeige der Grenzen zwischen Blöcken unterschiedlicher Detailstufen. 4.2, Theorie: Geometrie Clipmaps stellen eine relativ neue Art der Terrain Rendering Algorithmen dar und wurden erstmals in einem Paper von Frank Losasso und Hugues Hoppe vorgestellt. Ihr Ansatz basiert auf einer, damals schon bekannten Technik, den Texture Clipmaps. Diese Texture Clipmaps, oder auch virtuelle Texture Mipmaps, werden verwendet, um eine Textur in mehreren Detailstufen darstellen zu können. Die Geometrie Clipmaps sind ein Ansatz diese Art von LOD Berechnung für eine Landschaft zu verwenden. Dabei hängt die Detailstufe des Terrains nur von dem Abstand zum Betrachter ab und nicht wie andere Algorithmen von der Geometrie des Terrains. Ziel dieser Technik ist, im resultierenden gezeichneten Bild ungefähr ein 1:1 Verhältnis von Pixel am Bildschirm zu den Dreiecken des Gitternetzes des Terrains zu erreichen. 4.2.1, Funktionsweise: Im Folgenden wird die Technik der Geometrie Clipmaps näher erklärt. Folgende Dinge braucht man für die Berechnung: 1. Kamera: Die 3D Szene benötigt eine Kamera, einen Betrachter, von dessen Sicht aus die Szene gezeichnet wird. Für die Clipmaps benötigt man hier die relative Position der Kamera in Bezug auf das Terrain, um das Terrain mit den richtigen Detailstufen zeichnen zu können. Weiters ist es sinnvoll, wenn man die Kamera bewegen kann, denn dann kann man die dynamische Veränderung der Clipmaps am Gitternetz des Terrains auch sehen. 2. Gitternetz: Ein Gitternetz aus Vertizes repräsentiert das Terrain. 3. Heightmap: Basis jedes Terrains ist eine Heightmap, welche die Höhenwerte des Terrains liefert. Diese können aus drei verschiedenen Quellen kommen. Entweder echte Höhendaten in einem dafür vorgesehenen Datenformat, durch ein 3D Programm erstellte Höhenkarte oder wie in der Referenzimplementierung eine prozedural erstellte Heightmap. Anhand dieser Höhenkarte werden die Höhenwerte der einzelnen Vertizes des Gitternetzes verändert. Höheninformationen: Basis jeder Landschaft sind die Höheninformationen, welche die Höhe der einzelnen Vertizes das Gitternetz des Terrains verändern. Diese werden normalerweise einmal bei Programmstart geladen und stehen dann die ganze Zeit zur Abfrage bereit. Bei endlichen Höhenkarten entsteht hier nur ein Problem bei sehr großen Heightmaps, die eventuell nicht mehr in den Speicher passen. Bei quasi unendlichen Landschaften wie zum Beispiel die Höhendaten vom Mars, müssen die Daten laufend in einer Datenstruktur aktualisiert werden. Dies geschieht immer dann, wenn die Kamera den Standpunkt ändert und es zu einer so genannten Clipmap Aktualisierung kommt. Grundsätzlich unterscheidet man bei den Höhendaten für das Terrain unter unendlichen Heightmaps und endlichen. Die unendlichen Heightmaps sind zum Beispiel die Geoinformationen von tatsächlichen Landschaften, die über Messungen erfasst wurden. Die Größe solcher Landschaften ist so groß, dass sie im Kontext der Implementierung quasi unendlich sind. Bei endlichen Heightmaps, die üblicherweise bei Spielen verwendet werden, entsteht das Problem, dass man irgendwann an den Rand der Höheninformationen kommen kann. Nun gibt es mehrere Möglichkeiten wie hier verfahren werden kann. Bei kachelbaren Heightmaps könnte man beispielsweise die Heightmap wiederholen. Eine andere Möglichkeit kann sein, alle Werte die außerhalb der Heightmap liegen mit einer Höhe von 0 anzunehmen. Für Spiele würde man so in Verbindung mit einer Wasseroberfläche Inseln schaffen, die von einem endlosen Ozean umgeben sind.

• Geometry

• Computergrafik

• Algorithmus

• Höhendaten

• Landschaft

Werner Ziegelwanger, MSc, Jahrgang 1984, schloss sein Masterstudium Game Engineering und Simulation im Jahre 2011 erfolgreich mit dem Titel Master of Science in Engineering ab. Schon während seiner Ausbildung beschäftigte sich der Autor mit der Programmierung von Spielen und Computergrafik. Besonderes Interesse hatte er dabei an der Simulation und Darstellung von Landschaften. Aus dieser Faszination ist dieses Buch entstanden. Seit seinem Studium arbeitet der Autor als Spieleprogrammierer in einem namhaften Unternehmen.