If you have a bsp tree, then you’re almost home.

For collision detection, Quake uses beveled expanded convex brush hulls, which sounds complicated, but is actually one of the easiest and most intuitive methods around. The idea is this: First, I assume your world is composed of convex brushes (boxes, cylinders, spheres - any object such that every poly has every other poly behind it). When you create your bsp tree, you want to remember which brushes touch the empty leaves of your tree - just keep a list in your node structure:

struct bsp_node {

…

brush* brushList; // only for empty leaves

…

};

Now, when you perform a line trace, make a bounding box for the line, then expand the bounds by the size of you trace object. Take this expanded bounding box and filter it down the tree: if it’s in front of a node, then go down the front side; if it’s in back, then go down the back side; if it’s split, then go down the front and back sides. If you reach an empty leaf, you now have a list of convex brushes to test the line against.

Tracing a line through a convex brush is quite simple, due to the nice properties of convex brushes. I won’t go into the details here, but I would be happy to if you need them. Having done the brush trace, keep the intersection (if any) closest to the start point of the line. Once you’ve traversed the entire tree you should have the hit point.

Beveling a brush requires adding planes at the sharp edges and corners of the brush so that when you expand it, you won’t get extreme wedgies in your world. Imagine expanding the planes of a tall pointy cone; the difference between the expanded planes and the original planes becomes excessive. By capping the cone with a bevel plane on top you can prevent this from happening.

Expansion simply means pushing the plane out along the normal in some fashion. There are several ways to do this, depending on the geometry of the moving object ( i.e., sphere, box, or cylinder ).

A nice thing about this method is that it’s trivial to get surface information, such as textures and normals. Additionally, this method handles moving and rotating brushes.

Another method involves shifting the node planes, and requires beveling of the tree itself. Needless to say, this method is much more complicated, but worthy of mention.

edit:

worded some stuff differently