Game Development Stack Exchange is a question and answer site for professional and independent game developers. It only takes a minute to sign up.
Sign up to join this community
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.
First. Lets write what do we know about each voxel :
voxel = (x, y, z, color) // or some other information
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.
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 ...
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
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).
Other than Octrees is RLE compression with voxels, google "voxlap", "ken silverman" ...
There is list of resources and discussion on how to make fast voxel renderer, includes papers and source code.
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.
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.
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.
Here's one I made a long time back: http://sites.google.com/site/williamedwardscoder/spinning-voxels-in-flash
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...
