0
\$\begingroup\$

I am using an octree to define my 3D voxel world.

And I want to use octree subdivision as a LoD system.

This means, subdivide close to the player, but far away nodes un-subdivided.

But it occurs to me that in some cases, the octree can quickly degenerate to a grid.

To illustrate, see the 2D sample of a quad tree below.

enter image description here

If the player is at location A, no problem, subdivide that cell, done.

If the player is at location B, two cells would require subdivision.

But at location C, all cells are subdivided, causing no reduction in work.

Are octrees even viable approaches to LoD, or do I need something else?

\$\endgroup\$
  • 2
    \$\begingroup\$ Is your world only 2x2 cells? \$\endgroup\$ – Kromster Jul 26 at 9:26
  • \$\begingroup\$ It is a 2D analogy. The octree nodes all have 2x2x2 children. \$\endgroup\$ – Bram Jul 26 at 16:31
2
\$\begingroup\$

As Kromster alludes, this apparent problem occurs because of the small scale of your example. Usually when we reach for sparse octrees, we have more than two levels of subdivision.

Here's your same 2D quadtree example, but with 4 levels of subdivision instead of 2:

Quadtree example

You can see how, even in the worst case where we have a cluster of detailed content spanning the center cross of the tree, we only need 16 high-detail (blue) cells, 12 medium-detail (green) cells, and 12 low-detail (orange) cells, for a total of 40 active cells.

Compare this to subdividing the whole grid to the finest detail level, which takes 256 cells in this 2D quadtree example. (For a 3D octree, the exponent is even worse - you'd need 4096 cells for a full grid this fine), so we've potentially reduced our workload by 85% or more!

See this past Q&A for more examples of how you can leverage multiple levels of hierarchy for effective compression of voxels.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thanks, yeah, it gets a bit better at deeper levels. Still, with the player at world-centre, not a single lowest level cell survives without subdivision! It seems wasteful? (My max res cell takes a lot of resources, I can afford only a few of them.) \$\endgroup\$ – Bram Jul 26 at 16:36
  • 1
    \$\begingroup\$ It depends what "lowest level" means. In one view, the root (the containing square) is the lowest level cell, and it will always be subdivided. You never render a non-divided root. In fact, you don't have to render every cell at all — some can exist as organizing elements. You might decide that only green and blue levels need to be drawn, and the orange level is far enough away to be culled entirety, so you have just 28 active cells in such an example. The number of cells you draw is something you can control independent of the octree, the tree structure is just an organizational tool. \$\endgroup\$ – DMGregory Jul 26 at 16:55

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.