Strategien fürs Animieren von grobkörnigen Materialien

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.