Archived

This topic is now archived and is closed to further replies.

(Retitled) 2D ball collision and sliding (I am aware it is a repeated subject)

This topic is 5005 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

This should be as easy one: I am working on a 2D physics routine involving a bunch of balls bouncing and rolling (almost) around a world of line segments. The collision is handled via circle-segment sweeps and circle-circle sweeps. Here is my problem... A ball collides with a line segment. It is therefore moved to the point of collision and it's velocity is reflected. Next frame, ball is still colliding with that same line segment so, theoretically, its velocity is again reflected and the ball gets stuck. This problem is easily solved by ignoring collision when the ball is traveling away from the collision normal (correct term?). When the ball collides against the segment the collision normal is the normal of the line segment. Most of the time. I detect whether the ball is traveling away from the collision by checking to see the original ball's centre position (before the collision) minus a point on the line and the balls velocity are on the same side of the collision normal. If so, then the collision can be ignored: (an example) L1 and L2 defines the segment OP is the balls original position (centre) V is the balls velocity N is the normal of collision (which, usually, is L2-L1 with x equalling -y and y equalling x if the sign of (OP-L1).N and the sign of V.N are the same then the ball is moving away from the collision and therefore can be ignored. This works like a charm until it comes to bouncing the ball of the points of the line segment. In this case, the collision normal runs from the point of which the ball collided to the centre of the ball (after it has been moved to the point of first collision). Problem. The original position of the ball (centre) is now on the collision normal, for starters. I though I could perhaps treat the tangent formed by the ball and the collision point as the collision normal when testing but this did not seem to work (although it should be acknowledged that by this time my code is a mess). To cut a long story short, how do I determine if a circle is moving away from a collision detected with a fixed point? Damn this seems like such a simple one - I really should have figured this one out for myself . [edited by - jack_1313 on March 30, 2004 3:49:00 AM]

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Well, just compare the distances :
- collision point - sphere center
- collision point - sphere center + velocity

if the second one is greater than the second one, the sphere goes away...


quote:
Original post by jack_1313
This should be as easy one:

Next frame, ball is still colliding with that same line segment so, theoretically, its velocity is again reflected and the ball gets stuck
<SPAN CLASS=editedby>[edited by - jack_1313 on March 26, 2004 6:43:42 AM]</SPAN>


Here is your problem, this must not be the case. Next frame, the sphere position is the sphere position when colliding PLUS a bit of the reflecting vector. Determining this "bit" can be done by determining the time of "pure" collision.

Share this post


Link to post
Share on other sites
quote:
Original post by Anonymous Poster
Well, just compare the distances :
- collision point - sphere center
- collision point - sphere center + velocity

if the second one is greater than the second one, the sphere goes away...


quote:
Original post by jack_1313
This should be as easy one:

Next frame, ball is still colliding with that same line segment so, theoretically, its velocity is again reflected and the ball gets stuck
<SPAN CLASS=editedby>[edited by - jack_1313 on March 26, 2004 6:43:42 AM]</SPAN>


Here is your problem, this must not be the case. Next frame, the sphere position is the sphere position when colliding PLUS a bit of the reflecting vector. Determining this "bit" can be done by determining the time of "pure" collision.




Yeah, that was what I was initially doing. However, suppose that the ball ends up in a position like such:

\O/

(Try to be imaginative...)

Suppose the ball collides with the segment on the left. The ball is moved slightly in the direction of the reflection vector and now it intersects the segment on the right. I am only registering the first collision that occurred and ignoring the rest, which means that on the next frame the ball is already intersecting the segment on the right. The problems begin.

Thanks for providing a valid solution - it is so simple! But that should probably be:
collision point - sphere center
collision point - sphere center + velocity sized to (for instance) half the radius of the ball
This will eliminate false results in the case that the ball's velocity is very high (higher than double the ball's radius, if my mind is operating correctly).


[edited by - jack_1313 on March 27, 2004 9:38:22 PM]

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
hehe, you''re right...

I was intending to write you to make the test on left panel then on the right one, but I realised the sphere will repeat rebounding on right and left and right and left and so ...

Maybe you should try to cumulate the reflecting vectors (with the inital speedth vector) before moving the sphere ?

Share this post


Link to post
Share on other sites
Here is what I have ended up with and why:

After a collision move the ball a miniature amount in the direction it came from (-v). If the ball came from that direction then we know there will not be a collision there.
Ignore collisions with endpoints if the ball is moving away from it.

The reason I have done this is gravity - it poses problems because my circle-segment sweep acts as if the circle moved directly from one position to another (which it does, but in the real world it does not).
The first problem involves checking to see whether the ball is moving away from a collision with a surface by checking to see if the ball''s original position is on the same sides of the segment as the ball''s velocity. This works fine 99% of the time, except that occasionally the method fails due to the effect of gravity. When the ball is bouncing almost at a standstill there may be a time when the ball is determined to be moving away from the collision, but next frame the gravity has caused the ball to collide with the segment in question. This rarely happens but the fact that it does means it must be avoided. Therefore I move the ball slightly away from a collision in the direction it came from.
The second problem is similar but it involves collision with endpoints and the method of moving the ball slightly away after a collision. The problem is described in this thread, although I do not believe they came to a solution. Basically, the ball is reflected off an endpoint at a near horizontal angle, but next frame the path of the ball actually registers a collision with that same endpoint due to the fact that the new position of the ball has been effected by gravity. The end result is that the ball gets stuck on endpoints from time to time. One way to fix it is to increase the ''small value'' of which you move the ball after a collision to allow for this - an unattractive solution. A better solution is to ignore collisions that occur when the ball is determined to be moving away from the end point. Problem solved.

quote:

Maybe you should try to cumulate the reflecting vectors (with the inital speedth vector) before moving the sphere ?



Sorry... ah... what do you mean by ''cumulate'' the vectors? My vector maths isn''t quite as complete as I''d like it to be .

Anyhow, the issue I am facing now is that of getting the ball to slide realistically down a slope. Currently I am determining the new velocity of the ball after a collision by reflecting it off the collision normal. This causes the ball to eventually stop on a slope (well, it slides at a speed determined by the small value of which is used to move the ball away from the collision - this is obviously not correct). Any ideas? Is it a problem with the method I use to determine the new velocity of the ball? Time for me to do some searching...

Share this post


Link to post
Share on other sites
I believe that the problem regarding the lack of sliding is enhanced by my method of simulating the loss of energy in each bounce (dampening?).
Here is how my collision detection operates between segments and circles in 2D:

1) Go through all collisions and determine the earliest (Currently I only deal with the first collision)
2) Determine the point of intersection using a circle-segment sweep. Move the ball to the intersection point minus the ball''s velocity sized to 0.0001f.
3) Reflect the velocity off the collision normal:
R = V - N*(2 * V.N)
Where V is the ball''s velocity and N is the collision normal. The exception is when colliding with an endpoint:
R = (N*(2 * V.N)) sized to the length of V
4) Simulate the loss of force in the collision by multiplying the ball''s new velocity by 0.7

At this stage, the ball bounces about, losing energy in each bounce until it comes to a stand still, which may well be on a steep slope.
I believe the problem partially lies in the method used to dampen the ball''s velocity after each collision. It seems that the amount of energy lost should be determined by the difference between the balls reflected velocity and the normal of the collision. Is this correct? What is the formula? Will this cause the ball to both bounce and slide on a slope when appropriate?

Share this post


Link to post
Share on other sites
I break down the velocity of the ball along the normal, and the rest (being the direction of the edge in 2D, of the collision plane in 3D).

as to determine if the ball is moving towards the intersection point, I simply do

float vn = Ball.Vel * N;
if (vn > 0.0f) // ball moving away

so, it all becomes



Vector &V = Ball.Vel;
float vn = V * N;
Vector Vn = vn * N;
Vector Vt = V - Vn;
if (vn < 0.0f) Vn = Vector(0.0f, 0.0f);
V -= (1.0f + elasticity) * Vn + friction * Vt;


the friction is more like drag, really. but it slows down the ball. the ball velocity will never reach zero though, so you need to check it yourself against a threshold to stop the ball dead.



Share this post


Link to post
Share on other sites
Thanks Oliii. That kind of worked, but not really.
Just for testing, I ignore the endpoints and treat the collision surface as the line segment at all times. I tried your code but, while it produced a nicer reflection based upon the friction and elasticity (rather than perfectly reflecting the ball’s velocity off the surface), it did not allow the ball do roll down a slope successfully.
The first problem is that the reflection only works correctly on one side of a segment (!). Basically this means that half the time the ball will simply stick to the surface it collides with. This problem is solved simply by checking which side of N the ball’s velocity is on and reversing N in the case that it is facing the wrong way. Problem no longer exists.
The second (main) problem is my ball still does not roll. Sure, it glides down a surface while traveling at speed, but if it is bouncing up a slope, slowing down as it does, it will still comes to a stop on the slope due to the effect of gravity. I can change the value of which I use to move the ball away from a collision after detection to something substantial (ie 1 or 2) and the ball will slide (in an ugly way) – but this is an undesirable option as it looks odd, is incorrect and the ball slides at the exact same speed on any slope (determined by friction and gravity).
Here is the code I adapted (excuse the mess that it is):


Vector2D N = Lines[j].p2 - Lines[j].p1;
if(Balls[i].v.Side(N) != 1)
N.Invert();
//Be sure that N is facing the right way

N.Normalize();

float temp = N.x;
N.x = -N.y;
N.y = temp;

Vector2D &V = Balls[i].v;
float vn = V.Dot(N);
Vector2D Vn = N * vn;
Vector2D Vt = V - Vn;

if (vn < 0.0f)
{
Vn.x = 0.0f;
Vn.y = 0.0f;
}

float elasticity =0.7f;
float friction =0.5f;

V -= Vn * (1.0f + elasticity) + Vt * friction;


Does that look correct? How can I get the ball to slide down a slope correctly?

Share this post


Link to post
Share on other sites
that looks correct.

for the normal sign, I''d check the sign of the sphere position from the collision plane. if it is negative, invert the normal.

as for the correct friction behaviour, it''s tricky. Especially if you want to consider angular velocities so the ball actually rolls, not just slides.

something like


Vector Vt = V - Vn;

Vector Vf = Vt;
Vf.Normalise();
Vf *= -vn;

float elasticity = 0.3f;
float grip = 0.4f;
float drag = 0.1f;

V -= (1.0f + elasticity) * Vn + (drag) * Vt + (grip) * Vf;


it roughly based on the coulomb friction model. the maximum friction force you can get along the tangent plane is the vertical force times a friction constant (grip).

Share this post


Link to post
Share on other sites
Thanks oliii, I used your code, but it still does not get the ball to slide (sorry... I''m obviously not the best at this) . It has the effect of creating a nice reflection off the collision surface, but the ball still stops dead when it gets to be bouncing so low that gravity causes the ball to register a collision every frame. The only way I can get the ball sliding is to change the small value used to move the ball away from a collision from 0.01 to 1 - an even then it does not work particularly well.
I know I''m probably being a pain, but I just can get this to work... I''m thinking that, when detecting collisions, I need move the collision point along the normal of the surface by a certain value somehow determined by the velocity of the ball (the difference between the reflected velocity and the collision normal - but would this cause the ball to roll down a steep slope faster than a shallow one?)...? Any thoughts? Your code works like a charm except it does not solve my main problem

Share this post


Link to post
Share on other sites
if you want pure sliding, you just set the friciton and drag to 0.

so it just becomes

V -= (1.0f + elasticity) * Vn;

not sure what you want exactly though

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Just a remark on the normal:

If we have a circle exactly touching a line, then there is only one point which they both have in common.
The circle should know in which direction to reflect, despite the point by itself can not define a normal! The circle doesn''t know the other points of the line, only the colliding one.

So: the normal used to calculate the reflection vector is circle-center -> collision point or something like that. (think about a circle colliding off a point and see the line as a bunch of points)

Am I right?

You don''t have to check whether the circle hits an end point or not.

Share this post


Link to post
Share on other sites
Ooops... I'm not being very clear am I?
(Hope this helps)
What I mean is that eventually the ball is going to be bouncing so low that gravity will cause the ball to collide with the surface every frame . The result is that the ball stops dead:



The diagram shows the simplified path of the ball as it travels up a sloped surface. The ball ends up virtually on the ground and gravity has the effect of locking the ball into position on the surface. It certainly looks odd when the ball is bouncing down a slope, only to stop dead when it no longer bounces high enough to get off the ground. No matter how I handle reflecting the velocity after a collision the ball is always going to face this problem.

The system works like such:

ball velocity += gravity
Sweep test ball position to ball position plus velocity - note that the swept test does not take gravity into account; it acts as if the ball moved directly from on position to the other
If collision occurred, move to the point of intersection - balls original velocity sized to 0.01 (and calculate new velocity)
If not: ball position += ball velocity

What am I doing wrong here? (Ensuring that the ball’s velocity does not fall beneath a certain value does not work)

[edited by - jack_1313 on April 1, 2004 2:00:57 AM]

Share this post


Link to post
Share on other sites
The reflective model is mainly a hack, and it's not good to base a physics model upon it. It fine for things like camera movement, character movement, and simple physics, but it's in no way a substitute for rigid body dynamics, in the magnitude you want to do. Even for a simple ball rolling down the slope, you'll need some major changes. Not mathematically hard, but the algorithm will change significantly.

OK, now I've got my brain in gear, let's talk

in general, there are three stages/states in a collision. Impact, contact, separation. That's when the contact velocity (V * N) is vn < 0.0f, vn = 0.0f, vn > 0.0f.

Each state reacts differently from a collision. So, if when the ball enters the contact state (it's supposed to roll), you can catch it and do a diferent physical model than when it's colliding. That's one part of the problem.

the more important flaw of the algorithm, is that using the regular reflective model, you never consider the contact velocity, only the ball's linear velocity. Imagine the ball being a tyre on a car. it's like having the brakes locked so the tyre/ball never rotates. you'll see that the tyre will basically skid and comes quickly to a halt.

if the ball is allowed to roll, then it's a different story. The contact velocity will be 0.0f (the tyre will roll freely), so the friction force will be minimal, and the tyre/ball will just roll down the slope like you want.

so, you need to consider some more advanced physics, with the ball having an angular velocity as well as a linear velocity. That involves considering the inertia of the ball, and applying contact forces. But that will allow you to do a lot more realistic stuff though. You can probably hack it, but I would think it's more work than actually doing the proper stuff. It's not that hard. as per usual, you have a basic rigid body physics demo Cube on plane, or in 2D, a more recent physics demo Boxes and spheres. they calculate the contact impulses, the friction forces, the full rigid body update, with inertia matrix, ect... the references are

Chris Hecker
Stephen Ehmann
Sigraff'97 course notes

Martin Baker

and
Rigid body simulation lectures




[edited by - oliii on April 1, 2004 3:27:07 AM]

Share this post


Link to post
Share on other sites
Thanks a lot! I''ll have to get reading... I checked out your 2d demo and was very impressed. A question though: It looks as if the circles in the demo are a construct of connected vertices - is it necessary to treat plain circles that way as it seems like it could be rather inefficient (as opposed to using one large particle)? Of course, using a system like that would allow you to create a polygon of any shape and size and have it bounce around the game world, right? Anyhow, thanks for all the help, I appreciate it. This might take me a while though .

Share this post


Link to post
Share on other sites
it''s just the rendering, which is very low-tech. it''s a sphere (well, a solid circle) in reality. Polygons (at least convex polygons), would just be an extension of the box collision.

Share this post


Link to post
Share on other sites