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. "

Comments

You've probably used these before..

[irc.goatse.cx troll]

For anyone wondering why the name sounds familure, this is the format all games originating from Quake use.
That covers q1, q2, q3, hl+mods, hl2, jk2, rtcw, and everything between.

Re:You've probably used these before..

[lfourrier]

not from quake, from doom.
There was an interresting article on the subject in DDJ a couple of year ago, from one of those people at Id.

BSP trees and precision

[robson]

In my own experience as a designer, many engines that use the BSP tree for collision suffer from a sort of *precision fragility*. You're fine with big brushes that stick to the grid, but as brushes get smaller and angles deviate from 90 or 45 degrees, you start to get these little precision errors that create big problems at runtime. Usually it's either holes in the world that the player can fall through or tiny slivers of collision geometry that prevent movement through what should be empty space.

Many times I heard our programmers cursing "that damned epsilon".

(The project I'm currently on uses octrees and per-poly collision against the world, and while I believe it may be a little slower, it's vastly more robust.)

Terminology confusion in article

[TimoT]

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

My take...

[mstorer3772]

I'm a 'regular' programmer trying to break into the gaming realm.

I read this article. I understand how to build a BSP. I feel that left out some important details.

Like how you actually use it. The article mentions that modern games don't use it for dept-sort drawing any more, as hardware z-buffers are now good enough to make this unnecessary... it said that they're used instead for things like collision detection.

My question is HOW? Okay so I've got this tree of map hunks. So what? Given an object or person in *3D* space, I don't see how you're supposed to use it. Someone else mentioned an "octa-something" tree which sounds like it would be far easier (for me, conceptually) to use. With 8 directions, you've got above/below, right/left, in front/behind. 2^3 = 8. Groovy.

I suppose the articles example may have confused me a bit, being entirely 2d. In a non-trivial (I hesitate to use the phrase "real world" in this context ;) situation, many of the deviding planes wouldn't be lined up vertically, giving you some 3-d-ishness to your data...

That little trip down congnition ave still didn't help me figure it out though. Given a viewpoint and facing, I don't see how you're supposed to traverse this tree is going to help.

Okay, so you find the node the viewpoint is in. I can see how that works (am I inside this convex space? no, okay move on). I just don't see how that helps you. It seems to me that a given node could have been sliced out of your world-data by a plane on just about any angle... so I'm mysified as to how you find anything near you (that isn't in your current node), or traverse the BSP in z-order from your current position in some arbitrary direction.

Feel free to use the example data from the article (describing your own data sounds like a lot of work for a /. reply).

--Not afraid to be baffled

Re:My take...

[Anonymous Coward]

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

Re:My take...

[zonx lebaam]

I too am a 'regular' programmer, and have never used this, so take me with a grain of salt ...

Suppose we are in a cluttered world. We divide the world in half with a plane (that doesn't intersect us). We draw everything on the other side of the plane correctly (using magic or plain good luck). Then we draw everything on our side correctly (also lucky). Nothing on the other side of the plane can overlap anything on our side, so we know this solution would be right (if only we could guarantee the good luck on each half). But every plane forces us to be entirely on one side or the other, so by applying the decisions recursively, we can guarantee that good luck all the way home from the terminal nodes. Remember that as we travel into an 'other side' node, we have to reexamine our position and will discover that a nominal half of its contents will be in 'our side' of that new criteria.

It is unnecessary however, to subdivide the whole world into single polygons, however, because the polygon-facing principle described in the article gives us a heuristic atom of polygons for which we don't need to split, because inside that group, it is guaranteed that no one of them will ever block any other one.

Anyway, after you reach the deepest node, whose polygons are on the 'other side' of every dividing plane, we draw it, followed by the rest of the world. And so on and so on. The very last thing that we draw is on 'our side' of every single dividing plane.

Note that every polygon gets drawn. This algorithm only gives us an ordering. Also note that since polygons can lie on the dividing plane, we must draw them as well (after the 'other side' and before 'our side'). Another boundary condition is that the possibility exists that the viewpoint will fall onto a dividing plane, in which case, we can draw either side first, followed by the other side, followed by polygons in the plane. Please note that this can be done in any number of dimensions. In fact, for two dimensions use lines instead of planes. As a final note, it appears to me that the art here lies in choosing the dividing planes, and although the article provides a little introductory guidance, one could surely do better, and this appears to be where the real fun lies.

Right ???