• Advertisement
Sign in to follow this  

accurate ball-to-ball collision?

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

Is there any way to do 2d ball vs. ball collisions that uses a collision angle that is calculated from the positions of the balls AND their velocities? i'm thinking of something like this: When two balls are calculated to be colliding, each is projected out of collision along their previous movement vector INSTEAD of along the collision vector (the vector of the line between the ball centers), so that their collision angles are not calculated wrong, such as when a ball is halfway into another ball and it is projected out sideways instead of the way it came. The problem is that i don't know how to calculate how far the balls have to move backwards along their movement vectors. Maybe this isn't why my ball collision system isn't very stable, so if any of you have any examples of ball-ball collision algorithms that would be great. [Edited by - Epilef on January 30, 2007 6:58:27 AM]

Share this post


Link to post
Share on other sites
Advertisement
To reiterate the problem: you have two circles, A and B. A moves into B along vector V and you want to move it back out along along that vector until it's no longer colliding. We're trying to calculate "d", or the distance along the vector we have to retreat to fix the collision.

There are three points in this problem: A's position, B's position, and the point where you want A to be, after the collision has been fixed. You can think of the problem as an application of the Pythagorean theorem: a² + b² = c². Each of the values in this equation represents the length of a side of a triangle formed by these three points. If we know the length of two, we can calculate the third.

So, what two values do you know the length of?
1) distance from A to B, at the point of collision. (AB, or length(A.position - B.position))
2) distance from A to B, after the collision has been fixed. (A.radius + B.radius)

Applying the equation we now have:
AB² + (A.radius + B.radius)² = d²

Solve for d:
d = sqrt(AB² + (A.radius + B.radius)²)

Once you have d:
A.position -= V*d

Share this post


Link to post
Share on other sites
ah, thanks, now i understand. I'm still trying to integrate it into my current ball collision algorithm though...

Share this post


Link to post
Share on other sites
Maybe not as much help, since it is in lisp...


;;;;=========================================================================
;;;; 2D Vector/Point math
;;;;=========================================================================
(defun vector2d= (v1 v2)
(and (sys:dv= v1 0 v2 0)
(sys:dv= v1 1 v2 1)))

(defun vector2d/= (v1 v2)
(or (sys:dv/= v1 0 v2 0)
(sys:dv/= v1 1 v2 1)))

(defun vector2d-copy (v1 v2)
(sys:dv-copy v1 0 v2 0)
(sys:dv-copy v1 1 v2 1))

(defun vector2d+ (v1 v2 result)
(sys:dv+ v1 0 v2 0 result 0)
(sys:dv+ v1 1 v2 1 result 1))

(defun vector2d- (v1 v2 result)
(sys:dv- v1 0 v2 0 result 0)
(sys:dv- v1 1 v2 1 result 1))

(defun vector2d* (v1 c result)
(sys:dv* v1 0 c 0 result 0)
(sys:dv* v1 1 c 0 result 1))

(defun vector2d/ (v1 c result)
(sys:dv/ v1 0 c 0 result 0)
(sys:dv/ v1 1 c 0 result 1))

(defun vector2d-size (v1 result)
(let ((temp 0.0d0))
(sys:dv* v1 0 v1 0 temp 0)
(sys:dv* v1 1 v1 1 result 0)
(sys:dv+ temp 0 result 0 result 0)
(sys:ddsqrt result result)))

(defun vector2d-dot (v1 v2 result)
(let ((temp -1.0d0))
(sys:dv* v1 0 v2 0 temp 0)
(sys:dv* v1 1 v2 1 result 0)
(sys:dv+ temp 0 result 0 result 0)))

(defun vector2d-size-squared (v1 result)
(vector2d-dot v1 v1 result))

(defun vector2d-normalize (v1 result)
(let ((size (reuse (make-vector2d))))
(sys:dv* v1 0 v1 0 size 0)
(sys:dv* v1 1 v1 1 size 1)
(sys:dv+ size 0 size 1 size 0)
(sys:ddsqrt size size)
(sys:dv/ v1 0 size 0 result 0)
(sys:dv/ v1 1 size 0 result 1)))

(defun vector2d-left (v1 result)
(let ((negate -1.0d0))
(sys:dv* v1 0 negate 0 result 1)
(sys:dv-copy v1 1 result 0)))

(defun vector2d-right (v1 result)
(let ((negate -1.0d0))
(sys:dv* v1 1 negate 0 result 0)
(sys:dv-copy v1 0 result 1)))

(defun vector2d-perp (v1 v2 result)
(let ((temp1 0.0d0) (temp2 0.0d0))
(vector2d-right v2 result)
(vector2d-dot v1 result temp1)
(vector2d-dot result result temp2)
(sys:dv/ temp1 0 temp2 0 temp1 0)
(vector2d* result temp1 result)))

(defun vector2d-parallel (v1 v2 result)
(let ((temp1 0.0d0) (temp2 0.0d0))
(vector2d-dot v1 v2 temp1)
(vector2d-dot v2 v2 temp2)
(sys:dv/ temp1 0 temp2 0 temp1 0)
(vector2d* v2 temp1 result)))

(defun point-inside-rectangle (p corner-point opposite-point)
(cond
((AND (sys:dv< p 0 corner-point 0)
(sys:dv< p 0 opposite-point 0))
NIL)
((AND (sys:dv< p 1 corner-point 1)
(sys:dv< p 1 opposite-point 1))
NIL)
((AND (sys:dv> p 0 corner-point 0)
(sys:dv> p 0 opposite-point 0))
NIL)
((AND (sys:dv> p 1 corner-point 1)
(sys:dv> p 1 opposite-point 1))
NIL)
(T T)))

(defun distance-squared (p1 p2 result)
(let ((difference (reuse (make-vector2d))))
(vector2d- p2 p1 difference)
(vector2d-size-squared difference result)))

(defun distance (p1 p2 result)
(let ((difference (reuse (make-vector2d))))
(vector2d- p2 p1 difference)
(vector2d-size difference result)))

(defun vector2d-rotate (v1 orientation result)
(let ((orientation-right (reuse (make-vector2d))))
(sys:dv* v1 0 orientation 0 result 0) ; dot(v1 orientation) -> result 0
(sys:dv* v1 1 orientation 1 result 1)
(sys:dv+ result 0 result 1 result 0)

(vector2d-right orientation orientation-right)

(sys:dv* v1 0 orientation-right 0 result 1) ;dot(v1 orientation-right) -> result 1
(sys:dv* v1 1 orientation-right 1 orientation-right 0)
(sys:dv+ result 1 orientation-right 0 result 1)

(vector2d-normalize result result)))

(defun lerp (p1 p2 amount result)
(vector2d- p2 p1 result)
(vector2d* result amount result)
(vector2d+ result p1 result))

(defun is-right-of-line (p1 p2 point)
(let ((edge (reuse (make-vector2d)))
(normal (reuse (make-vector2d)))
(dotProduct 0.0d0))
(vector2d- p2 p1 edge)
(vector2d-right edge normal)
(vector2d- point p1 edge)
(vector2d-dot edge normal dotProduct)
(sys:dv> dotProduct 0 0.0d0 0)))

(defun distance-along-normal (p1 p2 normal result)
(let ((edge (reuse (make-vector2d))))
(vector2d- p2 p1 edge)
(vector2d-dot edge normal result)))

(defun perp-line (p1 p2 result)
(let ((temp (reuse (make-vector2d))))
(vector2d- p2 p1 temp)
(vector2d-right temp result)))


(defun test-dynamic-point-static-point (a1 a2 a-radius b b-radius)
"return approximate collision normal + approximate time of collision if detected"
(cond
((not (test-bounding-dynamic-point-static-point
a1 a2 a-radius b b-radius)) nil)

(t (let ((vTrack (reuse (make-vector2d)))
(vAB1 (reuse (make-vector2d)))
(vAB2 (reuse (make-vector2d)))
(vPerp (reuse (make-vector2d)))
(rAB 0.0d0)
(rAB2 0.0d0)
(vAB1dotvTrack 0.0d0)
(vAB2dotvTrack 0.0d0)
(rvPerp2 0.0d0)
(rvAB22 0.0d0)
(temp (reuse (make-vector2d))))
(vector2d- a2 a1 vTrack) ; assign vTrack
(vector2d- b a1 vAB1) ; assign vAB1
(vector2d- b a2 vAB2) ; assign vAB2
(vector2d-perp vAB1 vTrack vPerp) ; assign vPerp
(sys:dv+ a-radius 0 b-radius 0 rAB 0) ; assign rAB
(sys:dv* rAB 0 rAB 0 rAB2 0) ; assign rAB2
(vector2d-dot vAB1 vTrack vAB1dotvTrack) ; assign vAB1dotvTrack
(vector2d-dot vAB2 vTrack vAB2dotvTrack) ; assign vAB2dotvTrack
(sys:dv* vAB1dotvTrack 0 vAB2dotvTrack 0 temp 0)

; $$$ can optimize!
(vector2d-size-squared vPerp rvPerp2) ; assign rvPerp2
(vector2d-size-squared vAB2 rvAB22) ; assign rvAB22

(cond ((OR (AND (sys:dv<= temp 0 0.0d0 0)
(sys:dv<= rvPerp2 0 rAB2 0))
(sys:dv<= rvAB22 0 rAB2 0))
(let ((paraSize 0.0d0)
(para (reuse (make-vector2d)))
(para0 (reuse (make-vector2d)))
(centerPnt (reuse (make-vector2d)))
(rvTrack 0.0d0))

(vector2d-size vTrack rvTrack) ; assign rvTrack
;rvTrack is the distance A has travelled

(vector2d-size-squared vPerp paraSize) ; assign paraSize
(sys:dv- rAB2 0 paraSize 0 paraSize 0)
(setf paraSize (max paraSize 0.0d0))
(sys:ddsqrt paraSize paraSize)
(sys:dv+ paraSize 0 *half-epsilon* 0 paraSize 0)
; paraSize is the part of triangle parallel to A's path
; that would be rAB away from B

(vector2d* vTrack paraSize para) ; assign para
(vector2d/ para rvTrack para)
(vector2d-parallel vAB1 vTrack para0) ; assign para0
(vector2d- para0 para centerPnt) ; assign centerPnt
(vector2d+ a1 centerPnt centerPnt)

;(display temp rvTrack)

; Get movement normal and find out where
; centerpoint is relative to starting point
(vector2d/ vTrack rvTrack vTrack)
(distance-along-normal a1 centerPnt vTrack temp)

; the pushback goes past a1 against the movement,
; because the object was closer than *half-epsilon*
; so set time to 0.0d0
(cond ((sys:dv<= temp 0 0.0d0 0)
;(format t "temp=~S~%" temp)
0.0d0)

(T (sys:dv/ temp 0 rvTrack 0 rvTrack 0)
(when (sys:dv>= rvTrack 0 1.0d0 0)
(error "here"))
rvTrack)))))))))

Share this post


Link to post
Share on other sites
ive been working on this quite abit this week and had a few questions, now i have the same method you have just mentioned working, but it still appears to flicker when you reach certain areas of the sphere, ive been told that its possible to calculate the collision for the next frame but im not too sure what to base velocity on, ive been calculating it based on the position it was in the frame before, and the position it is in now, surely this isnt the most accurate way of doing it?

this is probably the easiest way to explain how im doing this

so i find the equation of the line between the positions of the centres of each object

y = mx + c

find m by subtracting the distance between each param on x and z (3d)

like so

m=((e1p.z-e2p.z)/(e1p.x-e2p.x));

finding the Y (or z in this case) intercept

c= e1p.z-(m*e1p.x);




get the relative distance

dist = relPos.x * relPos.x + relPos.y * relPos.y + relPos.z * relPos.z;


also get the minimum distance, being the combined distance of both the bounding spheres radius's

minDist = e1->boundRadius + e2->boundRadius;



get the square root of the distance

sqrtDist = sqrt(dist);


then ive moved onto my collision response

so if the square root of the distance from the centres of each object is less than the distance between them then

if(sqrtDist <= minDist)

move on to respond to the collision

so in a while loop until no longer colliding

if (e1p.x <= e2p.x)

i check if weither the X value of each entitys position is greater than the other, and then calculate weither there new X position is positive or negative to there own and clac the x and Y pos based upon that

if (e1p.x <= e2p.x)
e1p.x = e1p.x -amm;

if (e1p.x > e2p.x)
e1p.x = e1p.x +amm;

then i recalculate the Z intersect value for the line

c= e1p.z-(m*e1p.x);

from this can calulate what the new Z position is

e1p.z = (e1p.x*m) + c;

and finally set the new position

e1->setPosition(&e1p);


now i think the way the Z is calculated causes problems, but if one entity walks into another it can fly miles across the room rather than just to the edge, is also some aspect where at other angles it flickers for ages and ages but others it looks perfect

could it be to do with there buing multiple entitys colliding with it and getting stuck in a loop or something?

[Edited by - Stowelly on January 31, 2007 2:58:11 PM]

Share this post


Link to post
Share on other sites
You lost me with your code, but your conclusion is probably correct. You may get flickering back and forth if pushing your object out a collision with object A pushes it into a collision with object B. When your engine pushes it back out of object B, it starts colliding with object A again. Back and forth. When collision response is handled correctly, this shouldn't occur.

Here is how I would handle position, velocity, and collision. First,
- Your object has a position.
- Your object has a velocity independent of it's position. Position should be updated by velocity, but you shouldn't base your velocity on object position.

Then, each frame:
- Find the new position for the object based on it's velocity (new_pos = pos + velocity * frameTimeInSeconds).
- For bounding spheres, create a bounding capsule for the entire movement. e.g. a cylinder capped with spheres, starting at pos, ending at new_pos.
- Find all objects the capsule is colliding with.
- For each object it is colliding with, trace along the line of movement (using the process described in my first post) and store the point of collision closest to the starting of the line.
- After all objects have been checked, you'll have the point along the movement line closest to the start where the object first collided with something.
- You can respond to the collision by tracking how far it tried to penetrate past the point of collision, and use this to calculate a reflected velocity.

This method takes one thing for granted: your object must not be colliding with an object at the starting of the frame. If it starts the frame already colliding you're in trouble, and the collision response becomes unpredictable, as it has no valid line of movement to back out upon. If your simulation starts out with all bodies in a valid state, this shouldn't happen.

Share this post


Link to post
Share on other sites
hi, thanks for the fast reply, i have implemented it in the way you have said, and im very impressed by how much better it looks.

i was just wondering if you would mind going into abit more detail about the following method please?


Quote:
If you want to update the velocity based on the collision, you can track things like how far it has penetrated into each surface it collided with before you backed it out, and the normals of collision. Then you adjust the velocity of the object accordingly.


the way i interpret this is that you mean for both the x and the z params of the new_pos vector you would individually calculate the distance from the centre, and adjust that particular value to either a positive or negative number based on the distance from the centre?

kind of like so

if(new_pos1.x <= new_pos2.x)
{
new_pos1.x += velocity1.x;

}

if(new_pos1.x > new_pos2.x)
{
new_pos1.x -= velocity1.x;
}

im just wondering this as it works perfectly at some angles, but others it is possible to force you way through certain parts of some spheres still

cheers

Share this post


Link to post
Share on other sites
How are you calculating your reflection velocity right now? I would just ignore the penetration for now, and try to get the reflection working smoothly.

You can calculate the reflection with:
newVelocity = velocity - (2 * dotProduct(velocity, normal)) * normal

So, at the end of your collision response, where normal is the normal of the surface you collided against:
d = (velocity.x*normal.x) + (velocity.y*normal.y) + (velocity.z*normal.z)
velocity.x = velocity.x - (2 * d) * normal.x
velocity.y = velocity.y - (2 * d) * normal.y
velocity.z = velocity.z - (2 * d) * normal.z

There are lots of other things you can do with this, like changing the amount of bounce and adding friction. You might be interested in oliii's collision and response tutorial (fourth from the bottom).

Share this post


Link to post
Share on other sites
Is there any way of doing this using position-based velocity? I'm working on a verlet engine, which needs to have position-based velocity (i think). When i try to implement it anyways, the circles go all over the place unpredictably.

Share this post


Link to post
Share on other sites
ok as far as i understand this now

//calculate new position based on velocity and time
D3DXVECTOR3 new_pos1 = e1p + velocity1 * Timer;
D3DXVECTOR3 new_pos2 = e2p + velocity2 * Timer;

//find the distance between the 2 spheres centres

D3DXVECTOR3 newPos = new_pos1 - new_pos2;

float new_dist_sq = (newPos.x * newPos.x + newPos.y * newPos.y + newPos.z * newPos.z);


//A-B plus the size of the bounds combined
float AB = new_dist + (minDist * minDist);


// this is where i could be going wrong,calculating the normal

D3DXVECTOR3 normal;
normal.x = new_pos2.x /new_dist ;
normal.y = new_pos2.y /new_dist;
normal.z = new_pos2.z /new_dist;



//calculate d based on velocity and the normal value
float d = (velocity1.x*normal.x) + (velocity1.y*normal.y) + velocity1.z*normal.z);


///and from d calculate the new velocity

velocity1.x = velocity1.x - (2 * d) * normal.x;
velocity1.y = velocity1.y - (2 * d) * normal.y;
velocity1.z = velocity1.z - (2 * d) * normal.z;

//then

new_pos1 -= velocity1





Now this gives a very accurate collision, no overlapping or anything else, but the change is very sudden, i.e if you walk straight into a sphere holding forward, it will keep jumping back rather than a smooth non movement if that makes sense?


Share this post


Link to post
Share on other sites
Epilef:

Once you found a collision point and surface, for a position based velocity you would want to reflect the old position to the other side of the surface. This way, the next step will compare the "corrected" old position to position, and will get a vector pointing in the reflected direction.

In a Verlet integrated system, just doing this would cause you to lose velocity: the distance between the reflected old_position and the "stopped" collision position is shorter than what was originally calculated. To fix this you can either:
- Push old_position backwards along the reflected vector until it is the right distance away. This is a hacky way of fixing it, but it simplifies things.
- Push position forwards along the reflected vector for whatever distance was left after the collision bounced it. In this case, you would need to repeat your collision process.

It's hard to give more details without having any code.

Stowelly:

The change is probably sudden because:
new_pos1 -= velocity1

Velocity is units per second, and you're adding a whole second of velocity to the position. Hopefully you're not running at 1FPS :D You have to calculate how much "time" is left over after your collision happened, and scale the velocity accordingly.

Every frame you're processing movement over a period of time. e.g. the time since the last frame was 33ms (0.033s) and your velocity is 100 units per second. So, the movement for this frame is going to be 100 * 0.033 == 3.3 units. If you move 2 units before colliding, the reflected velocity should be scaled so that you only move 1.3 additional units in the reflected direction.

It also appears that you have TWO moving objects. The process as I described it is intended for one moving object and a static, world object that doesn't really react to collisions. If you have two moving objects and you want the second to get pushed around, you have to apply some velocity to the object you collide with as well.

[Edited by - SantaClaws on February 1, 2007 5:51:24 PM]

Share this post


Link to post
Share on other sites
thanks for being so patient, im in the process of studying maths and physics on my games degree and shouldnt have much more problems with this soon

i really dont think its the time causing this issue, ive tried multiplying the velocity by the current frame timer and although it does seem a little bit better it still has alot of issues, basically if i stand next to the sphere its fine, just edge towards it until its just within the collision area then it bounces back probably about the distance of the entire boundary

i just cant visualise where in the algorithm is causing this, again thanks alot

EDIT: it appears to do it on one side of the objects more than the other

ive also uploaded the release version of this to demonstrate what i mean

http://download.yousendit.com/050CCB60712EF5EA


also oli's collision and response tutorial has a broken link unfortunately

[Edited by - Stowelly on February 2, 2007 4:02:53 AM]

Share this post


Link to post
Share on other sites
what does the 2 represent in this operation?
velocity.z = velocity.z - (2 * d) * normal.z

if i make it smaller my refections on the smaller spheres are very accurate, if i make it larger the reflections for the bigger spheres is better

Share this post


Link to post
Share on other sites
ive solved this now, thanks alot for all your help

while(new_dist_sq <= minDist * minDist )
{
D3DXVECTOR3 normal;
float moveApart = 0.002f;

normal = e2p - e1p;
new_pos1 -= normal * moveApart * time;

newPos = new_pos1 - new_pos2 ;
new_dist_sq = (newPos.x * newPos.x + newPos.y * newPos.y + newPos.z * newPos.z);
}

Share this post


Link to post
Share on other sites
Damn you forums! My big explanation waiting to be posted goes to waste. :(

Haha, glad to hear you got it solved, though.

Share this post


Link to post
Share on other sites
Hi again, I'm working on this problem again after a long time of putting it aside. I hadn't gotten it to work before, and now I've tried a lot more and I still can't figure it out.
Why is the Pythagorean theorem used, if that's only for right angles? It seems like that's the problem, because 'd' is almost always larger than it should be. Also, in this line:
A.position -= V*d
Doesn't V*d come out to be a very large vector?
It seems like i'm doing this all wrong, but i've checked over it and tried lots of other things, but it just doesn't work...

Share this post


Link to post
Share on other sites
You should really start using vector notation.

Spheres [PA, ra], [PB, rb].


Vector Delta = PA - PB;
float d2 = Delta.DotProduct(Delta);
float r = ra + rb;
float r2 = r * r;

if(d2 < r2)
{
float d = sqrt(d2);
Vector Push = Delta * (r - d) / d;
PA += Push * 0.5f;
PB -= Push * 0.5f;
}


Share this post


Link to post
Share on other sites
Thanks a lot, this works great now. Does this push the particles back along their velocity vectors? From my observations it doesn't, but I don't trust my observations very much since I don't know much about vectors.

Share this post


Link to post
Share on other sites
it wont. If you want a 'bounce' effect, you can do

particle

A[Pa, Va, ra, ma] // ma : mass of particle A
B[Pb, Vb, rb, mb] // mb : mass of particle B

cor : coefficient of resitution (or bounce amount). in range [0, 1].


Vector Delta = Pa - Pb;
float d2 = Delta.DotProduct(Delta);
float r = ra + rb;
float r2 = r * r;

if(d2 < r2)
{
float d = sqrt(d2);
Vector Ncoll = Delta / d; // normal of collision
float dcoll = (r - d); // penetration distance

float percent_a = mb / (ma + mb); // How much of the impact will be affecting A
float percent_b = ma / (ma + mb); // How much of the impact will be affecting B

// push particles.
// the lighter one gets pushed more (transfer of energy).
Pa += Ncoll * (dcoll * percent_a);
Pb -= Ncoll * (dcoll * percent_b);

// make particle bounce against each other
Vector Vrel = VA - VB; // relative velocity of the particles
float impact_vel = Vrel.DotProduct(Ncoll); // impact velocity

// only if they are going towards each other
if(impact_vel < 0.0f)
{
// Apply the collision impulse
// the lighter one gets pushed more (transfer of energy).
Va += ((1.0f + cor) * (-impact_vel) * percent_a) * Ncoll;
Vb -= ((1.0f + cor) * (-impact_vel) * percent_b) * Ncoll;
}
}

Share this post


Link to post
Share on other sites
It's the classic Velcoty Reflect collision response, with the added effect that it also deals with the respective masses of the particles.

i.e. B has infinite mass, A will bounce off completely off object B, while B wont move. Both objects have equal mass, both will collide and bounce off with the same energy.

Share this post


Link to post
Share on other sites
No I mean when the balls are pushed out of collision do they move backwards along their movement vectors (so that they are accurately moved back from where they came from instead of to the side). Also, this would make the collision response more accurate since the collision vector would be calculated from the balls' "real" positions. For example, if a ball moved into another ball after a time step, could bounce sideways (depending on how far into the other ball it moved) instead of having a nearly head-on collision.

Share this post


Link to post
Share on other sites
no. if you want that, you will need to calculate the proper moment of collision. The spheres are just pushed apart so they are touching, along the vector of intersection, not the velocity vectors.

To calculate the time of collision (and therefore move them along the velocity vectors), you have to use an algo similar to a ray-sphere intersection test. Then you can place the ball exactly where the just collide (effectively moving along their respective velocity vector to the exact time of collision).

since I have 5 mins...

particle A [Pa, Va, ra]
particle B [Pb, Vb, rb]

at time of collision (t) we have these equations

(eq. 1) Pa'(t) = Pa + Va * t (equation of motion of particle A).
(eq. 2) Pb'(t) = Pb + Vb * t (equation of motion of particle B).
(eq. 3) [Pa'(t) - Pb'(t)]^2 = (ra + rb)^2 (meaning, Pa'(t) and Pb'(t)) are a distance = to (ra + rb)).

Replace Pa'(t) and Pb'(t) from equation 1 and 2 into equation 3 and you get

(eq. 4) [(Pa - Pb) + (Va - Vb) * t]^2 = (ra + rb)^2

this is an equation in the form

(eq. 5) (M + N*t)^2 - r^2 = 0

where

M = (Pa - Pb)
N = (Va - Vb)
r = (ra + rb)

develop (eq. 5) and you get

(eq. 6) [N.N]* t^2 + [2.0f * (M.N)] * t + [(M.M) - (r*r)] = 0;

=> this is a second equation in the form
a * t^2 + b * t + c = 0

where
a = (N.N)
b = (M.N) * 2.0f
c = (M.M) - (r*r)

let d = b*b - 4*a*c

if (d < 0) no collision. It means that the particles just missed.

You then get two roots t0 and t1.

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

you sort the times, so that

t0 = min(t0, t1)
t1 = max(t0, t1)

if(t1 < 0.0f) it means that the collision happened in a time before the frame started. So ignore.

if(t0 > frame_timestep) it means that the collision will happen after the frame time slice. YOu can also ignore.

if (t0 < 0.0f), it means that the particles intersect. You can use the previous algo to resolve the intersection.

if (t0 > 0.0f), it means that the particles collided. and that is your time of collision.

Then to find the position of the balls at that time of collision, you just use the value of tcoll you got and plug it in the (eq. 1) and (eq. 2). That's equivalent to 'moving along' the velocity vectors.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement