4

Did they use trigonometric functions to place every pixel on the screen independently?

It seems like you could rotate the camera 90 degrees, and the scene would refresh much faster than all those pixels could have been computed.

12
  • 6
    For a detailed explanation, read "Game Engine Black Book: Wolfenstein 3D" by Fabien Sanglard.
    – DarkDust
    Commented Jun 6 at 12:52
  • 8
    And why do you think "3d graphics couldn't exist"? Wolfenstein wasn't the first 3D game. There even were some during the 8-bit era, but with much simpler graphics, of course.
    – DarkDust
    Commented Jun 6 at 12:54
  • 5
    Battlezone (1980) in the arcade. Mercenary (1985) on the C64. Ultima Underworld (1992). 3D game graphics were nothing new. What Wolf 3D did is use ray casting to do texture-mapped 3D quickly enough for a fast action game,
    – Alan B
    Commented Jun 6 at 13:19
  • 1
    This does strike me more as a CS question. Game engine questions are fair game over at the CS SE.
    – Neil Meyer
    Commented Jun 6 at 15:06
  • 1
    Maybe Wayout and its sequel, Capture the Flag, are the best possible examples of 8-bit precursors to Wolfenstein 3d? They're the progenitors of MIDI Maze and therefore Faceball 2000, so they're free-movement first person games with shooting in a grid-based maze.
    – Tommy
    Commented Jun 6 at 17:04

2 Answers 2

25

Did they use trigonometric functions to place every pixel on the screen independently?

Yes, exactly. And, well, not quite.

As you've said, without any kind of accelerated drawing hardware, a programmer needs to calculate the colour of every pixel on her screen manually. With dedicated 2D or 3D drawing hardware, she can command it to draw shapes and regions without the CPUs attention, as well as faster or more accurately than the CPU alone could.

Let's take a brief surface-level (pun not intended) look at what a computer has to do to render a scene. This is typically called a graphics pipeline or rendering pipeline, as it's like a factory where data comes in, is processed in stages, and produces an image.

enter image description here Image by Vierge Marie enter image description here Image by Martin Wantke.

I include these diagram as an example of how complex the process of rendering is: elements like textures, models and other definitions of objects and surfaces within a scene go into the system, and calculations are applied that 'place' them into the world, draw them at the appropriate scale and colour and arrange them in order of depth in a realistic manner.

Over the 90s, the various stages of the rendering pipeline gradually moved into dedicated graphics hardware. But before dedicated graphics hardware was available, all of these stages would have to be done in software. You may have heard of the term software rendering.

Software rendering is the technique (many would say 'art') of writing computer software that produces output images on (typically commodity) general purpose hardware. In the case of your question, that is rendering the seemingly-3D scene within the main viewport of Wolfenstein 3D using an Intel 80286 CPU. What makes software rendering an 'art' in a sense is that although it's possible to express a rendering algorithm of any complexity on a general purpose CPU, it's not feasible to do so. Rendering every single pixel in turn using realistic simulations of light and surfaces and lenses is called raytracing - it literally considers rays of light in a simulation moving around and splitting between objects, which leads to, ideally, some form of physically based rendering. That would be nice for a game, but not very pleasant on an 8 MHz processor, especially with no hardware floating point unit.

What is needed is simplifications, assumptions, compromises and trickery.

So, no, John Carmack did not write a raytracer to render the scenes in Wolfenstein 3D. The engines for Hovertank 3D, Catacomb 3D, Wolfenstein 3D and Doom use simplified models of the world where anything that isn't necessary to produce acceptable output is not included.

For example, the camera cannot tilt side to side (so everything is vertical), lighting is heavily approximated if present at all, walls are perfectly straight flat lines and perpendicular to the floor, ceilings and floors are horizontal flat and parallel, in Wolfenstein 3D the floor and ceiling are at a constant elevation and symmetrical relative to the horizon, scaled objects and textures are blocky and not smoothly blurred at a distance or close up, semitransparent surfaces may not be present (thereby completely obscuring the scenery behind them).

Rules like these create relationships between parts of the scene so rather than things being independent like you've asked, there are commonalities that can be exploited to reduce the amount of calculations necessary to produce the scene.

Because the camera cannot tilt and scenery is opaque, Wolfenstein 3D's scenery can be drawn in pixel columns, where every part of the maze is guaranteed to be at the same depth away from the camera in that column, at the same top-down 2D map bearing from the player within the player's vision cone. The distance to the nearest opaque column of scenery is calculated once for every horizontal pixel across the screen. Doom provides a 'low detail' mode which uses a VGA unchained mode feature which allows for drawing pairs of adjacent pixels simultaneously, halving the amount of columns that need to be considered. I believe some of Carmack's 2.5D games before Doom exploit the fact that since the floor and ceiling are equally distant from the horizon, the projected size of the scenery for any given column will be symmetrical.

Trigonometric functions are approximated as lookup tables to some degree of granularity and accuracy. For example, a sin(x) table of 256 8-bit values encoding one quadrant of a sine wave could provide accuracy within 0.4 degrees of the input angle and 0.01 of the output value. That's great. You wouldn't want to launch a rocket and hit a 1cm target on the Moon like that, but to place something somewhat consistently within a 320x200 screen, it'll do.

When drawing the walls, you can if you want work out precisely what pixel from the original flat 2D texture should go where for each pixel on the screen independently, going back to the original equations every time. But there are relations between adjacent pixels that mean you can use values you've already worked out at one stage to help you draw the rest of the image. Whenever there is a task that involves you drawing a part of a polygon or strip of pixels (like the vertical pixel columns of the walls), there's usually a way of rewriting the equations so that you work out a starting value with a slow multiplication and then use repeated faster addition to proceed down the strip to draw the rest. The programmer chooses rules that simplify the calculations and allow for these optimisations to happen.

To refer back to your original question specifically then:

'On paper', trigonometric functions are used to place every pixel on the screen independently. However, in reality, trigonometric functions are approximated and used as infrequently and as quickly and accurately as necessary to determine the minimum number of values necessary to reproduce an acceptable representation of the scene.

As mentioned by DarkDust in a comment under your post, you will need to read Game Engine Black Book: Wolfenstein 3D by Fabien Sanglard for a detailed explanation of all the ways Wolfenstein 3D's renderer is good enough as opposed to realistic.


To consider the next part of your question, which is more of a 'why didn't he?' as opposed to a 'how did he?':

It seems like you could rotate the camera 90 degrees, and the scene would refresh much faster than all those pixels could have been computed.

I mean, you could. But Carmack didn't want to, because he wanted to write cutting edge, real-time action games.

Wolfenstein 3D was advertised as "256-color, smooth scrolling virtual reality". Doom was advertised as the "Ultimate 3D Virtual Reality Game". Fixed camera angles were a relic of the 70s, never mind the 80s. People couldn't wait to see what games could become.

enter image description here enter image description here

The simplification you've suggested makes no sense as an acceleration for real-time gaming, especially in the 80s and 90s, because if you were writing a tile-based game with the camera restricted to 90 degree turns, an artist could just draw the graphics in advance for the various walls, ceilings and floors and they'd look much better than what your computer could do using 3D maths.

Games that had fixed camera cell-by-cell rotation and movement had been around since before home computers existed (read CRPG Addict if you want to learn about PLATO university computer RPGs) - they began with simple wireframe tunnels and boxes and lines drawn by the computer, like Wizardry I, and then filled colours, but they were soon supplanted by pretty drawn graphics like Dungeon Master and Eye of the Beholder and Dungeon Hack and so on.

From my personal experience, as an Amiga 500 owner, we had Dungeon Master and Captive and Hired Guns and so on, but we wanted Ultima Underworld and Wolfenstein 3D and Doom. What we got was Corporation (realtime, flat colours), Behind the Iron Gate (realtime, shading) and Operation G2 (tilebased, pre-rendered).

Comparing Operation G2 to Behind the Iron Gate is, very generously to G2, a matter of taste. Comparing Operation G2 to Doom, however? You'd have to have a very strong personal leaning to the tile-based formula to even consider G2.

4
  • GOD that was interesting! Fake perspective from symmetry and increasingly large pixel columns. I never expected that the orthogonality was hiding such clever trickery!! Commented Jun 6 at 17:10
  • The symmetry doesn't give you the fake perspective, but it means that when you calculate 'how above the horizon' the top of a wall is, the bottom of the wall is guaranteed to be the same distance. Anything the engine programmer do to simply the equations used in drawing or reuse calculations from stage to the next helps a great deal.
    – knol
    Commented Jun 6 at 17:27
  • I think the questioner meant that the player could rapidly turn the camera 90 degrees using the mouse/keyboard, and the screen would instantly refresh, a seemingly magical feat. Commented Jun 7 at 22:54
  • Yeah I couldn't visualise how that would work in a real time game at all, that's why I suggested g2 (or perhaps Death Mask) as a comparison. But those games are not like Wolf, so I am confused
    – knol
    Commented Jun 8 at 8:43
5

Wolfenstein 3D used ray tracing/ray casting, but only in one screen dimension (two world dimensions). For each of the 300-or-so screen columns, it cast a ray through the 2D world to find the appropriate wall. Then, it drew the appropriate column of the wall's texture with the appropriate stretch factor to that column of the screen. For each different stretch factor (100 or so), there was pregenerated machine code that loaded the appropriate pixels and stored them in the appropriate positions on the screen, to avoid runtime calculation of the stretching. That approach was (just) fast enough to work on the hardware of the time.

In a comment, Tommy mentioned an interesting optimization I didn't know about:

It also uses a VGA optimisation: if two (or more) neighbouring columns are suitably aligned in memory and close enough in content, an appropriate latch mask allows the CPU to draw only one while having it deposited into video memory twice (or more).

This was possible because the game used a funny planar video mode (Mode Y) which also had the important advantage of supporting page flipping, so the next frame could be rendered offscreen. This mode was very awkward to program because you had to mess with I/O ports to write to different columns of the screen, but fortunately for Wolfenstein 3D it spent the bulk of its time drawing columns anyway.


It's worth mentioning that Ultima Underworld: The Stygian Abyss came out two months before Wolfenstein 3D and had true 6-degrees-of-freedom texture-mapped 3D graphics with dynamic lighting, albeit using a smaller portion of the screen and at a lower frame rate. So modern-ish 3D without Wolfenstein's limitations "could exist" (just) on consumer hardware at that time. There were flat-shaded and wireframe 3D games on consumer hardware far earlier, at least back to subLOGIC Flight Simulator for the Apple II in 1979.

4
  • 2
    It also uses a VGA optimisation: if two (or more) neighbouring columns are suitably aligned in memory and close enough in content, an appropriate latch mask allows the CPU to draw only one while having it deposited into video memory twice (or more).
    – Tommy
    Commented Jun 6 at 17:08
  • 1
    Something not obvious : the fact it use ray casting is not because of performance reasons. According to Carmack, it's because it made code simple and very robust. Glitches can be seen in Catacomb 3D while looking at walls at sharp angles (Carmack knew this). Ray casting can be expensive : for every column of the screen you need to walk across the 2D grid defining the level. This might results in thousands of iterations when you are inside large rooms. This cause performance issues with SNES port (which has a weak CPU). Another approach (BSP based) has to be used with that version.
    – tigrou
    Commented Jun 6 at 20:10
  • @tigrou: Any idea how Cat3d manage to do texture-mapped pixel plotting at a reasonable speed on an EGA card, which so far as I know only supported bit-plane-based graphics?
    – supercat
    Commented Jun 6 at 21:51
  • @supercat why not open a question? :)
    – knol
    Commented Jun 6 at 22:25

Not the answer you're looking for? Browse other questions tagged .