Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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).

share|improve this question
    
[unity] and C? That ... makes little sense. –  Martin Sojka Aug 29 '11 at 14:33
    
I understand C. –  Dan the Man Aug 29 '11 at 14:35
6  
You have a lot of faith in the community with such a bold request. I mean, a complete paper on a fully dynamic voxel terrain for today's hardware with good FPS, it should be easy, right? Well, the topic is so broad and difficult, I doubt you'll see a generic solution and even then, it may be completely useless for your case. But who knows, it may be doable depending on your role model. Do you want a Crysis 2 voxel terrain or a Delta Force one? Maybe you're doing a Minecraft clone or just need a sand simulation for a digging game? Define a scope, please. –  Vigil Aug 29 '11 at 14:59
2  
Check out this middleware: forum.unity3d.com/threads/…. Particularly the demo –  Tetrad Aug 29 '11 at 15:21
1  
GPU Gems 3 has a chapter about voxel terrain: http.developer.nvidia.com/GPUGems3/gpugems3_ch01.html –  Tamschi Aug 29 '11 at 15:56

3 Answers 3

up vote 51 down vote accepted
+50

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.

enter image description here

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.

share|improve this answer
    
The community wiki change is permanent, there is no way to reverse it. You would need to delete and recreate your answer (of course sacrificing your existing votes) –  Noctrine Aug 29 '11 at 17:58
    
meta.stackexchange.com/questions/2974/… claims moderators can remove it. Don't know if things have changed, though. Thanks for looking into it either way. –  Nick Wiggill Aug 29 '11 at 18:06
1  
Go figure, be careful next time. –  Noctrine Aug 29 '11 at 18:13
2  
The former is a discretised space where entities can only lie directly on a cell. Like perfectly-placed pieces on a chessboard, they cannot lie "between" cells or overlapping the borders. Whereas a continuous space is as found in most physics engines, i.e. it is based on floating point numbers and is thus continuous rather than quantised. Your entity can sit at any arbitrary position in space you choose -- just as in real life. –  Nick Wiggill Aug 31 '11 at 8:11
1  
Texturing is implicit. Real voxels, whether mesh based or not, each have a pure colour. The aforementioned approaches just create more realistic detail, and enable a combined-mesh approach (google Unity VoxelForm). The finer your voxels, the finer your resultant texture detail. Example: model a river bed as rock (grey). Convert every pixel within x distance of the surface, into sand, by setting these voxels to have material="sand"; they can then be rendered as sand-coloured. Additionally, this may also affect their physical interactivity, so sand may be moved by water, or dug away. –  Nick Wiggill Sep 11 '11 at 8:06

The best way to generate interesting voxel terrain is with a Perlin noise density map. Rather than using a 2D Perlin noise map defining the height of a 3D world, use a 3D Perlin noise map. Weight the map so that the values closer to the bottom will be more likely solid, and the values closer to the top will definitely be air. This gives your world height, but also allows for overhangs and caves, similar to Minecraft terrain, as this side-view of a slice of terrain shows:

World with overhangs

From here you can test for floating islands, or add cave systems using fractal noise:

World with cave system

The above pictures and cave system ideas are from this excellent blog post. You can learn all about Perlin noise here, and there is some sample code to get you started here.

share|improve this answer
4  
Nice resource links, thank you. –  James Aug 31 '11 at 0:48

The other answers here are excellent, but I took a slightly different approach.

I generate an environment in a modeling tool (3DSMAX), and build a sparse octree from it. Each cubical, non-empty leaf node is a voxel. At render time, I use raycasting (implemented in HLSL) to find which voxel occupies which pixel, and set the pixel to the color stored in the node, which I calculated when generating the tree by averaging the texture values from the source model.

This gives you a lot of nice benefits - collision detection for free, variable LOD, view space culling, etc - and, aside from the raycaster - its easy to implement.

Unfortunately, it's near impossible to post sample code from a phone.

share|improve this answer
    
+1 for an alternative. While not impossible to implement with reasonable performance, the pros are far outweighed by the cons. Voxel raytracing imposes a huge drain on the GPU. The arithmetic and conditionals necessary for this are very costly, when those same GPU cycles could be applying a number of impressive screen-space effects eg. SSAO. The biggest problem is that raycasting looks best with multiple bounces as found in radiosity -- not viable either for the scene which consists of millions or billions of voxels and where each ray segment takes considerable effort to bounce and composite. –  Nick Wiggill Jan 5 at 16:11
    
...This is why I mentioned scaline raycasting only as an aside in my answer (VoxLap) -- even it is difficult to implement well. If you can get a vertical scanline approach working, the cost is an order of magnitude less than per-pixel raytracing, since you've reduced dimensionality of the rendering process from 3D to 2D. This approach I still stand by, though it does preclude complex lighting solutions possible with your traditional RTRT. –  Nick Wiggill Jan 5 at 16:12

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.