Version vom 7. Oktober 2004, 13:36 Uhr

Octree

Bei einem Octree geht es um die hierarchische Einteilung einer Szene durch künstlich eingeführte Bereiche. Jeder Ast der baumartigen Struktur eines Octrees ist hierbei ein nach den Weltachsen ausgerichteter Würfel, dessen Raum wiederum durch bis zu 8 gleich große, kleinere Würfel eingeteilt werden kann die dann die Kinder dieses Astes dar stellen. Die Wurzel des Baumes bildet ein Würfel der die gesamte Szene umfasst.

Es gibt einige Abwandlungen bei der Verwendung von Octrees, beispielsweise könnte jeder Raum einen eigenen Octree erhalten, vom Prinzip her arbeiten sie jedoch alle gleich.

Für größere Landschaften eignet sich häufig eine Abwandlung eines Quadtrees (die 2D Variante eines Octrees) besser. Der Octree ist jedoch die allgemeinere Art eine 3D Szene einzuteilen.

Hierarchisches einteilen der Szene

Um den Octree für eine Szene zu erstellen, muss zuerst die Wurzel - also der Würfel der die Szene umgibt - gefunden werden. Wenn dieser Würfel gefunden wurde, so kann man für jedes Objekt (oder auch auf Dreiecksbasis) prüfen ob es in einen der 8 kleineren Würfel passt. Ist dies der Fall so wird dieses Objekt in diesen Würfel (welcher einen eigenen Ast bildet) verschoben. Die Objekte die nicht eindeutig in einen Würfel passen bleiben in der Wurzel des Baumes. Dieser Vorgang wird üblicherweise so lange rekursiv durchgeführt, bis eine weitere Unterteilung des Baumes nicht mehr sinnvoll wäre (da Beispielsweise zu wenige Objekte in die neuen Äste kämen).

Für statische Teile einer Szene (wo es häufig sinnvoll ist die einzelnen 3ecke in den Octree einzusortieren) können die einzelnen 3ecke auch an den Würfelgrenzen in 2 3ecke getrennt werden, um möglichst wenige 3ecke in den hierarchisch höher gelegenen Knoten zu habe. Um Hier eine brauchbare Abbruchbedienung für das Unterteilen des Baumes zu finden muss man beachten, das man nicht endlos 3ecke teilt. Eine Möglichkeit wäre beispielsweise zuerst nur den Octree zu erstellen, und die 3ecke erst an dem erstellten Octree entsprechend zu teilen.

Hierarchische Sichtbarkeitsabfrage am Octree

Hier Prüft man angefangen von der Wurzel jeden Knoten des Octrees auf seine Sichtbarkeit. Die 3 Möglichkeiten sind:

• Nicht sichtbar => zeichne weder diesen Knoten noch seine Unterknoten
• Komplett sichtbar => zeichne alle Elemente dieses Knoten als auch alle seine Unterknoten
• Teilweise sichtbar => zeichne alle Elemente dieses Knoten führe jedoch die Überprüfung an den Unterknoten fort

Kollisionsabfrage am Octree

Wen ein Objekt auf Kollisionen geprüft werden soll und der Octreeknoten in dem sich das Objekt befindet bekannt ist, so lässt sich auch die Kollisionsabfrage optimieren. Das Objekt muss nur im aktuellen Ast auf Kollisionen geprüft werden. Das heißt mit allen Objekten die sich:

• in hierarschisch höher gelegen Knoten,
• im aktuellen Knoten (in dem des zu prüfenden Objektes), oder
• in Ästen (Kinderknoten) des aktuellen Knotens

befinden.

Weiter Anwendungsbereiche

Die Hierarchische Natur des Octrees kann noch für einige weitere Anwendungsgebiete erweitert werden, welche ich aber nur kurz beschreiben möchte.

• Einteilung von dynamischen Lichtquellen: Hier können leicht die Knoten herausgefunden werden auf die eine Lichtquelle eine Wirkung hat und somit muss dieses Licht auch nur für diese Teile aktiviert werden.
• CSG (Constructive solid geometry): CSG lässt sich ebenfalls sehr effizient mit einem Octree durchführen. Der Nachteil ist natürlich, dass die Geometrie in Würfel zerlegt werden muss.

Links

• Octree DGL Tutorial