The Technology Behind ID's Games

orac2 writes: "The current issue of IEEE Spectrum has an article on the groundbreaking technology behind iD Software's games, from the days of Commander Keen through to Return to Castle Wolfenstein. Graphics technologies covered include the original 2-D buffer trick that made side-scrolling games on the PC feasible, as well as the more modern Raycasting and Binary Space Partition Tree techniques. Carmack is quoted extensively."

Comments

Quake I / II

[Shamanin]

I read this in the IEEE spectrum. They kept mixing up the advances in Quake I with Quake II. They even refer to a picture of Quake II as Quake I. But, there was some interesting history nonetheless.

Excellent diagrams

[jukal]

This one is particularly good: about binary space partition tree.

Re:Excellent diagrams

[jtdubs]

Binary space partitioning trees proper have fallen out of use in games.

All BSP-based games now-a-days use Solid Leaf BSP trees, which are a variation of the original and have many more useful properties for games.

It is these trees and the sectors that they create that are used for determining portals.

If two sectors have the same portal then those two portals connect and can see eachother. If a portal has no pair, then it is a portal out in to infinite space and is hence a leak in your map. Assuming, of course, a map based on a single BSP tree.

Once you have portals, PVS generation is easy. And there you go, BSP and PVS.

A lot of modern research is shying away from BSP and PVS. They limit you to indoor spaces. Entirely different technology is required for outdoor scenes. And then special hacks and logic are needed to allow for seamless transitions between the indoor and outdoor worlds.

Some think that octrees with a form of occlusion culling might very well be better as they can represent both indoor and outdoor geometry without making any distinction between them. They are much harder to cull though as no handy PVS information is present and only more difficult methods exist such as Z-pyramids.

Others stick with BSP and PVS and use the one-sided portals that would normally represent leaks but instead in this case represent windows from the BSP into the terrain, and vice-versa. This combined with some extra lighting and shodow-volume information and you can have your lighting and transitioning between indoor and outdoor be seemless.

Anyway, just the ranting of a bored man at work.

Justin Dubs

Re:Excellent diagrams

[jtdubs]

No problem. This is a common question.

Here's the thing.

BSP trees work by breaking up the world into arbitrary convex hulls. This is good because you can render a convex hull that you are inside without worry about some of the triangles overlapping other ones.

In other words, take two cubes connected by a recangular hallway.

Theoretically the BSP tree could divide this into three sectors. One for each room, and one for the hallway. Each of these individual sectors is a convex hull.

So, if you are in the sector for a room you can just render that entire sector, without using a z-buffer or any kind of depth testing, and you don't have to worry about things overlapping. I mean, there is nowhere in a room where you can stand where the left wall and the floor will overlap.

See what I mean?

Now, while you are rendering the room you render it's portals. It has a portal connecting it to the hallway sector. So, you render the hallway's sector, clipped to the polygon that is the portal.

Then, while drawing the hallway you draw the sector connecting to the second room. So, you draw the second room, clipped to the portal leading from the hallway to that room, which is already clipped to the original portal.

So, we just drew the two rooms and the hallway, with no traingles overlapping.

This is exactly how the original portal-based renderers worked.

Now, why doesn't this work for outdoor scenes?

Imagine a large field with rolling hills. Now, try and find a convex hull. It's tough.

Imagine a hill shaped like a dome.

This dome forms a conCAVE hull. You can't break it down in to ANY convex hulls. So, every single triangle has to be part of it's own, unique, convex hull.

So, now every triangle in this hill is it's own sector. Our BSP tree is huge. And we have MILLIONS of portals connecting every triangle to the ones next to it.

This is HORRIBLY ineffient and slower than just brute force rendering.

So, to summarize. Indoor scenes tend to be easily decomposable into convex hulls. And hence work well with BSP trees and PVS. Outdoor scenes aren't. They tent to have a lot of concave areas.

So, hope that helps.

Justin Dubs

Truly impressive

[aengblom]

The truly breakthrough technology is that ID made it possible to spontaneously induce vomiting without noxious fumes! ;-)

ARRG (offtopic)
Editors please (as in pretty) fix this:

User types in comment and submits it (without subject). Is told to type in subject, but then is told "you have submitted to quickly." User loses comment because it is cleared from browser cache and slashdot doesn't put it in the error page.

( /offtopic )

Id didn't develop the Keen trick

[Junks Jerzey]

Good article, but the Commander Keen scrolling trick was old news by then. Lots of Apple II, Atari ST, and Amiga scrolling games did the same thing. Impressive? At the time, yes. But let's not get too carried away with giving Carmack credit for everything.

Re:Amiga???

[mindriot]

My theory is that while the Amiga scrolled by changing the pointers to where the screen was in memory, the PC dumb-copies entire screens.

Well, that's what Id avoided on PC... (did you rtfa? :)) When EGA cards came up, they had enough graphic memory and functionality to change pointers... back then I tried this a little on VGA (320x200 tweaked mode giving four screens, and changing a pointer to scroll/switch screens for double-buffering).

The Amiga did of course have much better graphics hardware, including a blitter for fast graphics data transfer and accelerated drawing functions, (at that time) lots of video memory, and further hardware acceleration such as sprites support. And, also, support for bitplanar graphics modes, easing smooth scrolling.

Say it with me now...!

[aztektum]

It's *id* Software. Not ID. Not iD. id. as in the psychology term.

id
Pronunciation: 'id
Function: noun
Etymology: New Latin, from Latin, it
Date: 1924
: one of the three divisions of the psyche in psychoanalytic theory that is completely unconscious and is the source of psychic energy derived from instinctual needs and drives.

Re:Softdisk

[John Carmack]

Here is an interesting bit of history:

Greed was built on the engine I wrote for Raven/Origin's Shadowcaster game, while the other Id guys were working on Spear of Destiny, the commercial Wolfenstein game.

The reason softdisk got the technology was that they were still making lots of noise about suing us for doing Keen while we were working at softdisk. Our original parting deal was that we were going to continue doing the Gamer's Edge games for a while, basically for free, as penance. We weren't savvy enough to get anything binding down on paper, so even when it was all wrapped up, there was room for twisting our arm a bit. (another trivia bit -- George Broussard at Apogee arranged to have Apogee produce one of the Gamer's Edge titles for us, so we could focus more on Wolfenstein).

We finally arranged a technology transfer of the latest engine code for free and clear severing of our ties. After they showed that just having the technology was not a guarantee of success, they had the nerve to come back and ask for more, but by then we were able to just tell them to go away.

BTW, Duke Nukem does not have a Softdisk heritage, it was by Todd Replogle (sp?), who was strictly Apogee-grown.

John Carmack

Softdisk v. Id

[Sean Clifford]

Unsubstantiated company rumor on the Duke thing, I guess. :)

I remember Al talking about the lawsuit and the source code. One poker night (which I played badly) Dan Tobias went on a long rant (suprise) about the whole ordeal. I share his opinion that moonlight code belonged to the programmer, not the company.

Absolutely nothing came of the source code. It sat in Jim's office unused.

Originality, creativity, etc

[John Carmack]

I was fairly pleased with how that article turned out - when I first heard about it, I dreaded seeing a trivialized simplification of the issues, but it turned out as representative as you can be in that space.

However, I really dislike discussions of the attribution of techniques to a particular programmer. Everything is derived from things before it, and I make no claims of originality. I would say that one of my talents is the ability to be aware of what sources are feeding into my work, and be able to backtrack to them. Also, there are always lots of other possible answers for any given problem that can be made to work. BSP vs sector list, Portals vs PVS vs scan line occlusion, tilted constant Z rasterization vs block subdivision vs background divides, etc. Looked at in the proper perspective, individual techniques just aren't all that important. Sometimes it sounds like "Dude, he INVENTED needle nose pliers!!!"

Heck, I somewhat deride the very concept of originality. Creativity is just synthesis without the introspection. Lots of people will catch on that and start a rant about how Id games aren't original, but they are missing the point - it is possible to set out and develop something that will be received as "original" without ever having an "original" idea spring into your mind.

The best way to get answers is to just keep working the problem, recognizing when you are stalled, and directing the search pattern. Many of the popular notions of innovation and creativity are in some ways cop-outs that keep people from being as effective as they could be. The little document I wrote about developing a part of the shadow algorithm for Doom that Nvidia has on their website was a pretty good example of my process. Don't just wait for The Right Thing to strike you - try everything you think might even be in the right direction, so you can collect clues about the nature of the problem.

John Carmack