{"id":4759,"date":"2009-08-31T12:00:06","date_gmt":"2009-08-31T16:00:06","guid":{"rendered":"http:\/\/www.shamusyoung.com\/twentysidedtale\/?p=4759"},"modified":"2012-06-14T03:54:52","modified_gmt":"2012-06-14T08:54:52","slug":"bsp","status":"publish","type":"post","link":"https:\/\/www.shamusyoung.com\/twentysidedtale\/?p=4759","title":{"rendered":"The Truth About The BSP"},"content":{"rendered":"

Warning: The following 2,400 words attempt to take very complex 3D rendering problems and reduce them to simple language so that you can peer into the polygon-based sausage factory that is the videogame industry. I’m not sure if I pulled it off. <\/p>\n

Yesterday<\/a> I promised a writeup on “BSP technology”. Except, I was using BSP the sloppy way to mean “general level-optimizing type stuff”, which is not really correct. BSP is a technique<\/em> of level optimization. What I should have said is “how BSP technology is being marginalized in favor of other optimization techniques”. BSP stands for “Binary Space Partitioning”, which is obtuse programmer talk for “dividing space in two”. We love doing that because it lets us pretend our dull technical skills are a potent form of arcane magic. It’s the same reason we “launch applications” instead of just “running programs” like you simple folk. <\/p>\n

The idea of BSP was first conceived in 1969, but to my knowledge it wasn’t until John Carmack authored the Doom engine in 1991 that we saw someone put the idea to commercial use. It was the backbone of first-person games for over ten years, which is a long, long time for a technology to hang around in the fast-moving world of computer graphics. It’s still in use today but in a lot of places it’s at last being phased out or evolving into systems that wouldn’t have made any sense to programmers in the early 90’s. <\/p>\n

UnrealEd (released in 1999) was used to make the following illustrative images. I’m doing this simply because it’s quick and easy to make clear, uncluttered images with it.<\/p>\n

First, we make a simple box room. In the editor, you draw a box, and boom! You’ve got a hollow box to run around in. Lucky you.<\/p>\n

bsp1.jpg<\/td><\/tr><\/table><\/p>\n

If this was as complicated as it got with computer games, we wouldn’t need any fancy technology. But sadly, gamers like to play in spaces that are “interesting”. They want details and multiple rooms and other fancy stuff that makes our job harder. The selfish jerks. So, we’ll throw them a bone and put a pillar in the middle of the room. Also, let’s throw in a single light source, because I’m all about the eye-candy. <\/p>\n

bsp2.jpg<\/td><\/tr><\/table><\/p>\n

Woo! Game of the year, here we come! <\/p>\n

Remember I said that a BSP<\/a> is all about dividing space in two. Here is our mind-blowing pillar room in BSP view.<\/p>\n

You can actually see the order in which the cuts were made. The first would have been the line that divided the far side of the room from the near one. The far side was then a simple rectangle. The near side still had the pillar in it. Then it made the cut that divided the left from the right. The left was then a rectangle, but the right side had the pillar in one corner. Finally, it made the cut between the pillar and the right wall, making the last two areas rectangular.<\/td><\/tr>
You can actually see the order in which the cuts were made. The first would have been the line that divided the far side of the room from the near one. The far side was then a simple rectangle. The near side still had the pillar in it. Then it made the cut that divided the left from the right. The left was then a rectangle, but the right side had the pillar in one corner. Finally, it made the cut between the pillar and the right wall, making the last two areas rectangular.<\/td><\/tr><\/table><\/p>\n

Hey! The room seems to have been “cut up”. The seams you see are from the editor compiling the level. The goal of the BSP is to divide and sub-divide the gameworld until it’s made entirely of convex spaces. It needs to cut the world into three dimensional volumes, which I’ll be calling “zones” from this point on. Above, it has cut the world into four zones. Making them convex just means that all of the interior angles are 180 degrees or less. Another way to think of this is to imagine the boundaries of the zone as being walls. (Which is pretty easy when they’re nice clean rectangles like this.) It’s convex if no wall blocks your ability to move to any other wall. A circle is convex. A boomerang shape is not. A rectangle is convex. An “L” shape is not. A trapezoid is convex, a plus sign is not.<\/p>\n

It does this by finding a non-convex space and cutting it in half. It will then consider each half. Is either half non-convex? Yes? Then cut that half in half again, and consider each half, and so on, until the level is made entirely of convex zones. <\/p>\n

Image courtesy of Wikipedia. Note that in step 4, G and F and now fully convex and require no further divison.<\/a><\/td><\/tr>
Image courtesy of Wikipedia. Note that in step 4, G and F and now fully convex and require no further divison.<\/td><\/tr><\/table><\/p>\n

The upshot is that when you’re done you’ll have these zones – groups of polygons – that you know can be drawn in any order because they can’t possibly interfere with each other. The program will generate these lists of which zones can be seen from which other zones. In the above image, it’s likely that zone E will be occluded for anyone standing in zone G. If the player is in G, everything inside of zone E can be ignored when rendering. Walls, projectiles, characters, particle effects, everything. The game will have this handy list for each and every zone in the level that will tell it what areas need to be drawn when the user is in that location.<\/p>\n

This system was devised when the “fill rate” (or lack of it) was your nemesis as a programmer. The more pixels you had to draw, the slower your program would run. It was actually worth cutting the floor into four pieces instead of having it as one huge polygon, because then there would be a chance that we could skip drawing part of it. But graphics technology turned a corner at some point during the early part of this decade. Graphics cards got so fast that it was no longer worthwhile to obsess over each and every square inch of polygon fill. If you drew a few bits of wall that ended up getting drawn over (because they were really hidden behind another wall which was closer to the camera) it wasn’t any big deal. The graphics card could shrug off the overdraw and keep going without breaking a sweat.<\/p>\n

At the same time, designers were wanting to put all of that extra horsepower to use. They were tired of levels that looked like they were made of Duplo blocks. They wanted a few curves, some detail work, and some sloped surfaces. Let’s take our cheap, square pillar and replace it with a slightly less cheap 8-sided pillar.<\/p>\n

bsp5.jpg<\/td><\/tr><\/table><\/p>\n

Well, that really sliced up the room quite a bit, didn’t it? Keep in mind, each of these pie-slice zones has its very own visibility list of what areas you would see if your eyes ended up in that zone. But really, 8-sided pillars are kind of crappy. That’s 1997 level graphics, there. If you want something to look “round”, you ought to have at least 12 sides. And who has a single pillar in the middle of the room? Let’s have a few. And a ramp on one side.<\/p>\n

bsp6.jpg<\/td><\/tr><\/table><\/p>\n

Well, this is kind of starting to look a bit like something not completely hideous. Let’s see what the BSP thinks of it…<\/p>\n

A little photoshopping applied to emphasize the edges. Note that the engine is picking random shades of blue for each zone, but sometimes you end up with two zones that have nearly the same color. It looks like there is a big, non-convex zone right in the middle of the floor, but it’s really just a case of adjacent zones being the same color. <\/td><\/tr>
A little photoshopping applied to emphasize the edges. Note that the engine is picking random shades of blue for each zone, but sometimes you end up with two zones that have nearly the same color. It looks like there is a big, non-convex zone right in the middle of the floor, but it’s really just a case of adjacent zones being the same color. <\/td><\/tr><\/table><\/p>\n

Ahhh! It looks like someone chucked a brick through a stained glass window. This room is divided up into 248 zones. (Which are actually called “nodes” in Unreal. All these games use similar technology, but it’s pretty common for each one to have unique nomenclature for similar concepts. This is a common result of having many people working separately on similar technology. One exception is that John Carmack came up with some needlessly confusing terms. Instead of calling 3D primitive solids either “primitives” or “solids” he named them “brushes”. Wha? The faces of the brushes – which I might be tempted to call a “face” or a “polygon” were named “leaf”, the plural of which is inexplicably “leafs”. Some of this this unfortunate terminology was passed on to the various Quake titles, Doom3, and all of the Half-Life games.) <\/p>\n

Note that this whole visibility list business is now kind of pointless. Sure, there might be some spot behind one of these pillars where you won’t be able to see some tiny slice of the level behind a pillar on the opposite side of the room, but for the most part your CPU is going to be thrashing through these huge lists of zones only to end up sending the entire room to the graphics card anyway. The zone lists eat up a ton of memory and CPU power, and they aren’t really saving us anything. Meanwhile, the graphics card is spending most of its time waiting. All that vast power is going to waste. By the time we get done adding some doors to other rooms and some details on the ceiling this room will be even worse than it is now. <\/p>\n

A short-term solution was to make it possible to have geometry in the world which would not be considered when making a BSP. If we tell the BSP that the pillars are basically worthless for occlusion and should not create divisions, then the result is a lot less crazy.<\/p>\n

bsp8.jpg<\/td><\/tr><\/table><\/p>\n

Note that this means the pillars cannot ever block your view of anything else for the purposes of rendering. That is, if you mash your face against the pillar so that it fills your view, the game will still [attempt to] draw everything behind the pillar, despite the fact that you can’t actually see it. You won’t actually see through the pillar, but all that stuff will end up being drawn and then painted over, which is a waste. But big deal. Most of the time it would end up drawing all of that anyway. Only now the CPU isn’t going to waste everyone’s time churning through a list of 248 stupid little zones to reach that foregone conclusion. <\/p>\n

But as games continued to get more complex, it became increasingly common for the really detailed stuff to be made in a separate 3D program and imported into the editor. Perhaps the room needs a cryogenic stasis tank covered in control panels and tubes and cables and display screens. Believe me, it would be no fun trying to make that using UnrealEd or Hammer. Those programs are specifically designed for building environments, and it would be torture to try and use them to make detail objects. And there would be no reason to add those features to your level editor when you could buy high-quality, time-tested software to do it instead. <\/p>\n

This is the tech level that Hammer is using.<\/p>\n

Pretty soon it becomes clear that you’re dealing with two types of geometry: Environment (walls, floors, ceilings, etc) and details. (Furniture, windows, doors, vehicles, machines, etc.) Environmental geometry is generally big, simple, and blocky. Even if you’re in a really organic looking location where the walls are made from complex shapes, the room is rounded, and the floor is uneven, the space is generally created by making old-school box rooms and then adding modular bits to the walls and floor. Those modular bits are, as far as the engine is concerned, simply “furniture”. <\/p>\n

The world is divided into rooms, and you don’t ever want to worry about cutting up a room in case the fireplace might possibly, at some angle, obscure your view of the coffee table. Just draw the room and everything in it, because in 99.9% of all cases, the stuff inside of a room is not going to usefully block your view of other parts of the same room. Unreal Tournament 2003 explicitly embraced this distinction, and was built around this idea. The old BSP system was no longer used for occlusion, and instead they added a system of portals. (Not to be confused with anything you see in the game Portal. These “portals” are just simple 2D doors.) Doom3 was also built around this idea. I’m actually curious how that happened. Carmack was done with the core of the Doom3 engine long before UT2003 come out, so it’s not like either team borrowed from the other. Either both developers drew from a common source of knowledge, or they both looked at the problem and came to the same conclusions.<\/p>\n

bsp10.jpg<\/td><\/tr><\/table><\/p>\n

The idea is that you stick a portal in a doorway. (Actually, every doorway \/ window \/ hole that might allow line of sight.) The game makes note of that portal. If the portal ever ends up in view, then everything on the other side of the portal is drawn. (The next room.) If any of that room’s portals end up in frame (even if they are actually behind a bit of furniture or whatever) then that room is drawn, and so on. <\/p>\n

bsp9.jpg<\/td><\/tr><\/table><\/p>\n

This basically puts the job of optimization in the hands of the artist. It’s up to them to figure out where portals should go. This greatly diminishes the number of cuts from thousands of arbitrary cuts to just a few human-selected ones. This is actually something that’s easy for a human to intuit, and murderously hard for a program. Placing a portal is easy and it solves most occlusion situations. (Although it does impose a few limits on how you design your level, which aren’t worth getting into here.)<\/p>\n

Getting back to Hammer and its technology: They’ve embraced the idea of “BSP is for level data, detail meshes are for furniture” idea that Doom and Unreal are using, but the old-school design of Hammer means that level designers have to spend a lot of time fussing with which shapes should cut and which ones shouldn’t in order to avoid the “too many cuts” problem while still limiting overdraw. It’s another problem that’s a subtle annoyance at first, and quickly grows into an unwieldy headache as the level grows to gigantic proportions. If the tool was built with this concept in mind, the artist would just have to busy themselves placing portals (Valve would no doubt call them something else) and wouldn’t have to decide “this shape should cut, this one shouldn’t” on a per-primitive basis. This is just a bit more non-creative gruntwork loaded onto the artist in a system that’s already overburdened with limited tools and productivity-killing iteration friction. <\/p>\n

To Valve artists: My hat is off to you guys. You’ve got one arm tied behind your back and you’re kicking everyone else’s ass anyway.<\/p>\n","protected":false},"excerpt":{"rendered":"

Warning: The following 2,400 words attempt to take very complex 3D rendering problems and reduce them to simple language so that you can peer into the polygon-based sausage factory that is the videogame industry. I’m not sure if I pulled it off.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[66],"tags":[],"class_list":["post-4759","post","type-post","status-publish","format-standard","hentry","category-programming"],"_links":{"self":[{"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/posts\/4759","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=4759"}],"version-history":[{"count":0,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/posts\/4759\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=4759"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=4759"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=4759"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}