1
\$\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
  • 2
    \$\begingroup\$ Is your world only 2x2 cells? \$\endgroup\$ Commented Jul 26, 2020 at 9:26
  • \$\begingroup\$ It is a 2D analogy. The octree nodes all have 2x2x2 children. \$\endgroup\$ Commented Jul 26, 2020 at 16:31

1 Answer 1

Reset to default
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.

\$\endgroup\$
2
  • \$\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\$ Commented Jul 26, 2020 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\$ Commented Jul 26, 2020 at 16:55

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.