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

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.

• Are all the spheres the same size? I guess not otherwise you could just choose the nearest. I don't think you can do it without iterating over all of them at least once – Malrig Feb 27 '16 at 21:19
• Indeed, the problem here seems to be two-folded: 1) is the spheres are not of the same size, than we would need to use the equation that maps back distance from sphere center to desired value; 2) no, it's impossible to do that analytically, i.e. without iterating trough the spheres. But yes, there are ways to make the looping more efficient than one loop trough all to check point inside plus another loop trough all comparing values. – MAnd Feb 27 '16 at 21:56
• Do it any way you can, and see if it's fast enough. If it is (it may be!) then hooray, move on. – david van brink Feb 27 '16 at 22:29
• Yeah, the spheres are assumed to be different sizes. I asked this question just in case there was some crazy graph theory stuff that could make it a bit more efficient, but I'm a bit relived that it's just iterating through as I wasn't looking forward to implementing something really complex. – JamEngulfer Feb 28 '16 at 2:02
• @JamEngulfer A quick question that might allow me to give you a couple of suggestions: do you have to find out the "better sphere" where the points only once or many times (e.g. every frame, every X seconds, always when player move, etc)? – MAnd Feb 28 '16 at 2:59

## 2 Answers

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.

• Thanks for giving the pseudo-code for the algorithm! This seems like the best solution that I can implement. – JamEngulfer Feb 29 '16 at 10:14

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.

• I know you are going to have questions. Particularly, "Ok, the first shader finished. How many spheres are left?" That's an answer the second shader will need, too. When you get to that point, I'll revise my answer based on your progress up to that point. Those are details about "how to implement a ComputeShader" and not, "How best to process a bunch of spheres against a point". – Jon Feb 28 '16 at 22:04
• Please leave a comment indicating your overall level of experience with multi-threading and the caveats that accompany it. – Jon Feb 28 '16 at 22:07
• This looks like an ingenious solution to the problem. The only issue is that the calculation will be running on a server, so I don't reliably have access to a GPU/shader processor, so the solution can be CPU based only. – JamEngulfer Feb 29 '16 at 10:06
• @JamEngulfer, ComputeShaders were added somewhat recently. With an eye toward the future, I would not be surprised if typical server minimum hardware specs begin to include GPU's very soon, even if it's just a low-level Quadro (nVidia business class). Quadro's are very "recommended" in most of Autodesk's CAD software. Where Battlefield4 was limited to 30Hz tick-rates for a loooong time (because of the servers), I expect BF5 will use server-side enhancements like this to start closer to 60Hz. A $100 GPU is nothing for a$50/month server rental. I think it's just that no one's done it yet. – Jon Mar 3 '16 at 18:12