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

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.

Michael Abrash

[gaj]

But it wasn't just "one of those people at Id"; it was none other than Michael Abrash.

Also, it wasn't just an article, it was a series of articles. I'm at work (posting on /. rather than writing code ... bad coder, no donut), so I don't have my DDJ collection here (and their site seems not be be responding for the moment), but I think these [bluesnews.com] are the same basic content. This [c2.com] is another page with links to his stuff, but it is a bit out of date. For instance, I believe he's moved on from MicroSoft (though I can

not a format

[BinLadenMyHero]

BSP is not a format, it's an algorithm! In fact it's a spacial data strucutre (a space structure, like a double-liked list, a binary tree, etc, that uses spatial information to arrange the data).

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

Re:BSP trees and precision

[n.wegner]

>(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.)

I thought BSP trees were meant to be fast and cheap in comparison to per-poly tests, much like octrees. Is there some reason you can't use octrees alone? I'm betting it's because octrees have similar problems, which is why you get rid of as much as possible by octree culling and then do per-poly on as little as possible. You could have don

Re:BSP trees and precision

[robson]

I thought BSP trees were meant to be fast and cheap in comparison to per-poly tests, much like octrees. Is there some reason you can't use octrees alone? I'm betting it's because octrees have similar problems, which is why you get rid of as much as possible by octree culling and then do per-poly on as little as possible. You could have done that with BSP.

Again, I'm a designer, not an engineer, but I believe that's what they're doing -- using the octree for gross spatial culling and then only colliding ag

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=7 8 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 sep

Re:My take...

[mstorer3772]

Yes, actually. It does, at least as far as the collision detection goes.

But I'm still a little fuzzy on a couple points. Going back to the initial purpose of BSPs (according to the article): depth sorting.

Place the camera some point in the world looking in a particular direction.

Okay, so finding which leaf it's in isn't too hard. Got that.

But given a particular facing, how the heck do you sort all that stuff? Seems to me that any given node's parent deviding plane (whatever you call it) could be at

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 l