Jump to content
  • Advertisement
Sign in to follow this  
Epilef

accurate ball-to-ball collision?

This topic is 4241 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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!