Stone Devlog: Octree Subdivision

The last couple months have been a bit slow, but I wanted to drop a quick post to show where I'm at. The long and short of it is that I've got a working octree implementation going, with adaptive subdivision dependent on the complexity of the surface being contoured. Check this out:

Side view of the octree generated for a rotated cube

I'm using a pretty basic heuristic for the subdivision. First I sample the signed distance function at the center point of a given cell. If the distance at the center of the cell is more than half the diagonal of cell, I know a vertex will not be placed inside the cell and bail out. If the distance is less, I sample the eight corners of the cell and use trilinear interpolation to approximate the value at the center. Then, I compare the sampled distance to the interpolated distance. If the difference between the values is greater than a set accepted threshold, I subdivide and repeat for each of the new cells. The results can be seen in the image above.

It's certainly not perfect, but I think it does the job. You can clearly see the edges of the cube defined by the higher resolution of the tree. My next step will be integrating this into a new implementation of Dual Contouring. Finding neighboring cells becomes a lot more complex in an octree compared to a uniform grid, so that will be a good challenge to overcome. After that, maybe we'll see how this octree holds up against Cubical Marching Squares. Stay tuned for that.