(NOTE: /master may be slightly broken for the moment but in fact by changing the renderer via onscreen dropdown, you can view the running algorithm. Not all sliders work in all modes of the renderer. This should be fixed in the remaining weeks of 2023.)
My sincere regards to Sebastian Macke for reverse-engineering and releasing the original repository showcasing this old, but incredibly efficient technology developed by (as I understand from now-expired patent documents) Kyle G. Freeman, formerly of NovaLogic.
Raycasters in general were not just the work of one person, but of several great minds of the era (late 1980's-1990s), including most notably John Carmack and Ken Silverman; in developing this codebase further, my attention is not specifically limited to NovaLogic, but draws from all sources. While we nowadays have the ability to do hardware-native raytracing (per pixel / fragment) via GPUs like Nvidia's RTX, this does not change the fact that such older tech can be made to run exceedingly fast on newer hardware and may still find uses.
One benefit of such technology is the ability to render extensive heightmap terrains without need for (dynamic) mesh construction and upload to the GPU as seen in modern, triangle-based voxel games (e.g. Minecraft), each time the terrain mesh changes (which can happen often). This speeds up dev times for indie developers and small studios who only want to get a feel for a dynamic 3D terrain using exactly the same data structure as is typically used for game / simulation / physics logic -- the heightmap from which terrain meshes are usually derived.
-
Push performance limits using modern hardware. Parallelize by using multiple worker threads or by running WebGPU either on the main thread or in a decicated worker thread, computing the results into a buffer, and rendering that to a fullscreen quad. Vectorise arithmetic ops e.g. in shaders.
-
Explore possibility of adapting this renderer to solve the problems which Ken Silverman's phenonmenal Voxlap Engine solved: Using an ostensibly 2D, RLE column marching raycaster to achieve 3D perspective without perspective distortion when looking up and down, while supporting terrain overhangs (caves, tunnels).
-
Include a toggleable minimap showing the 2D rays being marched along the heightmap terrain, their lengths, spread angle, and sample points. This assists understanding for both beginners and those actively working on their own raycasters (as info used for debugging).
These images show how non-linear sampling allows for fine-grained voxel / cubic detail near the camera, while heightmap sampling is less intense and thus more performant further away. As can also be seen, besides existing optimisations of the software renderer (even without running on the GPU), I have also taken the time to make the original raycaster much more full-featured, including allowing for runtime adjustment via sliders of a conceptual near viewing plane, adjusting the far viewing plane's distance, heightmap height scaling, and more. Instead, the basic heightmap (with or without color data) from which meshes are usually derived, and which is anyway needed for game / simulation logic can be uploaded directly and used by the renderer.
Let us go back to the year 1992. The CPUs were 1000 times slower than today and the acceleration via a GPU was unknown or unaffordable. 3D games were calculated exclusively on the CPU and the rendering engine rendered filled polygons with a single color.
Game Gunship 2000 published by MicroProse in 1991
It was during that year NovaLogic published the game Comanche.
Game Comanche published by NovaLogic in 1992
The graphics were breathtaking for the time being and in my opinion 3 years ahead of its time. You see many more details such as textures on mountains and valleys, and for the first time a neat shading and even shadows. Sure, it's pixelated, but all games in those years were pixelated.
Comanche uses a technique called Voxel Space, which is based on the same ideas like ray casting. Hence the Voxel Space engine is a 2.5D engine, it doesn't have all the levels of freedom that a regular 3D engine offers.
The easiest way to represent a terrain is through a height map and color map. For the game Comanche a 1024 * 1024 one byte height map and a 1024 * 1024 one byte color map is used which you can download on this site. These maps are periodic:
Such maps limit the terrain to "one height per position on the map" - Complex geometries such as buildings or trees are not possible to represent. However, a great advantage of the colormap is, that it already contains the shading and shadows. The Voxel Space engine just takes the color and doesn't have to compute illumination during the render process.
For a 3D engine the rendering algorithm is amazingly simple. The Voxel Space engine rasters the height and color map and draws vertical lines. The following figure demonstrate this technique.
- Clear Screen.
- To guarantee occlusion start from the back and render to the front. This is called painter algorithm.
- Determine the line on the map, which corresponds to the same optical distance from the observer. Consider the field of view and the perspective projection (Objects are smaller farther away)
- Raster the line so that it matches the number of columns of the screen.
- Retrieve the height and color from the 2D maps corresponding of the segment of the line.
- Perform the perspective projection for the height coordinate.
- Draw a vertical line with the corresponding color with the height retrieved from the perspective projection.
The core algorithm contains in its simplest form only a few lines of code (python syntax):
def Render(p, height, horizon, scale_height, distance, screen_width, screen_height):
# Draw from back to the front (high z coordinate to low z coordinate)
for z in range(distance, 1, -1):
# Find line on map. This calculation corresponds to a field of view of 90°
pleft = Point(-z + p.x, -z + p.y)
pright = Point( z + p.x, -z + p.y)
# segment the line
dx = (pright.x - pleft.x) / screen_width
# Raster line and draw a vertical line for each segment
for i in range(0, screen_width):
height_on_screen = (height - heightmap[pleft.x, pleft.y]) / z * scale_height. + horizon
DrawVerticalLine(i, height_on_screen, screen_height, colormap[pleft.x, pleft.y])
pleft.x += dx
# Call the render function with the camera parameters:
# position, height, horizon line position,
# scaling factor for the height, the largest distance,
# screen width and the screen height parameter
Render( Point(0, 0), 50, 120, 120, 300, 800, 600 )With the algorithm above we can only view to the north. A different angle needs a few more lines of code to rotate the coordinates.
def Render(p, phi, height, horizon, scale_height, distance, screen_width, screen_height):
# precalculate viewing angle parameters
var sinphi = math.sin(phi);
var cosphi = math.cos(phi);
# Draw from back to the front (high z coordinate to low z coordinate)
for z in range(distance, 1, -1):
# Find line on map. This calculation corresponds to a field of view of 90°
pleft = Point(
(-cosphi*z - sinphi*z) + p.x,
( sinphi*z - cosphi*z) + p.y)
pright = Point(
( cosphi*z - sinphi*z) + p.x,
(-sinphi*z - cosphi*z) + p.y)
# segment the line
dx = (pright.x - pleft.x) / screen_width
dy = (pright.y - pleft.y) / screen_width
# Raster line and draw a vertical line for each segment
for i in range(0, screen_width):
height_on_screen = (height - heightmap[pleft.x, pleft.y]) / z * scale_height. + horizon
DrawVerticalLine(i, height_on_screen, screen_height, colormap[pleft.x, pleft.y])
pleft.x += dx
pleft.y += dy
# Call the render function with the camera parameters:
# position, viewing angle, height, horizon line position,
# scaling factor for the height, the largest distance,
# screen width and the screen height parameter
Render( Point(0, 0), 0, 50, 120, 120, 300, 800, 600 )There are of course a lot of tricks to achieve higher performance.
- Instead of drawing from back to the front we can draw from front to back. The advantage is, the we don't have to draw lines to the bottom of the screen every time because of occlusion. However, to guarantee occlusion we need an additional y-buffer. For every column, the highest y position is stored. Because we are drawing from the front to back, the visible part of the next line can only be larger then the highest line previously drawn.
- Level of Detail. Render more details in front but less details far away.
def Render(p, phi, height, horizon, scale_height, distance, screen_width, screen_height):
# precalculate viewing angle parameters
var sinphi = math.sin(phi);
var cosphi = math.cos(phi);
# initialize visibility array. Y position for each column on screen
ybuffer = np.zeros(screen_width)
for i in range(0, screen_width):
ybuffer[i] = screen_height
# Draw from front to the back (low z coordinate to high z coordinate)
dz = 1.
z = 1.
while z < distance
# Find line on map. This calculation corresponds to a field of view of 90°
pleft = Point(
(-cosphi*z - sinphi*z) + p.x,
( sinphi*z - cosphi*z) + p.y)
pright = Point(
( cosphi*z - sinphi*z) + p.x,
(-sinphi*z - cosphi*z) + p.y)
# segment the line
dx = (pright.x - pleft.x) / screen_width
dy = (pright.y - pleft.y) / screen_width
# Raster line and draw a vertical line for each segment
for i in range(0, screen_width):
height_on_screen = (height - heightmap[pleft.x, pleft.y]) / z * scale_height. + horizon
DrawVerticalLine(i, height_on_screen, ybuffer[i], colormap[pleft.x, pleft.y])
if height_on_screen < ybuffer[i]:
ybuffer[i] = height_on_screen
pleft.x += dx
pleft.y += dy
# Go to next line and increase step size when you are far away
z += dz
dz += 0.2
# Call the render function with the camera parameters:
# position, viewing angle, height, horizon line position,
# scaling factor for the height, the largest distance,
# screen width and the screen height parameter
Render( Point(0, 0), 0, 50, 120, 120, 300, 800, 600 )Web Project demo page
Voxel terrain engine - an introduction
The software part of the repository is under the MIT license. Please read the license file for more information. Please keep in mind, that the Voxel Space technology might be still patented in some countries. The color and height maps are reverse engineered from the game Comanche and are therefore excluded from the license. NOTE As of 2023, the US patent has expired.