An Intuitive Introductory Talk About BSP Trees

Here I’ll try to explain bsp trees here. I might not be right at all points, but I’ll try to make as much sense as possible, even at the risk of showing out exaclty the points at which I start not to understand. I do believe I have some understanding of them though based on a couple of articles I read, some discussions and the implementations I’ve seen. I will not give any code or math in this article! I’ll try to keep it strictly intuitive with the arguments. Oh, and in case you’re wondering why the heck you should read about bsp trees: they are used in such game engines as Doom, Quake series and Unreal. If that ain’t enough for you … I might say stuff like “they could be useful for rendering just about any 3d scene” … but other then that I don’t know (tell me if you know a way of finding burried tresures with them, please). If at some point you don’t understand what I’m talking about drawing yourself a picture might help. Oh, and one more thing: I will try to split the article into as many pieces as possible. (I decided to do this after writing a part of it and getting worried about the long, scarry and apparently meaningless paragraphs.)

And so, it starts

Ok. You got this far with the reading. That’s good. So what does bsp stand for. BSP trees officially stands for binary space partition (and the unofficial version has fallen in the hands of our much loved censor). The reason somebody came up with with them is to partition space (surprise). Why? Well, I don’t really know but I do know why they are good in 3d graphics.

(the problem)

Suppose you have two polygons (eg. they’re triangles) A and B, positioned in some way in our lovely 3d world (maybe rotated and moved). Let’s say your camera is positioned in such a way that polygon A is closer to you, and they are just about on the same line so that, although you can see (a bit of) both of them, polygon A obscures about half of polygon B. What you expect your renderer to do is to go through all the objects in the scene and render them. The problem is that if you render object A and then object B you get a different image than when you render object B and then object A. The correct version is having object B rendered first, because this way when rendering object A on top of that you have corectly obscured a part of object B.

(First draft solution: painter’s algorithm)

So, the solution would seem to be the painter’s algorithm: draw further objects first and then closer ones. The problem with this (as all articles on the subject will point out) are ‘strange’ cases. Polygons are not points. you cannot say: “this polygon is 2 metres away from me”, because a polygon has size. It’s also a bit closer and a bit further (this bit might be pretty big actually). So, you may find yourself with two polygons at about 2m away. Which one do you draw first? Even worse: suppose they intersect. Now each of them obscures a bit of the other. Neither drawing drawing object A and then B nor drawing object B and then A is correct. This is the kind of problem the bsp trees will provide a solution for. Even better: they will proove useful even when you don’t have ‘strange’ cases, as they will give you correct ordering.

(let’s dig in folks)

The idea of bsp trees is to partition space in two, and then each of the two sides in two and so on, until you’ve had enough (you’ll get a feeling of what I mean by enough a bit later). Now we’ll have a bit about the HOW?

(what the heck does partitioning space mean?)

Let’s say we have a scene with polygons A,B,C,D,E. Although five polygons is is not the kind of world you’d like to see on your fancy 3d card and your expensive up-to-date processor they can still give you a headacke as a programmer when you try to view them from different positions. There are a lot of ways they could obscure eachother from different positions.

Let’s assume that they’re pretty small compared to the distances between them (imagine a couple of stars in space). Now you can easily choose a plane that splits space in two parts. Let’s say one contains objects A,B and C and the other contains objects C and D. Let’s call them left and right side of the universe. Now we could split the left side again in two parts, one containing A and the other containg B and C (let’s call them lower left and higher left, in that order). Now we take the higher left side of the universe (which contains B and C) and split it into two parts again: one containing B and the other containing C. Now we’ve can say that the left side of the universe is nicely partitioned (not like my hdd). Then we look at the right side of the world. We split it in two parts: lower right containing D and higher right containing E. Now we’ve had enough. Why? Because each one of our polygons (stars) has it’s own peice of the world. It would make no sense to split regions of space that don’t contain any polygons into very small pieces (and that’s where you’d end up if you went on).

(the big WHY in the sky aka The big example)

That was boring, wasn’t it. I’m a graphics programmer, not a database programmer. I have no inner joy knowing things nicely partitioned (you don’t want to see my room). What I do want though is: Pretty Pictures (and moving ones too). So, how does binary space partitioning help us with that. For an intuition of this let’s step a bit back from 3d to 2d: let’s say that our polygons are just points and the planes with which we cut space are actually lines:

 

 

(you could just think of this as a scene vewed from above, the situation you might have felt in Doom, where the bsp tree was 2d and not 3d)

Now let’s choose a randome position in the world. Let’s say that after walking around through the world for a while you are in the same region as E (higher right part of the world). We will now see the solution to finding the order in which to draw the polygons so that we are sure one that is further away never obscures one that is closer. The idea is: always draw the stuff that is on the other side of the world of where you are compared to the current world splitter. Ok, let’s see it in action. We are at the top of out bsp tree, where space is split in left and right. First we render left, because we are to the right. Now we are on the left side, wondering wheather to go to the lower left (where A is) or to the higher left (where B and C is). Since compared to the line that separates lower left from higher left we are above it, we go below it. We are in the sector where A is, and there are no deeper partitions of space, so we just render A. Now that we’ve finished with lower left it’s time to take care of higher left. Because we are on the same side of the splitter as the sector with C we go to the other one, and since this one has only one object, B (a sector like this is called a leaf, because this is where the bsp tree ends)  we render B. Now that we go to the other half of higher left: the sector with C and since this is a leaf we render it. Now we’ve finished everything on the left side of the world. We go to the right side. The right part of the world is split into higher right and lower right. Since we are on the same side of the splitting line as the higher right we first render the lower right, meaning D, and after that we end everything by rendering E. Now look at the order we obtained and think about it (with the picture in front of you): B, C, A, D, E.

(why this is cool)

Are you getting excited yet? No? Let me explain: maybe you were thinking “I’m sitting right near E. I get correct rendering. C doesn’t obscure B. That is good”, but think again. You might not be near E. You might be very far away, but in the same slice of the world and you would still get correct rendering. Actually once you’ve determined that you are inside the higher right portion of space you can be SURE this ordering is correct. Example: Imagine you’re on the line that connects A with C, but in the higher right section of the world. Look at the ordering. C is drawn before A and that is how it should be. Not satisfied yet? Move ALL objects around the world to whatever you think would produce overlappings while still keeping them in their sectors and you will see that the ordering is COOL.

(getting more real, but also a bit more complicated)
When I said that the objects should be small compared to the distances between them you probably wondered why I said that. The answer is: I didn’t want my splitter planes to intersect with the objects. At this point you’re probably looking at this thing article thinking “if this guy got me reading this junk just to find out that if my world is complicated for me not to be able to use it, I’m gonna hunt him down and murderize him”. Well, I’m in luck. There is a simple solution: if your plane intersects one of the polygons then you simply divide the polygon into two smaller polygons, each going into one of the half-spaces created by the splitter plane. Now, you probably don’t like that. You don’t want your already high-polygoned scene get have lots of baby polygons. You’re right. Nobody likes this. But it’s done. Sometimes you won’t have any choice and you’ll be forced to produce splits, but most of the time you’ll have a painful choice to make: you either split getting lots of baby polys or you don’t split and get an ugly (less useful) tree, but with less polygons.

(happy end)

well, it’s over. Hurray! Hope this document has been of some use to yet. One of the obvious things you need to actually use the intuition you have just obtained is the actual way of determining wheather a point is on one side of a plane or another . Then you would probably go about implementing it in the programming language of your choice. As a wize man once said: “it is said that far greater power lies inside these magical trees. Find it and use it well, my son”.

Void lon iXaarii