procedural generation - How are voxel terrain engines made?

A few days ago I found something called voxel terrains and I think that they're pretty cool. But I don't know anything generating them. Do you model it in your modeling software or use something like a heightmap? I read on wikipedia that voxels are like 3d pixels or volumetric pixels.

After I make the voxel terrain, how can I take these voxels and make them destroyable/diggable?

I will pick the best answer based on:

1. code and algorithms. preferably based in C#


2. explanations. I am a beginner with algorithms but I'm very familiar with object oriented programming


3. step by step demonstrations. Not only concept but direction.


4. diagrams/illustrations. No, not screenshots of other engines.

I know that this is a complicating subject. But, thanks for any help!

No, I'm not trying to make a minecraft clone.

---

Edit

Thanks to everyone for your great help (especially Nick Wiggill)! This is what I managed to make (Work in progress).

Answer

To generate a voxel terrain

(a) A common method is to generate a heightmap using Perlin noise. A heightmap is basically a monochrome image representing different heights by the darkness or lightness of its pixels.

You'll look at individual pixels in this heightmap to create "stacks" of voxels up to different heights (z-axis) in different (x,y) locations, according to the brightness of that pixel in the heightmap image. Because a Perlin noise image is smooth (no sharp edges of light against dark), you will have smoothly rolling terrain as a result.

(b) You can construct it incrementally by creating the landscape out of different polyhedra. Create a polyhedral vector shape that approximates the voxel shape you want. Using any 3D-point-in-polyhedron method (most often, point-in-convex-hull), check which points of your world grid fall within that polyhedral volume. For example, define a pyramid in space. After checking every point in the local region of your world space against that pyramidal volume, you will know which points fall within it, and you can set those cells as "present" meaning they become voxels rather than empty space. You now have a voxel pyramid in your space. You can continue to add shapes of any sort together, in this way, until you have formed a terrain.

(c) (Really the same as b) Write a modelling tool. Voxatron show how this would look. This is just creating the voxel forms in a substitute world (the editor) and then importing these into your actual runtime game world. I believe Voxlap had the first open source editor for voxels. You can place individual voxels, or you can use a voxel "brush" with different shapes / volumes to draw voxels into your world.

---

What you'll need to construct your own voxel-based game

I include this section because the voxel road is not an easy one, at least not at present. Lately, a lot of research is once again being put into voxel engines by the big players, toward rendering and physics applications.

Simplicity may be a problem, because dynamically constructing a world out of raw voxels is a procedural approach to world construction and this not inherently simple. So sorry, there are going to be a few technical terms here. Writing a voxel engine is a pretty serious undertaking and requires knowledge across multiple areas of game engine development, particularly in terms of spatial concepts, and this means understanding 3D vector math, matrices and basic calculus to some reasonable level.

Having said that, your "generation of a voxel terrain" requires a context in which to work, since voxel engines aren't exactly widespread. Lets proceed to a basic description of how a voxel engine works.

Voxels are the basic building blocks of your world. Their positions are defined by an integer-indexed 3D grid (array) rather than a continuous floating-point space (as used in vector-based 3D games). These will be the "atoms" of your world. They could be 3 feet high as in games like Minecraft, or they could be smaller than your virtual character's eye could actually see, unless clustered together in large numbers -- a bit more like molecules. There are two kinds:

• Cubic mesh based voxels (example) -- these are a newer sort, used for simplicity and easily usable in conjunction with modern graphics tech. Used in games like MineCrat and Dungeon Keeper.


• Point voxels (example, example) -- the original voxel. Each is an individual, collidable point in space, although it may be surrounded by a spherical bounding volume. They are simpler, so you can have many more of them in your world, and you can thus make them smaller, which is generally favourable. Two games that used these were Comanche and the 1990s remake of Lords of Midnight.

Either way, your approach to manipulating voxels in your world is much the same, as follows.

To construct and move objects in your world, you will need the mathematical tools mentioned above. For example, to create a wall: Construct a box of the appropriate dimensions in 3D space, using vectors. Use matrix math to transform your box to the rotation and position you desire in your 3d world (in continuous vector space). For a voxel engine, the additional step is to now use a 3D point-in-polyhedron algorithm to determine which of your voxels fall inside that rotated space.

Essentially, this is the way you would construct most objects in your world. Beyond that, you could write your own tools to "model" a character in the way you might in say, Maya or 3DS Max. But since you are modelling you character out of voxels instead of points, edges and faces, your methods will be substantially different. If you decided to then rotate these objects in your world, you would need to similarly use matrix transformations to do so.

Destructible terrain is as simple as either removing one voxel at a time according to some method of your choosing, or using CSG (Constructive Solid Geometry) operations on large volumes of voxels to remove them according to some predefined volume; for example, if shooting a laser beam through a rock, you might use a cylindrical volume to subtract the voxels here the beam is shooting through the rock. CSG is a relatively simple process using the 3D spatial grids which form your voxel world, and checking every cell in a section of a base grid (in this case the rock) against another grid (in this case, the laser beam)

In order to have material "flows" (as Vigil hinted at in his comment on sand), you will need to look into fluid dynamics and cellular automata. These were used by the author of Dwarf Fortress, Tarn Adams, in what is essentially also a voxel world (albeit the voxels are much larger in this case, comparable to Dungeon Keeper, the principle remains the same). These are cutting edge topics and not a necessity for voxel engines as defined, so I will leave this as a "stub" for your own research.

CSG and fluid dynamics bring me, lastly, to optimisation. Voxel engines currently in development almost exclusively make use of sparse voxel octrees (SVOs) which is a method of subdividing voxel space to varying resolutions, as evidenced in this video showing off the upcoming Atomontage engine. Using octrees/SVOs is more of a necessity than an optimisation choice, because of the processing overheads involved in processing one massive, uniform grid. An octree is essentially an tree (directed acyclic graph) where every node has either 8 or zero child nodes depending on whether the space it represents contains any physical volumes. Diagrams showing how octrees subdivide space to form voxels are here.

The best open source voxel implementation I know of is Ken Silverman's Voxlap Engine, which was used for Voxelstein3D. It is written in C++, and implements CSG operations for terrain deformation.