Octree
 | |
| Eine Skizze die verdeutlicht wie der Raum in einem Octree eingeteilt wird. |
Inhaltsverzeichnis
Octree
Bei einem Octree geht es um die hierarchische Einteilung einer Szene durch künstlich eingeführte Bereiche. Der Octree ist damit eine mögliche Raumunterteilungstechnik. 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 Dreiecke in den Octree einzusortieren) können die einzelnen Dreiecke auch an den Würfelgrenzen in 2 Dreiecke getrennt werden, um möglichst wenige Dreiecke in den hierarchisch höher gelegenen Knoten zu habe. Um hier eine brauchbare Abbruchbedingung für das Unterteilen des Baumes zu finden muss man beachten, das man nicht endlos Dreiecke teilt. Eine Möglichkeit wäre beispielsweise zuerst nur den Octree zu erstellen, und die Dreiecke 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 Knotens sowie aller seiner Unterknoten
- Teilweise sichtbar => Zeichne alle Elemente dieses Knotens, führe jedoch die Überprüfung an den Unterknoten fort
Kollisionsabfrage am Octree
Wenn 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 hierarchisch 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.
