Objektverwaltung

Einleitung

Um viele Objekte (Modelle und andere Dinge) im Spiel sinnvoll zu verwalten braucht man eine Objektverwaltung. Diese kann bei guter Planung Objekte wesentlich effizienter verwalten, als daß eine Liste es könnte. Man kann zum Beispiel die Objekte in einem Baum speichern, der extrem effizient eine Umkreissuche durchführen kann. In einer Liste muss man dafür jedes Objekt einzeln durchgehen und schauen, ob es im Umkreis liegt. In einem Baum kann man sich nur Knoten in einem bestimmten Bereich anschauen. dadurch kann eine gewisse Vorsortierung erreicht werden.

Space Partitioning

Space Partitioning (oder auch Spatial Partitioning) bezeichnet den Prozess einen Raum in mehrere, sich nicht überlappende Bereiche aufzuteilen. Dadurch lässt sich jeder Punkt innerhalb des Raums eindeutig einem Bereich zuordnen.

Dieses Verfahren ist nicht mit dem Object Partitioning zu verwechseln welches einzelne Objekte in kleinere Teile zerlegt anstatt den Raum zu zerlegen in dem sich mehrere Objekte befinden.

Space Partitioning Systeme sind meist hierarchisch aufgebaut, das heisst dass ein Raum in mehrere Bereiche aufgeteilt wird, und dann werden die entstandenen Bereiche mit der selben Methode erneut rekursiv aufgeteilt. Die dadurch entstehenden Strukturen lassen sich z.B. mit Bäumen abbilden.

Im Bereich der Computergrafik werden Space Partitioning Verfahren dazu verwendet um die Objekte der virtuellen Szenen zu verwalten. Das Speichern der Objekte in Space Paritioning Datenstrukturen ermöglicht es jegliche Art von Algorithmen die die Geometrie der Szene verwenden effizient zu implementieren. Beispiele dafür sind die Kollisionserkennung von Objekten oder die Strahlverfolgung beim Ray Casting. Ohne eine räumliche Aufteilung der Objekte müssten für jeden Test immer alle Objekte der Szene überprüft werden, was vor allem bei größeren Welten sehr schnell sehr ineffizient wird. Ein Space Partitioning ermöglicht es die Tests auf die Objekte zu reduzieren, die aufgrund ihrer räumlichen Lage für Kollisionen überhaupt in Frage kommen. Dadurch müssen für gewöhnlich wesentlich weniger Objekte durchprobiert werden.

Eine weitere mögliche Anwendung ist bei der Auswahl der Objekte die in einem bestimmten Radius um den Spieler liegen, durch eine Raumaufteilung können die in Frage kommenden Objekte sehr schnell bestimmt werden:

Beispiel: Effiziente Suche von Objekten in Radius um einen Punkt in einem 2-dimensionalen Uniform Grid. Nur Objekte in den gelb hinterlegten Zellen müssen getestet werden.

Zu den gängigen Space Partitioning Systemen gehören unter anderem QuadTrees, OcTrees oder auch Uniform Grids

QuadTree

Ein QuadTree ist eine Datenstruktur mit der eine 2-Dimensionale Welt repräsentiert werden kann. Die Welt wird dazu in vier gleich große Rechtecke eingeteilt. Damit man viele Objekte effizient organisieren kann wird nur eine bestimmte Anzahl n Objekte in einer Zalle (Quad) gespeichert. Falls die gespeicherte Anzahl der Objekte n übersteigt wird das betroffene Quad in vier neue Quads geteilt und die vorhandenen Objekte auf die vier neuen Quads verteilt.

Im folgenden Beispiel wird angenommen, daß n=4

Quad teilen

Dabei entsteht ein Baum, der in etwa so aussehen könnte:

Ein Baum

Es kann durchaus sinnvoll sein, zu leere Quads wieder zu einem zusammenzufügen. Auch sollte man sich Gedanken machen, nach welchen Kriterium man Objekte in der Welt speichert. Da gibt es typischerweise drei Möglichkeiten:

Rein positionsbasiert

Da man die Positions und Größe jedes Quads kennt kann man relativ leicht prüfen, in welchen Quad ein Objekt liegt.

Position und Objektgröße

Man schiebt das Objekt in dem Baum so lange nach oben, bis es von den Ausmaßen vollständig in ein Quad passt.

Position und Objektgröße nur in Blättern

Man hat eine Referenz auf ein Objekt in allen Quads, die von einem Objekt berührt werden.

Vergleich

	Rein positionsbasiert	Position und Objektgröße	Position und Objektgröße nur in Blättern
Raycast	schwer, da man alle Quads durchsuchen muss um sicher zu sein, daß man ein Objekt trifft	mittel, da man schauen kann, ob der Ray ein Quad trifft und nur diese anschauen muss	einfach, man kann die Quads nacheinander in der Richtung des Rays durchgehen
sichtbare Objekte suchen	schwer, da man alle Quads durchsuchen muss	einfach, da man prüfen kann, ob ein Quad sichtbar ist und dann nur die enthaltenen Objekte prüfen muß	mittel, da man auch prüfen kann, ob ein Quad sichtbar ist, man aber prüfen muß, ob ein Objekt in mehreren sichtbaren Quads liegt.
Objekte verschieben	sehr einfach, da man es direkt in das passende Quad legen kann	mittel, man muss wieder prüfen, ob das Objekt in das aktuelle Quad passt	schwer, man man alle berührten Quads aktualisieren muss

OcTree

Im Prinzip ein QuadTree, der um eine Dimension erweitert wurde. Man kann sich einen OcTree als Würfel vorstellen, der in acht gleichgroße Würfel unterteilt ist.

Implementierung in XNA

Für die Implementierung eines Octrees in XNA kann man als Repräsentation der einzelnen Oktanden z.B. die BoundingBox Struct von XNA benutzen. Diese eignet sich relativ gut, da sie eine Methode besitzt über die einfach abgefragt werden kann ob sich z.B. ein Punkt oder ein anderes Bounding Volume innerhalb oder außerhalb der Box befindet oder diese schneidet. Damit lässt sich die Einsortierung von Objekten relativ einfach implementieren. Ein weiterer Vorteil ist, dass man BoundingBoxen auch mit Strahlen schneiden kann. Dies erleichtert die Auswahl in Frage kommender Objekte beim Ray Casting.

Uniform Grid

Bei einem Uniform Grid wird die Spielwelt in Zellen unterteilt die alle die selbe Größe besitzen. Dabei kann die Größe einer einzelnen Zelle auf den verschiedenen Achsen variieren. In jeder Zelle werden dann die sich darin befindenden Objekte gespeichert.

Typischerweise kommen 2- oder 3-dimensionale Gitter zum Einsatz.