this space intentionally left blank

April 29, 2009

Filed under: tech»coding

Voxel Populi

Behold, the mighty voxel terrain engine:

Click on the Flash window to give it focus, then press space to start/stop the animation thread. The two numbers at the top are the framerate and the level-of-detail (LOD) constant. You can adjust the LOD, and thus the framerate, by pressing the [ and ] keys. The ' key cycles through three post-processing options: poor-man's light bloom, simulated drunkenness, and none.

I've been working on this in my spare time for a couple of days now, just as a kind of mental exercise. Also, the techniques that I figure out on problems like this could be useful for work--I'd love to do a scatter plot or density map of the US using this kind of approach. Finally, it's a chance to get back to the kind of frame buffer-centric graphics hacking that I used to do.

So why voxels? Well, for one thing, they're easy to debug. An engine like this works by casting rays out from the viewpoint for each pixel of the display, stopping when they intersect the landscape, and drawing a texture point at that position. The heightmaps are pulled straight from images that I can make in Photoshop (thus keeping my toolset fast and simple). There aren't any BSP trees or polygon normals to compute (usually). Voxel engines may have fallen out of popularity with professionals because they can't be easily hardware accelerated (although some coders hope that will change), but they have relatively few points of failure and mistakes tend to be pretty obvious.

Getting this to work was easy. Getting it to run at 30fps or more was a bit harder. A few notes:

  • Actionscript 3 is a surprisingly fast language with a nice built-in graphical library, but its methods for working directly with framebuffers are very limited. In C, I would have loaded the map data into an array and run through it with pointers, poking values into screen memory as I went. Actionscript, being a managed language, has no pointers, and its arrays kept giving me fits. When I did get the code running using data structures, it was often too slow, because the code had to be more complex (to add bounds-checking, casting, dereferencing, and index-manipulation). In the end, I went back to doing data retrieval using BitmapData.getPixel(). In comparison to array operations, getPixel offers two nice features: it fails gracefully when my rays overshoot the map, and it accepts floating point values. The end result is actually faster, even though getPixel itself is almost twice as slow as simple array lookup. As always, avoid premature optimization.
  • Likewise, I tried a lot of different methods to see if I could beat setPixel(), without any success. It's odd, but there doesn't seem to be any speed advantage to populating a ByteArray and then copying it into the BitmapData, either for the entire frame or for each column. And the bookkeeping's a lot easier this way.
  • You may notice that there's not much penalty for opening the SWF at full size. This is counterintuitive: voxels don't scale to high resolutions well, since they have to cast a ray for each pixel of the screen buffer. So figuring that it was always going to be pretty blocky anyway, this version renders internally to a 320x240 bitmap, then uses Flash's native scaling bring it up in size.
  • In fact, generally speaking, I try to write for the parts of the Flash API that are clearly implemented in native code. It just makes sense to let the VM do the heavy lifting. In this case, bitmap scaling and copying is very fast, and the blur filter is optimized for powers of 2. Put an 8-pixel blur on a 50% transparent bitmap copy, and voila! instant bloom effect with practically no performance penalty.
  • Actionscript may not have pointers, but some of the same rules apply. For example, property lookup on an object (dereferencing, if you will) is a lot slower than making a local reference variable. Also, creating objects (allocating memory) is expensive. I got a pretty significant boost early on by switching from "ray.x" to "rayX" for casting, initializing variables outside of loops, and storing references to object properties (particularly those behind two or three dot operators) whenever possible.
  • Most of the program is spent in a single loop, incrementing rays and checking for intersections with the landscape, so that's where optimization was really needed. I spent some time tweaking the operations there, but by far the most effective addition was LOD: effectively, lowering the accuracy of the ray as it gets farther from the viewpoint. Implementing level-of-detail alone was responsible for a 400% speed increase. It works by increasing the casting distance each time through the loop. To get a logarithmic increase, the increase is equal to the ray's length shifted to the right by a set number of places. When you change the LOD above using the [] keys, you're changing the amount of the bitshift. At 10, the ray is accurate out to 1024 units (which is the maximum view distance). On my laptop with the debug player, setting it to 7 (meaning that detail drop-off begins at 256 units) seems to be a good tradeoff between speed and accuracy. A setting of 5 or 6 is faster but with visible jumpiness. Below 5, some wacky (but fun) behavior emerges.
  • Another increase comes from being smart about the ray behavior. I render each column of pixels from the bottom up. Since the heightmap can only contain one height value, any given pixel's ray will never intersect the map in less distance than the pixels under it, so it can continue from the same X and Y coordinates as the previous ray, adjusted to a new height and vertical angle. Also, once a ray hits nothing but sky, all rays above it will do the same--so there's no need to bother with them.

Although it's simple, coding this was a lot of fun. The next goals are to add support for tiled heightmaps (for building bigger worlds), multiple landscape textures, and sprites. If the framerate would support it, I'd put a second, inverted landscape on the "ceiling" for creating more complicated structures. One thing I didn't anticipate was how much I like the look of the bold colors and gradients in the current "programmer art" texture--maybe that's a look I'd like to preserve. And of course, somewhere along the line, I'll have to figure out what I'm doing with it. Any ideas?

Future - Present - Past