The Birth and Death of Voxely Thingies

Background

As briefly mentioned earlier, Payback Time's graphics are based on voxels. What exactly is a voxel, then? Even Wikipedia is quite vague about the origins of these nifty little chunks.

This late to Friday, it suffices to say that voxels are cells of a 3D volume. So, pictures come with pixels and volumes with voxels (pi-xels and vo-xels).

Pros and Cons

Besides their cubic looks, voxels offer some pretty great advantages:

On the minus side, there are some shortcomings to voxels:

Polygons Won't Cut it

Early on, when I was thinking of different ways to approach the game graphics, I made a mental note about not wanting to deal with actual 3D polygon models while creating graphical assets.

Polygons simply felt too static - also, I'm just not that great in 3D modeling.

Instead, I wanted something that was simple to create graphics with; something that would offer easy extensibility and would produce voxely objects, ready to be destroyed by various kinds of in-game incidents.

Here's Where We Derail

Photo hulls. Space carving. I'm reading all of it.

I'll decide to try something simple, albeit absurd. What if we imagined a group of orthogonal views from all of the six sides of an object and tried to form an understanding of the 3D volume bounded by the views?

This has been done before, in fact. Sure, it's a pretty simplistic approach and will not cover all of my goals, but it's something to be inspired by.

Bring Out The Voxely

I'll explain my weird approach to turning a set of plain 2D images into voxely thingies below.

It all starts with the old idea of using an image to represent a heightmap. Greyscale images work the best, 8-bits per pixel PNG-files is what I currently use.

Here's an example heightmap (16x16 px) visualized as a 3D mesh. All of the pixels of the image have been set to maximum value of 255, so the heightmap is just a square floating about in space.

Heightmap

If only you could read the small text in the picture, you'd see the axis of depth pointing down, i.e. the smaller the pixel value in the image the deeper down would the heightmap be mapped to.

In the following 2nd picture, the heightmap is altered by making the centermost area slightly darker in the image, lowering the mapped mesh at that neighbourhood.

Heightmap

It's a good time for a quick'n'easy math lesson.

To tell whether a 3D point within the heightmap box (x and y: 0-15, z: 0-255) is either above or below the heightmap surface, one might use the following function:

f(x, y, z) = z < heightmap(x, y)

So, the function evaluates to true when the 3D point is under the heightmap surface, aka. inside.

Another Day, Another Dimension

In order to be able to create objects other than Perlin-noisy grass, we need to be able to carve the bounded volume in more sophisticated ways. This is achieved by combining further orthogonal views (heightmaps) into the volume mapping phase.

So, we'll simply create another image representing another view or side of the volumetric box we're observing.

Heightmap

Now, we must somehow take the new heightmap into account while determining whether a 3D point is inside the volume. Back to the math class with us:

f(x, y, z) = z < heightmap_top(x, y) && y < heightmap_front(x, z)

Holy axis swap. You can probably see where this is going:

By simply defining the direction of depth for each individual (up to 6) heightmaps of a box-bounded volume, one can easily test whether a 3D point is inside the intersection formed by all of the heightmaps.

The dimensions of the box-bounded volume can be easily determined from the heightmap image dimensions.

After setting up one more heightmap, a simple, fully enclosed and rendered object with its source images can be seen here:

Heightmap

There's Symmetry in Everything

I've noticed that it is easy to setup heightmap symmetry rules for the voxely generation. In case there are fewer than the full set of 6 heightmap images available for an object, one can simply re-use the available ones following priority rules, e.g.:

This way one can create a solid 3D cube by simply drawing a single greyscale image in MS Paint. Wicked, no? Typically though, I've seen that simple objects require 2-3 images (e.g. front, top, left).

Must Meshify

Okay, so everything's fine in our fantasy land, where voxelies magically appear onto the screen. There, where reality still rules, there are things to be done yet. We cannot simply render the functions yielding us boolean results - the information about 3D volume properties needs to be turned into something drawable, 3D primitives, that is.

The simplest way is to take an existing meshing algorithm and plug the previously coined up volume sampling function into it.

For smooth forms without too many sharp features, one might use Marching Cubes or a more modern approach of isosurface extraction. A collection of information can be found here.

For sharp features and Minecrafty looks, you should take a look at. Greedy Meshing, for instance.

Personally I use an algorithm inspired by Greedy Meshing, enhanced with support for 45-degree slopes. It may be that I'll use another algorithm for smooth features (e.g. game characters) later.

With any of the above algorithms, the basic principles of meshing are the same: walk over the box-bounded area and generate vertices and indices for the geometry. In addition, one typically collects normals and UV-coordinates for the purposes of lighting and texture mapping.

Voxelies, What Are They Good For?

All in all, the above approach for generating voxel objects from images has the following advantages:

There are some caveats too, surely:

Wrapping up

That's all for tonight - if/when everything about this post is unclear, don't hesitate to contact me! Next up will be Adventures in UI Land and map editor progress.