Archived

This topic is now archived and is closed to further replies.

Acurate Response to Sphere-Sphere Intersection

This topic is 5152 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

Ok, nice simple collision response i can do but i have got into a little bit of a situation trying to do things properly. My Collision Detection tells me that two spheres have collided. Fair enough. But the spheres are intersecting, inorder to get an accurate collision response i need to backtrack to find the exact point of contact. so for each sphere: Point at contact = Current point - Velocity * t; the problem is isolating the value of t at which the collision occurs. There are 3 unknowns, Point of contact for each sphere and t. The above equation can be used twice (once per sphere) but i still need another equation to solve them simultaneously. Anyone know how?

Share on other sites
If you know the position of each sphere at the momment they intersect you can equal the two sphere-equations to get a point that satisfies both equations.

[edited by - owl on January 13, 2004 6:25:21 PM]

Share on other sites
Ok slightly the wrong end of the stick. Due to the time steps you step over the actual moment when the spheres touch, leaving the spheres overlapping each other, i need to find the point of initial contact.

I have drawn a diagram to illustrate my problem.
Diagram

[edited by - aleks_1661 on January 13, 2004 6:54:41 PM]

[edited by - aleks_1661 on January 13, 2004 6:55:08 PM]

Share on other sites
you''ve got to solve a second order equation.

First, you need to make one sphere relative to the other (compute the relative velocity of sphere2 to sphere1), and you can use a ray-sphere intersection test. If a ray that intersects a sphere of radius (r1 + r2) is equivalent to a sphere of radius r1 colliding with a sphere of raduis r2.

ray equation
D = (V2 - V1)
O = (P2 - P1)

P = O + D.t

sphere equation
r = r2+r1

P2 = r2

substitute P with (O + D.t) into the second equation and it gives

(O + D.t)2 - r2 = 0

equivalent to a second order equation
a.t2 + b.t + c = 0

where

a = D2
b = 2.(D.O)
c = O2 - r2

to solve the second order equation a.t2 + b.t + c = 0

d = b2 - 4.a.c

if (d < 0.0f)
no intersection

t0 = (-b - sqrt(d)) / 2.a
t1 = (-b + sqrt(d)) / 2.a

you find the first positive between t0 and t1, and that will give the point of collision.

if none are positive, then it means that you need to backtrack the sphere (use negative number closest to 0)

t will be the time of collision, then you can move both sphere at that time

you can use the same principle with a cylinder and a sphere using the equation

L is the direction of the cylinder
r = rcylinder + rsphere

(P x L)2 = r2

Share on other sites
You are a Guru Oliii, Thanks. Quadratic Equations, euuuuuu!!!!

When i finished school I didnt realise i would actually need to use them.

For this problem, i thought there would have been an easy answer. Though thinking about it that is the right approach because the spheres could touch a number of times in that period, I suppose that in most cases i wil only find one instance. Its a shame i have to use sqrt though.

Share on other sites
quote:
Original post by aleks_1661
For this problem, i thought there would have been an easy answer. Though thinking about it that is the right approach because the spheres could touch a number of times in that period, I suppose that in most cases i wil only find one instance. Its a shame i have to use sqrt though.

This is a pretty easy answer when it comes to collision detection... its nice and clean, no need to perform some kind of numerical technique. And what is wrong with the sqrt function?

Share on other sites
Yeah, this is one of the classic problems of col det. It's easy peasy

you don't need to worry about sqrt. You only perform the square root if the spheres are on a collision path (or already colliding in your case), else 'd' becomes < 0 and you exit early in this case. There is a more goemetrical approach to the problem (ray-sphere intersection), but I can't remember it. It relies on trigonometry, if it makes you more comfortable.

[edited by - oliii on January 14, 2004 4:06:27 AM]

Share on other sites
I was only joking, the answer is cool. and to be honest a single sqrt is probably better than the sin/cos etc needed for a trig answer.

Now i know this is probably getting advanced, but does anyone know much about what to do when objects are at rest and stacked on each other?

Currently i have two spheres and a plane, the two sphers are positioned one above the other and they land on the plane in a stack. the only problem is that once stationary the top sphere slides down into the bottom sphere. I have programmed collision detection/response (not with the piece above, im still working on that) but i dont think i know how to use it in a proper physics system. Currently I perform detection and response between teh spheres and then with the plane. I can see that if i have more objects i would need some way of recording the collisions, sorting them chronologically and then executing responses, but even then, what if the response to one collision causes another collision like when you break in pool? or a newtons cradle?

[edited by - aleks_1661 on January 14, 2004 7:10:48 AM]

Share on other sites
usually, you don''t bother about that. You just provide an impulse, which changes the sphere velocities, and check for collisions again. It''s far from perfect, but it''s either that, or solving a set of linear (I think differencial also) equations for solving contacts. It''s called on LCP problem, and it''s the way to solve simultaneous contacts.

if you don''t use it, the objects will jitter, but it''s the price to pay.

If you sort collisions by time, you have to be careful with systems like "2 balls on top of each other and a plane". you can potentially run into an infinite loops, as the objects will collide indefinitely, then time of collision will decay to 0 exponentially, but never hit 0. That''s the theory anyway. A couple of cheats.

- You can run a maximum number of iterations, and if reached, force the sphere to have 0 velocity.
- If the sphere velocity reaches 0, stop collision tests.
- you can check if the last 2 or 3 collision planes found previously on an object completely enclose an object, if so, set it''s velocity to 0 and stop checking for collisions
- you can detect collisions that happened simultaneously (in a small time range), calculate the constrain from the planes
- for one plane (the usual case), the ball cannot move towards the plane
- for 2 planes (like a groove), the ball cannot move towards the line defined by the intersections of the plane
- for 3 planes (like a dip), the ball should move upwards from the intersection point of the three planes,
- for more planes, reduce them to the best 3 plane candidates
- and if the planes don''t intersect, you need special cases.

this becomes quite similar to an linear system of equation, which might be good to implement, as an exercise.

note : the geometrical solutions is trig, but mostly pythagor stuff, no sines or cosines. it''s got similarities with the equation solving I propose, but probably easier to visualise.

Share on other sites
Ok I have a problem in the above equation,

-------------------
equivalent to a second order equation
a.t2 + b.t + c = 0

where

a = D2
b = 2.(D.O)
c = O2 - r2
--------------------

Now D and O are Vectors ( or a point and a vector). is D.O a dot product or cross product?

Share on other sites
sorry, I misunderstood the problem.

That would happens when the time of collision is slightly negative. in that case, if ''c'' is less than 0.0f in the equation, the spheres are overlapping, and the time calculation will return something < 0.0f.

So, if ''c'' < 0.0f, catch it as an overlap collision, and push the spheres apart, so sphere2 is at the surface of sphere1.

float overlap_depth = r - O.Magnitude();
Vector OverlapNormal = O / O.Magnitude();

sphere1.position -= OverlapNormal * overlap_depth * 0.5f;
sphere2.Position += OverlapNormal * overlap_depth * 0.5f;

the same applies to sphere/plane collision, if you do a time-based collision detection (let''s call it a swept volume test). If sphere intersects plane, move it away from the plane so it is on the surface of the plane.

also, if you find (D * O) > 0.0f (''*'' is dot product for me), you may want to cut the collision test early, or you could have a build up of energy, of the spheres could get entangled or ''sticky'' (if you reflect velocities).

Share on other sites
I have come up with something

CP1 and CP2 - Position of Spheres at first contact
P1 and P2 - Positions of Spheres at end of timestep, where
they were intersecting
V1 and V2 - Velocity of spheres
t - time of first contact.

// Now by backtracking the positions by t the collision point
// can be found, but these two equations leave 3 unknowns.
// CP1, CP2 and t, therefore we need another eqn to solve them
CP1 = P1 - V1.t
CP2 = P2 - V2.t

// the sum of their radii is the same as the distance between
// the spheres
R1 + R2 = |CP1 - CP2|

// substituting ( | | = magnitude or length of the vector )

R1 + R2 = |(P1 - V1.t) - (P2 - V2.t)|
--------------------------------------

can this be solved? or am i just being dodgy!! :-)

EDIT -----------------------------------------------

Ok May have solved it:

R1 + R2 = |(P1 - V1.t) - (P2 - V2.t)|

R1 + R2 = |P1 - V1.t - P2 + V2.t|

R1 + R2 = |P1 - V1.t - P2 + V2.t|

R1 + R2 = |P1 - P2 - t(V1 - V2)|

0 = |P1 - P2 - t(V1 - V2)| - (R1 + R2)

|t(V1 - V2)| = |P1 - P2| - (R1 + R2)

t = |P1 - P2| - (R1 + R2)
------------------------
|V1 - V2|

Is that right? if so then now i can work out t, which would allow me to work out CP1 and CP2, giving me the EXACT point and time when the spheres first touch.

[edited by - aleks_1661 on January 14, 2004 8:24:36 AM]

Share on other sites
Proposed alternative solution:

Correct me if I''m wrong but it seems you could lineraly interpolate the distance between the centers of the spheres to determine point of contact. Example:

Scenario

Initial distance = 5.5 // Distance between centers
Initial Time = 0

At some time t, collision occurs at Distance = 5 (2 + 3)

Final Distance = 4.8 // Distance between centers
Final Time = 700 ms

It seems logical to assume collision occured at 500ms. Is this not true? Is the relationship not linear?

-----------
VenDrake

"My stupid jar is full. I can''t talk to you anymore."

Share on other sites
quote:
Original post by aleks_1661
Ok I have a problem in the above equation,

-------------------
equivalent to a second order equation
a.t2 + b.t + c = 0

where

a = D2
b = 2.(D.O)
c = O2 - r2
--------------------

Now D and O are Vectors ( or a point and a vector). is D.O a dot product or cross product?

yeah, D . O is a dot product, as well as D * O (it''s the ''*'' overload operator for vectors).

D2 is (D * D). A dot product of a vector by itself, it''s also equal to the length squared of the vector''D''.

Share on other sites
quote:
Original post by aleks_1661
// the sum of their radii is the same as the distance between
// the spheres
R1 + R2 = |CP1 - CP2|

// substituting ( | | = magnitude or length of the vector )

R1 + R2 = |(P1 - V1.t) - (P2 - V2.t)|
--------------------------------------

can this be solved? or am i just being dodgy!! :-)

this can be solved if you square the equation

(R1 + R2)2 = |CP1 - CP2|2

(R1 + R2)2 = (CP1 - CP2)2

which is the equation I use

(R1 + R2)2 = ((P1 - P2) + (V1 - V2).t)2

it''s exactly the same thing

Share on other sites
quote:
Original post by aleks_1661
EDIT -----------------------------------------------

Ok May have solved it:

R1 + R2 = |(P1 - V1.t) - (P2 - V2.t)|

R1 + R2 = |P1 - V1.t - P2 + V2.t|

R1 + R2 = |P1 - V1.t - P2 + V2.t|

R1 + R2 = |P1 - P2 - t(V1 - V2)|

0 = |P1 - P2 - t(V1 - V2)| - (R1 + R2)

|t(V1 - V2)| = |P1 - P2| - (R1 + R2)

t = |P1 - P2| - (R1 + R2)
------------------------
|V1 - V2|

this is wrong.

0 = |P1 - P2 - t(V1 - V2)| - (R1 + R2)
=> |t(V1 - V2)| = |P1 - P2| - (R1 + R2)

you assume that |A + B| = |A| + |B|

which it isn''t. too bad, it would be simpler otherwise

Share on other sites

The linear interpolation should work. God knows why i hadn''t seen that one!!!

Ill try both, see where I end up.

also i should have realised the modulus idea was lame!

Forums make the internet a better place. And having a forum with clever people makes them an incredible resource.

Share on other sites
quote:
Original post by VenDrake
Proposed alternative solution:

Correct me if I''m wrong but it seems you could lineraly interpolate the distance between the centers of the spheres to determine point of contact. Example:

Scenario

Initial distance = 5.5 // Distance between centers
Initial Time = 0

At some time t, collision occurs at Distance = 5 (2 + 3)

Final Distance = 4.8 // Distance between centers
Final Time = 700 ms

It seems logical to assume collision occured at 500ms. Is this not true? Is the relationship not linear?

-----------
VenDrake

"My stupid jar is full. I can''t talk to you anymore."

that would be fine if the spheres were moving exactly towards each other. But if they clip each other, like in a pool game, that won''t be sufficient.

if you need to get the points of contact, without all that malarkey, simply do

Vector N = (P2 - P1);
N.Normalise();

Pcoll1 = P1 + N * r1
Pcoll2 = P2 - N * r2