Mit modernen Computern werden immer aufwendigere virtuelle Spielwelten, 3D-Simulationen und andere Anwendungen möglich, die äußerst realistische Grafik bieten. "Für die Animation oder um über den Bildschirm bewegte oder fliegende Objekte zu simulieren, müssen die Objekte auch auf Kollisionen reagieren können", betont Thomas Larsson vom Mälardalen Research and Technology Centre an der schwedischen Mälardalen University. Er hat einen Ansatz entwickelt, damit entsprechende Kollisionsberechnungen noch schneller erfolgen können - selbst, wenn die virtuellen Objekte dabei realistisch stark deformiert werden.

Figuren sollen nicht durcheinander hindurch laufen

Die Kollisionsabfrage verhindert, dass beispielsweise Spielfiguren einfach durcheinander hindurch laufen. "Die Kollisionsberechnungen müssen in vielen Fällen genau wie der Bildaufbau selbst in wenigen Millisekunden erfolgen, da sonst die Interaktivität und damit das Nutzererlebnis leidet", betont Larsson. Larsson setzt auf adaptive Algorithmen zur Kollisionsabfrage in Verbindung mit Optimierungen an den sogenannten "Bounding Volumes". Das sind in der Computergrafik geometrische Grenzflächen, die die virtuellen Objekte komplett umschließen.

Rechenaufwand soll sinken

Solange sich die Bounding Volumes zweier Objekte nicht berühren, ist somit eine Kollision auszuschließen. Komplexe Objekte werden dabei mithilfe ganzer Bounding-Volume-Hierarchien beschrieben, sodass die Grenzflächen bei Bedarf - also, wenn sich zwei Objekte kollisionsgefährlich annähern - immer genauer aufgelöst werden. "Bei deformierbaren Körpern liegt das Hauptaugenmerk auf einer schnelleren Rekonstruktion und Korrektur dieser Hierarchien", beschreibt Larsson. Die einzelnen Grenzflächen werden dazu möglichst einfach gehalten. Für starre Körper dagegen schlagen Larsson und Kollegen mit dem "Slab Cut Ball" ein neuartiges Bounding Volume vor, das wenig Speicher verbraucht und durch das es länger dauert, ehe bei einer drohenden Kollision mit höherer Auflösung gearbeitet werden muss. Dadurch sinkt insgesamt der Rechenaufwand.

Einsatzgebiete

So theoretisch die Arbeit an der verbesserten Kollisionsabfrage auch klingt, so praktisch ist eine ihrer möglichen Anwendungen. "Obwohl unser Ziel die High-Level-Simulation war, werden auch die Modelle in Spielen immer komplexer. Es werden also auch im Gaming-Bereich bessere Methoden nötig", betont Larsson. Abgesehen von Computerspielen zählen etwa die Robotik, das Virtual Prototyping und Chirurgie-Simulationen zu den Anwendungsfeldern, die von Larssons Arbeit profitieren könnten. (pte)