How do you represent objects and terrain in a 3D video game?  A partial list includes triangle-meshes (very common), geometric primitives (ROBLOX), and height maps (terrain).  Today I’m going to talk about another way of modeling objects and terrain – the voxel.

 

Voxels store information in a 3D grid.  In the simplest case, all of the 3D space in your video game is divided into a grid, and each cell in the grid is either empty (air) or full (ground).  To make the world look more realistic, each cell can be a different color or material.  Just like with your mega-pixel camera or HDTV – the more voxels, the more realistic the game world.

A naive voxel implementation requires enormous computing, rendering and storage.  A game world implemented as a voxel grid one million cells per side would contain 1,000,000,000,000,000,000 cells and require more storage than all of the world’s computers.  The good news is that in most voxel implementations many of the cells are identical to their neighbors, which leads to incredible compression.

Some notable voxel projects:

1986-1991 – Voxel Man is a medical surgery simulator that uses voxels to render and simulate a 3D human body.  Voxel Man can be used to simulate surgical procedures.  This video does a good job of showing how voxels can represent solid 3D data composed of different materials (bones and muscle in this case).

2000 – Voxlap Engine is a game engine/world created and rendered with voxels.  Ken Silverman wrote the Build Engine used in the game Duke-Nukem 3D.  In 1999 Ken started work on a voxel-driven engine called Voxlap.  What’s cool about the Voxlap engine is that the entire world is made up of reasonably small voxels.  In addition there’s a cool “destruction” effect that simulates some rigid body motion when you blow things up.

https://www.youtube.com/watch?v=XaUt31ooCXs

2007, 2008 – John Carmack, creator of the Doom Engine shows a tech demo of voxel-based game technology which is very cool, and later talks about it in an interview.

2009 – Inifiniminer was developed by Zachtronics Industries, and is credited as the inspiration behind Minecraft.  The game was originally developed using .NET technology and was soon hacked.  Here is a cool video of early voxel building in Infiniminer.

2009 – 2010 – Minecraft is one of the most popular indie games of the past decade, and shows cool innovation by using the the voxel grid to help create realistic physical and lighting effects. 

2011 – ROBLOX introduced an integrated Voxel/Physics system at the ROBLOX Rally and has continued to refine the system. 

Some innovations include:

• Physics integration between voxels and moving parts.  Moving parts can collide with voxels, and parts can be joined to voxels.
• Full Lua API’s to access both the moving part and voxel system.  For many operations, such as a hit test, the creator of a script does not need to bother doing two separate hit tests, one against moving parts and one against voxel terrain.  In a follow-up blog post we will look into some of the proceduraly generated worlds that users are creating with complex Lua scripts.
• Integrated wedge shapes and terrain smoothing.  ROBLOX terrain voxels can be either box or wedge shaped.  This allows for autosmoothing functions on the ROBLOX terrain using a combination of block and wedge shaped voxels.
• Integrated 1st and 3rd person creation using the same tools for voxels and parts.  Simple objects in the ROBLOX world such as grass can be sketched with the same tools used to insert complex part-based models such as mechanical doors.
• Programmable studio tools for editing, painting and manipulating voxels.  All of the voxel tools in ROBLOX Studio are written in Lua against the ROBLOX API and can be inspected and modified.

The future of voxels is promising because voxels lend themselves to simple parallel computation for a wide range of terrain and environmental functions.  For example, aerospace engineers have used grid-based FEA simulation for quite some time to calculate moving airflow and simulate the peformance of aircraft.

Wind simulation in games will be common in the future and will be done using coarse voxel grids.  Simple thermal models will make it possible to generate functioning tornadoes inside games – all based on first principals.  Set up the initial conditions of your air voxels correctly (air density, temperature, velocity, pressure and moisture content), press go, and you should get a nice twister!

If you really want to get ‘deep’ into voxels, check out Stephen Wolfram’s book A New Kind of Science where Stephen postulates that maybe the entire universe is running on a grid as a cellular automata!