Bounds Queries for Simplex Noise Function

Question

How do I construct a Bounds Query for 3D Simplex Noise?

---

[This is more or less a follow-up to my last question]

Simply put, for an arbitrary octree node (cube) in my volume (a section of Unity3d world space), I am trying to find out whether there is a surface inside the octree node (to determine if I need to subdivide my octree node). As explained in the other question, I cannot rely on edge-crossings to detect if a node contains a surface or not. Right now, I query each Vector3 integer coordinate in my volume (appropriately scaled by ~1/50) for a simplex noise value.

I was directed to bounds queries, where instead of querying for a specific point by supplying specific coordinates, I query for a [min,max] of the function in a certain volume (my octree node). If min > 0 or max < 0, I need not subdivide, because the surface is outside my node (the surface intersects edges between vertices with different polarity/signs).

What (I think) I understand so far:

• At every simplex vertex, the value is 0. This means that my minimum is not greater than 0, and my maximum is not less than 0. Turns out, because of my scaling, a single octave of simplex noise usually just puts 2 simplex vertices in my volume. Does this mean that my bounds query will require I subdivide every node that contains one of these simplex vertices? This is obviously wrong, else I would be subdividing infinitely...
• If I do not have any simplex vertex in my node, I still have to find the vertices' unit vectors of the simplices my node exists in. Then, somehow, I decide on a min/max. I suppose, it would come down to the nature of the simplices I am in...If they both give positive/negative values, then my bounds query would pass, and I wouldn't need to subdivide...right? But how do I calculate this?
• To construct the bounds query, I must find the pseudo-random unit vector assigned to each simplex vertex found in my node. This allows me to view the range of possible values in each simplex found in the node.

(I hope that all wasn't too confusing)

Despite/Because all that, I can't for the life of me think up any algorithm. What am I missing?

If there are any resources on this, please point me to them! I've googled about every keyword-loaded phrase I can come up with, but found nothing.

Answer 1

The strategy we will follow is bounding the derivative, as the technique of splitting the query regions is very complex and probably very slow. Consider first a 1D function f, for which everywhere, |f'| < 0.3. We are given that f(3)=-2. What is a bound for f over the interval [1, 5]? Looking at the derivative bound, we have:

| df |
| -- | < 0.3
| dx | 

So, abusing calculus:

|df| < |dx| * 0.3

Thus if |dx| < 2, then |df| < 0.3 * 2, and the range is thus [-2-0.6,-2+0.6] = [-2.6,-1.4]. Now of course, this is conservative: unless the derivative actually is 0.3 throughout the range, f will not actually be that large.

So how does this help us? Well we can just sample the simplex noise at the center of our query region, and then based on the "size" of that query we can compute how much the function is allowed to vary away from that central value.

The size we are looking at is the distance from the center to a corner. Now we just need to bound the derivative. We could do this analytically, but it's kind of a pain. (Actually, its a huge pain.) An easy way to do this is to just compute the gradient at a bunch of places (say, 10,000,000 random points) using finite differences, take their lengths, then add about 5%, and call it a day. You only need to do this once. The important bit is we are using this one number as the derivative bound over all of space.

Note that this method involves performing the point query, then doing a simple distance calculation and a multiply, so it is very fast. However, it is quite inaccurate, and will result in more splitting that will eventually be empty. Remember to limit the calculated bounds to the min and max possible values for your noise. Very large queries would otherwise result in huge ranges.