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:
Start traversing the Octree at the root node
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.
