From voxels to triangles

Voxels are hot topic. Ever since the minecraft game ‘voxels’ are popping up everywhere. The technology is not new, but with the power of modern-day GPU’s, advanced techniques are now possible in real-time.

I was particularly impressed by the works of ProcworldVoxel Quest and Blockscape. Since this technology requires combining computer graphics, maths, CPU/GPU parallelism and complex algorithms, I was very excited to taste some of those delicious voxels myself!

Player build from landmark, made possible with the procworld engine.
Built by players in Everquest Landmark, a game made possible using Procworld voxel technology.

Voxels are the three-dimensional equivalent of 2D pixels on your screen. Your screen is divided in a finite set of points (hopefully at least Full HD 🙂 ). Each point corresponds to a dot or a square with a single color. Put all of these millions of points together and you get an image.

Voxels follow the same principle. The 3D world is divided using a regular (equally spaced) grid, and each gridpoint corresponds to a single voxel. Instead of containing color, a voxel typically holds the type of material present at this point, like grass, dirt, rock, air, but a voxel can be used to store any kind of volumetric information.

CubeGrid
6x6x6 voxel grid of a cube with voxels displayed as small boxes. White boxes represent air, green boxes represent solid material.
21x21x21 voxel grid of a sphere.
21x21x21 voxel grid of a sphere.

I deliberately didn’t refer to voxels as cubes, since they aren’t. Voxels can be represented as cubes, by placing a cube at each voxel using the voxel’s material (as done in Minecraft). However, alternative techniques exist, Procworld converts the 3D voxel information back to 2D triangles by generating the surface between air and solid. I’m guessing blockscape stores different shapes of cubes in its voxels and displays those. Voxel Quest is using some sort of ray marching algorithm and evaluates 3D mathematical functions.

For my implementation, I started with a surface extraction approach as in Procworld, since it has as a main benefit that it outputs triangles, making it compatible with most mainstream 3D rendering technologies. This way I can render the voxel world using my existing deferred rendering implementation.

Intelligence upgrade

The RTS testcase is slowly being implemented (due to lack of time). The intial magic + crystal system is working. This system allows the player to store magic energy and transport it using crystals. The system should allow for building energy transport networks. But beware what might happen if you focus too much energy in one place 😉

The goblins have received upgrades! Now they can receive commands through the use of command orbs. The player can pick up these orbs and place them somewhere or attach them to containers. The can even use carts to store their items in. The implementation is still a work in progress, but so far it is looking promising.

Goblins performing all sorts of tasks with command orbs
Goblins performing all sorts of tasks with command orbs

Goblins have a lot more to do, so their brains should get somewhat larger. Since scalability is very import in the wizards, I opted to use behaviour trees for implementing their AI. This will not give us goblins that invent time travel, but allow for easy adding and adjusting behaviour in a scalable manner. Currently the behaviour tree’s implementation is pretty basic, but I am eager to learn if they are as scalable as they seem to be :).

References

http://aigamedev.com/open/article/bt-overview/

Progress update

The last couple of weeks, i’ve started working on some basic gameplay play-tests. The current setup features a sort of RTS, but where you can walk around the world in third person view. Skinned animation support is currently missing from the engine, so the primary agents in this testcase are barrels :). I added some very simple crowd control to make them more realistic. Check this video: Crowd control

Pathfinding was added to the engine to support this gamemode, here are some pics: Big objects pathfindingjump search astar

Goblins are able to accept commands from the player, which makes them move resources, powering basic factories.

Now it’s time to combine these features into some more challenging gameplay 🙂

Blog about Software Engineering and Game Development, home of The Wizards Engine