Voxel Space

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. 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. 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.