Efficiently calculating best nearest sphere from a point in 3D space

Question

I have a point in 3D space and a number of spheres (anywhere from 0 to thousands) at random locations in said space.

Each sphere has a property that falls off in a smooth gradient from the centre to the edge.

The point could be inside between 0 and all of the spheres.

How do I calculate the sphere that the point is inside that has the highest 'value' at its current position?

I was wondering if I could get away with just looping through every sphere and adding the ones the point is inside, then looping through those and testing the value. However, the calculation for this needs to be calculated 'instantly', or at least with minimal delay, so I'm wondering is that is too inefficient.

Answer 1

You said that the value you describe falls off in a gradient from the center of the sphere. So I suppose it achieves its minimum (e.g. zero) when reaches the sphere boundaries. In that case, there is a very simple way of making your problem easier than using 2 loops.

I guess you already know how to check if a point is inside a sphere, but for the sake of completion, I will quickly summarize it. Let R be the radius of the sphere, C be its center and P be the point whose position is being checked. So:

• if Distance of P to C is greater than R, then P can't be inside the sphere;
• if Distance of P to C is smaller than R, then P is inside the sphere;
• if Distance of P to C is equal R, then P lays over the circumference of sphere.

That said, let's get into your specific setting. In terms of pseudo-code, according to your question you wondered if there was a better way than doing the following:

float minvalue = 0; //if your value can go below zero, alter this with the minimum it can achieve
int bettersphere_index = null; //declares the variable that will hold the index of the better sphere, if any (if P is not inside any sphere, than this variable will retain the value you define here). If not initialized as `null`, then it should be initialized always with value below zero.

//this loop goes trough all spheres to check the ones that P lays inside of:
for(int i=0; i<listofspheres.Length; i++)
{
    //check whether point P is within sphere and, if yes, save the sphere
    float distance = Distance(P.transform.position , listofspheres[i].transform.position); //calculates the distance between P and the center of current sphere being evaluated
    if(distance < listofspheres[i].radius) //performs the P in sphere test
    savedspheres.Add(listofspheres[i]); //add the current sphere to a list of saved spheres that will be further evaluated later in the second loop
}

float biggestvalue = minvalue; //declare the variable that will store the greatest value
//this loop goes trough all saved spheres to check which is the best match, as per the definition of your question:
for(int j=0; j<listofspheres.Length; j++)
{
    //check which is the better sphere, as per your definition:
    float distance2 = Distance(P.transform.position , savedspheres[i].transform.position);
    float currentvalue = MapDistanceFromCenterToValue(savedspheres[j]); //this represents your function that converts the distance from sphere center to the desired value
    if(currentvalue  > biggestvalue ) //this is the part that makes the comparison across spheres
    {
        biggestvalue = currentvalue; //update the biggestvalue found so far
        bettersphere_index = j; //update the index of the better sphere found so far
    }
}

Well, you can't achieve what you want without iterating trough the spheres, i.e. there is no analytical solution to such a problem. However, you don't have to use two loops to achieve that. And you can also drop one of the distance calculations and use SquaredDistances instead of Distances for the P-in-sphere tests. These minor things can result in a significantly more performant way of achieving what you want. In pseudo-code:

float minvalue = 0; //if your value can go below zero, alter this with the minimum it can achieve
int bettersphere_index = null; //declares the variable that will hold the index of the better sphere, if any (if P is not inside any sphere, than this variable will retain the value you define here). If not initialized as `null`, then it should be initialized always with value below zero.
float biggestvalue = minvalue; //declare the variable that will store the greatest value

//one single loop trough the spheres:
for(int i=0; i<listofspheres.Length; i++)
{
    float squareddistance = SquaredDistance(P.transform.position , listofspheres[i].transform.position); //calculates the SQUARED distance between P and the center of current sphere being evaluated. See: https://stackoverflow.com/questions/3693514/very-fast-3d-distance-check

    if(squareddistance < listofspheres[i].radius*listofspheres[i].radius)  //performs the P in sphere test, using squared distance - which, of course, demands that R needs to be squared too
    {
        float distance = Math.Sqrt(squareddistance); //just calculate the real distance, i.e. applying the squareroot, when it will be really needed, which means when you already know P is inside sphere.
        float currentvalue = MapDistanceFromCenterToValue(distance); //this represents your function that converts the distance from sphere center to the desired value

        if(currentvalue  > biggestvalue ) //this is the part that makes the comparison across spheres
        {
            biggestvalue = currentvalue; // update the biggestvalue found so far
            bettersphere_index = i; //update the index of the better sphere found so far
        }
    }
}

In the end, the variable bettersphere_index will hold the index of the sphere you wanted to find out (i.e. the index of its position within the listofspheres array). If bettersphere_index ends up being null (or equal the below zero value you defined at the beginning, before the loops), you know that point P was not inside any sphere in the scene.

Notice that, as previously pointed, I used SquaredDistances instead of Distances to test P within sphere. That's a very common simple optimization, see more about it here: Very fast 3D distance check?. Lastly, it means that if by any chance you can adapt your function that converts distance from center to custom value, to use SquaredDistances instead of Distances, then you can also avoid doing the square-root calculation in the code and have yet more performance gains.

Answer 2

The basic problem you are facing is having to multiply iterate and the cost of doing so each frame. (Apologies if my DirectX lingo confuses)

You feel that the only option available to you is to:
Iterate through and evaluate every sphere against the point, every frame.

But, what you'd really prefer to do is:
Iterate through and evaluate every sphere against the point, every frame, simultaneously.

Good news! You can easily accomplish that by moving your current algorithm to a ComputeShader. Good news; doing so is rediculously easy!

Right now, you index the "current sphere" by a for(i=0; ...). With a ComputeShader, we can Dispatch a fixed number of threads or thread groups based on how many spheres there are, and index the sphere list using SV_ThreadID. Each thread, simultaneously evaluates your falloff formula against the point. If we start off with an empty AppendBuffer, and only Append where the falloff is non-zero, we end up with a list of only the spheres that influence the point, as well as the calculated influence for each.

At this point, you can retrieve the "instantly" filtered list and iterate it on the CPU. However, since it was so easy to implement the first, why not just create a second one:

This one uses the previously created AppendBuffer as a ConsumeBuffer. This will only contain a couple of variables like BestInfluence and BestInfluenceSphereIndex, initialized to their most-negative values. We'll use a single thread and a plain, old, for loop that will Consume() each influencing sphere from the buffer, and compare it to BestInfluence. If BestInfluence is lower, replace both with the current sphere.

At the end, you are left with the "best nearest sphere from a point in 3D space", which you can then read back on the CPU. This method has approximately "fixed" performance. The first ComputeShader will take about the same time to finish, regardless of sphere-count (thread-count). You say you won't be calculating this every frame, but what you mean to say is that it's impossible to do so every frame and still maintain a good framerate. Well, now you can do both!

The most important factor here, is that the CPU only has to tell the GPU "go". The CPU can continue on, updating your camera, objects, etc. while the GPU crunches the spherical falloff. You're doing more than one thing at a time and one of those things is operating on all of its' inputs at the same time.

---

The new shaders can feel like scary, intimidating beasts that should be avoided at all costs. Spend a good week learning each of them now, so that your future designs can include their use. You'll find that each one, approached individually, is actually not that hard to understand. If you are successful implementing the ComputeShaders described, you'll have expanded your limits exponentially. When you are able to fully utilize every shader stage, you can, then, combine them and discard any previously perceived limitations.