When would you use an octree in a voxel Engine?

Question

I've been reading about Octrees, and I understand how they work (or at least I think I do). However, I can't figure out why you would use octrees instead of a simple multidimensional array.

In my project, I use chunks in my world. Every chunk is made up of 16x16x16 voxels. If I need to access a voxel, I just use the notation myChunk[x][y][z]. If I need to check neighboring voxels, I can use the same notation. I've already implemented frustum culling, face merging, and hidden surface determination. With these optimizations and this simple multidimensional array, I can render about 500 chunks at 80 fps. So, in which situation would I use octrees in this kind of Voxel Engine? Or is it useless?

I can see the purpose of octrees if I would implement LOD into my voxel engine (which I'm not planning to do). Is my lack of experience in Game Development blinding me on something?

Answer 1

Short Answer

The Octree is favoured in games and rendering, because

1. It supports visual level of detail, sensibly.
2. It provides extremely tight compression of sparsely-populated spaces. (c.f. SVOs)
3. At its lowest level it matches the uniformly-sized / -placed cells required for a voxel world. Other 3D accelerative structures may not do this, as explained below.

Full Explanation - TL;DR

Hierarchical spatial subdivision is used for two main reasons

• LoD: To avoid iterating over detail that is far away and thus not of interest;
• To accelerate iteration through a space, e.g. in raytracing or AI pathfinding, by walking a shallow level of the data structure where possible, i.e. where there are fewer nodes across a given distance.

Why is the octree commonly touted? As compared against it's usual competitor, the KD-tree, it...

• Provides uniform subdivision at every level. This is an excellent way to achieve smoothly-degrading LoD (level of detail) while maintaining equal "smoothness" across each LoD grade. So visually this works better than a KD-tree, which isn't really suited to the purpose of LoD.

• Is exactly the same form of subdivision at each level (8 children per parent with the same layout each time) so certain assumption can be made, resulting in fewer conditionals. Perhaps more importantly, this gives us more accurate bounds on processing cost than a KD-tree, which may have N != 2 subdivisions in each axis... there is a general rule in engineering real-time systems that it is better to have a lower but stable FPS than an FPS with a high maximum rate and a too-low minimum.

• Provides extremely rigourous compression as compared with other 3D spatial subdivision approaches; hence the term, "sparse voxel octrees" (SVOs). This means you can store a relatively enormous space containing a very small amount of voxel solids, efficiently, using an octree.

To give you some further persective, pros and cons for KD-trees:

• KD-trees tend to make more efficient use of space / time overall, in terms of the number of boundary planes the data structure contains, which also improves speed of traversal.
• Simply not suitable for distance-based LoD, due to variable granularity and alignment.

For most, it turns out that the pros of octrees end up winning the day. From an engineering standpoint, conceptual uniformity (simplicity) and predictability of execution paths win the day.

Less compact alternatives

In many instances it has been proposed that in spite of the conceptual simplicity of octree traversal, the octree is non-optimal in this sense due to the sheer number of levels of subdivision, which results from the division ratio (1:2 per axis) being so low. If, as in your case, instead of 2x2x2 children per node, there are 16x16x16, we would greatly reduce the number of node boundaries, simplifying cache linearisation which leads to better performance on the overall. Of course, what is crucial to note is that, as with most engineering decisions, this is a trade-off between space and time; the compression of sparse spaces will be far worse with 16x16x16 subdivisions, than with an octree. We call this flattening the data structure.

Answer 2

Like any data structure octrees come with pros. and cons.

Octrees are hierarchical. This is usually a compelling reason to use them, if you don't need this property then you probably don't need octrees. Remember to always use the appropriate data structure when actually needed.

You can use a uniform grid for your voxels engine, and it works. But you won't have the extra benefits (and complexity) that comes with an octree. For example octrees are good for voxels LOD, and like any hierarchical data structure they can speed up certain tests like ray casting and frustum culling.

On the down side Octrees are also known as harder to make cache friendly. Also a complete octree with certain depth takes a lot of memory, and that's why sparse voxel octrees exist.