Octree

aus GlossarWiki, der Glossar-Datenbank der Fachhochschule Augsburg
Wechseln zu:Navigation, Suche

Dieser Artikel sollte auf Korrektheit, Quellenangaben und GlossarWiki-Konformität hin überprüft werden.

1 Definition

Ein Octree ist eine Datenstruktur, in der dreidimensionale Daten nach dem Teile und Herrsche-Prinzip verwaltet werden. Das Datum enthält wiederum acht Octrees oder keinen.

Ein Einsatzgebiet von Octrees ist das Beschleunigen der Kollisionserkennung in (3D) Physiksimulationen. Für Berechungen im zweidimensionalen Raum verwendet man einen Quadtree.

2 Beispiel

Hier eine kleine Beispielimplementierung eines Octrees zur Kollisionserkennung in ActionScript3.

Es wird empfohlen für das verwendete Set bzw. Iterator die AS3 Data Structures von polygonal labs zu verwenden.

package {
	public class Octree {
		public const MAX_OCTREE_DEPTH:uint=6;                     // maximum depth
		public const MIN_OBJECTS_PER_OCTREE:uint=3;               // the minimum count of Objects in a Cube
		public const MAX_OBJECTS_PER_OCTREE:uint=6;               // the maximum count of Objects in a Cube

		private var corner1:Vector3D;                             // the lower-left-far corner of the cube
		private var corner2:Vector3D;                             // the upper-right-near corner of the cube
		private var center:Vector3D;                              // the middle of the cube
		private var children:Array;                               // the children of this octree
		private var hasChildren:Boolean;                          // if this octree has children
		private var objects:Set;                                  // the object in this if it has no children
		private var depth:uint;                                   // the depth of this in the tree
		private var numberOfObjects:uint;                         // the number of objects in this, inluding the ones in its children
		private var potentialCollisions:Set;                      // the all objects that may collide soon

		public function Octree(corner1:Vector3D,corner2:Vector3D,depth:uint) {
			this.corner1=corner1;
			this.corner2=corner2;

			// calculating the center of the octree
			this.center=new Vector3D(corner1.x + corner2.x / 2,corner1.y + corner2.y / 2,corner1.z + corner2.z / 2);

			hasChildren=false;
			this.objects=new Set  ;
			this.potentialCollisions=new Set  ;
			this.depth=depth;
			this.numberOfObjects=0;

			// three-dimensional array
			this.children=new Array(new Array(new Array  ,new Array  ),new Array(new Array  ,new Array  ),new Array(new Array  ,new Array  ));
		}

In dieser Methode wird die Position des CollisionObject object im Octree bestimmt und je nach dem Wert von addObject hinzugefügt oder entfernt.

		private function fileObject(object:CollisionObject,pos:Vector3D,addObject:Boolean):void {
			if (object == null) {
				return;
			}
			//Figure out in which child(ren) the object belongs
			var x:uint;
			var y:uint;
			var z:uint;

			for (x=0; x < 2; x++) {
				if (x == 0) {
					if (pos.x - object.circumCircleRadiusX > center.x) {
						continue;
					}
				} else if (pos.x + object.circumCircleRadiusX < center.x) {
					continue;
				}
				for (y=0; y < 2; y++) {
					if (y == 0) {
						if (pos.y - object.circumCircleRadiusY > center.y) {
							continue;
						}
					} else if (pos.y + object.circumCircleRadiusY < center.y) {
						continue;
					}
					for (z=0; z < 2; z++) {
						if (z == 0) {
							if (pos.z - object.circumCircleRadiusZ > center.z) {
								continue;
							}
						} else if (pos.z + object.circumCircleRadiusZ < center.z) {
							continue;
						}
						// Add or remove the object
						if (addObject) {
							Octree(children[x][y][z]).add(object);
						} else {
							Octree(children[x][y][z]).remove(object,pos);
						}
					}
				}
			}
		}

Unterteilt den Octree in 8 weitere Octrees, die sogleich die Objekte des ursprünglichen Octrees bekommen.

		// Creates children of this, and moves the objects in this to the children
		private function haveChildren():void {
			var x:uint;
			var y:uint;
			var z:uint;

			var maxX:Number;
			var maxY:Number;
			var maxZ:Number;

			var minX:Number;
			var minY:Number;
			var minZ:Number;

			for (x=0; x < 2; x++) {
				if (x == 0) {
					minX=corner1.x;
					maxX=center.x;
				} else {
					minX=center.x;
					maxX=corner2.x;
				}

				for (y=0; y < 2; y++) {
					if (y == 0) {
						minY=corner1.y;
						maxY=center.y;
					} else {
						minY=center.y;
						maxY=corner2.y;
					}

					for (z=0; z < 2; z++) {
						if (z == 0) {
							minZ=corner1.z;
							maxZ=center.z;
						} else {
							minZ=center.z;
							maxZ=corner2.z;
						}

						children[x][y][z]=new Octree(new Vector3D(minX,minY,minZ),new Vector3D(maxX,maxY,maxZ),this.depth + 1);
					}
				}
			}
			//Remove all objects from "objects" and add them to the new children
			var it:Iterator=objects.getIterator();
			var obj:CollisionObject;

			while (it.hasNext()) {
				obj=it.next();
				fileObject(obj,obj.position,true);
			}
			objects.clear();

			hasChildren=true;
		}

Hier werden alle Kind-Octrees entfernt und deren Objekte dem aktuellen Octree hinzugefügt.

		//Destroys the children of this, and moves all objects in its descendants to the "objects" vector
		private function destroyChildren():void {
			collectObjects(objects);

			var x:uint;
			var y:uint;
			var z:uint;

			for (x=0; x < 2; x++) {
				for (y=0; y < 2; y++) {
					for (z=0; z < 2; z++) {
						delete children[x][y][z];
					}
				}
			}
			hasChildren=false;
		}

Diese Methode sammelt alle Objekte des Octrees und seiner Kinder und fügt sie dem übergebenen Set hinzu.

		// Collects all Objects and Objects of its descendents
		private function collectObjects(arr:Set):void {
			var x:uint;
			var y:uint;
			var z:uint;

			if (hasChildren) {
				for (x=0; x < 2; x++) {
					for (y=0; y < 2; y++) {
						for (z=0; z < 2; z++) {
							Octree(children[x][y][z]).collectObjects(arr);
						}
					}
				}
			} else {
				var it:Iterator=objects.getIterator();
				var obj:CollisionObject;

				while (it.hasNext()) {
					obj=it.next();
					arr.set(obj);
				}
			}
		}

Löscht ein Objekt.

		//Removes the specified object at the indicated position
		public function remove(object:CollisionObject,pos:Vector3D=null):void {
			if (pos == null) {
				pos=object.position;
			}

			numberOfObjects--;

			if (hasChildren && numberOfObjects < MIN_OBJECTS_PER_OCTREE) {
				destroyChildren();
			}
			if (hasChildren) {
				fileObject(object,pos,false);
			} else {
				objects.remove(object);
			}
		}

Fügt dem Octree ein Objekt hinzu.

		//Adds an object to this
		public function add(object:CollisionObject):void {
			if (object == null) {
				return;
			}
			numberOfObjects++;

			if (! hasChildren && depth < MAX_OCTREE_DEPTH && numberOfObjects > MAX_OBJECTS_PER_OCTREE) {
				haveChildren();
			}
			if (hasChildren) {
				fileObject(object,object.position,true);
			} else {
				objects.set(object);
			}
		}

Aktualisieren der Objekt-Positionen und Kollisionsberechnung untereinander. Eine Wand- oder Bodenkollision ist (noch) nicht vorhanden.

		public function objectMoved(object:CollisionObject,oldPos:Vector3D):void {
			if (object != null) {
				remove(object,oldPos);
				add(object);

				TriangleMesh3D(object.renderObject).x=- object.position.x;
				TriangleMesh3D(object.renderObject).y=- object.position.y;
				TriangleMesh3D(object.renderObject).z=- object.position.z;
			}
		}

		public function moveObjects(timeStep:Number):void {
			var arr:Set=new Set  ;
			collectObjects(arr);

			if (arr == null) {
				return;
			}
			var i:uint;
			var oldPos:Vector3D;
			var obj:CollisionObject;
			var it:Iterator=arr.getIterator();

			while (it.hasNext()) {
				obj=it.next();
				oldPos=obj.position;
				obj.update(timeStep);
				objectMoved(obj,oldPos);
			}
		}
		//Adds potential Object-Object collisions to the specified vector
		public function potentialObjectCollisions(collisions:Set):void {
			if (hasChildren) {
				var x:uint;
				var y:uint;
				var z:uint;

				for (x=0; x < 2; x++) {
					for (y=0; y < 2; y++) {
						for (z=0; z < 2; z++) {
							Octree(children[x][y][z]).potentialObjectCollisions(collisions);
						}
					}
				}
			} else {
				//Add all pairs (object1, object2) from objects

				var it1:Iterator=objects.getIterator();
				var it2:Iterator=objects.getIterator();
				var obj1:WParticle;
				var obj2:WParticle;

				var a:uint=0;
				var b:uint=0;

				for (it1.start(); it1.hasNext(); it1.next()) {
					obj1=it1.data;

					++a;
					b=0;
					for (it2.start(); it2.hasNext(); it2.next()) {
						++b;
						obj2=it2.data;

						if (a < b) {
							collisions.set(new CollisionPair(obj1,obj2));
						}
					}
				}
			}
		}
	}
}

3 Quellen


4 Siehe auch

Quadtree