4
\$\begingroup\$

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?

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thanks for this great explanation. I've understood now, with a Octree I can make my game more robust and this will avoid some headache in future. Also you've pointed another good reason to work with it: It's commonly used, so as a i'm (or want to be) Game Developer, I need to know it. Thanks again. \$\endgroup\$ – Afonso Lage Feb 23 '14 at 10:09
  • 1
    \$\begingroup\$ @AfonsoLage I am afraid robust isn't the right term, I think it doesn't directly deal with robustness. Nick's great answer didn't even mention it (so I am confused about your deduction). But anyway +1 for Nick complete answer. \$\endgroup\$ – concept3d Feb 23 '14 at 10:14
  • \$\begingroup\$ @concept3d With robust I meant this will help me in other functionalities, like better Frustum Culling and Collision Detection, making my Voxel Engine more stable and fast (if well implemented ofc), may I've used the wrong term... \$\endgroup\$ – Afonso Lage Feb 23 '14 at 10:16
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thanks for this answer, I'll stick with Octrees because Ray Casting and a better Frustum Culling (my actual one takes 12ms on a 500 chunks tile map). \$\endgroup\$ – Afonso Lage Feb 23 '14 at 10:11
  • 2
    \$\begingroup\$ @AfonsoLage but keep in mind that octrees also need some more investment in the time to implement. \$\endgroup\$ – concept3d Feb 23 '14 at 10:20
  • \$\begingroup\$ Yes, i'm reading many articles to try to implement it, the hardest thing is to know what is GigaVoxels, Sparse Octree, Loose Octree. But when I know how to distinguish those three, I'll be able to implement :). \$\endgroup\$ – Afonso Lage Feb 23 '14 at 10:27
  • 1
    \$\begingroup\$ @AfonsoLage check my blog, I've written an article that can help you get started codingshuttle.com/2014/01/… \$\endgroup\$ – concept3d Feb 23 '14 at 10:35
  • 2
    \$\begingroup\$ @AfonsoLage Yes -- do take into account what concept3d has said about complexity. To implement in the non-naive i.e. performant sense, octrees are certainly a non-trivial undertaking for someone new to 3D engines. Caveat emptor! \$\endgroup\$ – Engineer Feb 23 '14 at 11:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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