0
\$\begingroup\$

I am working on a voxel engine that uses a huge Hashed Linear Octree that reconfigures when you move. Each octree leaf is a voxel. The world is procedurally generated using 2D Perlin noise.

The octree utilizes face culling and instancing to accomplish pretty good performance in OpenGL. I have implemented LODs in order to allow for much bigger scenes and my bottleneck has quickly shifted from rendering faces to generating the Octree.

Each time the camera moves I need to reconfigure the Octree's LOD in order to ensure the viewer sees high detail near him and low detail in the distance. The system works great for small Octrees (256^3) but as soon as I go to a 1024^3 Octree, the generation of the Octree LOD takes 1-2 minutes. Even done on a separate thread it isn't enough.

I am sure there is a way to generate the Octree world without traversing the whole Octree but I could not find it.

The basic outline of how I do the Octree LOD generation when the camera moves:

  1. Start traversing the Octree at the root node

  2. For each node, check the distance of the node's center from the camera

    2.a. If the node is a leaf and the distance is smaller than the node size * CONSTANT, divide it. If it is not a leaf, traverse its children and go back to (2).

    2.b. If the node is not a leaf, and the distance is larger than the node size * CONSTANT, collapse the node if needed.

That's basically it. Because the world is procedurally generated, dividing each node means iterating its entire volume (x+1,z,x+2,z...x,z+1,x,z+2...x+1,z+1....) to determine if the 2D Perlin noise passes through the node volume, above it, or below it (This has to be part of the problem as for 256^3 nodes it takes 65536 iterations).

I know that I can improve this by parallelizing the entire algorithm, but I still feel like there has to be 1) a way to calculate LODs without entire tree traversal, and 2) figuring out if to divide the node without iterating through its whole volume 1 by 1.

Would love to get some pointers, I could not find many resources about this online.

\$\endgroup\$
5
  • \$\begingroup\$ You may be able to generate some coarse bounds from your noise function, evaluating just the top few octaves (proportional to your current depth in the octree), to quickly reject nodes that are obviously too far from the noise function to intersect it. You can also cache this information, so you don't need to re-evaluate the noise function for a chunk on every move after you've evaluated it once. \$\endgroup\$ – DMGregory Mar 19 at 13:58
  • \$\begingroup\$ @DMGregory Interesting, Got any resources I can look at? \$\endgroup\$ – Amit Assaraf Mar 19 at 14:59
  • \$\begingroup\$ No, to find some I'd just type those keywords into a search engine. If you're able to share details of your noise function, we may be able to help you find appropriate bounds in an answer. \$\endgroup\$ – DMGregory Mar 19 at 15:02
  • \$\begingroup\$ @DMGregory I use this noise function: github.com/SRombauts/SimplexNoise , specifically fractal noise \$\endgroup\$ – Amit Assaraf Mar 19 at 15:06
  • \$\begingroup\$ That belongs in your question, not in a comment. Don't forget to include the parameter values you use. \$\endgroup\$ – DMGregory Mar 19 at 15:07

Your Answer

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

Browse other questions tagged or ask your own question.