Did two spheres intersect?
Author
Hi there,
I have been thinking about this for some time, but I can''t seem to come up with a final solution:
Say I have two spheres A and B which can have different radii.
The initial position of A is Xa(t0). The final position is Xa(t0+delta t)
The same goes for sphere B.
The problem I want to solve is "did the two spheres intersect or touch and if so at what time of the interval [t0 , t0+delta t]"?
I can assume constant velocity during delta t.
Is there a fast solution for this problem?
Kind regards,
Bart
Search google for line line intersection code, line line intersection returns the closest distance, you can convert that to time. Most of the routines are barely optimised so take your time i''d say. I will look for a fast routine i have used before, i will post it as soon as i find it.
int LineLineIntersect( VERT p1,VERT p2,VERT p3,VERT p4,VERT *pa,VERT *pb, double *mua, double *mub){ VERT p13,p43,p21; double d1343,d4321,d1321,d4343,d2121; double numer,denom; double EPS=0.000001; p13.x = p1.x - p3.x; p13.y = p1.y - p3.y; p13.z = p1.z - p3.z; p43.x = p4.x - p3.x; p43.y = p4.y - p3.y; p43.z = p4.z - p3.z; if (abs(int( p43.x )) < EPS && abs(int( p43.y )) < EPS && abs(int( p43.z )) < EPS) return(FALSE); p21.x = p2.x - p1.x; p21.y = p2.y - p1.y; p21.z = p2.z - p1.z; if (abs(int( p21.x )) < EPS && abs(int( p21.y )) < EPS && abs(int( p21.z )) < EPS) return(FALSE); d1343 = p13.x * p43.x + p13.y * p43.y + p13.z * p43.z; d4321 = p43.x * p21.x + p43.y * p21.y + p43.z * p21.z; d1321 = p13.x * p21.x + p13.y * p21.y + p13.z * p21.z; d4343 = p43.x * p43.x + p43.y * p43.y + p43.z * p43.z; d2121 = p21.x * p21.x + p21.y * p21.y + p21.z * p21.z; denom = d2121 * d4343 - d4321 * d4321; if (abs(int( denom )) < EPS) return(FALSE); numer = d1343 * d4321 - d1321 * d4343; *mua = numer / denom; *mub = (d1343 + d4321 * (*mua)) / d4343; pa->x = p1.x + *mua * p21.x; pa->y = p1.y + *mua * p21.y; pa->z = p1.z + *mua * p21.z; pb->x = p3.x + *mub * p43.x; pb->y = p3.y + *mub * p43.y; pb->z = p3.z + *mub * p43.z; return(TRUE);}Well, this one can be optimised a bit further, anyway what do you call fast?
fast, not really 
it involves solving a second order equation, in the form
at² + bt + c = 0
and you need to find t that satisfy that equation.
not that much of a big deal, to be honest.
the problem is getting to that equation.
the simplest solution is to consider these equivalences.
first, sphere structure
CSphere
{
Vector C;
Vector V;
float r;
};
V is the velocity, of displacement of the sphere, whichever you prefer. for you, V = Xa(t0+delta_t) - Xa(t0), it''s a displacement vector.
the time of impact of a moving sphere S0 against another moving sphere S1 is equal to the time of impact of a moving sphere S1'' of displacement S1''.V = (S1.V - S0.V) against a static sphere S0'' (S0.C, Vector(0, 0, 0), S0.r)
the time of impact of a moving sphere S1'' against a static Sphere S0'' is equal to the time of impact of a sphere S1'''' of radius (0) and a static sphere S1'''' of radius (S1'' + S0'').
that sphere of radius 0 basically defines a segment. So you end up doing a segment against a large sphere intersection test, and that will give you the time of impact.
MovingSphere S0(C, V, r)
MovingSphere S1(C, V, r)
Segment Seg(S1.C, (S1.V - S0.V))
StaticSphere Sph(S0.C, (S0.r + S1.r))
a point P is on segment [A, B] if
P = A + D.t, 0
a point P is on sphere [C, r] if
(P - C)² = r² [eq2]
replace P in [eq2] with P in [eq1] and you get
[(A - C) + t.D]² = r²
[(A - C) + t.D]² - r² = 0
expand and you get
t².[D²] + t.[2.(A-C).D] + [(A-C)² - r²] = 0
so, this is a second order equation in the form
t².a + t.b + c = 0 where
a = [D²]
b = [2.(A-C).D]
c = [(A-C)² - r²]
this equation can yield two solutions t0, t1.
the first time of collision will be the first minimum positive value between t0 and t1.
if you can''t find a solution, the sphere won''t collide.
however, there is a chance they are overlapping, meaning, one of the solution is < 0, and close to zero.
they do overlap when c < 0.0f. if c < 0.0f, they are already intersecting, and the time of impact is 0.0f
also, if b > 0.0f, the sphere are moving away from each other. meaning, they should not collide, unless they already intersect. so you might return "no collision" when b > 0.0f and c > 0.0f.
note : doing D² when D is a vector, it''s like doing D.dot(D).
it involves solving a second order equation, in the form
at² + bt + c = 0
and you need to find t that satisfy that equation.
not that much of a big deal, to be honest.
the problem is getting to that equation.
the simplest solution is to consider these equivalences.
first, sphere structure
CSphere
{
Vector C;
Vector V;
float r;
};
V is the velocity, of displacement of the sphere, whichever you prefer. for you, V = Xa(t0+delta_t) - Xa(t0), it''s a displacement vector.
the time of impact of a moving sphere S0 against another moving sphere S1 is equal to the time of impact of a moving sphere S1'' of displacement S1''.V = (S1.V - S0.V) against a static sphere S0'' (S0.C, Vector(0, 0, 0), S0.r)
the time of impact of a moving sphere S1'' against a static Sphere S0'' is equal to the time of impact of a sphere S1'''' of radius (0) and a static sphere S1'''' of radius (S1'' + S0'').
that sphere of radius 0 basically defines a segment. So you end up doing a segment against a large sphere intersection test, and that will give you the time of impact.
MovingSphere S0(C, V, r)
MovingSphere S1(C, V, r)
Segment Seg(S1.C, (S1.V - S0.V))
StaticSphere Sph(S0.C, (S0.r + S1.r))
a point P is on segment [A, B] if
P = A + D.t, 0
a point P is on sphere [C, r] if
(P - C)² = r² [eq2]
replace P in [eq2] with P in [eq1] and you get
[(A - C) + t.D]² = r²
[(A - C) + t.D]² - r² = 0
expand and you get
t².[D²] + t.[2.(A-C).D] + [(A-C)² - r²] = 0
so, this is a second order equation in the form
t².a + t.b + c = 0 where
a = [D²]
b = [2.(A-C).D]
c = [(A-C)² - r²]
this equation can yield two solutions t0, t1.
the first time of collision will be the first minimum positive value between t0 and t1.
if you can''t find a solution, the sphere won''t collide.
however, there is a chance they are overlapping, meaning, one of the solution is < 0, and close to zero.
they do overlap when c < 0.0f. if c < 0.0f, they are already intersecting, and the time of impact is 0.0f
also, if b > 0.0f, the sphere are moving away from each other. meaning, they should not collide, unless they already intersect. so you might return "no collision" when b > 0.0f and c > 0.0f.
note : doing D² when D is a vector, it''s like doing D.dot(D).
oliii probably already gave the solution (sorry i didn''t read all the way through, but here is the code i use):
struct XYZ{ float x, y, z;};// c : old position of sphere 1// d : new position of sphere 1// e : old position of sphere 2// f : new position of sphere 2// fDistance : radius of the two spheres// fU : return value giving the first point of collisioninline bool SphereColisionDetect(const XYZ &c, const XYZ &d, const XYZ &e, const XYZ &f, const float fDistance, float &fU){ fU = 0; XYZ K1, K2; float A, B, C, Delta, u1, u2; K1.x = e.x - c.x; K1.y = e.y - c.y; K1.z = e.z - c.z; K2.x = f.x - e.x - d.x + c.x; K2.y = f.y - e.y - d.y + c.y; K2.z = f.z - e.z - d.z + c.z; A = K2.x*K2.x + K2.y*K2.y + K2.z*K2.z; B = 2*(K1.x*K2.x + K1.y*K2.y + K1.z*K2.z); C = K1.x*K1.x + K1.y*K1.y + K1.z*K1.z - fDistance*fDistance; Delta = B*B - 4*A*C; if (Delta<0) return false; Delta = sqrt(Delta); u1 = (-B + Delta)/(2*A); u2 = (-B - Delta)/(2*A); if (u1 < u2 && u1 >= 0) fU = u1; else fU = u2; if (fU >= 0 && fU <= 1) return true; return false;}
Ok, this is pretty simple. The situation can be solved by calling a function that solves if a line from the origo to some point collides with a static sphere. (Yeah, it''s really that simple!)
Of course, the function parameters have to be modified according the the different sphere sizes,posions and movement.
Let''s make the funktion first.
Some math behind the function in 2D but you can easily just add another dimension here.
If at some value of t between 0 and 1, the following function has a value of 0 or less, is is a collision. (You also want to find the first time between 0 and 1 that this is true)
f(t)=(sx-px*t)^2+(sy-py*t)^2-r^2
where sx and sy are the coordinates of the sphere
and px and py are the ending points of the line
t^2*(px^2+py^2)+t*(-2*(sx*px+sy*py))-r^2
ok you might want to do the following
float a=(px^2+py^2);
float b=(-2*(sx*px+sy*py));
float c=-r^2;
The lowest point of this function is at t=-b/(2*a).
If the function is greater than zero there, there is no collision.
The smallest value of t where f(t)=0 equals
t=(-b-sqrt(b^2-4*a*c))/2a (a>0)
If this value is between 0 and 1 this is the collision time.
If this value is smaller than 0 you have to check the value of f(t) at t=0. If it is greater than 0 there is no collision. If it is smaller than zero there is a collision. (There was a collision right at the start)
If the value is greater than 1 there is no collision.
Lets syat the function looks like this
func(px,py,sx,sy,r)
that returns if there is a hit and when it was.
Ok simple, right? Now on to how to modify the parameters.
1. The sphere size...
func(px,py,sx,sy,r1+2)
Get it?
2. The positions ...
sphere 1 is at {px1,py1} and goes to {px2,py2} (sphere 2 is still at one place..
func(px2-px1,py2-py1,sx-px1,sy-py1,r1+r2)
Right?
3. Now sphere 2 moves at well...
Sphere 2 starts at {sx1,sy1} and goes to {sx2,sy2}.
func(px2-px1-(sx2-sx1),py2-py1-(sy2-sy1),sx1-px1-sx2,sy1-py1-sx2,r1+r2)
Ok, thats it. Wasn''t too hard was it?
Of course, the function parameters have to be modified according the the different sphere sizes,posions and movement.
Let''s make the funktion first.
Some math behind the function in 2D but you can easily just add another dimension here.
If at some value of t between 0 and 1, the following function has a value of 0 or less, is is a collision. (You also want to find the first time between 0 and 1 that this is true)
f(t)=(sx-px*t)^2+(sy-py*t)^2-r^2
where sx and sy are the coordinates of the sphere
and px and py are the ending points of the line
t^2*(px^2+py^2)+t*(-2*(sx*px+sy*py))-r^2
ok you might want to do the following
float a=(px^2+py^2);
float b=(-2*(sx*px+sy*py));
float c=-r^2;
The lowest point of this function is at t=-b/(2*a).
If the function is greater than zero there, there is no collision.
The smallest value of t where f(t)=0 equals
t=(-b-sqrt(b^2-4*a*c))/2a (a>0)
If this value is between 0 and 1 this is the collision time.
If this value is smaller than 0 you have to check the value of f(t) at t=0. If it is greater than 0 there is no collision. If it is smaller than zero there is a collision. (There was a collision right at the start)
If the value is greater than 1 there is no collision.
Lets syat the function looks like this
func(px,py,sx,sy,r)
that returns if there is a hit and when it was.
Ok simple, right? Now on to how to modify the parameters.
1. The sphere size...
func(px,py,sx,sy,r1+2)
Get it?
2. The positions ...
sphere 1 is at {px1,py1} and goes to {px2,py2} (sphere 2 is still at one place..
func(px2-px1,py2-py1,sx-px1,sy-py1,r1+r2)
Right?
3. Now sphere 2 moves at well...
Sphere 2 starts at {sx1,sy1} and goes to {sx2,sy2}.
func(px2-px1-(sx2-sx1),py2-py1-(sy2-sy1),sx1-px1-sx2,sy1-py1-sx2,r1+r2)
Ok, thats it. Wasn''t too hard was it?
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
