I'm trying to implement a voxel-based terrain generation system in Unity3d (C#). I have successfully implemented a uniform 3d grid system, and have extracted the isosurface out using Marching Cubes and Surface Nets algorithms.
I quickly bumped up against the inherent issues in representing all space with a 3d grid. Much of this space was either above or below the surface, and I turned to space partitioning with octrees, as it didn't seem too difficult. One of the great things about octrees is that octree nodes that that don't have edges intersected by the surface don't need to be split again.
I researched, and found a couple resources to construct my code. One is Volume GFX, and another is the original Dual Contouring paper by Ju et al. My edge-checking is done by the Marching Cube's checking from Paul Bourke's code. If the "cubeindex" is either 0 or 255, then no edge is intersected, and the octree node does not need to be split.
My Octree generation code works for something like a quarter-sphere, where the surface features are extremely normal:
As seen in the picture, only octree nodes containing the surface are subdivided. Working great.
Now, however, when we move to something more complex, like Unity3d's PerlinNoise function: GASP! What's that hole doing in the mesh at the lower-right corner? Upon closer inspection, we see the octree didn't subdivide properly (red lines highlighting the offending node's dimensions): This turns out to be the same issue Jules Bloomenthal highlights in her paper on polygonization, page 10, Figure 10. Traditional methods at generating top-down octrees ("Adaptive Subdivision"), are sensitive to fine surface features relative to the size of the octree node.
X-------X | | | | <- Node X--/\---X X's - tested values, all outside of the surface! / \ <- surface
The surface breaks the surface, but comes back down before it goes over a vertex. Because we calculate edge intersections by looking at the signs at the two vertices, this does not flag the edge as crossed.
Is there any method to determine if these anomalies exist? Preferably, the solution would work for more than just the Unity3d noise function, but for any 3d noise function (for cliffs/overhangs/floating islands, etc).
Thanks to Jason's awesome answer, I was able to answer my own questions I asked (in the comments under his answer). The issue I had was that I didn't understand how I could create a bounding function for trigonometric functions (sine,cosine,etc) due to their periodic nature.
For these guys, the periodicity is the key to bounds functions. We know that sin/cos reach their extrema values at a set interval, specifically every
π/2. So, if the interval we are checking contains any multiple (cos) or half-multiple (sin) than 1/-1 is the certain extrema. If it doesnt contain a multiple (i.e. the interval
[0.1,0.2]), then the range is simply the values of the function evaluated at its endpoints.
If the above doesn't make sense, check Jason's answer to my comments.