Linear Fog

     1 |              --------------
 fog   |             /
 amt   |            /
     0 | __________/
       ---------------------------
       0          s   e
                distance

    function Unlerp(v, v1, v2) = (v - v1) / (v2 - v1)
    function Clamp(v, v1, v2)  = min(max(v, v1), v2)
    fog_amt = Clamp(Unlerp(distance, start, end), 0, 1)

Linear fog is zero until the start distance and then linearly rises to 1 at the end distance. All distances beyond the end are 100% fog. Linear fog does not look as nice as other fog models, but the explicit end distance provides another benefit.

The engine casts a single ray for each screen column. In a Wolfenstein 3D style world, all of the walls are the same maximum height and they occlude all walls behind them. As a result, you can stop casting as soon as you hit a single wall and render it. However, when rendering with variable floor and ceiling heights, each collision with a block may occlude some of the bottom and top of the column, but not all, so you cannot stop casting at the first wall.

At each tile edge, if the floor height changes, the old and new floor heights are perspective projected onto the column. Then either a floor then wall, or just a floor (if the new height is lower) are drawn upwards from the top of the last floor/wall segment drawn. The same thing happens for the ceiling heights, drawing from the top down. Rendering is not done until the last rendered bottom pixel (rendering floors) meets the last rendered top pixel (rendering ceilings) and all of the column's pixels are written. This, however, can take a while and will cause your rays to cast out to a very far distance just to render a small number of floor and ceiling pixels in the center.

The linear distance fog allows you to end the ray cast early. Once the ray length is beyond the end distance for the fog, the remaining pixels in the column can all be written as the fog color. When rendering a large level, this can provide a huge speedup. However, if the end distance for the fog is short and the color of the fog is a strong color, this creates an obvious "fog wall" beyond which nothing is rendered.

To make nice, "realistic" fog, like what you would use for atmosphere, the exponential fog equation is better.

Exponential Fog

Exponential fog rises quickly but slows as it approaches full fog, never quite reaching it.

    fog_amt = Clamp(1 - exp(-(distance * density)), 0, 1)

The density parameter replaces the start and end distances. A higher density makes the fog greater and closer. This looks much more like actual fog, but it no longer has an explicit end distance. Still, past a certain point, nothing is visible.

In the engine, both of these fog effects are used at the same time. The exponential fog is used for effect, but at a far distance (where the expontential fog is already thick) linear fog is applied too, allowing the rays cast for each column to end early.

Perspective Projection

When doing rasterization (ie, rendering the normal, familiar way), you have a camera and some objects somewhere in world coordinate space. The coordinates of all of vertices of the objects are transformed from world space into camera space: a coordinate system with the camera at the center ( 0, 0 ) and with two of the axes (typically, X and Y) aligned with the axes of the 2D projection plane. In this space, (typically) Z is perpendicular to the projection plane, parallel to the direction vector of the camera. Once transformed into camera space, the X and Y coordinates of a perspective projection onto the projection plane are simply:

proj_x = vertex_camera_space_x / vertex_camera_space_z;
proj_y = vertex_camera_space_y / vertex_camera_space_z;

This same transform from world space to camera space to the projection plane occurs in ray casting, but is never made clear by tutorials. Because each ray is cast per screen column, we already know the X coordinate for a column:

proj_x = 2 * column_number / screen_width - 1

The Y coordinate of the point still needs to be found. From the ray cast, we know the distance ( full_distance below) between the player and the point in question. This full_distance needs to be transformed into a distance perpendicular to the projection plane in order to use the perspective transform above. This can be done by multiplying the full distance by the cosine of the angle between the ray and direction vectors (you can see this by drawing a right triangle using the ray, the direction vector, and the point). This gives you the following:

// Dot product is an easy way to get cosine iff both are unit vectors:
ray_cos = Dot(ray, direction) 

perpendicular_distance = full_distance * ray_cos
camera_space_z = point_z - camera_z
proj_y = camera_space_z / perpendicular_distance;

Note that the projection plane Y is computed from the camera space Z. X and Y are the top down coordinates corresponding to the 2D tile map and Z is height. Now that we have coordinates for a point on the projection plane, we can convert them to pixel coordinates on the screen buffer. Remember, our 90 degree field of view gives a [-1, 1] to [0, 640] mapping, so 1 projection plane unit is 320 pixels. Thus:

pixels_per_proj_plane_unit = screen_width / 2   
screen_x = screen_width / 2  - pixels_per_proj_plane_unit * proj_x
// screen_x here is superfluous, since it should be equal to
// column_number, which is already known
screen_y = screen_height / 2 - pixels_per_proj_plane_unit * proj_y

Just getting the height of a wall (like in the lodev code that started this section) is:

screen_line_height = pixels_per_proj_plane_unit * 
                     wall_height / perpendicular_distance

Different FOV

But what if we have a 60 degree field of view?

For a 60 field of view, the rays are cast from -(2/3)N to (2/3)N . So [-0.66, 0.66] on the projection plane maps to [0, 640] on the screen. This means we have:

pixels_per_proj_plane_unit = (screen_width / 2) / 0.66

In general, for any field of view, we can get this value:

fov_ratio = field_of_view / 90.0
pixels_per_proj_plane_unit = (screen_width / 2) / fov_ratio

Putting this all together

This gives us the following alternative to the lodev tutorial's formula for getting wall heights.

fov_ratio = field_of_view / 90.0
pixels_per_proj_plane_unit = (screen_width / 2) / fov_ratio
screen_line_height = pixels_per_proj_plane_unit * wall_height / perpendicular_distance

This shows the unexplained assumptions that are present in the lodev tutorial code:

• It assumes that the walls have a height of 1.0.
• It assumes that the field of view is 90 degrees with a 2:1 aspect ratio
• OR It assumes that the field of view is 60 degrees with a 4:3 aspect ratio (see below).

// The lodev tutorial uses a 60 degree field of view and a 640x480 screen
// Lets compute the pixels per projection plane unit:
pixels_per_proj_plane_unit == (640 / 2) / 0.66 == 484.84... ~= 480
// HUH, the result is almost exactly the screen_height, making the formula
// in the tutorial approximately correct.

In general, the tutorial uses default values of 1.0 in many places to simplify the code, but this comes at a cost of not fully explaining how or why things work. The screen size and its relationship to the projection is another one unexplained.