Point Versus Triangle Set Collision (BSP-Based)

Let's now explore one of the most popular ways of testing for collisions in a game level. The method takes advantage of the quick sorting behavior of a Binary Space Partition (BSP) tree to quickly find out where the player is standing.

Basically, we will traverse the BSP, selecting for each node the subnode in which the point is lying, according to the division plane. Remember that the planes we visit on our way to the leaf form a convex shape around the point. Logically, these planes are the closest ones to the viewer. So, all we have to do is a point versus polygon test to determine if we are actually lying in a valid region. Because the BSP will have divided the input set in half at each level, the total cost of the operation will be O(log2n), which is the number of levels in the BSP. Notice that we are assuming the division criteria is perfect, thus the BSP is a balanced tree.