Previous: Realtime Raytracing - Page 3 of 3 - Home

Voxels, Voxels, Voxels!

The word "voxel" is actually a horrible train wreck compacting the words "volumetric" and "pixel" into 2 mashed syllables.  A volumetric pixel is exactly what you'd expect ... whereas a pixel defines a square of color on a 2D screen, a voxel defines a cube of color in 3D space.

Real legitimate voxel images are usually used in medical imaging.  Instead of having a 2D picture made of pixels, you have a 3D picture made of voxels generated from several MRI or CT scan cross-sections.

Until recently your average desktop computer was far too slow to render these types of medical images (mostly because they require insane amounts of memory and tons of "faking" to interpolate the image in 3D).

However, in the early 90's programmers started figuring out that there was one case wherein a typical desktop computer could easily handle voxel rendering: a heightmap landscape.  Instead of storing a 3D array with colors in it, you store 2 2D arrays, one with heights and the other with colors.  You then use the pixel coordinates as your X and Z position and the height on the map as your Y coordinate.  And by locking the camera to the X-Z plane, you ensure that any variations in Y go straight up-and-down on the screen.

So here's the quick and dirty guide to generating a voxel landscape.  Step #1: generate a heightmap:

The preferred way is to use Perlin noise.  It's a pseudo-random function - meaning that while it looks random the results are reproducable as long as you have the same seed and offset parameters.

Step #2: place your camera at point p

Step #3: define your view frustum with 2 vectors v1 and v2:

Step #4: go across every pixel between the 2 view vectors

Sample along those view vectors as p + v*t incrementing t by a set amount each time.  At p+v*t, you already know the X and Z positions, so you sample the Y position from the heightmap, giving you a point in 3D space.  You then project that point onto the screen.  And, since the camera is locked and the Y axis is is straight-up-and-down, you can actually draw the point as a vertical line going up from the bottom of the screen to that point.

So Why Is This Any Faster Than Just Raytracing?

Well, you can see that there are certain place where this can be sped up.  Instead of figuring out v from scratch for every pixel, we simply increment our way from v1 to v2 as we go across the screen.  Instead of a tracing a ray for each pixel, we simply increment v along the ground and draw the heights onto the screen.  Since we're drawing from the front to the back, we know that nothing we draw will go over anything else we've already drawn.

So here, in general, is how you do it:

GIVEN:
v1, v2, p (as listed above)
hfov (horizontal field of view - the angle between the center of the screen and the edge of the screen)
hmap (height map)
colmap (color map)
buff (buffer onto which we're drawing)

SETUP:
vinc = (v2-v1)/SCREEN_WIDTH;
zoom = (SCREEN_WIDTH/2)*cos(hfov)/sin(hfov);
zvalinc = sin(hfov);
v = v1;

for (x=0;x<SCREEN_WIDTH;x++) {
  bottom_y = SCREEN_HEIGHT;
  v += vinc;
  pos = p;
  zval = 0;
  // sample 100 points, unless we hit the top of the screen
  for (i=0;(i<100) && (bottom_y>0);i++) {
    zval += zvalinc;            // z value, for projection
    pos += v;               // step along the view vector
    height = hmap[pos.x,pos.y];            // get the height
    col = colmap[pos.x,pos.y];              // get the color
    top_y = (SCREEN_HEIGHT/2) - (height-p.y)*zoom/zval;            // find the "y" position on the screen
    if (top_y<0) top_y = 0;                  // if it's above the top, then only go to the top
    for (y=(bottom_y-1); y<=top_y;--y) {
      buff[x,y] = col;                 // fill in with this color from the last pixel drawn to the current one
    }
    if (top_y<bottom_y) bottom_y = top_y;             // keep track of what pixel was last drawn to
  }
}

In practice, we're sampling SCREEN_WIDTH*100 points, and almost all of our internal operations are increment operations.  This allows for some very fast execution.

But Where Do The Artifacts Come From?

Remember, we calculate the direction for each column of the screen, but we're incrementing along that direction.  We aren't getting the exact value like you would with a raytracer, we're sampling.  The artifacts you see in a voxel engine are results of that resampling.  It's like when you resize an image, ... if you use nearest neighbor sampling, things will look jagged and strange, but it's very quick.  Voxel landscapes look the way they do because you're essentially doing just that, but in 3D.

Comanche series by Novalogic

Comanche and its sequels were a series of helicopter flight simulators on the PC that made use of voxel rendering.  The first one looked pretty standard:

But as you can see their engine got quite advanced by Comanche 3 in 1997 (before 3D accelerators had really caught on widely)

Given the limited abilities of PCs in the mid 90's, voxels were an excellent way to generate that sort of sprawling, differentiated, but still very generic terrain you need for a flight simulator.

Amok for Saturn and PC

Amok was a game created by a small demoscene group (Zyrinx) with a technical prowess that few other developers could demonstrate at the time.  Being sceners, of course, they recognized the potential of rendering with voxels and put them to work on Sega's 32-bit behemoth.

Zyrinx (as a team in the development house Scavenger which went bankrupt as GT Interactive screwed them with their pants on) had the insight to do with the Saturn what so many developers probably should have done from the start: put the powerful dual CPUs to work instead of merely relying on the underpowered 3D hardware.

In all seriousness without voxels, this sort of environment wasn't really possible on the Saturn.

Outcast by Appeal

Appeal was another one of those absolutely incredible coding groups that got shoved out of games far before their prime.  Their magnum opus Outcast was made in 1999 and even though 3D cards had caught on by then, they still managed to push beyond what 3D cards could do thanks to a decent software polygon engine melded with a tile-based voxel terrain engine.

This kind of detailed terrain just wasn't possible in real time with a 3D accelerator at the time.  Keep in mind that it goes on for miles, and yet the voxels are detailed enough to actually model the cobblestones on the path as raised bumps.

The custom-made polygon couldn't handle many polygons, but it did manage to do some very special things.  The characters are all bump-mapped and anti-aliased.  They blend seamlessly into the voxel landscape and even cast shadows on it.

(As an aside, Outcast is an amazing game and was in many ways ahead of its time.  A few fans have taken up the flag and are attempting to do a remake as a Crysis mod.  There's a chance they may pull it off too, since neither Appeal nor GT Interactive exist anymore to sue them.)

Hey, You Promised "Something Special"

And so I did.  It had been a few years (like maybe 5) since I'd last thought about voxels in any real way.  They're largely irrelevant now thanks to the insane speeds we get off of 3D accelerators.  But they're still somewhat relevant on platforms where speed is a major issue.  Like, say, portable platforms.

So I set out to make a voxel engine running on the DS.  It's not anything terribly impressive, and I've basically spent all my time wrestling with my unfamiliarity with the platform, but it's up-and-running at about 5 fps so I'm somewhat proud.

It generates a map using perlin noise, then does some special shading to get both the sun and the sky-blue glow.  It's super slow but it means almost no memory footprint.

(Don't be fooled, it doesn't actually run at 86fps.)  The engine demonstrates how to generate and draw voxels, and even has one nice special effect (fog, which we all hate since the N64, but it's important for giving a decent depth cue in a voxel scene).  And what's best is that you can download the source and NDS file here: http://mpierce.pie2k.com/voxel.zip  It runs in iDeaS and No$GBA, but not in Dualis and I don't have the equipment necessary to run it on hardware.  If anybody does get this running on hardware I would love it if you dropped me a line.