BSP collision detection

From CGAFaq

Detecting whether or not a point moving along a line intersects some object in space is essentially a ray tracing problem. Detecting whether or not two complex objects intersect is something of a tree merging problem.

Typically, motion is computed in a series of Euler steps. This just means that the motion is computed at discrete time intervals using some description of the speed of motion. For any given point P moving from point A with a velocity V, it's location can be computed at time T as P = A + (T * V).

Consider the case where T = 1, and we are computing the motion in one second steps. To find out if the point P has collided with any part of the scene, we will first compute the endpoints of the motion for this time step. P1 = A + V, and P2 = A + (2 * V). These two endpoints will be classified with respect to the BSP tree. If P1 is outside of all objects, and P2 is inside some object, then an intersection has clearly occurred. However, if P2 is also outside, we still have to check for a collision in between.

Two approaches are possible. The first is commonly used in applications like games, where speed is critical, and accuracy is not. This approach is to recursively divide the motion segment in half, and check the midpoint for containment by some object. Typically, it is good enough to say that an intersection occurred, and not be very accurate about where it occurred.

The second approach, which is more accurate, but also more time consuming, is to treat the motion segment as a ray, and intersect the ray with the BSP Tree. This also has the advantage that the motion resulting from the impact can be computed more accurately.

Initial content for this page from the BSP tree FAQ, included with permission of its maintainer, Bretton Wade.