Separating Two Intersecting Spheres

I would suggest using the vector that goes from one center to the other. Evaluate the speed of both spheres along this vector through projection, and determine how much you have to move back in time for the spheres to be merely tangent (assume speed is uniform). Then, move each sphere back by its velocity multiplied by the aforementioned time.

I need a static test.
I want to know how much to move one sphere along an arbitrary direction to make it stop penetrating the other.

You don't want to choose an arbitrary direction.

You probably want to choose the direction that results in the minimum translation necessary to separate them.

This direction is the normalised delta between the two sphere centers.

The distance (D) is the sum of the sphere radii minus the magnitude of the delta. Add 0.5 * D * delta to the position of one sphere, and -0.5 * D * delta to the position of the other.

e.g.

Vector delta = sphere2.pos - sphere1.pos;
D = delta.NormaliseSafe(); // returns the original length
sphere2.pos += 0.5f * D * delta;
sphere1.pos -= 0.5f * D * delta;

That's an obvious solution, but it is wrong.



'A' shows a sphere traveling downwards, colliding with another sphere in its new position.
'B' shows the results of the suggested solution.
'C' shows the correct solution.

The sphere should be pushed back in the direction of the velocity, i.e. upwards.
Thanks anyway.

[EDIT]

Yes, I know it would be hardly noticeable in real-time, but still, isn't there a better solution?

[Edited by - mrbig on August 17, 2006 10:04:21 AM]

Quote:

Original post by mrbig That's an obvious solution, but it is wrong.

MrRowl's solution isn't wrong; it is the standard solution to the problem of resolving a discrete intersection between two spheres.

It appears though that you're asking a different question: how far do you need to move one sphere along an arbitrary vector to resolve an intersection. MrRowl mentioned that typically you want to resolve the intersection along the minimum penetration vector (which is true), and gave the solution to that particular problem.

Out of curiosity, why do you want to resolve the intersection in an arbitrary direction?

Ah - I see - I guess you didn't ask the right question (inserting the word static into the question was a bit misleading, you must admit!) :)

I guess you would form the quadratic equation:

d = f(t)

where d is the distance between your red sphere centre and your blue sphere at "time" t (t = 0 gives the blue sphere, t = 1 gives the white sphere).

Then solve to find the two values of t where d = redRadius+blueRadius. Take the minimum value of t (assuming it's real and > 0).

A common trick for this type of situation is make one of the spheres into a point and change the radius of the other one to be the sum of the two original radii. You are left with the problem of finding the intersection of a ray and a sphere.

Quote:

Original post by mrbig Yes, I know it would be hardly noticeable in real-time, but still, isn't there a better solution?

Could you explain, in detail, why my solution does not correspond to your needs?

All my solution uses is the current and previous position (or velocity) of the spheres. If all you have is the current position, there is no better solution than simply moving the two spheres along the line through their centers. If you have the previous position or the velocity, my solution works. What's the catch?

For the record, I ask the right question, you just read them wrong. :P

I asked, "how do I correctly separate two intersecting spheres?", which was too general, perhaps unclear, but not incorrect.

Therefore I clarified it in my second post:

"I need a static test.
I want to know how much to move one sphere along an arbitrary direction to make it stop penetrating the other."

The way I asked it, the problem doesn't involve any velocity or time, therefore, is static.

And assuming that Mr. Rowl was trying to answer my question, his solution IS wrong.
The attached picture shows why it can sometimes be not very plausible.

And here's the key point:
Actually, I need to resolve the collision in the direction of the velocity, but since I was talking about a static test, I generalized it as "an arbitrary direction", to avoid confusion, which I clearly haven't. :P

And finally, ToohrVyk, you quote me in a reply to another person!
See how you all got it all wrong? :P

But all that really doesn't matter.
The solution to my question (yet again) appears to involve complex calculations.
Especially considering the fact that I'm planning to approximate my objects using spherical voxels. (Yes, I know it's madness. But hell, why not try it?)
I'll stick with Mr. Rowl's standard (and inexact) solution.
It shouldn't be too much apparent, especially with the collision response generated for my voxel objects, which would draw the user's attention with its oddness.

Thanks for your help, everybody!

Quote:

Original post by mrbig See how you all got it all wrong? :P

No, I don't see how I got it wrong.

Quote:

The solution to my question (yet again) appears to involve complex calculations.

It involves solving a second-degree equation, which is taught to 12-year olds in school. I fail to see how that is "complex calculations".

Use alvaro's line->sphere solution, it's "obviously" correct (sorry ToohrVyk but whilst your solution (if I interpretted it correctly) is correct it's not "obviously" so...!) and you can get the answer from 6 million places on the internet with no trouble.

I still say I answered your question correctly the first time - you just didn't ask the correct question :) You had a very specific direction in mind - not an arbitrary one.

Ok Alvaro, so not all of you got it all wrong.
Does that really matter?
Solving 2nd degree equations 400 times per pair of objects each frame doesn't sound like a good idea to me.

Mr. Rowl, whether the direction is specific or arbitrary doesn't matter.
That way or another, there are no wrong questions, only wrong answers.

Quote:

Original post by mrbig Ok Alvaro, so not all of you got it all wrong. Does that really matter? Solving 2nd degree equations 400 times per pair of objects each frame doesn't sound like a good idea to me. Mr. Rowl, whether the direction is specific or arbitrary doesn't matter. That way or another, there are no wrong questions, only wrong answers.

Why would you have to perform this 400 times per pair, surely once would be enough? The trick to fast collision detection isn't so much in the speed of the intersection test itself but rather in the method you use to cull the number of tests you have to perform anyway. Even so, solving such an equation isn't such a costly operation. If you have many objects what you want to do is use spatial partitioning and/or take advantage of temporal coherence in order to make the time taken as linearly dependant on the number of objects as possible rather than being an n squared process which results from brute force. I recommend you look into collision culling methods such as 'sweep and prune' and 'quad trees' before you start worrying about saving a few cycles on the actual narrow phase intersection test used.

And for the record whether the direction is specific or arbitrary is far from insignificant. In fact I'd say that is the sole reason why you perceive one answer to be correct and the others wrong.

There we go again... Read my posts!
I said I want to approximate my objects using spherical voxels.
400 tests per pair might be a bit too much, but I'm always prepared for the worse! xD
Anyway, looking at my rating I can clearly see where this is all going, so thanks everybody, and good day.