what are sparse voxel octrees?

Question

I have reading a lot about the potential use of sparse voxel octrees in future graphics engines.

However I have been unable to find technical information on them.

I understand what a voxel is, however I dont know what sparse voxel octrees are or how are they any more efficient than the polygonal techniques in use now.

Could somebody explain or point me to an explanation for this?

Answer 1

Here's a snippet about id Software on this subject.

id Tech 6 will use a more advanced technique that builds upon the MegaTexture idea and virtualizes both the geometry and the textures to obtain unique geometry down to the equivalent of the texel: the Sparse Voxel Octree (SVO).

It works by raycasting the geometry represented by voxels (instead of triangles) stored in an octree.

The goal being to be able to stream parts of the octree into video memory, going further down along the tree for nearby objects to give them more details, and to use higher level, larger voxels for further objects, which give an automatic level of detail (LOD) system for both geometry and textures at the same time.

Also here's a paper on this.

Found more information in this great blog entry.

Well, voxels alone are not that interesting, because for any reasonably detailed modeled, you would need extremely huge amounts of voxels (if using an uniform grid).

So, a hierarchical system is needed, which brings us to octrees. An octree is a very simple spatial data structure, which subdivides each node into 8 equally large subnodes.

A sparse octree is an octree where most of the nodes are empty, similar to the sparse matrices that you get when discretizing differential equations

Answer 2

an octree has 8 neighbors because if you imagine a square, that was cut into 4 equal quarters like so

______________ |     |      | |     |      | |_____|______| |     |      | |     |      | |_____|______| 

then it would be a "quad"(four)-tree.

but in 3 dimensions, you have yourself, a cube, rather then a square, so cutting it horizontally, vertically, and along the Z axis, you'll find 8 chunks rather then 4 like so

    _____________    /     /     / |   /-----/-----/  |  /_____/_____/ | |  |     |     | |/|  |-----|-----|/| |  |     |     | |/  |_____|_____|/ 

hope that makes since..

what makes the SVO unique, is that it stores Voxel information, which is a point in space, that has properties such as Color, Normal, etc..

the idea behind SVO is to ignore triangles, and the need of textures, by putting them together into a single SVO which contains the Voxelized Triangle Hull(the Model), and its surface textures all in one object.

The reason a Octree is needed here, is that otherwise a uniform grid structure would require far to much memory for existing graphics cards to handle..

so using the SVO allows for a sort of Mip-Mapped 3D Texture..

MipMapping basically is the same image, but at difference scales, one which has more detail, and the latest which has the least detail(but look fairly similar from a distance)

that way near objects can stream from the SVO with greater detail, while further objects stream with less detail.. that is if you're using Ray-Casting.. the further away the ray from the camera, the less we dig into our Mega-Texture/SVO

But, if you think outside the box like "Euclideon" with its "unlimited-detail", you would just use frustum slicing, and plane/aabb intersection, with projected UV of our sliced billboard for finding each texels color on the screen, opposed to Width*Height pixels, shooting out rays, with nvidia's naive "beam optimizations".

PS(sorta off topic): for anyone who doesn't understand how Euclideon does their shi, I believe thats the most practical solution, and I have reason to back it up(that they DO NOT use ray casting)

The biggest mystery they have, isn't rendering, but storing their data.. RLE simply doesn't cut it.. because some volume/voxel data may be more random, and less "solid" where RLE is usless, also compression of which for me typically requires at least 5 bytes into anything less. they say they output roughly half of what is put in) through their compression.. so they're using 2.5 bytes, which is about the same as a Triangle now-adays