History
Let us go back to the year 1992. CPUs were 1000 times slower than today and acceleration through GPUs was unknown or unattainable. 3D games were calculated exclusively on the CPU and the rendering engine filled polygons with a single color.
The game Gunship 2000 was published by MicroProse in 1991.
It was during that year that Novalogic published the Comanche game.
The game Comanche, published by Novalogic in 1992
At the moment the graphics were breathtaking and in my opinion 3 years ahead of their time. You see many more details such as textures on mountains and valleys, and for the first time a clean shading and even shadows. Sure, it’s pixelated, but all games from those years were pixelated.
render algorithm
Comanche uses a technique called voxel space, which is based on similar ideas as ray casting. So the Voxel Space Engine is a 2.5D engine, it doesn’t have all the degrees of freedom that a regular 3D engine provides.
height map and color map
The easiest way to represent a terrain is through height maps and color maps. For the game Comanche a 1024*1024 one byte height map and 1024*1024 one byte color map are used which you can download on this site. These maps are periodic:
Such maps limit terrain to “one elevation per location on the map” – it is not possible to represent complex geometry such as buildings or trees. However, one big advantage of a colormap is that it already has shading and shadows built into it. The voxel space engine only captures colors and does not have to calculate lighting during the render process.
basic algorithm
The rendering algorithm for a 3D engine is surprisingly simple. The voxel space engine graphs the height and color map and draws vertical lines. The following figure demonstrates this technique.
- Clear the screen.
- Start from the back and present to the front to guarantee interception. This is called Painter algorithm.
- Determine the line on the map that corresponds to the equal optical distance from the observer. Consider field of view and perspective projection (objects are smaller from far away)
- Rasterize the line so that it matches the number of columns on the screen.
- Get elevation and color from 2D maps corresponding to line segments.
- Perform perspective projection to height coordinates.
- Draw a vertical line with the color corresponding to the height obtained from the perspective projection.
The core algorithm in its simplest form consists of 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 )
add rotation
With the above algorithm we can only look north. Rotating the coordinates to a different angle requires a few more lines of code.
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 )
more performance
Of course there are a lot of tricks to achieve high performance.
- Instead of drawing from back to front, we can draw from front to back. The advantage is that we don’t have to draw lines at the bottom of the screen every time there is an interruption. However, we need an additional y-buffer to guarantee interception. For each column, the highest y position is stored. Because we are drawing from front to back, the visible portion of the next line can only be larger than the tallest line drawn earlier.
- Level of detail. Present more detail up front but less detail at the far end.
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 )
Link
web project demo page
Voxel Terrain Engine – An Introduction
personal website
MAPS
color, height
color, height
color, height
color, height
color, height
color, height
color, height
color, height
color, height
color, height
color, height
color, height
color, height
color, height
color, height
color, height
color, height
color, height
color, height
color, height
color, height
color, height
color, height
color, height
color, height
color, height
color, height
color, height
color, height
color, height
license
The software portion of the repository is under the MIT License. Please read the license file for more details. Please be aware that voxel space technology may still be patented in some countries. The color and height maps are reverse engineered from the game Comanche and are therefore excluded from the license.
<a href