Anonymous Anonymous - 1 month ago
146 0

No description

ActionScript

quadtree 3d (2)

public class Quadtree {

	private int MAX_OBJECTS = 10;
	private int MAX_LEVELS = 5;

	private int level;
	private List<Cuboid> objects;
	private Cuboid bounds;
	private Quadtree[] nodes;

	/*
	 * Constructor
	 */
	public Quadtree(int pLevel, Cuboid pBounds) {
		level = pLevel;
		objects = new List<Cuboid> ();
		bounds = pBounds;
		nodes = new Quadtree[8];
	}

	/*
 	 * Clears the quadtree
	 */
	public void clear() {
		//objects.clear();

		for (int i = 0; i < nodes.Length; i++) {
			if (nodes[i] != null) {
				nodes[i].clear();
				nodes[i] = null;
			}
		}
	}
	/*
	 * Splits the node into 4 subnodes
	 */
	private void split() {
		int subLength = (int)(bounds.getLength() / 2);
		int subWidth = (int)(bounds.getWidth() / 2);
		int subHeight = (int)(bounds.getHeight() / 2);

		int x = (int)bounds.getX();
		int y = (int)bounds.getY();
		int z = (int)bounds.getZ();

		int x_ = 0;

		for(int a = 0; a < 1;a++) {
			for (int b = 0; b < 1; b++) {
				for (int c = 0; c < 1; c++) {
					nodes[x_] = new Quadtree(level+1, new Cuboid(x + (subLength * c), y + (subWidth * b), z + (subWidth * a), subLength, subWidth, subHeight));

					x_++;
				}
			}
		}

		/*
		Original code (I try to preserve it but I don't like typing):



		nodes[0] = new Quadtree(level+1, new Cuboid(x + subWidth, y, subWidth, subHeight));
		nodes[1] = new Quadtree(level+1, new Cuboid(x, y, subWidth, subHeight));
		nodes[2] = new Quadtree(level+1, new Cuboid(x, y + subHeight, subWidth, subHeight));
		nodes[3] = new Quadtree(level+1, new Cuboid(x + subWidth, y + subHeight, subWidth, subHeight));*/
	}

	/*
	 * Determine which node the object belongs to. -1 means
	 * object cannot completely fit within a child node and is part
	 * of the parent node
	 */

	private int getIndex(Cuboid pRect) {
		int index = -1;

		double xMidpoint = bounds.getX() + (bounds.getLength() / 2);
		double yMidpoint = bounds.getY() + (bounds.getWidth() / 2);
		double zMidpoint = bounds.getZ() + (bounds.getHeight() / 2);

		// Object can completely fit within the top quadrants
		bool topQuadrant = (pRect.getX() < xMidpoint && pRect.getX() + pRect.getLength() < xMidpoint);
		// Object can completely fit within the bottom quadrants
		bool bottomQuadrant = (pRect.getX() > xMidpoint);

		/* Copied code below */

		// Object can completely fit within the front quadrants
		bool leftQuadrant = (pRect.getY() < yMidpoint && pRect.getY() + pRect.getWidth() < yMidpoint);
		// Object can completely fit within the back quadrants
		bool rightQuadrant = (pRect.getY() > yMidpoint);

		/* Copied code ends */

		// Object can completely fit within the left quadrants
		if (pRect.getZ() < zMidpoint && pRect.getZ() + pRect.getHeight() < zMidpoint) {
			if (leftQuadrant) {
				if (topQuadrant) {
					index = 0;
				}
				else if (bottomQuadrant) {
					index = 1;
				}
			}
			else if (rightQuadrant) {
				if (topQuadrant) {
					index = 2;
				}
				else if (bottomQuadrant) {
					index = 3;
				}
			}
		}
		// Object can completely fit within the right quadrants
		else if (pRect.getZ() > zMidpoint) {
			if (leftQuadrant) {
				if (topQuadrant) {
					index = 4;
				}
				else if (bottomQuadrant) {
					index = 5;
				}
			}
			else if (rightQuadrant) {
				if (topQuadrant) {
					index = 6;
				}
				else if (bottomQuadrant) {
					index = 7;
				}
			}
		}

		return index;
	}

	/*
 	 * Insert the object into the quadtree. If the node
	 * exceeds the capacity, it will split and add all
 	 * objects to their corresponding nodes.
	 */
	public void insert(Cuboid pRect) {
		if (nodes[0] != null) {
			int index = getIndex(pRect);

			if (index != -1) {
				nodes[index].insert(pRect);

				return;
			}
		}

		objects.Add(pRect);

		if (objects.Count() > MAX_OBJECTS && level < MAX_LEVELS) {
			if (nodes[0] == null) { 
				split(); 
			}

			int i = 0;
			while (i < objects.Count()) {
				int index = getIndex(objects[i]);
				if (index != -1) {
					nodes[index].insert(objects [i]);
					objects.Remove(objects [i]);
				}
				else {
					i++;
				}
			}
		}
	}

	/*
	 * Return all objects that could collide with the given object
 	 */
	public List<Cuboid> retrieve (List<Cuboid> returnObjects, Cuboid pRect) {
		int index = getIndex(pRect);
		if (index != -1 && nodes[0] != null) {
			nodes[index].retrieve(returnObjects, pRect);
		}

		returnObjects = AddAll (returnObjects, objects);

		return returnObjects;
	}

	public List<Cuboid> AddAll (List<Cuboid> returnObjects, List<Cuboid> ReferenceObjects) {
		List<Cuboid> newReturnObjects = new List<Cuboid> ();
		for (int x = 0; x < returnObjects.Count; x++) {
			for (int y = 0; x < ReferenceObjects.Count; y++) {
				if (returnObjects [x] = ReferenceObjects [y]) {
					newReturnObjects.Add (returnObjects [x]);
					y = ReferenceObjects.Count;
				}
			}
		}
		return newReturnObjects;
	}
}

public class Cuboid {
	Vector3 BeginningBounds;
	Vector3 EndBounds;

	public Cuboid (int x, int y, int z, int length, int width, int height) {
		BeginningBounds = new Vector3 (x, y, z);
		EndBounds = BeginningBounds + new Vector3 (length, width, height);
	}

	public float getLength() {
		return EndBounds.x - BeginningBounds.x;
	}
	public float getWidth() {
		return EndBounds.y - BeginningBounds.y;
	}
	public float getHeight() {
		return EndBounds.z - BeginningBounds.z;
	}

	public double getX () {
		return BeginningBounds.x;
	}
	public double getY () {
		return BeginningBounds.y;
	}
	public double getZ () {
		return BeginningBounds.z;
	}
}