--------------------------------------------------------------
BSP-Tree Primer
By Matthew Mastracci (mmastrac@ucalgary.ca)
(c) Copyright 1998 by Matthew Mastracci. All Rights Reserved.
--------------------------------------------------------------
Introduction
While listening to discussions on how Quake and DOOM work, while reading
Michael Abrash's columns in DDJ or even while browsing the released source to
Wolfenstein, you've probably come across discussions about an algorithm that
seems to be able to do amazing things: BSP-trees.
What is a BSP-tree? Well, the acronym "BSP" stands for "Binary Space
Partition". So, you may then ask, "What exactly is a binary space?" and "How
the heck do we partition it?" We'll get to all of that eventually. The
concept of a BSP-tree is fairly complex to visualize if you don't understand
it, however, so I urge you not to go on before you've finished comprehending
the earlier sections.
When the concept of BSP-trees is first explained, you may find yourself
doubting that they actually work. When you see them in action from your own
code, however, you will be amazed. Once you can grasp these fundamentals,
the harder concepts will come together a lot easier.
There are exercises included at the end of some of the sections to help
illustrate the concepts. If you find something confusing, doing one or two
of the exercises may help clear things up.
Binary Spaces
The name "binary space" is a sort of misnomer. It's not actually a
"space" in the mathematical vector definition, but instead a representation
of the relative positions of objects. As you may have guessed, there are
only two (hence binary) relative positions: ahead and behind. Now, if you've
ever worked with some simpler polygon-rendering programs, you've probably
heard of something called the "painter's algorithm". It means that if you
want to draw object 2 in front of object 1, just draw object 1 and then
simply draw object 2 on top of it.
With a little abstract connection, you can begin to see how BSP-trees
can be used for quickly drawing polygons. The BSP-tree will be able to tell
you what's right in front of you and what's behind what's in front of you.
By traversing the BSP-tree, you can quickly generate a drawing order for your
polygons, saving you the time spent Z-sorting or raycasting.
Binary Space Partitions
Id Software's DOOM, a mega-hit that pushed popular 3D-dungeon gaming out
of the unshaded raycasting era of Wolfenstein, was the first BSP-tree game to
be put in the spotlight. All of a sudden, you could run around a giant
dungeon, instead of a tiny one. You could run up and down stairs, jump off
cliffs and even see the sky outside. For those who were used to 90-degree
dungeon games like Wolfenstein, it was a wonderful change.
So how did Id do all this? The answer, as you have probably guessed, is
by using BSP-trees. You should note, however, that the BSP-trees used in
DOOM are actually 2D, not 3D like Quake, and were mapped into the 3D space
you see. It's like taking a square to make a cube and a circle to make a
cylender. It makes sense though: the walls in your house are all vertical,
are they not? Note that DOOM doesn't do it exactly like this: the bright
folks at Id came up with ways to optimize the process, but we'll discuss that
later.
Let's get into our exploration of BSP-trees. Before we start, just take
a look at the actual term we're using: binary space partition tree. Don't
forget that a BSP-tree is a tree made up of BINARY SPACE PARTITIONS. It's
not made up of the actual polygons (these are stored in "leafs", to extend
the metaphor). Why don't we take a look at an example, to get us started:
^ Y
| /\
| / \
| | \
| | |
| | |
| | /
| \ /
| \/ X
+---------------->
O
Now this is a farily simple room- one you might find in DOOM. We'll
try to partition everything so that the partitions run through the
intersection of two walls (or split a wall fairly evenly, as we'll see
later). Let's start with something we could call the "trunk node", "main
partition" or "main node" (we'll use main partition). To keep things simple,
all of our partitions will be parallel to the X- or the Y-axis. This first
partition will go straight down the middle of the room, vertically:
^ Y
| /\
| / | \ Note: the plus side will always point to
| | | \ the increasing value of X or Y by convention
| | -|+ | (for this part only)
| | | |
| | | /
| \ | /
| \/ X
+---------------->
O
Notice the plus and minus signs to either side of the main partition.
These are just to help us keep track of what we'll call our "front" and
"back" nodes. These nodes link us to the next partition ahead or behind the
main partition. We'll put one more single partition on the plus side and one
more on the minus side:
^ Y
| /\
| / | \
| | + | \
| |---| + |
| | - |----|
| | | -/
| \ | /
| \/ X
+---------------->
O
Whoops! It looks like the partition on the left-hand side goes right
through the wall and cuts it into two parts. Not a problem. We'll split the
wall into two different parts, one on the plus side of the line and the other
on the minus side. Also, notice that the bottom partition on the right-hand
side is finished: it only contains one wall. To finish, we'll put in the last
three partitions, one for each new area we created before containing more
than one wall:
^ Y
| c /\
| /__| \ d
| b | |___\
| |---| | e
| a | |----|
| |___| /
| \ | / f
| g \/ X
+---------------->
O
We're now finished. Notice how the walls have been labelled with
lowercase letters. The one we split into two parts has two letters
associated with it. How do we construct our tree? Well, just remember that
each partition will have two links. These links will either both connect to
two subpartions, both connect to a wall or one to a subpartition and one to
a wall. The BSP-tree for this room, bearing in mind our convention of the
plus side of a horizontal partition being up and the minus side down, and
the plus side for a vertical partition being right, while the minus side is
left, is this:
main
+/ \-
/ \
sub sub
+/ \- +/ \-
sub sub sub f
+/ \- +/ \- +/ \-
c b a g d e
Our tree is now complete. Note that each of the partition nodes
contains only the direction of the partition and its x- or y-coordiante.
The wall nodes will contain the information detailing the (x,y) coordinates
of the two vertices of each wall segment. Now that we have the tree built,
we can go on to drawing it.
Traversing the BSP-Tree
Drawing a room from a BSP tree is very simple. Let's use a little C
pseudocode. Note that a node has two links: Node->Plus and Node->Minus. We
could use "Ahead" and "Behind" instead, but they won't always represent the
current situation. It also has a linked list of walls coplanar (or
collinear) with the actual partition. This allows us to define a leaf in the
same way we define a node, while also allowing us to create partitions that
run across walls (as we'll need for some of our later examples).
Boolean PlusSide(Node CurrentNode, Location2D OurLocation)
{
if (CurrentNode->Orientation == HORIZONTAL) {
if (OurLocation->y > CurrentNode->Coord)
return True;
else return False;
} else {
if (OurLocation->x > CurrentNode->Coord)
return True;
else return False;
}
}
void DrawNode(Node CurrentNode)
{
if (CurrentNode->WallsOn) {
DrawWall(CurrentNode->WallsOn);
} else {
if (PlusSide(CurrentNode, OurLocation)) {
if (CurrentNode->Minus) DrawNode(CurrentNode->Minus);
if (CurrentNode->Plus) DrawNode(CurrentNode->Plus);
} else {
if (CurrentNode->Plus) DrawNode(CurrentNode->Plus);
if (CurrentNode->Minus) DrawNode(CurrentNode->Minus);
}
}
}
It may seem a little cryptic, but consider the following situations:
^ Y *
| c /\ * = Situation 1
| /__| \ d # = Situation 2
| b | |___\ % = Situation 3
| |---| | e
| a | |----|
| # |___| % /
| \ | / f
| g \/ X
+---------------->
O
| Drawing | Situation |
| Order | 1 2 3 |
+---------+-----+-----+-----+
| 1 | g | d | c |
| 2 | a | e | b |
| 3 | b | f | a |
| 4 | c | c | g |
| 5 | f | b | d |
| 6 | e | g | e |
| 7 | d | a | f |
If you trace through it in your head, you'll get the same results. On
closer inspection, you'll see that if you draw these polygons (adjusting for
perspective and clipping ones behind the viewer), you'll get a perfect view
of the room. Take a pencil and paper and try partitioning some oddly shaped
rooms. Remember a few simple hints (we'll keep our trees simple for the
moment):
1. Leaves represent the basic objects that you are drawing
2. Each node must have two links, and can only link to other nodes or to
leaves
3. Don't make the work hard for yourself- use the fewest number of
orientations for your partitions (two for 2D, three for 3D, but some
situations may require others, as we'll see)
4. If you have to, place a partition on top of a wall
In the next section, we'll figure out ways to partition by algorithms.
Exercise:
Try partitioning the following rooms, creating their BSP-trees and testing
the drawing order for the points marked with an asterisk (enlarge the diagram
on a piece of paper to make things easier)
__f_ ___a___ (note: the letters tagging the walls
i. g/ \e ii. m/ b\_c go either clockwise or
h| |d l| h_ |d counterclockwise from "a")
a\____/c k\__/ g\__/e
* b j i f
*
BSP-Tree Objects
Before we start growing our first computer-generated BSP-trees, we need
to define the basics of the objects we're going to use. To start, let's
create the definition of a BSP-tree and work down:
class BSPTree {
BSPTree(); // Constructor
~BSPTree(); // Destructor
BSPNode * TrunkNode; // A pointer to our trunk node
};
class BSPNode {
}
Growing a 2D BSP-Tree (the simple way)
As an introduction, we'll start with the least-intelligent algorithm for
a 2-dimensional set of lines, arranged like a room. Let's start with our
first example:
c
____
b / \ d
a | . ___\
| / e*
\/ f
g
This example may seem complicated, but the abstract nature of the
algorithm allows us to do things like this with ease. According to this
algorithm, each of the partitioning lines runs collinear with each of the
walls in the room. Our first step is, of course, to pick the truck node.
Let's pick it as a line collinear with the wall marked with an asterisk.
We'll then see where every other wall fits in relation to this one (commonly
referred to as "pushing" a wall through the BSP-tree). Now we have to sort
the walls into ahead, behind, spanning or collinear. To simplify this
example, the side of the line containing the pseudo center of the room
(marked by a period) will be the plus side. Our list becomes:
Plus Minus Spanned Collinear
d f a e
c g
b
We'll split the wall spanned by the partition (at the point indicated by
an underscore) into a and a':
c
____
b / \ d
a' |_ . ___\
a | / e*
\/ f
g
Our list is now:
Plus Minus Collinear
d f e
c g
b a
a'
Let's recurse, doing this using the plus list instead of the whole list
and by taking the first element in the list as the initial partition:
Plus Minus Collinear
c d
b
a'
Continue this method with the plus lists, and then repeat for the minus
lists. Eventually, you'll get a BSP-tree that looks like this (check if you
want):
main (e)
-/ \+
sub (f) sub (d)
|+ |+
sub (g) sub (c)
|+ |+
sub (a) sub (b)
|+
sub (a')
This list may seem more like a hanging germanium than a tree. There's
no problem with this, however. It just means that the room is constructed
fairly simply. Consider the point marked with an asterisk:
c
* ____
b / \ d
a' | . ___\
a | / e
\/ f
g
Using the algorithm we learned earlier, let's write the drawing order
from back to front (remembering the order: the opposite side to the one we're
currently on, any collinear walls and then the walls on the same side we
are):
f, g, a, e, d, a', b, c
Not surprisingly, it works.
Splitting a Wall in 2D
Splitting a Polygon in 3D
Adding Objects
So far, our virtual world can handle static scenes with ease. You might
be wondering how we can incorporate dynamic objects into the picture. These
objects should be able to move around with ease and hopefully not consume a
lot of processing power. Luckily, it turns out that for most cases, even if
our objects are comprised of BSP-trees themselves, we won't have to break a
sweat over this.
Determining Relative Position to a Plane
Determining your relative position with a plane is quite simple. All it
requires is: the normal of the plane (precalculated), the closest distance
from the origin to the plane (precalculated) and a vector going from the
origin to your position (ie: your location). To get the formula,
let's start with a simple diagram:
_____________
u /| Where:
/ | |d|, n - v is a vector from the origin to the viewer's
\ V| location
v \| - d is the shortest distance from the plane to
o the origin
- n is a vector running OPPOSITE to the direction
of the plane's normal
- u is a vector from the closest spot on the
plane to the origin to the viewer
- V is the angle between v and n
If you've worked with vectors before, you'll remember that the dot
product is equal to the product of the absolute lengths of the two vectors,
multiplied by the angle between them or the sum of the products of the
components. Mathematically:
dot(v, n) = |v||n| cos V = v.x * n.x + v.y * n.y + v.z * n.z
Since the length of the normal is one, we can simplify this to:
dot(v, n) = |v| cos V = v.x * n.x + v.y * n.y + v.z * n.z
But wait! |v| cos V is just the component of the vector v in the
direction of the vector n. That means if dot(v, n) is less than d, we're on
top of the plane (the side the plane's normal points to) and if dot(v, n) is
greater than d, we're on the bottom. So, we can just subtract the two and
simplify this a little further:
Side = sgn(d - dot(v, n))
Side = sgn(d - v.x * n.x + v.y * n.y + v.z * n.z)
Note: sgn is the signum (or sign) function, sgn(x) = x / abs(x), sgn(0) = 0
We can determine quickly which side of any polygon we're on by using
our formula.
Determining Relative Position to a Line
Determining which side of a line you're on is simply a degenerate case
of relative position to a plane. Extend the partitioning line into three
dimensions by adding a z-component of zero. We can now take a normal from
our pseudoplane which can be used for determining relative position by the
formula above.