©Jakub Cejpek, 123rf.com

Unter den Special Effects in PC-Spielen und in gerenderten Filmen spielt Sand noch eine Nebenrolle, zumal das Riesel für 3D-Programmierer Tücken bereithält. Open-Source-Programmierer aus Bremen zeigen aber, wie sie realistisch animierte Fußabdrücke auf losem Untergrund hinterlassen.

Die Computergrafik der Spieleindustrie, beschäftigt viele Programmierer mit der möglichst realitätsgetreuen Darstellung von Wasser. Für die Entwicklung des preisgekrönten Windows- und Konsolen-Games Bioshock [1] hat der Hersteller 2K Games sogar eigens auf Flüssigkeiten spezialisierte Programmierer eingestellt, um die Unterwasserstadt Rapture noch lebensechter zu gestalten.

Aber Wasser ist nicht das einzige Naturphänomen, das für 3D-Software-Entwickler eine interessante Herausforderung darstellt. Das Projekt Blendax (Kasten “Das Blendax-Team”) der Universität Bremen nimmt sich der Aufgabe an, mit möglichst einfachen Mitteln auf herkömmlichen Heim-PCs einen virtuellen Sandkasten zu konstruieren. Als Werkzeuge dienen Open-Source-Tools. Neben Blender (Abbildung 1, [2]) kommen die freie Entwicklungsumgebung Eclipse [3] und die Lightweight Java Gaming Library (LWJGL, [4]), die OpenGL [5] gleich mit im Gepäck hat, zum Einsatz.

Abbildung 1: Eine einfache, noch recht unförmige Sandkugel im 3D-Animations- und -Rendering-Programm Blender.

Das Blendax-Team

Im Wintersemester 2007 haben Prof. Dr. Rainer Malaka, die Arbeitsgruppe Digitale Medien und die Studenten Valeri Kremer und Igor Pfeifer das Projekt Blendax ins Leben gerufen. Zehn Informatikstudenten (Abbildung 16) der Universität Bremen arbeiteten ab dem Wintersemester 2008 unter der Leitung von Dr. Martin Faust an der Idee, Sand mit Open-Source-Tools zu animieren. Abbildung 16: Die Mitwirkenden des Blendax-Projektes. Obere Reihe: Dr. Martin Faust, Prof. Dr. Rainer Malaka, Ulf Braun, Jan Holthusen, Malte Humann und Valeri Kremer. Untere Reihe: Igor Pfeifer, Norman Gülcü, Anton Moor und Christoph Greulich. Nicht auf dem Foto: Markus Aust und Jannis Stoppe.

Eine Datenstruktur für Sandkörner

Für den Sandkasten im Garten reicht ein Konstrukt aus Holzplatten und Nägeln, aber die Darstellung im Computer erweist sich als deutlich komplizierter. Die Präsentation jedes Sandkorns als einzelnen Partikel in einem Volumenmodell mit dreidimensionalen Pixeln (Voxeln), bedarf eines Speicher- und Rechenaufwandes, der von keinem normalen Computer mehr zu bewältigen ist.

Alternativen gibt es, aber alle haben sie ihre Schwächen. Besonders Computerspiele generieren Oberflächen häufig aus einer simplen Height Map, einer zweidimensionale Tabelle. Deren Zellen enthalten ähnlich wie bei einer Bitmap-Grafik die Höheninformation der jeweiligen Position. Tatsächlich implementieren viele Programmierer Height Maps in der Praxis häufig als Graustufen-Bitmaps. Je heller die Farbe, desto höher der Boden, je dunkler, desto tiefer. Solche Flächen lassen sich schon in primitiven Zeichenprogrammen malen. Für die Darstellung von interaktivem Sand reicht die Height Map jedoch nicht aus, weil sie nur eine einzelne Ebene repräsentiert, nicht aber das Volumen des Sands oder unterschiedliche Bodenschichten (Abbildung 2).

Abhilfe schafft das von Onoue und Nishita vorgeschlagene Konzept der Height Span Map (Abbildung 3, [6]) Die Idee ist so einfach wie genial: Anstelle der Höheninformation ist in jeder Zelle der Tabelle ein Height Span untergebracht, eine Säule aus den einzelnen Bodenschichten an der jeweiligen Position (Abbildung 4). Die einzelnen Segmente enthalten nicht nur eine Höheninformation, sondern zwei, einen Start- und einen Endpunkt. Außerdem lässt sich hier festhalten, um welches Material es sich handelt, zum Beispiel Sand, massives Gestein oder aber auch Luft.

Abbildung 2: Eine Säule aus zwei Materialien (Sand und ein anderes Objekt) wird der Unterlage hinzugefügt. Eine Height Span Map speichert dann auch die Beschaffenheit und Volumina der Säule, während…

Abbildung 3: … bei einer Height Map der Algorithmus nur die Höheninformationen der höchsten Punkte (Maxima) betrachtet, er „verschluckt“ die anderen Schichten.

Abbildung 4: Die Height Span Map löst das Problem eleganter: Mehrere Materialschichten dürfen übereinander liegen – theoretisch sogar mit Lücken dazwischen, die vielleicht ganze Tunnel bilden.

Sich durch Sand bewegen

Darüber hinaus muss die Datenstruktur auch die Objekte repräsentieren, die sich durch den Sand bewegen und ihn beeinflussen. Für ein vorher modelliertes Objekt, etwa eine Schaufel oder einen Fuß, der einen Abdruck hinterlassen soll, braucht es zunächst im Sandkasten eine Ortsbestimmung. Dazu spannt die Software um das Fuß-Modell eine Bounding Box auf, die den kleinstmöglichen Quader beschreibt, der noch das vollständige Fuß-Modell enthält. Die X- und Y-Koordinaten der Bounding Box geben an, welche Height Spans möglicherweise Fußsegmente enthalten.

Nun kommt das Raycasting-Verfahren dran (Abbildung 5), mit dem zum Beispiel Blender durch jede Säule einen Strahl schickt (to cast a ray = einen Lichtstrahl werfen).

Abbildung 5: Das Raycasting-Verfahren schrittweise illustriert. Mit Hilfe der Strahlen ermittelt die Software ständig die genaue Position und Ausdehnung des Fußes.

Strahlenwurf

Gibt es Schnittpunkte zwischen dem Strahl und dem Fuß-Modell, so ist der Säule ein neues Segment hinzuzufügen. Das bekommt die Schnittpunkte mit dem Fuß als Start- und Endpunkt zugewiesen und übernimmt die Materialeigenschaft des Fuß-Modells.

Dieses Raycasting findet nicht nur einmal statt, sondern wiederholt sich jedes Mal, wenn der Fuß sich bewegt, um dessen neue Position zu lokalisieren. Abbildung 1 zeigt das mit einer Sandkugel.

Damit der Fuß im Sand Abdrücke hinterlässt, muss ein Verdrängungsalgorithmus implementiert werden, der den Sand verschiebt, wenn sich der Fuß so weit bewegt, dass die Sand- oder Fuß-Segmente der Height Span einander überlagern (Abbildung 6). Sand zu verschieben bedeutet in diesem Fall, soviel davon aus dem überlagerten Segment zu subtrahieren, wie nötig ist, um die Überlagerung aufzulösen (Abbildung 7).

Die gleiche Menge Sand muss der Programmierer dann auf ein oder mehrere angrenzende Zielsegmente addieren lassen (Abbildung 8). Gibt es keine geeigneten Zielsegmente, so muss er in benachbarten Height Spans neue Segmente mit der entsprechenden Menge Sand einfügen. Verdrängt der Fuß das Material vollständig, ist das leere Segment zu löschen.

Abbildung 6: Der Fuß versinkt im Sand. Aus der Kontaktfläche ergeben sich die btroffenen Sand-Segmente…

Abbildung 7: … und damit auch die Menge an Sand, für die der Programmierer Verdrängungsmechanismen anwerfen muss.

Abbildung 8: Der verdrängte Sand türmt sich zunächst um den Fuß herum auf. Ein Mechanismus muss her, der für eine realistische Verteilung sorgt.

Woher kommt der Fuß?

Die Überlagerung kann dabei auf zwei verschiedene Arten entstehen: Horizontal und Vertikal. Drückt der Fuß von oben in den Sand, dann verdrängt er den Sand gemäß der physikalischen Gegebenheiten zur Seite.

Am Rand des Fußes sollte sich der Sand auftürmen. Die Software muss also bei jeder Überschneidung prüfen, ob mehrere Segmente des Fußes von der Kollision betroffen und ob diese benachbart sind. Wenn die beteiligten Segmente eine zusammenhängende Fläche bilden, dann stellen deren äußerste sich mit dem Sand über lagernden Fuß-Segmente die Kontur.

Jetzt kann der Entwickler für jedes Segment der Fläche seine Distanz zur Kontur berechnen. Er fängt in der Mitte an, also bei den Segmenten, die am weitesten vom Rand entfernt sind. Dann verteilt er den zu verdrängenden Sand, also den, der über der Untergrenze des Fuß-Segments liegt, gleichmäßig auf alle umliegenden Segmente, die eine geringere Distanz zur Kontur haben. Dieses Vorgehen schiebt den Sand tatsächlich von der Mitte an den Rand.

Schleifspur und Schaufel

Eine horizontale Bewegung des Fußes dagegen verdrängt den Sand nicht mehr gleichmäßig in alle Richtungen, sondern hauptsächlich in Bewegungsrichtung, sodass eine Schleifspur entsteht. Hier ist weder eine Fläche noch eine Kontur zu errechnen. Stattdessen verschiebt eine Überschneidung von zwei Segmenten den zu verdrängenden Sand vollständig in der Bewegungsrichtung.

Auf dem Fuß ist Sand unangenehm, auch für den Programmierer, weil die Auflage schließlich mitkommen muss, wenn sich der Fuß darunter bewegt. Das heißt, wann immer sich die Fuß-Segmente in der Height Span Map in einen anderen Span verschieben, muss die Software prüfen, ob sich unmittelbar darüber Sandsegmente befinden. Wenn ja, sind diese sofort mit zu verschieben. Wer jetzt den Fuß durch eine Schaufel ersetzt, kann so schon im Sandkasten buddeln.

Erosion

Zwar gibt es bereits eindeutige Fußspuren im virtuellen Sandkasten, der verdrängte Sand hat aber immer noch eine sehr unnatürliche Form. Verhältnismäßig große Säulen aus Sand türmen sich auf, die eigentlich zu einem Haufen zusammenfallen müssten (Abbildung 9).

Geologen sprechen von Erosion, wenn äußere Einwirkungen wie Wind und Wasser Material abtragen. Im beschrieben Beispiel interessiert aber primär der Einfluss der Gravitation. Selbst dafür wäre es zu aufwändig, die realen physikalischen Gegebenheiten zu simulieren. Vielmehr soll der Sand so versickern, dass das Resultat bei sparsamer Rechenleistung noch einigermaßen ansehnlich bleibt.

Abbildung 9: Bevor die Erosion mit Hilfe zellulärer Automaten stattfindet, türmt sich der Sand teilweise in unnatürlich hohen Säulen auf.

Bei den gewöhnlichen, zweidimensionalen Tabellen gibt es für solche Probleme bereits Lösungsansätze. Ein Satz von Veränderungsregeln legt bei bestimmten Konstellationen der Zustände von benachbarten Zellen definierte Veränderungen fest. Man spricht bei solchen Modellen auch von zellulären Automaten.

Ein typisches Beispiel dafür ist Conways Spiel des Lebens [7], bei dem jede Zelle genau zwei Zustände haben kann – “lebendig” oder “tot”. Regeln legen fest, ob die Zelle in der Mitte im nächsten Schritt stirbt oder neu geboren wird, wenn die acht umliegenden Zellen einer bestimmten Konstellation entsprechen.

Ein solcher Automat eignet sich hervorragend, um den virtuellen Sand erodieren zu lassen, da er auf einer gewöhnlichen Height Map problemlos operieren kann. Die Regeln dafür sind vergleichsweise simpel. Jede Zelle einer Height Map enthält eine Höheninformation, die die Software mit den acht umliegenden Zellen vergleicht.

Aus der Entfernung und dem Höhenunterschied lässt sich die Steigung zwischen zwei zu vergleichenden Zellen ermitteln. Sie darf einen definierten Schwellenwert nicht übersteigen, sonst muss der überschüssige Sand erodieren, also auf die niedrigere Zelle rutschen. Aber Sand versickert nicht nur in eine Richtung. Der Programmierer muss zunächst für alle Nachbarn die Steigung berechnen lassen und den überschüssigen Sand gleichmäßig auf Zellen verteilen, deren Steigung über dem Schwellenwert liegt. Ein gutes Ergebnis erzielt er mit einem Schwellenwert von 30 Grad (Abbildung 10).

Abbildung 10: Eine maximale Steigung zwischen benachbarten Zellen definiert, wann und wie lange Sand abrutscht und sich gleichmäßiger über sie verteilt. Ist der Winkel größer als der definierte Schwellwert, so versickert der Sand auf die benachbarten Säulen.

Noch etwas komplizierter

Damit so ein Automat auch auf einer Height Span Map funktioniert, müssen die Programmierer das Regelwerk entsprechend erweitern. Während bei der Height Map für jede Zelle acht potenzielle Nachbarn existieren, gibt es bei der Height Span Map zwar auch nur acht benachbarte Säulen, jede davon enthält aber mehrere Segmente, die als potenzielle Erosionsziele in Frage kommen.

Es gilt also, herauszufinden, auf welche dieser Segmente der Sand fällt, bevor man die Steigung berechnen kann. Zu beachten ist auch, dass Sand nicht nur auf andere Sandsegmente fallen kann, sondern natürlich auch auf massives Gestein oder andere Objekte innerhalb des Sandkastens. Damit nicht genug: Wer die Regeln direkt auf die Height Span Map selbst anwendet, beeinflusst mit jeder Änderung bereits einige Zellen, die er in diesem Durchlauf möglicherweise noch gar nicht betrachtet hat.

Es kann also passieren, dass sich eine Änderung im selben Berechnungsschritt viel weiter auswirkt, als eigentlich geplant. Darum ist es wichtig, die nötigen Veränderungen auf der richtigen Height Span Map zu berechnen, die Änderungen aber zumindest vorerst nur auf einer Kopie durchzuführen. Diese Kopie ersetzt nach dem Durchlauf die ursprüngliche Height Span Map. Anstatt der riesigen Säulen findet der Betrachter nun erodierte Sandhaufen vor (Abbildung 11).

Abbildung 11: Schon besser: Zelluläre Automaten helfen, die Erosion glaubwürdiger zu gestalten. Der Erosionsvorgang verteilt den Sand gleichmäßig.

Grafik: Punkt für Punkt

Der virtuelle Sandkasten scheint vollständig, denn der Sand lässt sich bewegen und verdrängen und erodiert, sobald ein Sandhaufen zu groß wird. Ein sehr wichtiges Puzzlestück fehlt bisher allerdings: Die grafische Darstellung. Auch die erledigt Open-Source-Software, wie versprochen mit Java.

Um aus der tabellenartigen Datenstruktur eine virtuelle Landschaft zu machen und Objekte wie etwa den Fuß per Tastendruck darin zu bewegen, greift der Programmierer auf die umfangreichen Möglichkeiten der Light Weight Java Game Library [4] zurück. Damit kann er Tastatur- und Mauseingaben auslesen und verarbeiten, und dank der mitgelieferten Grafikbibliothek OpenGL entsteht aus der Height Span Map eine dreidimensionale Landschaft. Vom Prinzip her sind eine Height Span Map und eine Height Map ähnlich zu visualisieren. Allerdings enthält die gewöhnliche Height Map nur Höheninformationen an bestimmten Koordinaten.

Bei der Height Span Map dagegen heißt es, viele verschiedene Schichten zu unterscheiden. Komplexe Gebilde wie Tunnel können entstehen, was die Visualisierung um ein Vielfaches erschwert. Wer diese Eigenschaften ignoriert und nur die obersten Punkte der Height Span Map zu einer Fläche verbindet, der verliert aber nahezu alle Vorteile der Datenstruktur.

Die einfachste und ressourcenschonendste Möglichkeit, das Ergebnis sichtbar zu machen, ist die punktweise Visualisierung der Height Span Map. Dazu lässt der Programmierer für jedes Segment ein Punkt zeichnen, der die obere Grenze des Segments repräsentiert. Die Implementierung ist einfach und das Resultat nicht besonders schön, aber es eignet sich gut, um den Sandkasten zu testen und Fehler zu suchen. Etwas hübscher wird das Ganze, wenn für jedes Segment ein massiver Quader an die Stelle der einfachen Punkte tritt (Abbildung 12 und 13).

Mit unterschiedlichen Farben, je nach Material, oder sogar dem Einsatz von Texturen, lässt sich ein ansehnliches Ergebnis erzielen. Natürlich ist das noch sehr eckig und kantig, aber der Betrachter erkennt, ob alles richtig funktioniert und einzelne Schichten und Objekte deutlich voneinander abgrenzen.

Abbildung 12: Die Blockdarstellung schaut bereits deutlich realistischer aus, …

Abbildung 13: … vor allem in Kombination mit einem Fußmodell.

Noch schöner

Wirklich schön macht das Ergebnis jedoch erst eine glatte Flächendarstellung, wie sie herkömmliche Height Maps benutzen. Dazu versucht der Programmierer, die Height Span Map in einzelne zusammenhängende Abschnitte zu unterteilen, indem er benachbarte Segmente des gleichen Materials zu einer Einheit gruppiert. Die oberen Grenzen der Segmente jeder einzelnen Gruppe darf er dann wieder wie bei einer gewöhnlichen Height Map zu einer Fläche zusammenfassen. Der Rechenaufwand wächst hier allerdings sehr schnell an. Deshalb gilt es, zunächst die Datenstruktur der Height Span Map zu optimieren, damit sich benachbarte Segmente leichter finden lassen. Wie bei einer Height Map vernachlässigt diese Darstellung aber die Information über Seiten- und Grundflächen der einzelnen Segmente.

Auch das Problem, eine beliebige Fläche geglättet darzustellen, ist nicht neu. Gängige 3D-Modellierungs-Werkzeuge bieten dafür so genannte Subdivider (Abbildung 14 und 15) an. Für die Height Span Map heißt das, die zusammenhängenden Segmente gleichen Materials zu suchen und daraus eine geschlossene Fläche zu erstellen. Anschließend muss über jedes dieser Objekte ein Subdividing-Algorithmus laufen, der beliebig oft die großen Dreiecke einer Fläche in mehrere kleinere unterteilt und die Eckpunkte so verschiebt, dass sich die Oberfläche glättet. Zwar bietet diese Methode das optisch schönste Ergebnis, sie hat aber auch ihren Preis: Für eine Echtzeit-Anwendung ist sie in den meisten Fällen schlicht zu rechenintensiv.

Abbildung 14: Der Abdruck in der geglätteten Subdivision-Darstellung …

Abbildung 15: … passt perfekt zu dem eingebetteten Fußmodell.

Ein zu großer Sandkasten

Die beschriebene Simulation steckt buchstäblich noch im Sandkastenalter, denn ab einer gewissen Größe der Height Span Map reicht ein herkömmlicher Computer nicht mehr aus, um die Berechnungen der zellulären Automaten in angemessener Zeit durchzuführen. Auch die Visualisierung mit Hilfe von Subdividern und die Suche nach zusammengehörenden Segmenten stößt den Rechner früher oder später an seine Belastungsgrenze.

Zwar gibt es im Verhältnis zu einem Partikelsystem drastische Geschwindigkeitsvorteile. Für den effizienten Einsatz in Computerspielen und dergleichen ist diese Lösung aber längst noch nicht ausgereift genug. Wer selbst versuchen will, mit eigenen Optimierungen mehr herauszuholen, hat dazu bald Gelegenheit: Fürs Linux-Magazin will das Projekt seine bisherigen Errungenschaften auf seiner Webseite [8] veröffentlichen.(mfe)