Last Updated September 22, 2009

Single Phase Collision detection with BSP trees

BSP trees

BSP trees are used for single phase collision detection. These can be used in two ways;

1. ray intersecting
2. tree merging

Using BSP trees for ray intersecting

Testing for ray intersecting objects in a scene is a useful procedure in graphics and games. It asks the question, "if I move along this direction, which objects will I hit?". This is an important question for path finding, interactive games and has applications in lighting and shadow calculations. Testing for ray intersection is also a solution to the time-step problem, in which a collision might not be detected because the collision fell between two time steps. (An example of under sampling).

The test procedure is recursive, as usual;

testintersect(bsp_root,start_of_ray, end_of_ray);
...
...
test_intersect(node, s, e){
	check which side of plane for s and e
	if(s and e are on +ive side) // ray cannot intersect plane
		test_intersect(node.positivechild,s,e);
	else if(s and e are on -ive side)// ray cannot intersect plane
		test_intersect(node.negativechild,s,e);
	else{ // points on either side of plane
		find point of intersection (i) between ray and plane
		if( i is inside face)
			output intersection;
		// split ray in two and test the two pieces against the left and right sub trees
		p=point on positive side;
		n=point on negative side
		test_intersect(node.negativechild,n,i);	
		test_intersect(node.positivechild,p,i);	
	}
}
		

To test if a point is inside a triangle (or any polygon) test if the point is on the 'inside' of each edge of the triangle. Normals for each edge need to be maintained.

Collision detection using BSP tree merging

Given a local BSP tree for an object, it can be seen that the left most node corresponds to the inside of the object. We can merge two bsp trees to determine if their spaces overlap. By merging one tree with another, a collision is present if parts of the second tree are inserted into the leftmost node of the first tree.

© Ken Power 1996-2016