How the Renderer Works

The map is divided into zones, which are surrounded by walls. The renderer draws the walls in a zone. The walls that make up a zone must be ordererd so that they appear on screen from left to right. This allows the renderer to start with the wall that is leftmost in the view and proceed until the right side of the view. Once the right side is reached, it is known that no other walls will be visible.

To determine the window that is leftmost in the view, a lookup table is used. This table uses the direction of the left edge of the view as an index. The result of the lookup is an index into the array of walls that make up the zone. Specifically, this is the first wall that can potentially be intersected by a line going in that direction. Depending on the position of the camera, the wall that is actually leftmost in the view may be later in the array, but it is known that no wall earlier in the array can be seen. This way, the renderer can avoid having to do translation, rotation, and perspective mapping for some of the walls in the zone.

The requirement that the walls must appear on screen from left to right restricts the possible shapes that zones can have. Specifically, zones must be convex. This ensures that walls always appear on the same side of one another for any viewing angle where they are in front of the camera.

Although zones are required to be convex, this requirement does not apply to the map as a whole. To allow concave geometry to be rendered, portal rendering is used. Walls can be designated as portals (called "windows" in the code) through which another zone can be seen. This zone is then rendered with the same algorithm, restricting the viewing angles and screen coordinates according to the position of the window.

The optimizations the renderer uses to reduce the amount of computation necessary are:

  1. Only the zone the camera is in and any zones that are visible through windows are rendered. This allows potentially large parts of the map to be ignored.
  2. Walls that are known not to be visible due to camera angle are ignored. This is done by finding the view angle in a lookup table.
  3. Walls are ordered so that once the right side of the view is reached, no other walls need to be considered.

The above optimizations happen before the coordinates of a wall are considered. This means it is not necessary to do any translation, rotation, or perspective mapping on those coordinates. Generally, these optimizations will eliminate all or almost all walls that end up not being visible.