[size="5"]Introduction

Many happy returns! :-)

I know I said I wasn't going to write any more of the 3D series until after NAID, but I found that I had some time today to write this article before then, so today we'll be discussing

The Joy of BSP Trees! :-D

Oh, and before I begin, for those of you who've been looking for the article 3&4 source code and haven't found it, you're not alone... I haven't had the time to write up the source for all 3 compilers (WC, BC, and TP) and don't think I'll have that much time until NAID. The articles are quicker to write than the source, and when I write the source, my primary language/compiler is Watcom C. I generally write the Turbo Pascal version last, and since I know many of you are Pascal coders, the C version wouldn't do you much good. So unless somebody for some reason wants to offer to help convert the 32-bit C/Asm into 16-bit TP/Asm, I'm gonna be a little slow on that source. Sorry about that; so much work these days...

But don't worry, just be patient, the stuff will be there eventually. :-)

Anyway, a couple quick notes from back in article 4...


[size="5"]Typos Etc. (Article 4)

In article 4, at one point in explaining a way to do the left-right scanline filling, there was the following code block...

The last line (the second "rep stosd") should be "rep stosb" instead. Sorry about that; I meant to say stosb, but for some reason looking 3 lines above that just influenced my typing. All apologies, although I'm sure many of you figured it out (and many thanks to the 3 or 4 of you who emailed me notifying me of this error; I really appreciate it. Please make me aware of any future bugs like this; I know I won't catch many of them

Also, a couple of you have mailed me about the lack of efficiency in the edge tracing algo I mentioned, mostly regarding the "check against the left and right edges each line to see if they're new extremes" part. Please remember that in these articles, I'm covering very very general explanations of routines; this is intro to 3D here. There are many faster of ways of doing just about everything I put in here, so don't take the contents as the final word, they're just methods. And for you beginners, remember that too... I'm not giving you the fastest routines around... you can always optimize! :-)

(Hint - for the edge tracer, if you order your points in a certain way, either clockwise or counterclockwise, and then check the locations of each point before a trace, you can automatically determine which edge it will trace over, and can quickly overwrite the values along that edge without any comparisons...)

Oh BTW, for those interested in the fixed point square root routine I mentioned last time, the article explaining that will be in the Coding Corner of Imphobia 12, coming out sometime in the next month. So keep an eye out for that if you're interested.

Okay, enough preface junk, time for the meat of the article! :-D


[size="5"]What's a BSP Tree Anyway?

Okay, if you've played Doom extensively or even just read random articles on 3D, you probably have heard BSP trees mentioned off and on. But what are they, and how can you use them? That's what we're gonna find out today.

BSP tree is short for "Binary Space Partitioning" tree. What it is, is a tree of line or polygon "nodes" (for 2D or 3D, respectively) that's pregenerated before run-time for a given static object or set of objects. Once you calculate this tree once for the object(s), you can use it in your program each frame to draw the polygons in correct order regardless of your view position, just by "walking" the tree in a certain way.

I'll be covering both how to build a tree, and how to walk it during your program. The walking part is very easy to code, and is quite a fast way of drawing surfaces in the right order. The tree generation part is not so easy, though, for several reasons which I'll get to shortly.

Nonetheless, BSP trees are well worth the trouble if your scenes are pretty static... they are quite quick and very effective.


[size="5"]What do you mean by "static" anyway?

By "static" object I mean an object (or set of objects) that doesn't move with respect to itself. Like, take a standard cube. The cube is a static object... you can move the whole cube around the environment, translate it, rotate it, etc. But regardless of where it is, it's still a cube. But if you take a few of the vertices of the cube and move them around, the parts of the cube (i.e. the 6 faces) are no longer the same... hence, if you have an object and the object is always that object, it's static. But if you morph the object or explode it or something, it's not. Scaling is okay, as long as all the vertices are scaled the same (it's still a cube, only a different size). It's when the shape changes that causes problems. You'll see why.

(Note: There are some cases where you can change face positions in an object and still have the tree be valid, you just have to be very careful how your tree is constructed if you wish to try something like this).

Well, now that we know our limitations, let's build a tree! :-)


[size="5"]So How Do We Build These Trees?

The term "Binary Space Partitioning" is exactly what it seems to be. BSP trees, in essence, "cut" space into two equal halves, over and over again, until effectively nothing is left to work with. The space is cut along the polygons of your object (although some prefer to cut with axis-aligned planes instead, which is a bit faster but has flaws of its own). The best way to demonstrate this is to walk through a sample tree building of a small scene.

We'll work in 2D for this little sample, but the principle carries over into 3D the same way. Let's say we have a static scene (when I say scene I mean one big object, effectively... or in Doom's case, the level map) that we want to build a tree for. Our scene is composed of 5 lines, arranged in a somewhat random order...

(Note: I hope that formatting errors don't happen this time, because if those lines aren't in the right places, this will make no sense. :-)

Anyway, let's label each of these lines (which we'll pretend are top views of 3D polygons, like walls)...

We also need to give each line a "positive" side, and a "negative" side. For this, pretend that the positive side of each line is the side where the letter is on.

Now, like the name suggests, we need to cut space in half along some line (or axis aligned plane, but I'm not going to get into that method). In essence we can just pick a line at random, but as you'll see soon, that's not a good idea completely...

Say we pick line C. It's facing diagonally, with the upper right on its positive side and the lower left on its negative side. Now what we do is, we extend this line segment to its full line length, cutting space in half.

Looking at the result, we've got A, E, and D on the negative side, and B on the positive side. This was the first step in our tree generation. Let's start our tree with the "home" node (the first one we picked)...

A BSP tree itself is set up with nodes that have one parent (node above it) and between 0 and 2 children (up to one positive and one negative). We chose line C as our first "node" to split with, so we put it at the top. The - and + symbols above are to let you know which side is negative and which is positive.

Now, let's continue with the tree. On the positive side, we only have B, so let's just slap that into the tree (since it's our only pick)...

The "x"s mean that there are no more nodes left in that "space", and the tree stops. You don't use lines that were already used or lines on the opposite side of space... remember, we're splitting space, so when looking at the positive side of C, it's as if the negative side doesn't even exist. All that we have is B. And then when B splits space again (only splitting the positive side of C, no lines are on either side, so it's done.

So now we just have to contend with the negative side of C, where A,E, and D are hanging out. We have three possible choices, so let's just pick A for the heck of it.

Well A has nothing on its negative side, and E and D on its positive side. So let's update the tree...

(Note: The long line at the bottom is just to make room, but it's from the positive side of A).

Now we have D and E left. We can pick either of them. But let's see what happens when we pick E....

We've just cut D in half! That's not good. In a BSP tree, there's only positive and negative, not both. When splits are encountered, there are two options. One is to calculate the split point, and split D into two lines, D+ and D-. In which case, our final tree would look like this...

That works, but the problem there is that 1) we have to calculate the split, and 2) we've just added another line (or wall) to render. The calculation part is not that big a deal. The bad thing is, when you think about a large scene, splits can add tons upon tons of polys to the drawing pipeline. That's a devastating thing that we must try to avoid.

Generally it's impossible to avoid splits completely; they are going to happen, so you better make code to handle it when it does. But the fewer the better. And because of this, we have a second option to avoid splits...

Pick a different node.

Even by just choosing D instead of E in our last step,

... we've just eliminated the split. This is the kind of thing you want to do when building your trees. Unfortunately, when the scenes are large, you don't have the time to build your trees manually, and a program to do it for you won't have the luxury of knowing the best way to avoid splits without trying every single possible tree combination (called the "brute force" method), and that takes an eternity. As if to add another problem to the mix, Split Avoidance is not the only goal of a good BSP tree... we also want a tree that's as balanced as possible. Take a look at the above tree; it's got no splits, but it's pretty unbalanced. But take a look at another possible tree of the same scene...

It's got no splits either, and look how much more balanced it is... we only go down three levels deep instead of four. Why is being balanced also important? Because when we walk the tree, A) the fewer chain links to process the faster it is, and B) on occasion we can eliminate whole branches from the pipeline, and the more nodes on the branch being eliminated, the better.

So which is more important, Split Avoidance or Balancing? It turns out the two are generally mutually exclusive goals; the quest for the perfect tree is always continuing. For most objects/scenes, the splitless trees aren't as balanced as possible, and the most balanced trees have splits. Which is better? In truth it depends on the application.

We're using the trees for real-time 3D hidden surface elimination, in which case both are important, but splitlessness is a slightly higher priority. Not that you'll always have a splitless tree though; there are some scenes that cannot possibly be done without at least one split. But the lower the better. So you want trees that have as few splits as possible, and are as balanced as possible, if possible.

And you have to make a program that knows this. Sound like fun?

I didn't think so. :-)

Generally, the common method is what I've heard called the "sample outlook" method. What you do is, at each step in the tree generation you pick a sample of your nodes (say 10-20%), and pick the one which results in either A) the best possible next layer (quick version), or B) the best possible tree altogether (long version). When I say quick and long, I don't mean so much about how long they take to code, but how long the program runs. The less analysis involved, the quicker the generation is (but the less likely that the tree will be as good as you can get it). It's a tradeoff, and in my opinion, a really good tree is worth the time it takes to go get more coffee, so make your program very critical.

Also, in case you hadn't already guessed, the tree generation is a recursive function, yes. You generate your node and pick two children, then for each child, the function calls itself on the child, and the process continues until the tree is over (no children to process).

The problem is here that picking 10-20% of your possible nodes makes the results rather random, and doesn't guarantee a thing. But, for the most part it's one of the only ways out there to build a tree...

For the most part. ;)


[size="5"]There Is An Alternative

For those interested, I have made an alternative algorithm for tree generation. You should be quite familiar with standard methods of building first though, in order to understand the algo.

The cons are:

1. Rather complicated to understand
2. Harder to code
3. VERY long building time (not nearly as long as brute force though)
4. Sucks up memory (or disk space) like a hog.

The pros though are:

1. If there is a splitless tree it will most likely find it, even with thousands of nodes
2. If there are multiple splitless trees, it will go for the more balanced ones.

It can also be modified to prefer balancing, for example, depending on what you're looking for. As I said, this is a pretty complex (and weird) algorithm, and I can't explain it in here. But if you're familiar with standard recursive sampling methods, you might find it interesting.

(Incentive to go to NAID) I will most likely be holding a couple coding seminars up at NAID, one for beginners, and one more open forum for experienced guys. In the open forum I'll be explaining this alternative BSP tree method to anyone who asks. And no, it's not BS; it's been verified by multiple people already as being quite effective. So if you want to know how, and you can make it to NAID, here's another reason to. :-)

Okay, enough stupid plugging of my stuff... Time to actually put these trees to use! :-)


[size="5"]Alright, I've Got A Tree. What Do I Do With It?

If we've got our tree, using it for polygon displaying is a pretty simple matter. Basically, if we think about it, this tree holds a system of what polygons are on what sides of each other. So by traversing the tree during display, we can get the polygons to show up in correct back-to-front order (you can also walk the tree front-to-back if you like, if you have a system that would use it).

So how do we traverse the tree? Like this...

Take our tree (the balanced one, the one we liked more)...

Now lets say, in the Doom analogy, that we have a player at the X in the scene...

By checking which side of the polygon our viewer is on at each node, we determine which branch of the tree to take first, and as we return to the node before taking the second branch, we draw the polygon. Let's start at the top, at node D. Looking at X, it's on the positive side of D. We don't walk the positive side of the tree though, we walk the OPPOSITE side, the negative one (since it's in the opposite space, generally meaning further away). Now we're at node C. We're on the negative side of C, so we walk the positive side, to B.

But looking at B, it's got no nodes below it. So as if we followed one of them, we come right back to it, and draw it...

And we return back up to C. We've just come back to it from the first branch, so we draw it next.

And then we would follow the negative side of C, but there's nothing there, so we return back up to D.

Now that we're back to D, after walking the first branch, we draw it as well

And drop down to A. We're on the positive side of A, so we walk the negative branch. And since nothing is there, we return back to A, and draw it.

And follow the same-side branch, down to E. E has no child nodes, so we draw it, and notice that we're done, since all five nodes (walls) have been drawn (or queued to draw, depending on how you do your system; it's the same principle)...

Now look at that order from X's viewpoint. If you draw the walls in that order, they'll be in the correct order from that viewpoint! :-) By doing this "which side am I on" checking, you will get a drawing order that works perfectly from any position, all the time.

The same thing holds over to 3D, by checking your position against the plane of each polygon. If you're on the positive side of the plane, go one way, if you're on the negative side, go the other. Same thing, but with lines instead of planes, and it works every time.

Now earlier I mentioned that a balanced tree was not only important for speed of recursion, but also because it could eliminate unwanted branches. To demonstrate this, pretend that the X character was facing to the upper left corner, where it could see part of E and part of A, but none of D or any of the others. Well if we think about it, if we're on the positive side of D, and none of D's negative space is visible (and I mean that, none of D's negative space... D could be invisible while same of its space is, so it's the entire space)... then all the nodes in its negative space (in this case, C and B) can be discarded right off the bat. No need to process them or anything, since there's no way you could see them. This is very very handy, and the more balanced the tree, the more you can discard when this kind of situation occurs.

One final section before I go... throughout this doc you can see how everything is based on what side one thing is on from another. But how do you find this out?


[size="5"]Line and Plane Equations Via Normals

In order to find out what side a point is on from a line or plane, all you have to do is pump the coordinates of the point into the line or plane equation, respectively (and checking a line or plane against another line or plane is done just by checking both points of the line, or all the vertices of the plane, so in the end it comes down to points).

But how do we know the equation of the line or plane to test against? Here's where our wonderful normals and dot products come in again. :-)

If you're pre-storing your normals, then by just pre-storing one more value you can have the entire equation of a line or plane right at your fingertips. For any line with the equation

it turns out that A and B are the components of the normal of the line, and -C is a constant, equal to (Normal.P1), where . is the dot product function, and P1 is the first point of your line segment, the one where the normal was determined from. Once you have this equation (which is pre-stored as just the normal and that constant, -C), you plug in the coordinates of the point to check against into x and y. The result will give you 0 if the point is on the line, but it will also be positive if the point is on the positive side, and negative if the point is on the negative side. The value itself doesn't matter, it's just the sign that counts. Let's do an example. Say we have a line from (0,0) to (1,1). If our positive side is to the lower right, then our normal from P1 goes from (0,0) to (1,-1). And

Sure enough, the equation for the line is

Take any point on that line, and the result is 0, like in the equation. But take a point on the positive side, like (4,2) and you get

... and the result is positive. Similarly, a negative-side point will give a negative side result. So just plug in the numbers of the point to check, look at the sign of the result, and boom, off ya go. :-)

The same thing holds for plane equations in 3D, where

Sure enough, A, B, and C are Nx, Ny, and Nz, the components of the normal to the plane. And -D is (N.V1) where N is the normal and V1 is vertex 1, i.e. the vertex where your normal was based from (the center point of the two vectors in the cross product... remember the cross product? :-) By plugging in numbers, you check what side the point is on during BSP tree walking with just three multiplies for a 3D plane...

where N.V1 is precalculated and Result holds the sign value giving the side that (x,y,z) is on. Sound simple? That's all there is to it. You use the same thing in tree generation to determine sidedness, by checking each point. If all the points are on one side or the other, you know the side of the whole line or plane. If not, then a split has occurred. Be warned though, if you use floating point, that you'll want to make room for a bit of rounding error. A result of 0.00002 doesn't necessarily mean that the point is on the positive side; it could be rounding error, and sometimes you can use this as an excuse to fudge (especially if all but one of the points is on one side, and the one that isn't is only off by a tiny margin).

(PS: Nifty trivia... take a look at the BSP tree of any sphere (including cubes, which are six sided spheres)... you'll notice the tree is not exactly balanced, is it? :-)


[size="5"]That's About It!

If you have any questions, feel free to email me. Although I might be a little delayed in replying, I respond to pretty much everyone. Also, look for the supplement source to this volume and volumes 3 and 4 sometime shortly after NAID (May 31-June 2). And speaking of NAID, if you can make it, make it! It's gonna be a great time, I guarantee it. :-D

Until next time (or NAID),

Kiwidog / Hornet , Terraformer