Slashdot Mirror
BSP Trees: Theory and Implementation
Anonymous Coward writes "DevMaster.net has an article by Samuel Ranta-Eskola which offers a detailed explanation of Binary Space Partitioning (BSP) theory for real-time engines, along with various implementation details, complexity anaylsis, optimzations, and rendering. "
I know this is nitpicking, but I couldn't resist.
A convex set is a set where the joining line segment between any two points in the set is also in the set ("no dents in the boundary"). It's easy to see that the intersection of two convex sets is also convex.
In a binary space partitioning tree (BSP) each node splits the space into two halfspaces (halfspace is convex) using a (hyper)plane (the other half is in front of the plane the other behind.) In case of computer graphics the plane used is typically one spanned by a polygon in the scene (a polygon is a planar figure and thus lies on some plane). The resulting halfspaces are recursively split again giving a binary tree. Polygons may have to be cut in half if they intersect the dividing plane on each division and the halves put on different sides of the plane.
To draw the scene properly see which side of the dividing plane the viewer is, draw the polygons on the other side first (recursively), then the polygons on the dividing plane (there might be multiple polygons on the plane) and the the polygons on the same side as the viewer. Why this works is that the polygons on the other side of the plane are behind the ones on the same side as the viewer from the viewer's point of view.
If you're using modern hardware do the exact opposite and hope that the polygons already rendered save some cycles on shaders which are not run on pixels that are not visible by the Z-test.
-Timo
First read the previous comment (http://developers.slashdot.org/comments.pl?sid=78 530&cid=6964818) to understand how a BSP is organized (I did not fully read the article, as it was quite long, and the author seemed confused)
Doing collision detection with a BSP is trivial:
You have a line [A-B] and want to find if a polygon intersects the line.
Start at the root of the tree.
If A and B are on the same side of the separating plane, recurse there.
If not, compute C, the intersection of [A-B] and the separating plane. Look if C is inside any polygon from the separating plane (easy, there are not a lot). If C is inside a polygon, then your line intersect. If not, look [A-C] in one half space, then, if neccessary [C-B] in the other half space.
This can easily be modified to get all the polygons intersecting, in any order (say all the polygons, from A to B).
Hope that helps, if not, reply.
--fred