[Algorithms] BSP-Primitive intersection testing

[Charles B. <cb...@cb...>]

Is there a fast and correct way to ask a BSP if it
intersects with a primitive (AABB or sphere, for example) ?

The context of this question is the traditional hack
which all the BSP-based games used.  They use a collision
detection scheme where they take a primitive, and send it
down the tree as if it were a point, but shift the BSP planes
by the radius of the primitive in the direction of the
plane's normal.  The problem with this test is that it just
doesn't work near corners where planes intersect.  Many
people are under the false impression that if you put
extra "cap" planes on your leaves it will fix the problem,
and while it certainly greatly decreases the error (because
the error is roughly proportional to the angle difference
of the joint, so adding more planes at a joint smooths out
the error), the problem does remain.

Of course, you can test an AABB against a BSP exactly by sending
the polygons of the AABB down the bsp tree and doing the full
polygon clipping shish-poo-bah, but that seems a rather expensive
way to an AABB-in-region test.

Using "cap planes" the error can be controlled, and you can
make sure that the error is conservative (returns more
intersections) so perhaps that's the best solution - be approximate.

--------------------------------------
Charles Bloom           www.cbloom.com