accurate ball-to-ball collision?
Author
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]
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
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
Author
ah, thanks, now i understand. I'm still trying to integrate it into my current ball collision algorithm though...
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]
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.
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?
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
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:
So, at the end of your collision response, where normal is the normal of the surface you collided against:
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).
You can calculate the reflection with:
newVelocity = velocity - (2 * dotProduct(velocity, normal)) * normalSo, 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.zThere 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).
Author
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
