# Which data structure should be used to represent voxel terrain?

According to the Wikipedia page about voxels, "[...] the position of a voxel is inferred based upon its position relative to other voxels (i.e., its position in the data structure that makes up a single volumetric image)."

How should one implement such a data structure? I was thinking about an octree but I'm wondering if there's something else that I never heard about.

-
This is a somewhat hard question to ask because its very dependent upon what data your voxel data is going to need. Things like how full the voxel is, what does it look like, etc are going to be fairly dependent on what you are doing. Secondly the data structure has to lend itself to high speed access for real time manipulation of the data and subsequent updating of it.. How to keep memory structure low per voxel and data fast access/manipulation fast are pretty much the key technical challenges that are fairly intent specific when working with voxel engines. Not an answer, so a comment. – James Sep 8 '11 at 20:16

First. Lets write what do we know about each voxel :

``````voxel = (x, y, z, color) // or some other information
``````

## General storage

General way is simply this:

``````set of voxels = set of (x,y,z, color)
``````

Note, that triplet (x,y,z) identify each voxel uniquely, since voxel is point in space and there is no way two points occupy one place (I believe we are talking about static voxel data).

It should be fine for simple data. But it is by no means a fast data structure.

Rendering is AFAIK done by scanline algorithm. Tom's Hardware article on voxels has image of scanline algorithm.

## Fast lookup

If fast lookup is needed, then the fastest data structure for lookup is hash (aka array, map ...). So You have to make hash out of it. So, naively we want just fastest way to get arbitrary element:

``````array [x][y][z] of (color)
``````
• This has O(1) for looking up voxel by x,y,z coordinates.

• Problem is, that it's space requirements are O(D^3), where D is range of each x,y and z numbers (forget Real number, since if they were Chars, which have range of 256 values, there would be 256^3 = 2^24 == 16 777 216 elements in array).

But it depends on what You want to do with voxels. If rendering is what You want, then it is probably this array what You want. But problem of storage still remains ...

## If storage is the problem

One method is to use RLE compression in the array. Imagine a slice of voxels (set of voxels, where voxels have one coordinate constant value .... like plane where z = 13 for example). Such slice of voxels would be looking like some simple drawing in MSPaint. Voxel model, I'd say, usually occupy fraction of all the possible places (D^3 space of all possible voxels). I believe, that "take a pair from triplet of coordinates and compress the remaining axis" would do the trick (for example take [x][y] and for each element compress the all voxels at z axis at given x,y ... there should be 0 to few elements, RLE would do fine here):

``````array [x][y] of RLE compressed z "lines" of voxel; each uncompressed voxel has color
``````

Other method to solve storage problem would be instead of array using tree data structure:

``````tree data structure  = recursively classified voxels
for octrees: recursively classified by which octant does voxel at (x,y,z) belong to
``````
• Octree, as mentioned by Nick. It should compress voxels. Octree has even a decent speed for lookup, I guess it is some O(log N), where N is number of voxels.
• Octree should be able to store decently arbitrary voxel data.

If voxels are some simplistic heightmap You might store just that. Or You might store parameters to function which generates the heightmap, aka procedurally generate it ...

And of course You can combine all possible approaches. But don't overdo it, unless You test that Your code works and measure that it is REALLY faster (so it is worth the optimization).

## TL;DR

Other than Octrees is RLE compression with voxels, google "voxlap", "ken silverman" ...

## Resources

-
"If storage is the problem": also you can use VTC (oss.sgi.com/projects/ogl-sample/registry/NV/…) or DXT compression – KindDragon Sep 11 '11 at 17:59
@KindDragon thank You for this information. :) That is very good idea. – user712092 Sep 11 '11 at 19:38
Resource link is down. – Ezequiel Mar 31 '14 at 4:33

There are two different data structure aspects they may be talking about.

Array structures

When you reference an element of an array of any number of dimensions, consider that the array itself, once you pass the indices (eg. `myArray[4][6][15]`) knows what is at that location. If what is at that location is a voxel, that voxel doesn't need to additionally record it's own x, y, and z coordinates -- the array holding the voxel specifies it's world location implicitly based on it's array-indexed location.

The reason this is good is that the pointer arithmetic used for this sort of array access is inherently fast and generally speaking, provides the foundation for most of the quick (often called "native") arrays found across languages. The downside to these arrays is that they must have elements of equal size in bytes, in order for said pointer arithmetic to be applicable.

Octrees

(I note this second, because this is less likely to be what wikipedia refers to, and voxel implementations do not require the use of octrees although nearly all modern ones do use octrees.)

An octree's root node is a single, undivided cube. Let's set up an example. Say your octree's root, the very centre of the cube, is at `{0, 0, 0}` in 3D space. Once you begin to place objects within that space (read: more than one object), it is time to subdivide the octree further. This is where you divide into 8 (oct-), by slicing it up using 3 planes, these planes being the xy, xz and yz planes. Your original cube now exactly contains 8 smaller cubes. Each of these sub-nodes is positioned as an offset from the central, parent cube. That is, that for example, the cube lying in the positive xyz octant would have an offset from the parent / containing cube's centre of exactly `{root.width / 4, root.height / 4, root.depth / 4}`. Rather than specifying an absolute position for each subnode, it makes more logical sense to consider the parent node as the origin of its childrens space. This is the same way scene graphs work.

It is simple enough to see this in a 2D drawing, where you draw a square, and subdivide it into 4 equal regions. If, like our octree root node, the centre of the parent square were considered to be `{0, 0}`, then the 4 centres of the child squares would be

`{root.width / 4, root.height / 4}`, `{-root.width / 4, root.height / 4}`, `{root.width / 4, -root.height / 4}`, `{-root.width / 4, -root.height / 4}`

...As relative to their parent -- the same principle as in 3D.

-
Thank you for your answer. In my case, some large parts of the terrain would be made from the same type of voxel which is why I was thinking about octrees (a large chunk would not have to be subdivided). However, I'll give the 3D array a shot since it looks simpler to implement. I'm sure I can manage to abstract the implementation details of my terrain class enough so that it's not so hard to switch implementations would the need arise. – pwny Sep 8 '11 at 20:31
You're welcome. I definitely would suggest looking into octrees, really they are not hard to grasp. But yes, your approach makes sense for now, certainly it is worth doing initial prototyping using a 3D array. – Arcane Engineer Sep 8 '11 at 20:35
As further reading, a good discussion of the implementation of octrees including several useful references can be found in Intel's Extending the STL for Games article. – Martin Foot Sep 9 '11 at 6:41

Generally you can avoid a 3D data-structure for terrain. You can use a heightmap instead. This can be very cheaply and efficiently voxelised at runtime. It usually pays (in my experience) to track the minimum height you need to render in each column and also sometimes start-stop-top angles so you can cull backface columns too.

If you terrain has a small number of overhangs or caves or other features that cannot be represented by a heightmap, then you can have holes in your heightmap and have an alternative representation e.g. true 3D voxel objects that fill just those localised places where the runtime expense is warranted.

Sparse voxel representations are worth it when you have large true voxel worlds. John Carmack has been talking them up for the past few years now...

-
I thought about heightmaps as well but a couple of things drove me away from them. The thing is that in my case, the terrain is not truly large by any means or very complicated (think a maze type terrain, very cartesian). I'd also like part of the terrain to be destructible or allow the user to affect the terrain through construction. This may result in the player creating "tunnels" in the terrain that seem more complicated to represent with a heightmap. – pwny Sep 9 '11 at 5:26

You can use RLE. But you can use SVO (Sparse Voxel Octree), id Tech 6 uses SVO. A SVO is a 3D computer graphics rendering technique using a raycasting or sometimes a ray tracing approach into an octree data representation.

The technique varies somewhat, but generally relies on generating and processing the hull of points (sparse voxels) which are visible or may be visible, given the resolution and size of the screen.

Use raycasting, because it's more fast.

-