The Gory Details: Compile Process - BSP

NoodleCollie

Stoat fiend
aa
Jul 30, 2009
383
335
I've been spending a fair bit of time lately learning all about the BSP file format for a project I'm working on, which involves converting BSP files from an existing game into a format that the GoldSrc engine can work with. Since I'm a bit bored this evening, I thought I'd put together an informative piece on what I've learned in the hope that it can help give map makers more of an insight into how the engine makes use of what they've created.

So here it is: all the things you didn't know you wanted to know about the first stage of the Source map compilation pipeline - vbsp.exe. If this proves useful, I might make some more on vis and rad (which I know less about, but whose code I have also had to probe in the past).

What is "BSP"?

Volumes and planes are the building blocks of levels in the Source engine. Every brush you create is a convex volume defined by its surfaces, which lie on a plane*. The empty space remaining within the map is also made up of volumes - volumes defined by the space your brushes don't take up. Volumes and planes make up the most basic capabilities of what the Source engine can do: player collision detection against the world, detecting which parts of the map players are in (eg. trigger volumes), calculating which areas of the map can be seen and so should be rendered, assisting trace line calculations for hitscan weapons, etc.

* Technically, the plane itself is mathematically infinite, so a brush surface is not quite the same as a plane. This might seem like splitting hairs, but it's important to remember. It's actually the BSP process itself that creates the brush surface polygons - an edge on a brush is just the line along which two infinite planes intersect one another.

"BSP" stands for Binary Space Partition. This is the name of the algorithm (meaning process) used for splitting up an area of space according to planes, and BSP files take their name from this algorithm. The BSP algorithm is run in the first stage of a Source engine map compilation by vbsp.exe, and takes a map from VMF format into a planes and volumes format that the engine can use for its calculations.

Basically, the BSP algorithm can be thought of as progressively splitting up the space in the map into smaller and smaller volumes, one plane at a time. If you cut a volume with a plane, this means that the plane partitions the volume into two - hence the name Binary Space Partition. Once you have created two volumes from your original single volume, you can use further planes to partition these volumes again and again; the only rule is that you consider each volume in isolation. A plane that splits one volume does not affect any other, previously created volumes.

The BSP compile step performs this process with each brush in your map, to form what's called a BSP tree. (Note that the "tree" part is very important - I'll explain why later.) It'll be easier to see this with an example.

lTFKfzh.png


Here, the world volume (ie. maximum map extents in Hammer) is shown in black, and a single oblong brush is shown in blue. In this simpler 2D world "planes" are actually lines, but the process is easily extended to 3D - you just have another dimension to split on.

One important thing to note is that each plane has an "in front" direction. Technically it doesn't matter which direction this is, but it's easier to consider these brush surfaces where the front of a plane is the front of the surface pointing away from the brush, and the back of the plane points inwards to the brush's "solid matter".

The BSP algorithm says that we must pick a plane (any will do) and split the volume of space up by that plane. This will divide the volume into two - the space in front of the plane, and the space behind the plane.

EZgmzrl.png


Remember that footnote about brush surfaces and planes not being the same? This is why. We haven't looked at any other planes yet, so we don't have any information on how they partition the space. All we can do in our current step is divide the larger volume into two smaller volumes according to the (infinite) plane we've chosen.

The next step is to classify the remaining surfaces of the brush into those that are in front of the split plane (in the pink area) and those that are behind (in the teal area). Because this example is extremely simple**, all the remaining surfaces of the brush are behind the plane, and nothing but empty space is in front.

** As it happens, this will be the case for any convex brush, no matter what order you process the planes in.

Next, we process each of the two volumes we've created in turn. Because there's nothing in the front volume we don't have anything to do there, so all that's left is to process the back volume.

Then it's as simple as applying the same steps over and over. Where before we were considering the entire volume, in this case we only consider the teal volume. We pick any of the remaining planes, split the volume into two, decide which surfaces are in front and which are behind, and keep repeating. Once we've considered every single plane, the algorithm is finished.***

*** In more complicated scenarios, we may have to split certain surfaces of other brushes if the plane we're splitting with intersects them. In this case, the some of the brush surface will be in front of the plane and some will be behind. This increases the number of individual surfaces we have to deal with at the end of the day, but the algorithm still works the same.

I'm not going to go through everything in excruciating detail, but this is one possible end result for the BSP algorithm, based on the brush layout we're working with:

0l3t74s.png


Here, the planes were picked in the order 1-4. Notice that each time, the remaining volume to be split gets smaller. In the end, we have 5 volumes: volumes 1-4 correspond to the empty space in front of planes 1-4, and volume 5 is the solid brush volume.

Now, remember I mentioned a BSP tree earlier? We can draw out this splitting process in a tree diagram. Each plane in the BSP process is represented by a node in the tree, and the two branches coming off the node correspond to the contents (in front vs. behind) of the world when that split happened.

CGtHS3l.png


This is the tree diagram representing the splits we made in the previous image. You can see that plane 1 was used to make the first split; we could say for certain that everything in front of plane 1 was empty space, and then we recursively split the contents behind according to the other planes.

The result of running vbsp.exe on a map is essentially just a version of this tree diagram, encoded in the .bsp file. Using it, the engine can determine very quickly whether a given point in the world is in empty space or within a solid volume, which is useful for things like collision detection.

ZHNYdlq.png


For example, consider points 1 and 2 marked on the image. For each point, the engine can start at the root of the tree and ask "Is this point in front of or behind the split plane?"**** If the point is in front, the engine proceeds down the left branch; if the point is behind, the engine proceeds down the right branch. It keeps asking the same question at each split plane it encounters in the tree, until it reaches a "leaf" (ie. a node in the diagram which does not have any more branches proceeding from it). Notice that every leaf in the diagram is either "empty" or "solid". Each leaf corresponds directly to one individual volume.

Now when you see "leaves" mentioned when talking about maps, you know what they are! Note that solid brush volumes are still leaves - they're just not empty. As well as empty and solid, the Source engine also has other types of leaves (water, for example). The vis process uses leaves to calculate which map areas can see which others, but that talk is for another day.

**** The point could be on the plane itself, but in most cases this is insignificant. In these cases, "on" the plane is usually treated as being the same as either "in front" or "behind", whichever is most applicable.

How many nodes in the diagram need to be checked depends on where the point is located in the world. You can see that in order to determine that point 2 is inside a solid brush, the engine has to check every node in the diagram; in order to determine that point 1 is in empty space, it only has to check one node.

Regardless of how much you've understood of the process above, you may at this point be asking - why? What's the point of going through this protracted set of steps to build up a tree of split planes that gives you information in this very specific way? What's wrong with just creating a big list of all the brushes and asking the engine to test points against each of them in turn? It'd certainly make maps quicker to compile, and make this post a lot shorter for everyone.

The answer to this is that the structure of the tree diagram is very important. If you test a point against a split plane and you get directed down one branch, this means you can be 100% sure that nothing along the other branch, no matter how deep in the tree it is, needs to be tested. Looking again at point 1 in the above image, the fact that it is in front of split plane 1 means that, by definition, it is not in any of volumes 2, 3 or 4, or inside the brush. The BSP tree is an efficient way of encoding this information: as soon as the engine reaches the "empty" leaf below split plane 1 in the diagram, it knows that none of the other split planes ever need to be considered.

If you scale this tree up to the size of a TF2 map, which can contain thousands upon thousands of split planes, being able to say in advance "I know I don't need to check any of this large group of planes" can save a lot of computing power and, more importantly, time. In contrast, if you had an unordered list of brushes, you'd have to check every single one of them every time, just in case the point you were checking happened to be inside the very last one.

At the end of the day, you can do many more computations with a BSP tree than without, meaning more frames per second for your game. Many, many traversals of the BSP tree will happen on every game frame (just think how many players, projectiles, bullets and physics props need to be constantly simulated in TF2), so the quicker it can be done, the better.

----

I'll leave this here for today because I need to get to bed at a reasonable time for work tomorrow, but I'd like to expand on it another time to add information on why "hint" brushes exist, and a bit on why you're able to do things like edit entities and pack contents into a .bsp file without recompiling.