flipcode - Voxel Polygons

Voxel Polygons
by (19 February 1999)

Introduction

Let me introduce you to something completely different: Voxel graphics. A voxel rendering engine is totally different from a traditional 6DOF polygon engine, because it doesn't render polygons. Instead, it fills the screen with vertical bars that represent the heights that are stored in a so-called voxel map. A voxel map is a huge array, with for each location on the map a color and a height. The voxel renderer maps pixels from this map to the screen. Effectively an area of the total map is projected on the screen as if it where a flat landscape, so for each pixel on the screen a corresponding location on the voxel map is determined. Instead of plotting this pixel right away on the screen, it's height is determined using the height stored in the voxel map and the distance of the pixel, so 'mountains' that are far away look smaller. The map is drawn from 'close' to 'far', so the engine first fills the bottom line of the screen, and then goes up to approximately halfway the screen, wich is the horizon. After each span is drawn, it's height is stored in an array, so that bars that are drawn behind this bar can be clipped against it. That way, overdraw is completely prevented. The screen space above the horizon can then be filled with a nice backdrop, wich makes the picture complete.

The Good & The Bad

That's the basic algorithm. Good thing about voxel engines is that their speed is virtually constant: No matter how much detail there is in the scene, it is drawn at (almost) the same speed. [Worst case is in fact a completely flat floor, because in that case, every column of the screen becomes one heigher every time a new line of the screen is processed. For the single pixel that is drawn in that case, there is quite a lot of work to be done: The single pixel is compared to the current column height, clipped against it, the pixel is drawn and the column height is updated. Probably more expensive than just drawing a single perspective correct texture map.]

Another good thing about voxel engines is that you do not need al the usual nasty 3D operations like 6DOF rotation matrix calculation (voxel landscapes can only be rotated around the y-axis), clipping and so on.

But there are bad things about voxels too. Let me summarize a few:

Voxels look blocky on screen, unless you have a huge map so that the closest voxels still cover only a single pixel on screen.
Small details tend to flicker when the camera moves. This gets worse when you try to reduce the blockyness.
Voxel maps are huge. That's why 'Comanche Total Overkill' was the first 386 game that required an awesome 4Mb of memory.
You can only have a single height per voxel.

It is possible however to overcome these problems. Once we have tackled all of them, voxels can be really cool: You can do things with them that are impossible with polygons, even if those polygons are blasted to the screen using an accelerator. Let's have a look at each of the problems I listed above:

The Blocky Voxels

This problem can be overcome by applying 'bilinear filtering' to the voxels that are fetched from the voxel map. Instead of fetching a single voxel, four voxels are retrieved. The height of a single (one-pixel wide) span on screen is then determined by taking a weighted average of the heights of the four texels. For more details on this, see my document about fast bilinear texel filtering. The very same technique can also be applied to the color of the bar. Now even very blocky terrain will look smooth. This is IMO how the famous 'Mars' demo was done.

Flickering Details

This problem is reduced, albeit not completely eliminated by the bilinear filtering. The bilinear filter takes more texels into account, so less texels will be skipped. Besides that, since the voxels can be larger thanks to the bilinear filtering, this will be less of a problem anyway.

The Huge Map Problem

There is a very good solution for this problem, and it's called 'tiling'. If you simply build your voxel worlds using pre-build tiles of voxels, you can reuse them without sacrificing huge amounts of memory. This allows for huge worlds, although the technique is not particularly usefull for huge mountain worlds: The main problem with tiles is that they are square, and square is bad. So, don't use tiles. :) Use polygons instead. Not the usual polygons, but voxel-polygons: If you build your map from polygons that are 'more or less' horizontally oriented, you can do really nice things:

Vary the detail of the voxel set locally: Create hills with just a few voxels, and human-build structures with lots of 'm.
Add the (local) height of the polygon to the voxel height, to reuse certain details on a different height, or on a hillside.

The Single Height Problem

This can also be solved using the voxel polygons. Just make sure that every part of the map is covered by a blanket of polygons, representing the ground, and add extra voxel polygons above this ground for the finishing touches. And, because floating polygons have not only a top side, but also a bottom side, it might be a good idea to store not just a height for each voxel, but also a 'depth'. This introduces an interesting problem: How do we handle floating voxel bars? The usual voxel algorithm assumes that each bar starts at the bottom screen line, so that overdraw can be eliminated by clipping subsequent bars against the height as indicated by the array that I mentioned before. The answer is: An s-buffer. I suggest you read my c-buffer document (on the tutorials section of http://www.flipcode.com) if you don't know what I'm talking about. If we implement a 'vertical c-buffer', all our voxel bar problems are completely solved. So now we can have interesting terrain, where global detail is represented by large polygons, and small details by the voxel texture that is applied to the polygon. Voxels can go up and down, so indoor scenes are also possible. Really small details can be added by adding extra polygons. MIP-mapping can be applied if small details get too small. In short, all the usual 3D engine tricks can be applied, AS LONG AS the scene is ONLY rotated around the y-axis. To complete the picture, we need normal polygons, because we would otherwise not be able to texture a perfect vertical wall. And that's where my little Focus engine comes into play again...

Conclusion

I'm seriously considering to add the voxel polygons to Focus. This will allow me to do graphics with much more detail than any 3D accelerator can ever handle, with a great natural look. All this comes at the expense of one single limitation: The y-rotation. A voxel engine is NOT capable of rotating around the other axes. That might not be a problem for the z-axis (tilting), but it's a pitty for the x-axis (looking up and down). You could look slightly up and down, but not a lot: Voxel bars MUST be perfectly vertical. Looking down by 45 degrees wastes the picture. About 10 degrees is fine, though.

One last thing that I just thought of:
The height of a single polygon can be interpolated fluently to be able to construct a perfectly round hill with just 4 polygons. Just interpolate the height as you would interpolate intensities using gouraud shading... You see, the sky is the limit. I think. :)

Happy coding,

Jacco Bikker, a.k.a. "THE PHANTOM"