How not and how to do a raycast renderer for modern resolutions

What is a Raycast Renderer?

In the 1990's "id Software" produced the game changing (pun intended) video game "Wolfenstein 3D" (see here). This game is considered the parent of all FPS games in existence today. It faked 3D using a rendering technique that became popular during the 90's before the birth of true 3D games. The extension of this technique with BSP allowed id to produce a game which feigned verticality and led to them producing one of the most popular games of all time: Doom. 

The original techniques used to produce Wolfenstein 3D have since become arcane knowledge, mostly unused since the same effect can be produced in a modern 3D engine (such as Unity) with a camera at a fixed height and perfectly vertical walls. However, that doesn't mean there aren't people using this raycast rendering technique in their own tools to produce games. In fact there are multiple guides available to assist someone who still wants to do this the "traditional" way: 

• Raycasting (lodev.org) 
• Ray Casting / Game Development Tutorial - Page 1
• https://web.archive.org/web/20220806025729/https://orbb.neocities.org/tutorials/... 

The Traditional Method

The traditional method of implementing this renderer (as outlined in the links above) is to: 

1. Take a tile map and position a camera at some grid location within it
2. Bound the tile map with walls with some texture
3. Cast a series of rays from the camera location out towards the direction the camera faces
4. When a wall is encountered calculate a height for the wall, and draw the wall to the screen, applying the correct texture

This is an extreme over-simplification of the sequence of events that goes into this technique, but it gives a rough idea of the steps involved. However, what it hides is the crux of the performance problems with this technique on modern hardware, that we must iterate over every pixel on the screen and set the colour of every pixel. And we must do this on the CPU at runtime, for every frame. This is perfectly reasonable when  drawing only a small resolution of say 640x480, but when drawing to modern screen sizes (such as 1920x1080) this technique breaks down.

As a team we lost a lot of hours trying to counter this problem through various  means, we tried some of the following techniques to improve rendering performance whilst CPU rendering: 

• Rendering the ceiling and the floor across two threads.
• Rendering the ceiling & the floor whilst the walls are being rendered to a separate image.
• Rendering each column of a sprite that will be displayed on screen across threads.
• Discarding updating pixels via calculations which were 100% fogged, and instead setting them to the fog colour.

The combination of these techniques improved our rendering performance on the CPU drastically, however we were still seeing average draw times spike the closer the player was to a wall, or the more sprites were needing to be drawn. We could hit a 6ms average time to paint ceiling/floor/walls/sprites, but because these tasks were all threaded their individual execution times were still unreasonable. On slower hardware we could see performance dips of an average update time of 33ms. Far exceeding our target of 16ms (60 FPS).

Shaders, shaders, shaders

I imagine now that any reader with a certain degree of knowledge about computer graphics programming is likely rolling their eyes at the section above questioning why didn't we just swap to using shaders. For those who aren't well versed in the land of computer graphics programming, shaders are computer programs that run on the GPU during rendering and leverage the GPUs natural advantage over the CPU: extreme parallelism. With shaders you can perform certain computations significantly faster, computations whose access to data is independent and don't rely on waiting for a result from another thread. This is why the GPU is so unbelievably fast for rendering 3D geometry and shading it. But there's a reason we didn't begin with a shader based approach:

The team as a whole is not knowledgeable in shaders. One member of the team is, but the team as a whole is not. This shifts the burden of maintenance onto one singular person, and reduces the capacity for interested team members to tinker with the logic for rendering. Though we gain significant rendering time savings (from highs of 33ms to highs of 4ms at 1080p), we lose out on shared maintainability of the code. But, we eventually decided to eat this cost as the savings from shaders were substantial. 

In a future post we'll share some snippets of code from our optimised CPU rendering approach, showcasing the advantages vs disadvantages of it. We'll also share some of our shader code, and dive deeper into how we managed to use this raycast renderer approach with GLSL.