Wall Collision Detection using Binary Space Partition Trees

Binary Space Partitioning allows for a tree representation of graphs. They are often used for a collision model to detect the edges between a given point. Standard collision algorithms run in O(n) time where n represents the number of edges in the graph. It is possible however to increase the running time by merging some techniques from Splay Trees with distinct non-intersecting walls. Splay Trees have the property that recently accessed elements are quick to access again. Since most worlds in games only simulate physics within small areas, the technique of bringing recently accessed edges to the root would be ideal.

Tree Structure

A binary space partitioning tree (BSP tree) recursively subdivides an n dimensional space into hierarchical partitions [1]. The generation process can be best described in two dimensional space as seen in Figure 1 below. Each new line added to the tree will split an existing partition into two. Each leaf node in the tree describes a partition, while each internode describes a line that intersects the partition.

In the context of game development, this data structure is very useful in determining which faces should be drawn depending on the location of the camera. If the camera is found in a given partition, every face that touches that partition will be drawn, while every other face will be culled. The same strategy can be used for collision. For each collidable object in question, its residing partition is found, and each face bordering the partition will be checked for an intersection.

If there are n collidable objects, and m walls to be queried for a collision the running time will be n *log(m). This will probe for the partition that each collidable object is residing. The non-trivial matter is discovering which adjoining faces are surrounding the partition. A series of successor and predecessor algorithms can be performed to find the perimeter, however this causes a large increase in running time. It is here where the property of the static, non-mobile environment becomes important. During the creation step of the data structure, an extra algorithm runs that calculates each edge along the perimeter of the partition. This information is stored at the leaf nodes.

Node Entity

class Node<T>
{
	T x1, y1, x2, y2;
	Node<T> left, right, parent;
	public Node(T x, T y, T x2, T y2)
	{
		this.x1 = x;this.y1 = y;this.x2 = x2;this.y2 = y2;
	}
}

Data Structure Operations

Search

Let K represent the number of possible edges that are next to a given point P in the graph. The first access to these K elements will require computation time of K×log(n). After the first iteration, each k edges will have rotated to the top due to the BTF property mentioned in Splay Trees.

Each edge will have been inserted in Lexicographical order, so binary search is performed based on the location of the point. If the nearest edge is found, the splay operation is run to bring the edge to the root. Otherwise, the point is outside the universe, and no collision is found.

The traversal algorithm mentioned in Binary Space Partitioning will find the given side on which the point is located. If P is found to be inside two edges which represent a wall, a collision is detected. This algorithm can run quickly assuming K is small. If K is large, too many comparisons are made between each edge to determine if the point is inside. It must be proven then that K is no larger than the number of edges in a given polygon in the world.

Case 1

(P is inside a wall) The binary space partitioning traversal will find the K closest edges to P. If K is at least the number of edges of the shape, then the query for the point inside the wall will return true.

Case 2

(P is outside all walls) The binary space partitioning traversal will find the K closest edges to P. Since each wall is distinct and non intersecting, a false negative cannot happen due to excessive trimming. In the event that a high polygonal shape is directly beside P, but P is already intersecting inside another shape, the traversal algorithm will prune that side of the tree based on other edges occurring closer than the outside edge.

Implementation

protected Node findLast(Edge x) {
	Node w = r, prev = nil;
	while (w != nil) {
		prev = w;
		int comp = c.compare(x, w.edge);// uses lexicographical comparison
		if (comp < 0) {
			w = w.left;
		} else if (comp > 0) {
			w = w.right;
		} else {
			return w;
		}
	}
        splay(x);
	return prev;
}

Splay

Implementation

public void splay(Node<T> u) {
// Runs a series of rotations on node u to make it the root.
	while (!r.equals(u)) // while not the root
	{
		if (u.parent.left != null && u.parent.left.equals(u)) // left
		{
			if (u.parent.parent == null) {
				zig("left", u);
			} else if (u.parent.parent.left != null
				&& u.parent.parent.left.equals(u.parent)) // left left
			{
				zigzig("left", u);
			} else if (u.parent.parent.right != null
				&& u.parent.parent.right.equals(u.parent)) // right left
			{
				zigzag("left", "right", u);
			}
		} 
                else if (u.parent.right != null && u.parent.right.equals(u)) // right
		{
			if (u.parent.parent == null) {
				zig("right", u);
			} else if (u.parent.parent.left != null
				&& u.parent.parent.left.equals(u.parent)) // left right
			{
				zigzag("right", "left", u);
			} else if (u.parent.parent.right != null
				&& u.parent.parent.right.equals(u.parent)) // right right
			{
				zigzig("right", u);
			}
		}
	}
}

Throughput

The most important results, throughput and robustness, were found using the throughput test program. The BSP tree ran the same test program that measured the build time of the trees, along with some sample probes to simulate in game run times. The table below depicts the results of the test program.

Sources

[1] William C. Thibault and Bruce F. Naylor. Set operations on polyhedra using binary space partitioning trees. In Proceedings of the 14th annual conference on Computer graphics and interactive techniques (SIGGRAPH '87), Maureen C. Stone (Ed.). ACM, New York, NY, USA, 153-162.