The Truth About The BSP

By Shamus Posted Monday Aug 31, 2009

Filed under: Programming 66 comments

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.

Yesterday 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 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.

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.

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.

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.

bsp1.jpg

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.

bsp2.jpg

Woo! Game of the year, here we come!

Remember I said that a BSP is all about dividing space in two. Here is our mind-blowing pillar room in BSP view.

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.
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.

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.

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.

Image courtesy of Wikipedia. Note that in step 4, G and F and now fully convex and require no further divison.
Image courtesy of Wikipedia. Note that in step 4, G and F and now fully convex and require no further divison.

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.

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.

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.

bsp5.jpg

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.

bsp6.jpg

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

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.
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.

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.)

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.

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.

bsp8.jpg

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.

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.

This is the tech level that Hammer is using.

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”.

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.

bsp10.jpg

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.

bsp9.jpg

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.)

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.

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.

 


From The Archives:
 

66 thoughts on “The Truth About The BSP

  1. Kel'Thuzad says:

    You succeeded.

  2. Ahluka says:

    I haven’t read it yet, just scrolling down here to leave a thank you comment :-)

    Thanks for taking the time to write this!

    EDIT: T’was great! :-D

  3. chabuhi says:

    I loved editing via BSP back circa 1993-94 because, for some reason, my mind used to work with “subtracting” space from a whole better than “adding” a shape to “nothing”.

    I dunno, same reason that I “draw” better by erasing from a blackened sheet of paper than by drawing on a white sheet.

    I know … I got issues.

    1. Shamus says:

      chabuhi: I am also a fan of subtractive geometry. Since you have to “seal” additive worlds, you end up screwing around with large numbers of stupid little brushes at the edges of the world, and adding rooms is always a lot of hassle compared to just subtracting a new space. Subtractive worlds are always sealed, which is one less thing to worry about.

      I do note that there are smart, talented people who simply cannot get their heads around the subtractive / additive model and regard the whole thing as nonsense and voodoo.

  4. Kdansky says:

    Not bad at all. I will add some more knowledge:

    If you want to see portals in action, go to Stormwind in WoW. You will quickly realize how you cannot see any of the tunnels from one district to the other while standing in another of these tunnels. Why? Because they are the perfect portals and especially built for this purpose. During beta, SW was redone completely at one point with the patch notes saying something technical about drawing less polygons. At that point, FPS skyrocketed for everyone in SW by a factor 10 or so.

    Something you missed: Building levels with BSP also means that the order in which you place the things influences the partitioning, as it does not chose the halves cleverly, but quite arbitrarily. If you put the left column before or after the right column, you end up with different results. And one of these might be a lot better than the other, forcing the designer to learn very unintuitive rules to get a better performance out of the geometry. Chabuhi commented on this fact, but I don’t think people understand that without explanation ;)

    As for portals and BSP: Another technique that is used are Quadtrees (or Octtrees), which are a similar idea, but used for wide, open spaces. BSP does not work there (too many cuts) and portals also fail, since the whole level only takes up “one” room. This is the major reason why only newer games have wide, open areas, because with BSP and portals, those were pretty much unfeasible. You could write about these now :)

  5. BuschnicK says:

    I think you’ve got concave and convex mixed up.
    Convex: every straight line segment between any two points in the set is fully contained in the set.
    Concave: there exists a straight line segment between to points in the sets that is not fully contained within the set.

    http://en.wikipedia.org/wiki/Concave

    …back to reading the rest of the article. Thanks for writing it up…

    1. Shamus says:

      BuschnicK: Of course, it all depends on whether you’re inside or outside of the region in question. The article you linked is talking about the region from “outside” of it. BSP’s usually talk about their regains from the inside perspective.

  6. Sam C. says:

    Are you using the Deus Ex UnrealEd in the examples? Those textures look very familiar.

    1. Shamus says:

      Sam C.: UT99. UTech1 set. The whole tech series are a favorite of mine, although I don’t think I ever released a map using them.

  7. nille says:

    Didn’t UnrealEd already had Zones/Portals, but used them for special areas like water..?

    1. Shamus says:

      nille: Yes. In 2003 they changed portals to serve as above. I forget how water was done. Still with portals? Or with cube volumes? Geeze. I forget now. It’s been years.

  8. Rob says:

    Could be that I’m in the same mistaken boat as Bushnick, but it does seem you switch around Concave and Convex at the end of Paragraph 9 (below the first cut-up room). Of course, my source material is even simpler:

    http://www.mathsisfun.com/definitions/concave.html

    1. Shamus says:

      Rob: Whoops. You are right. The word “convex” should never have appeared at all. I changed them to “concave”. Hopefully got them all.

  9. KarmaDoor says:

    Here I go clarifying Unreal Tournament knowledge, again.
    Zone portals existed in U.T.

    There were also “furniture” (“decor”) models, but were primarily used for moving objects as they were lit differently than regular geometry (vertex versus lightmap, hence no shadows,) plus had no default collision. (That could be added.) You created them as actors, just like players and bots.

    There are alternative BSP types.
    Non-solids are exactly as one expects; lacking collision of any sort, including lacking shadowing of other objects. They reflect light like any BSP, though, via lightmaps.
    There is also semi-solid. Both prevent BSP cuts. The semi-solid type behaves interestigly in that it can be bumped into, but could “eat” certain weapons projectiles when it was in the mood. Semi-solids still cast shadows.

    Portals should be described as planar objects, not 2-D ones. The latter implies they can only be used along the axes. Lastly, I find it interesting that the Binary part of BSP wasn’t covered, in that volumes are split in half repeatedly (at least in most systems.) It’s not taking that into consideration that often leads to the dreaded BSP holes existing in a map.

    I know there is more I will likely add later, but I think I’ll end right now.

    1. Shamus says:

      KarmaDoor:

      Yes, zone portals existed in UT. I obviously had to create some to make the above shots. But I didn’t want to burn three paragraphs explaining how they changed purpose. The important part was that they became a key component of occlusion, where they hadn’t done so before.

      Yes, there are lots of CSG and solidity options, and I suppose I might have listed them if I was writing a book on UT and not trying to give a crash course on what BSP was and how it worked.

      Sure, I’ll heap another 1,000 words into the article to clarify these side issues that weren’t germane to the discussion at hand.

      Sheesh.

  10. Meatloaf says:

    Delicious delicious blue rooms. It’s like a short lecture in logical computational science mixed with level design.

    I’d take that course.

  11. Neil says:

    You know, I never knew any of this stuff when I was making my silly little levels with UnrealEd 1999, yet I was able to get along just fine by half reading some tutorial online and experimentation. It was the only editor I was never intimidated by. Reading this was a hardcore nostalgia wave.
    Also, holy god, making levels like the beach ones in Half Life 2 with Hammer must have been horrible.

  12. Drew says:

    Kdansky: I never thought about it, but now that you mention it I’m sure you’re right about Stormwind. It’s impressive that they’re able to build a city that seems to make sense in its layout and doesn’t seem like it’s forcing the situation you refer to, and yet it works and limits your required draw at all times. I did wonder at one point why there are walls outside some of the exits to the districts, but it doesn’t really seem out of place, and now I know why they are there.

  13. Alan De Smet says:

    Thanks, Shamus. I enjoyed it!

  14. neolith says:

    Shamus:
    Yes, Water in UT2k3/4 is done with cube volumes.

  15. KarmaDoor says:

    Sorry, Shamus. I guess I was getting a bit muddled between examples using UT and the ranting on Hammer.

    Zone portals have always been used in visibility determination. There are differences though. In UT a sight check was performed first; if you cannot see the portal, the BSP “behind” it, then no further visibility calculations are performed. In UT 2003, portals (and anti-portals, antoher subject) are the only visibility determination. (They also cannot determine physics in UT 2003, which they could in UT.)
    See : http://wiki.beyondunreal.com/Legacy:Zone

    I know it isn’t the point of the article, (and I’d much rather discus the article,) but having to explain these things is enough of a headache. Having incorrect information on the Internet just makes things more difficult. It’s apparent you aren’t trying to confuse people.

    Again, sorry for derailing the subject.

    1. Shamus says:

      KarmaDoor: Wow. Thanks for the heads up on old portals. I didn’t know the “new” portals were actually in service back then. I thought it was all BSP-all-the-time.

      Wait. This means you could make new-style levels using Ued 99.

      I wonder if that would help with holes. So many later level projects had to be abandoned because the BSP goes right to hell once you have too many semisolids.

  16. Steves says:

    I would just like to say that this is the most fantastically well written and easy to understand explanation of what is undoubtedly a horribly complicated subject, and even though my particular brand of professional geekery has nothing to do with graphics or 3D, I find it all fascinating.

    So well done, more like this please!

  17. bbot says:

    Source also has a portal system, which it calls areaportals and occuluders. Both are as old as Source, being used in Half Life 2. Both do fancy visibility checking, and thus are somewhat expensive.

    There’s also the hint brush, which is a textured brush that just tells vvis to split visleafs (BSPs) at the brush, and are probably maybe not included in the compiled map, I think.

  18. KarmaDoor says:

    Portals mainly help with performance. BSP errors often were caused by vertices not being “on the grid.” Specifically, they didn’t pay nice unless placed on multiples or divisors of two. I’ve never read a full or authoritative explanation, but I’d guess it comes from having to divide the space by two excessively to achieve the required precision to describe the location of each corner. It is possible to nudge each vertex to nicer positions, but many level designers resort to designing blockier architecture.

    Last heads up; Unreal Engine 3 (used in Unreal Tournament 3 and Gears of War) supports and prefers additive geometry. Somehow they made it so you don’t have to create an air-tight seal around the level. I don’t know how portals are handled in UE3 at all.

    P.S. I think I’ll just e-mail this stuff from now on.

  19. KarmaDoor says:

    Oops… for anyone reading the comments in order, the last one was specifically about Unreal Tournament, not BSP in general.

  20. Carra says:

    Reminds me how math heavy creating a graphics engine is.

    Interesting read and still understandable. All those new graphics technologies look like a list of buzzwords you can tick on or off in your game. I’m reminded of a picture where all the options were changed to how the average person must see those options. Trilinear filtering or Quadpolar lightning, sounds all the same to most people.

  21. Heron says:

    Awesome article, thanks Shamus :)

  22. errolian says:

    Excellent article.. many thanks for posting.

  23. pjw says:

    I hate to continue this…really I do, but every place you used “concave” above…it needs to be changed to convex. I promise. Really.

    The goal of the BSP process is to subdivide the world into convex spaces.

    A circle is convex. A boomerang shape is not.

    …G and F are now fully convex…

    And so on.

    (Also, “all of the interior angles are 180 degrees or less.” should really be changed to “all the interior angles are less than 180 degrees.” 180 degrees exactly is not an angle–it’s a straight line.)

    Good article, other than that. :)

    1. Shamus says:

      Concave vs convex: It still feels wrong, because – at least in my mind – I’m talking about the shape of the thing as if I were INSIDE of it. (Which is the point in a BSP.) Also because when you measure the angles, you do measure them from the INSIDE. (We say a square has a 90 degree angle, not a 270 degree angle.)

      However, this is apparently not correct from a geometry standpoint. I am currently lobbying the mathematicians of the world to have this changed, but in the meantime I have altered the article to work with the current system.

      Also I should get them to do something about this base 60 nonsense when measuring degrees. Thank you so much Babylonians.

      1. Shamus says:

        Radians are indeed better, although all those decimal places are hell when you’re juggling variables in computer code. Just having something turn in place at (say) quarter-turn intervals will steadily accumulate rounding errors. Of course, you can make up any integer system you like for your program. (256 “degrees” for a full circle is quite attractive.) But only if you want to drive the next programmer nuts. (He’s making 64 degree turns!?!? Wait, what number system is he using? This Shamus guy is a nutjob!)

        Actually, you can get away with just about anything if you just put a smiley at the end of your inline comments.

  24. SHODAN says:

    While we’re on about the subject of portal technology, one might want to mention Descent from early 1995. Pretty impressive game for it’s time.

  25. Zock says:

    Shamus, you only need to look at the BSP article you linked to see that the word you should be using is ‘convex’ instead of ‘concave’. Otherwise, I’d like you to demonstrate how to divide convex space into concave subspaces using only straight cuts.

  26. Zock says:

    Also I should get them to do something about this base 60 nonsense when measuring degrees. Thank you so much Babylonians.

    Well, that’s why we have radians. A way more elegant solution for geometric calculations.

  27. Zock says:

    So… You’re not using rotation matrices? ;)

    1. Shamus says:

      “So… You're not using rotation matrices?”

      For storing rotations of actors? No. I prefer to keep those as ints or int-friendly variables and then plugging those into the matrix when it’s time to make with the transforming and whatnot. I like to think of the matrix as a nice box in which to keep all those messy radians. :)

  28. Neko says:

    A circular obstacle is convex, yes, but a circular room is concave.

    1. Shamus says:

      Neko: I’m on your side with this.

      Technically, I should probably say “concave” when discussing rooms and “convex” when discussing how the primitives are divided, but that would only make things MORE confusing for the intended audience.

      Maybe I shouldn’t have changed it. I don’t care. I’m sick of arguing about it.

  29. Zock says:

    True; surfaces of a circular room, when viewed from inside, are concave. However, the room itself as a polyhedron, or a cross section of the room as a polygon, is convex.

  30. KarmaDoor says:

    Of course, you can make up any integer system you like for your program. (256 “degrees” for a full circle is quite attractive.) But only if you want to drive the next programmer nuts.
    Am I detecting a stab at Epic, because they use 16-bit integers for rotations (-32 kibi to 32 kibi.)

    1. Shamus says:

      KarmaDoor: I’d forgotten all about that.

      Actually, I think it’s a fine system internally, although through the editor I would not have exposed the system to the level designers. I can just IMAGINE trying to explain that one to the art team. A couple of lines of code would have converted the number in the interface from degrees and back for them. Still, that’s a minor quibble. I still embrace Ued as the Bestest editor ever, but maybe that’s just my love of subtraction geometry talking.

  31. DanTycoon says:

    It sounds as if you’re saying that Hammer has no portals. Maybe you didn’t, but that’s what I think I saw. And if that’s the case, look at comment 25. Or look here. Probably my first and last comment here, but good article anyways.

  32. MikhailBorg says:

    I’ve only ever built levels on the Macintosh, using the tools for the Marathon 1 and Marathon 2 engines. That was all subtractive geometry, and this article brought back many memories! You can still see some of my work in the “Excalibur: Morgana’s Revenge” conversion for M2/Infinity.

    (For some reason, all the polygon vertices had to be placed in clockwise order. Just one more thing to think about when building the room in the sixth engine screenshot, there.)

  33. Dev Null says:

    Wow. You got all the way through that without using the “death of a thousand cuts” gag. My hats off to you; I wouldn’t have been able to resist.

  34. LafinJack says:

    chabuhi: You should try scratchboard, it’s really cool stuff.

  35. Ralph says:

    For a quick demonstration of how level designers have to think about visibility, open TF2 and load Goldrush. Go and stand in the corridor between the 1st and 2nd, or 3rd and 4th areas. Notice that while you are in the corridors, they are shaped so that’s its impossible to have both areas in view at any one time. So wherever you look/stand the game only ever has to draw one area.

    Also quite obvious in dustbowl, those corridors are there for engine purposes as much as they are for gameplay. In games that have actual doors that open/close, this usually manifests as ‘airlocks’ everywhere with 2 doors set up so one of them is always closed.

  36. Zack says:

    Portals have existed in concept since at least 1996. I was working at Second Nature Interactive (now called Turbine Games) and I remember system programmers wanting to call our rendering engine “the Portal Engine” because they had come up with the idea of using portals to draw things like pillar supported walkways running through a room.

    I am not surprised that other companies also had the same idea at that time. I think it was largely a matter that theory had come up with a way of doing something new and computers had gotten to the point they could handle the concept. I think many game companies were trying to stay cutting edge following publications for the newest theories on caching and rendering.

    They were excited about the idea of portals but in retrospect I believe it was just an industry concept that had found its day and age.

  37. tussock says:

    I remember how much quicker the homemade doom levels would run if I left the computer on all night to BSP them properly. You could take quite complex levels that let you see a long way into the distance through multiple rooms and suddenly (well, the next day, at least) they’d be flying on the old 486.

    These days you’d just procedurally generate multiple such levels realtime, displayed on the faces of a spinning dodecahedron, with a few hundred bots playing deathmatch quite intelligently in each view, as a billboard display in a real game that you’d see for all of three seconds.

  38. octopusfluff says:

    Re: existence of portals in commercial games
    I know Descent 1 and 2 were portal-based geometry, and Descent 1 was released in 1995. Some clever map authors even made interesting abuses of geometry such that you had overlapping 3d space. One of my favorite deathmatch levels for Descent 2 was named Duality, and it had two exact copies of the physical layout superimposed upon each other. You would occasionally slip from one to the other through “malformed” geometry junctions. It made things interesting when using the automap to find an opponent; even if they were visible on the map to you, you didn’t know precisely where they were because of the additional dimension that the map could not account for.

  39. Tom H. says:

    Portals date back to at least 1995 in academia:

    David P. Luebke, Chris Georges: Portals and Mirrors: Simple, Fast Evaluation of Potentially Visible Sets. SI3D 1995: 105-106, 212

    They published in ’95, but IIRC the work started in ’93 and the paper was probably complete by late ’94; that’s before there was so much web, so I don’t know how much they disseminated in 93-94. It’s also a reasonable extrapolation of the previous work in walkthrough visibility (John Airey & Seth Teller’s PhD theses), so other people could have invented independently at the same time, but I think Dave’s paper made a bit of a splash when it was published. I3D’s always been smaller than SIGGRAPH but more focused on graphics techniques that cross over well to games.

  40. Steve Kroon says:

    Great article – thanks!

Thanks for joining the discussion. Be nice, don't post angry, and enjoy yourself. This is supposed to be fun. Your email address will not be published. Required fields are marked*

You can enclose spoilers in <strike> tags like so:
<strike>Darth Vader is Luke's father!</strike>

You can make things italics like this:
Can you imagine having Darth Vader as your <i>father</i>?

You can make things bold like this:
I'm <b>very</b> glad Darth Vader isn't my father.

You can make links like this:
I'm reading about <a href="http://en.wikipedia.org/wiki/Darth_Vader">Darth Vader</a> on Wikipedia!

You can quote someone like this:
Darth Vader said <blockquote>Luke, I am your father.</blockquote>

Leave a Reply to Shamus Cancel reply

Your email address will not be published.