Building an Octree for terrain generation

Question

I've previously implemented marching cubes/tetrahedra to render an IsoSurface. It worked (YouTube), but the performance was dire as I never got around to implementing variable Level of Detail based on view distance (or even removing old, distant chunks).

I decided to have another go and do it properly this time. I've started by creating an OctreeNode that works as follows when Build() is called.

• If the chunk is too small to build, return immediately.
• Work out if the surface passes through this chunk's volume.
• If so, then decide if we want to raise the LOD (because the camera is close)
• If so, then spawn 8 children and call the same process on them
• If not, build the mesh using the current node's dimensions

Some PseudoCode:

OctNode Build() {
    if(this.ChunkSize < minChunkSize) {
        return null;
    }
    densityRange = densitySource¹.GetDensityRange(this.bounds);
    if(densityRange.min < surface < densityRange.max) {
        if(loDProvider.DesiredLod(bounds)² > currentLoD) {
            for(i 1 to 8) {
                if(children[i] == null) {
                    children[i] = new OctNode(...)
                }
                children[i] = children[i].Build();
            }
        } else {
            BuildMesh();
        }
        return this;
    }
}

¹ As well as returning density at a point, the density source can determine the possible density range for a given volume.

² The LoD provider takes a bounding box and returns the max desired LoD based on camera position/frustum, user settings, etc...

So... This all works fairly well. Using a simple sphere as the Density source, and showing all nodes:

And just the leaves:

However, there are a couple of issues:

• I have to define the initial bounding volume (and the larger it is, the more processing I need to do)
• At the root of the tree, I have no idea how deep the leaves will be, so my LoD numbering starts at lowest quality (root) and increases as chunks get smaller. Because LoD is now relative to initial volume, it's not much use when I want to do things at specific sizes / qualities.

I've thought of a couple of options but both seem flawed:

• Maintain a collection of Octrees and add/remove depending on distance. Can't see how I'd mesh across nicely¹, plus I'd need a list of known-empty nodes, especially if I want arbitrary 3D surfaces (to avoid re-calculating empty volumes repeatedly)
• Add a parent Node to the current root, then add seven siblings for the original node. This would work and be on-demand but it seems complex to shrink back down sensibly as the player moves through the landscape. It would also make LoD numbers even less meaningful.

¹ [In clarification to Q below] At present, if 2 physically adjacent nodes in the tree are at different LODs, I have some code to coerce the verts such that there's no seam when the meshes are generated. I'm able to do this by knowing the the density for multiple of surrounding nodes. In a scenario where I have 2 independent octrees side-by-side, I'd have no easy way to retrieve this information, resulting in seams.

What's an optimal way to approach this?

Answer 1

I'm not sure I'm answering the exact question, so I'm going answer in segments, and feel free to reply in comments if there's a misunderstanding about the particulars of a specific question.

I have to define the initial bounding volume (and the larger it is, the more processing I need to do)

This doesn't seem like it should be the case. Since the octree increases in granularity exponentially, adding a few levels at the top should be a very small net increase in performance hit.

At the root of the tree, I have no idea how deep the leaves will be, so my LoD numbering starts at lowest quality (root) and increases as chunks get smaller. Because LoD is now relative to initial volume, it's not much use when I want to do things at specific sizes / qualities.

If you fix your root octree to some "large enough value" then "LoD relative to initial volume" shouldn't be an issue. And as mentioned above, I don't think having extra level at the top will impact overall performance.

Maintain a collection of Octrees and add/remove depending on distance. Can't see how I'd mesh across nicely, plus I'd need a list of known-empty nodes, especially if I want arbitrary 3D surfaces (to avoid re-calculating empty volumes repeatedly)

As I understand it, this proposed solution is about lowering LoD when moving away from a previously detailed area. I figure it should look very similar to the "increasing LoD" code path:

if (loDProvider.DesiredLod(bounds) <(is a lot less than)< currentLoD) { 
    for(i = 1 to 8) { 
        children[i].Destroy();
    }
    BuildMesh();
}

Then, you're not spending too much time checking distant nodes because you can rely on the fact that while far away, there aren't too many "active" nodes, since all the higher-resolution nodes will have been removed.

---

Assuming small nodes are rock-scale, that would mean potentially dozens if not hundreds of levels as I travel across a continent

I think the logarithmic scale of the octree makes it still feasible. If your top level is 1,000,0000,000 m wide (this would be 25 times wider than the real Earth, and with 625x the surface area) and your lowest level bits are 10cm across, that's 32 levels in the octree, which is probably manageable enough. If you wanted a planet 100 times wider than the Earth (and with 10000 times more surface area), that's only an additional 3-4 levels in your octree. At this point it would take a player hundreds of years to walk across the the world, and if you use naive floating point math the world will be accumulating precision errors.

Maintain a collection of Octrees and add/remove depending on distance. Can't see how I'd mesh across nicely¹, plus I'd need a list of known-empty nodes, especially if I want arbitrary 3D surfaces (to avoid re-calculating empty volumes repeatedly)

Isn't this fundamentally equivalent to having the billion-km-wide octree but keeping a list of pointers to every, say, 1km block? Then "meshing across" would simply be relying on the 2km-size nodes. Keeping a local reference to each mid-level "large block" also keeps you from having to iterate through the top-level nodes, if you're worried about the "possibly dozens of additional octree levels"