Test if SDF surface is inside AABB

[SpiderPig]

I wonder if anyone here has heard of a way to do this?  I'm sure it's possible somehow...

In voxel terrain the 8 corners of a node are tested against some user function that defines a surface.  A Signed Distance Field is a perfect example of this.

Each corner tests it's distance to the circle's centre and subtracts the radius to get the distance to the circles surface.  If the corner is above the surface, it returns a positive value.  If it is below, it returns a negative value.  If all corners are above the surface, the node is discarded because it doesn't represent the surface.  It's the same result if all the corners are below the surface.

Thus to check if a node needs subdividing further or if a mesh should be made inside of it, a bit flag is set in an unsigned char that corresponds to the corners index.  So a node has a voxel_index which ranges between 0 and 255.

0 means all corners are outside the surface.  255 means all corners are inside.  Anything between and a marching cube table is looked up to see how a triangle mesh should be created inside the node.

Right now I do not use nodes with a voxel_index of 0 or 255, because both of these cases understandably do not make any triangles.

However, in the 2D example below there are a few cases where a voxel_idex of 0 still needs to be subdivided (it won't represent a mesh at all, because the surface doesn't intersect an edge) but it does need to be subdivided to a lower node size because chances are high that some of its children will represent the surface.

Finally I reach my question - the green squares are cases where the node should be subdivided because the circle intersects the edge or is inside the square.  However all corners are outside the surface in all cases so the voxel_index is 0 and is discarded (creating holes in the final mesh).

The black lines are distances to the surface and are all positive values.  I wonder, knowing the corners positions and the distances to the surface can it be determined if the surface exists within the square?  I was thinking if I get the average distance and it is below some threshold, maybe the radius of the AABB (distance from the centre to any one of the corners)?  I think this could give false positives as it's kinda checking it against a sphere rather than a cube...

Curious if anyone has any input.  I will be thinking on this for a while.

[SpiderPig]

Each corner distance isn't a distance to the same point on the surface either, pretty sure it's just the closest point, whatever that may be.

But - I'm pretty sure all distances will go through a common point - the sdf's origin.  In this case the circles origin. 🤔

So maybe if I get a vector from the corner to the SDF origin; multiply it by its distance to the surface and the add it to the corner's position I could then do a simple check to see if that surface point is inside the nodes bounds or not.  If the result is true for any of the 8 corners then that would be problem solved.

Sounds too easy though. 🤔

[Josh]

This is just a sphere / bounding box intersection test, right?

[SpiderPig]

Kind of, except I only have the distances from each corner to a surface.  I need to turn those 8 distances into 8 points, or just one.  Then I can check against the bounding box.

[SpiderPig]

A better description of what I'm looking for might be "AABB intersection with a Signed Distance Field".

[SpiderPig]

4 hours ago, SpiderPig said:

But - I'm pretty sure all distances will go through a common point - the sdf's origin.  In this case the circles origin. 🤔

So maybe if I get a vector from the corner to the SDF origin; multiply it by its distance to the surface and the add it to the corner's position I could then do a simple check to see if that surface point is inside the nodes bounds or not.  If the result is true for any of the 8 corners then that would be problem solved.

Sounds too easy though. 🤔

My epic MS Paint skills tell me that the rays would not go through the origin.  They would all meet at different points and even their intersection points would (in this case) say the surface is outside of the bounds.

[Josh]

FIrst step is to test AABB/AABB intersection, that will eliminate 99% of your cases.

[SpiderPig]

...did you know that never crossed my mind to encapsulate the whole SDF into it's own bounds.  

[SpiderPig]

After the quicker AABB test I might be able to use the circle (or sphere) intersection points. 

[Josh]

It depends on how precise you need it to be. Ultra never does a real sphere-AABB test because it's too expensive. Usually it starts with a sphere/sphere test and then moves onto a box/box test in some cases. The AABB::IntersectsPoint method takes an optional radius, but it just treats the point like a box.

[Josh]

There is also an Aabb:DistanceToPoint method, which I believe can be used for a perfect box/sphere test. If the distance to the point is less than the sphere radius, then the two intersect.

[SpiderPig]

Thanks I reckon they'll come in handy.  I think what I really need to do is ray-march the surface so I can get a point that is on the surface and then I can test that against the node bounds.  For now I have taken a simpler approach which is to average out all the corner distances and then test if the result is less than the radius of a sphere that enclosures the bounds of the node.  It should solve the problem at the cost of creating a few nodes that aren't actually needed.

[SpiderPig]

I believe I have found a solution.   If the node's corners are all above OR all below a surface (so a voxel index of 0 or 255) then the corner with the shortest distance is retrieved and it's distance is tested against half the radius of a sphere that encompasses all of the nodes corners (the distance from one of the corners to the centre of the bounds).  This way it ensures that the surface is not within the bounds of the node.  It creates nearly double the amount of nodes, and I dare say 30 to 40% of them don't represent the surface, but it fixes the gaps in the mesh and it's still fast.  Exploring the 4k terrain only uses about 100k nodes so it's not bad at all.  Fingers crossed it holds up!

[SpiderPig]

Thanks for you help too Josh.  Your pointing out what should have been obvious to me pushed me in the right direction.