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