For the past few months I've been working on Voxel Terrain for Ultra.  I started by creating an octree whose parent node encapsulates the bounds for the entire terrain and must be a perfect cube with dimensions that are a power of two.  This ensures all child nodes can be neatly subdivided.  If a more rectangular terrain is required the octree creates more than one parent node to make up the rectangle.

The next step was to subdivide the parent node to a level where each node would represent a portion of the terrain called components (or chunks).  Each component has the potential to be a model with one mesh that forms the surface.  Here the terrain dimensions are 2048 x 1024 x 2048 which are composed of four parent nodes each with a size of 1024x1024x1024.

The next step was to create a recursive function that would start by checking each component to see if it intersects the surface, if it does it will subdivide it adding eight children which are then also checked.

The intersects_surface() function is a custom function and must return true if the current nodes needs subdividing, it also sets the current nodes voxel_index which says how the node is to be rendered later on.  There is a few issues with this technique though that I need to re-think.

If I voxelize a large plane, all is well.

However adding some noise to the mix results in some gaps.

Upon closer inspection it turns out that even though a node's corners may all be inside or outside the surface, it's child node may yet still represent the surface.  I guess that's why we use noise - because it's random!  Below shows a components node has the lower four corners outside of the surface, however if it were subdivided further at some point the surface will intersect its children.

A way around this is too just subdivide every node until I reach the surface depth (or voxel size, usually 1m cubed) needed.  However this takes time and uses a lot more memory!  Other work arounds may be to test all nodes at the lowest depth required (depending on LOD) and then cache the result and work my way back up to the root node, creating parent nodes for a collection of eight nodes only if they represent a surface, and then deleting those who are complete in air or in solid ground.  Seeing as I'm using multiple threads and the surface_intersection functions is very fast (at least for now) this might be the best and only choice.

I did toy with the idea to predict whether or not a node intersects a Perlin Noise sample based on it's frequency, amplitude and octaves and what values each of its corners were... but, yeah.  Maybe.

Here I tried it in 2D but am stumped if I can take the idea any further.  You can see each corner is a negative number so by the standard test I'm using the node shouldn't be subdivided, yet clearly if it were it's children would represent some of the surface (shown in white).

Who knows, maybe this has been solved already by someone a lot smarter than I am or large amounts of time and memory is just what voxel terrain does?  I know it's not what a SpiderPig does...