Pixelate:Issue 1/BSP Trees
From Allegro Wiki
2D and 3D BSP trees - by Noiprox
Contents |
Introduction
There is a lot of hype going on about BSP trees lately. Game publishers advertise about how their game 'uses BSP trees to produce lightning-fast stunning graphics', or game reviewers talk about how Quake3 uses some revolutionary BSP technique to render 'curved surfaces'. A lot of programmers also seem to think BSP trees are this obscure and very difficult technique that only John Carmack (who wrote the Doom and Quake series' engines) and Tim Sweeney (Unreal Engine...) know how to use. Ok, back to reality ;) BSP trees are, in fact, quite a simple technique that helps a lot with one of the biggest problems in 3D programming: depth sorting.
BSP trees are not perfect, though. No algorithm is. The biggest single problem with BSP trees is probably that they only support static scenes (this is not entirely true, but I'll explain later). There are other methods, such a portal engines (another article, maybe ;), octrees, and so on. Many engines are hybrids of several algorithms.
The Algorithm
BSP stands for Binary Space Partitioning trees. I'm going to describe 2D BSP trees first, then I'll explain what it takes to do them in 3D.
Let's say you have a very simple, 2D level. In fact, it's only one room. Like this:
There is no need to sort the walls of this room, because no matter what order you draw them in, they will never be able to overlap each other, and therefore they can never be in the 'wrong' order, assuming of course that you always remain inside the map (the room in this case). This we call an atomic subspace. That is, one where no polygon ever 'overlaps' another.
Now, consider this room:
In this room, if the viewpoint is at V, looking towards the target T, there is a distinct order in which the polygons MUST be rendered. AB must be drawn first, then BC, and lastly CD. If the polygons are not rendered in that order, they will overlap and cause a strange (and incorrect) display. This is the problem that BSP trees address. BSP trees work as follows:
If you divide the room up so that you have the large part, and the piece below it, then you will see that each part is now an atomic subspace. So if you render all the walls of the large piece, and then those of the small part below, you will have solved the problem! So how do you determine in what order to render the parts in? Simple, you check which side of the divider the viewpoint is on, and you render the other part first. That way, you will have drawn the far walls first, and then the nearer ones over them. This is the correct order, of course.
Realistically, most levels will have more than two parts (called sectors). All that this means is that you will also have to subdivide the subspaces themselves.
BSP trees are binary. This means that each node has exactly two children. No more, no less. This comes from the fact that in 2D, all points can be classified as being either on one side, or the other side of a given line. If a point is exactly on a line, it can be considered to be on either side of it. The entity with the property of dividing a dimension into two sides is called the hyperplane of that dimension. As I said, a line is the hyperplane for 2D, for 3D, it's a plane. Now, in C/C++ the data structure for a BSP tree is related to that of a linked list. We have a structure with two pointers: 'left' and 'right', and a pointer to a list of walls present in this node. If 'left' and 'right' are NULL, 'divider' will also point to NULL, the current node is an atomic subspace (called a 'leaf' of the tree) and it doesn't have children. The list of walls will be defined for leaf nodes. Otherwise, 'left' and 'right' point to other nodes, possibly with their own children, the divider will point to a hyperplane, and the list of walls will be a NULL pointer. For example:
struct tree_node
{
wall_list *walls;
line *divider;
tree_node *left, *right;
}
struct tree_node root;
Of course, this won't compile because tree_node isn't properly defined when it's used to declare *left and *right, but that's not the point :) It should be obvious from this that BSP trees are a recursive data structure. Root is the top of the tree, and unless the whole map is atomic, it will have children and no walls.
Rendering a BSP Tree
Ok, so now we want to render a BSP tree. To do this, we start at the root node (the top of the tree). We check if it has children. If it does, we find out what side of the divider we are on. We then visit the node representing the other side (Red Hot Chilli Peppers: "Take it on the Otherside..." =), and we do the same. That is, we check if it has children or not. If not, we render the walls, and we back up one. Then we visit the node on the side that our viewpoint is on, and so on. This algorithm works, but it has one little flaw (don't they always...). You end up visiting every node, every frame. This isn't necessary, because more often than not, you aren't looking at the whole map at one time. We can safely ignore a node (and all it's children) that isn't in our field of view. This is called 'pruning' the tree, and it makes for HUGE speed increases for the most part. It also makes sense to backface cull your walls. Backface culling simply means you only render walls that face you. Since you are always on the inside of your map, you will only ever see one side of your polygons. This saves you the trouble and rendering time of drawing a lot of invisible polygons. You can also render the polygons front-to-back, and use a z- or s-buffer to ensure that there is no overdraw. This has the advantage that you don't even have to draw the farther invisible walls if they are obscured by pixels from nearer ones. I'll leave this up to other sources for a complete discussion.
Generating a BSP tree
This is all fine and everything, but we still have one problem. How do we actually get the BSP tree? Well, there are two solutions. One is to make it necessary to manually draw the dividers in your map editor. This would work, and it would usually generate a good BSP tree, but it's a lot of work for your poor level designers, and sometimes it's impractical. The trees get exponentially more complex with your polygon count (i.e. architecture impressiveness ;), and in 3D it becomes an unreasonable burden for your level designers. The other option is to write a tool to automatically generate them from your map data. This is what "bsp.exe" does for the Quake series.
Let us say you've got a list of vertices, and a list of walls running between them. You start by making the whole map the root node. Then you see if it's atomic. The way to check if a space is atomic is if the hyperplane in which a wall lies ever intersects with another wall, the space is not atomic (because only convex spaces are atomic). If not, you take the offending wall's hyperplane and use it as a divider. You determine which side of the divider each wall is on, and you put them in the 'left' or 'right' child nodes accordingly. BUT... it is possible for a wall to be on both sides of a divider.
That is, the divider can cross a wall like this:
In this case, the east wall is on both sides of the divider. To handle this, you have to split the wall into two smaller walls. Two half walls will render the same as one big one, so that's not a problem. You add in a new vertex, and you put each half in the appropriate child node.
Usually when we are going through the walls to find if any of their hyperplanes intersect with any others, we will find that several of them do. Our choice of which wall to use can affect the performance of the final BSP greatly. A BSP tree with a lot of split walls is imprecise because of floating/fixed point error, and such a tree will have more polygons than one with fewer splits. Therefore your primary criteria for generating a BSP tree is to minimize splits. It is also good if your dividers are orthagonal (i.e. parallel to a principal axis) because these are less likely to cause rounding errors. A divider which causes fewer divisions in it's children is also desirable because it makes your tree smaller. A divider which produces a balanced tree is also good, because if you prune your nodes, a balanced tree will be faster (you'll be able to prune bigger chunks at a time). Unfortunately, balancing trees, especially BSP trees are very hard, and it may be better to ignore this (unless you're Carmack! ;) ). A BSP compiler can take ages to produce a good tree, because finding an optimal tree, or one as close to optimal as possible means exploring and comparing a lot of possibilities recursively. This is why the Quake2 BSP compiler takes so very long to compile maps.
BSP in 3D
3D BSP trees are exactly the same as 2D ones, except that the hyperplane for 3D is a plane, not a line, and your walls are polygons instead of line segments. Splits become even worse (heavy linear algebra: plane/plane intersections). But that's about it. Nothing revolutionary here, see!
Limitations of BSP trees
BSP trees are a great algorithm for sorting polygons. Probably the biggest problem with them, though, is that they don't allow for much in the way of level dynamics. Walls in a BSP tree cannot be allowed to move because that can affect the validity of the dividers, and therefore that whole branch of the tree. One could always precompute the before and after branches, and switch between them as needed, though (I'll leave the details up to you). Specifically, a divider can be invalidated if a wall ever leaves it's hyperplane, or crosses the hyperplane of one of it's parents. So limited movement is possible. But if you think about it, you will realise that such movement is basically useless.
I think the 'curved surfaces' of Quake3 and the updated Unreal Engine are simply treated as their bounding boxes by the BSP engine, but when they are rendered, they are rendered as the full polygonal piece of architecture (like that ridiculous tongue in Quake3 for example...).
The Unreal Engine does a very clever thing (okay, it does a lot of clever things, but anyway...). It doesn't treat the moveable sectors as part of the BSP tree. That is, it renders them independently, using the BSP tree only as a guide as to when to render them. In other words, instead of just rendering the walls of your leaf nodes, you render the walls, and everything contained inside them (z-buffer is needed here). Look at the first level of Rune (an Unreal Engine game) for a good example. I doubt those cages are part of the BSP tree.
Contacting Me
I'll welcome comments or suggestions.
Please email them to noiprox[at]mailbox.co.za
By Dieter Buys (Noiprox)
| Issue 1: The Awakening | ||
| Previous: Allegro Tutorial | Present: BSP Trees | Next: Crossing Platforms |
