accurate ball-to-ball collision?

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

ah, thanks, now i understand. I'm still trying to integrate it into my current ball collision algorithm though...

Best thread title ever.

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)))))))))

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]

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.

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

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.xvelocity.y = velocity.y - (2 * d) * normal.yvelocity.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).

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.

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?

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]

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]

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

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);
}

Damn you forums! My big explanation waiting to be posted goes to waste. :(

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

haha please post it anyway, im sure itll help others

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...

You should really start using vector notation.

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

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.