3D Overview and History
Table of Contents:
What is a 3D game?
History and Background
Doom
Generic 3D engines
Examples

What is a 3D game?
3D games have become a way of life. People now spend hours of time looking down cooridoors, exploring tunnels and viewing intricate extraterrestrial planets. All of this is possible because of recent developments in computer hardware. It is now possible to do these things, but it still requires a lot of effort, on the programming side, to get it looking respectable. In the following articles, I will begin to cover the essence of our 3D engine.

The question still remains, however, what IS a 3D game? This is not an easy question to answer. Most people would say that the hit MYST is a 3D game. Although it is, it is in a different class than we are interested in. We are interested in REALTIME 3D games. These games calculate all of the view data as the program is running. It should be flexible enough that it can be extended and modified in the future, and robust enough to be useful. Games such as Doom, Descent, and Quake are good examples of this genre of 3D games.

History and Background
All of this 3D stuff began back in the 386 era when Wolfenstien 3D came out. It was an outragously popular game for the time, showing people that their lowly PCs can do more than they thought. People were absolutely amazed that PCs could display 3D imagery at interactive frame rates. Even on high powered graphics workstations, you couldn't do that. Well, ID proved everyone wrong.

The idea behind Wolf3d is that all of the walls are spaced evenly on an 8x8 foot grid. In other words, each of the walls had to be aligned to a multiple of 90 degrees, and had to be the same height. These restrictions made it possible to make many assumptions about the engine and make rendering very fast. The floor and ceiling of the enviroment was not texturemapped, but it was added to the engine in games after it, such as Blake Stone.

In order to texture map walls, from each column of the display a ray is shot out. The map is traced along this ray until it strikes a wall. The distance of the wall found from the viewer determines the height of the wall sliver to draw. A sliver of wall (one pixel wide) is scaled from the appropriate texture map and drawn to screen on that column.

Later extenstions to this engine allowed the walls to be variable height (Legends of Valour), have texture mapped floors and ceilings (Blake Stone), have reflections, the ability to change altitude (slightly), etc... But all of the walls were still at 90 degree angles to each other 8' apart. Because of this tremendous limitation, and because they liked to push the envelope, ID Software released Doom.

Doom
Doom took a radically different approach to rendering the 3 dimensional data. It is a true polygonal engine, but it has limitations of it's own. These limitations include the inability to tilt the view, and the inability to have walls that are not vertical. Also, you cannot have maps that have more than one level in the same place. Although these limitiations are certainly much less than Wolf's, they aren't bad. Doom was a break through in technology.

Doom broke the game map into sectors. Sectors can be thought of as the rooms in the level, each sector could have a certain floor height, ceiling height, floor texture and ceiling texture. This allows for stairs and cliffs, where Wolf3d only had one altitude. The breakthrough behind Doom, though, was the way that they drew the 3D perspective.

When you have a game such as Doom, you want to draw as few polygons as possible. If you drew every object in the level, you would end up covering a majority of them up with other objects. To get an interactive frame rate, you must eliminate surfaces from the draw list... in other words, draw only what you can see. To do this, ID Software decided to use a Binary Space Partitioning Tree, or BSP tree.

The advantage of a BSP tree is that you can progressively eliminate or accept half of the surfaces at a time. Think of the number game where you try to guess a number. It goes something like this:

Thinker: I'm thinking of a number between one and one thousand. Try to guess it.
Guessor: 500?
T: Higher
G: 750?
T: Lower
G: 625?
T: Lower
G: 562?
T: Higher
G: 593?
 T: Lower
G: 577?
T: Higher
G: 585?
T: Higher
G: 589?
T: Higher
G: 591?
T: Higher
G: Then it must be 592.
T: You're right!
The point behind all of this is that it is possible to guess a number between 1 and n with log2n guesses. That means that with 1000 possibilities, you can guess it on or before the 10th guess. (With random guessing, it could take a slightly longer time... :)

A BSP tree breaks the "Space" of a level up recursively into chunks. From the partition information, it can quickly eliminate surfaces that are impossible to see. Perhaps later I will cover this in more depth.

The game Quake, also by ID Software uses a very similar scheme, except that it uses a three dimensional BSP tree rather than the 2D tree of doom. This allows complete freedom in level design. The downside is that it has an order of magnitude of more stuff to keep track of. Also, the BSP tree is really only suited for "indoor" scenes. Never in quake do you go ouside and look across long distances...

Generic 3D engines
In this series, we will create a generic 3D graphics engine. This engine is capable of displaying any type of objects, indoor or outdoor. As the series progresses, we will add features and details to objects that we can render. I will try to make the mathematics behind it clear as much as possible. I will not just skip the math, because it is good to see why some things work, and understand the basis behind it.

Example
Since I didn't actually cover any material in this article, I refer you to the following commercial games:

  • Wolfenstien 3D
  • Doom
  • Ultima Underworld
  • Descent
  • Quake

  • Created by Chris Lattner