Projecting 3D
Joel "Bisqwit" Yliluoma created an excellent video "Creating a Doom-style 3D engine in C". The video actually focuses on portal rendering, the method used by Marathon and Duke Nukem 3D, rather than the visibility-tree technique that Doom uses.
From 1:22 to 5:16 Bisqwit goes through the steps required for projecting the 2D vertices of the lines to the screen, which is exactly what Doom does;
- Translate the vertex from world-space to player-space (make it so the world literally revolves around the player)
- Clip the vertex pair (line) to the player's view-plane (pretty much the 2D line perpendicular to the player's view direction)
- Calculate the angles between the player's location and the vertex pair
- Use these angles against a lookup table to figure out where they will appear in screen-space (X co-ordinate on the view-plane)
- Using the Z depth of the vertex pair in screen-space, interpolate the height of the wall from the first vertex on screen to the second vertex on screen *
* This part sounds like the complicated part.
Two pieces of information are known which can be used to calculate the height of the wall on the screen;
- Projected X location on screen of the two vertices (and clipped against the side of the screen)
- Distance away from the view-plane (distance from the player)
Far-away objects tend to be smaller, so by using the distance from the player we can figure out a good height to draw the wall at the screen-X co-ordinate of the two vertices, so to fill out the wall between these two lines we just need to interpolate the height of the wall between them.
Point both your index-fingers upward infront of your face, move one hand away from you, then imagine filling the gap between your fingers with a solid colour or a pretty picture. That's what Doom does.
Here is a shot of E1M1 drawing only the outlines of the walls.
The vertical lines are the projected vertices of the walls, clipped to the screen. The upper and lower bounds of the interpolation between these lines are connected as well, forming the outline of the visible wall.
Because Doom does a lot of work figuring out the clipping to zero-overdraw with the solid walls and floors, the outline actually follows the clipping result against the surrounding walls, so when wall A is partly infront of wall B, you'll notice that the outline of wall B follows the outline of wall A.
This is what the shot looks like with the walls filled, rather than outlined.
If you're thinking "that looks 3D to me" then the engine has done its job with rendering a 3D world for you to play in.
Dimensions
How is the actual projection performed? A look-up table! An incredible cheat that is precalculated with real maths with void R_InitTextureMapping( void ); in the r_main.c file.
The look-up table is defined as int viewangletox[4096]; and with this the angle between the player and any other point can be converted to an X cordinate on the screen. Projection is achieved by figuring out the angle between the target and the player and simply looking up where that goes on the screen.
All the traditional mathematics involved with 3D projection has been pre-calculated at load-time to be used later on. This only works because everything is projected from 2D space into 1D space, which sits nicely in a single-dimension table.
Wait, does this mean Doom is not a 3D or a 2D game, but a 1D game? It's definitely arguable.
Clipping
Projecting the wall vertices into a 1D vector on the screen (X co-ord) makes clipping very easy as all you need to do is make sure that the two X values of walls that are further away do not overlap with any X value pair of existing walls that have already been projected.
This is pretty much how the internals of Doom sees the solid walls in a section of E1M1;
And this is what the same view looks like rendered out for the player;
The BSP tree is used for sorting the order that the walls take when filling in the clipping information. Read about the Binary Space Partitioning and this step here.
What we're left with after all this is a picture that looks very much like 3D graphics, built from a 2D world projected onto a 1D line.
Looking Up and Down
You can't look up or down in the standard Doom client. You also don't need to as the game will auto-aim in the vertical axis.
The height of the walls are drawn based on the distance from the player (and some meta data about the height of the ceiling and the vertical location of the player), so the walls will always be drawn with straight lines. There is no information at all for the pitch of the player (pitch is the look up/down angle).
The main factor here is the fact that Doom is only aware of the walls along a single dimension (see that block of colours above), it has no concept at all of an "up" direction, so even if we could look up/down how would the clipping of the walls to the screen be maintained?
It simply cannot be done. However, with some trickery it could be faked.
Marathon featured the ability to look up/down (sort of), as did Duke Nukem 3D (sort of) and Dark Forces (sort of), however in these games you will notice a freaky warp effect occuring with the walls.
If you look closely, you'll see that the walls always stay perfectly vertical, they don't warp as they should. You may notice that the image doesn't change at all, it's being shifted up/down. This technique is called "Y-shearing", literally because it's a shear operation (a movement) in the Y direction.
This is what looking up/down in Duke Nukem 3D: Megaton Edition looks like with the fully-3D renderer;
We can attempt to see Y-shearing by shrinking the viewport in Doom and moving it up/down in an image editor.
These images should hopefully look like the player is looking up, forward and down.
Fantastically, Duke Nukem 3D also attempts to fake a "roll" rotation (Z-axis turn) - which you can see in-game when your player is killed and the camera's view port is on the floor. This is achived with a simple screen-space displacement (pre-calculated, basically it's post-processing!).
Conclusions?
I'm not sure there is a good conclusion at the end of all this. It's down to your personal feelings if you believe Doom is 3D or 2D, it makes no difference to the game or the game industry. Doom's technology is obsolete these days and now that we have hardware 3D acceleration in every device there's little reason to implement a renderer like Doom's. Doom's developers set out to do 3D graphics as cheap as possible and I think they achieved that, just because it doesn't follow what the crowd does these days does not mean it is not "true 3D" - afterall you can argue that every game is 2D once it hits the display device.
Additional Reading
I highly recommend reading Fabien Sanglard's Doom Engine source code review.
Chocolate Doom is an excellent source-port of Doom for SDL1 software rendering. I recommend it to anyone who wants to hack at Doom's renderer themselves.
There's a (rather complicated) ray-casting tutorial written way back in 1996 that explains Y-shearing with illustrations; permadi.com/tutorial/raycast.
"Creating a Doom-style 3D engine in C" by Joel "Bisqwit" Yliluoma, whilst based on Duke Nukem 3D, this video has a lot of content that is also relevent to Doom.