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