Slashdot Mirror

← Back to Stories (view on slashdot.org)

BSP Trees: Theory and Implementation

Posted by Hemos on from the new-techniques dept.

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

16 comments

  1. You've probably used these before.. by irc.goatse.cx+troll · · Score: 3, Interesting

    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.

    --
    Pain lasts, kid. Its how you know you're alive. Sometimes I think this growing up thing is just pain management-TheMaxx
    1. Re:You've probably used these before.. by lfourrier · · Score: 2, Interesting

      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.

  2. not a format by BinLadenMyHero · · Score: 1

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

  3. Michael Abrash by gaj · · Score: 1
    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 are the same basic content. This 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't be botherd to check on that ... what d'ya want for nuthin?).

  4. BSP trees and precision by robson · · Score: 3, Interesting

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

    1. Re:BSP trees and precision by n.wegner · · Score: 1

      >(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 done that with BSP.

    2. Re:BSP trees and precision by robson · · Score: 1

      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 against polys that are "close enough".

  5. Terminology confusion in article by TimoT · · Score: 4, Informative

    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

  6. My take... by mstorer3772 · · Score: 3, Interesting

    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

    --
    Fooz Meister
    1. Re:My take... by Anonymous Coward · · Score: 2, Informative

      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

    2. Re:My take... by zonx+lebaam · · Score: 2, Interesting
      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 ???

    3. Re:My take... by mstorer3772 · · Score: 1

      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 basically any orientation at all.

      I get the top-down usages... it's the bottom-up ones that confuse me.

      And maybe I'm just looking at the problem wrong, and this is a top-down kinda thing in the first place.

      --
      Fooz Meister
    4. Re:My take... by Anonymous Coward · · Score: 0

      > Going back to the initial purpose of BSPs (according to the article): depth sorting.

      Nope. Depth sorting is one use of BSP. BSP are just (as the name says) a way to partition space (in convex subparts). As I recall John Carmack saying, there is an awfull amount of information in a BSP.

      > I get the top-down usages... it's the bottom-up ones that confuse me.

      There is no bottom-up usage needed. Top down, always.

      Imagine your view frustrum (6 planes, defining the sides of the pyramid, the front and back culling planes).

      Now, imagine your BSP, as a kind of abstract hierarchical structure (like a calder mobile (http://www.guggenheimcollection.org/site/artist_w ork_md_26_2.html)), recursively splitting the world.

      Now, imerge the frustun into the BSP, using the following algorithm, that emit faces (like a kind circular saw, if you don't mind the image [tired, just finishing a 18 hours coding session]).

      * If root plane don't cross frustum, imerge in the subtree where frustum is located.

      * If root plane cross frustum, then
      * imerge the frustum into the subtree near the eye
      * emit faces
      * imerge the frustum into the other subtree.

      By definition, you faces will be sorted. Enlightening, isn't it ?

      Hope that helps. Must go, now.

      --fred

  7. additional articles? by Anonymous Coward · · Score: 0

    According to the article, it seems there are 3 more articles coming in the "series":

    2. Hidden Surface Removal
    3. Radiosity and BSP-Tree Rendering
    4. Physics in BSP-Trees

    Wouldn't those articles answer the questions some guys were asking. In that case, we'll need to keep patient for the upcoming articles I guess.

  8. Pay no attention by Anonymous Coward · · Score: 0

    Sorry, I just modded the wrong comment. Hafta post to get my moderation dropped.

  9. Worry Not by Anonymous Coward · · Score: 0

    Worry not for moderation, for it is oft the mean of subjective opinion, anger, spite and ignorance.