• Advertisement
Sign in to follow this  

verlet object-object collision

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

Hi, I'm working on collision detection and response between two verlet bodies (specifically 2D boxes). Right now I'm basically testing to see if a vertex intersects the contraint of another box. I then move the vertex half the shortest distance to the contraint and the 2 vertices that make up the contraint the same distance in the opposite direction (this basically ignores the point of intersection and the masses of the boxes, but it works fine for testing purposes). I'm having a problem testing if the vertex intersects a contraint. I've tried using the current position and the old position to do line segment-line segment collision. A collision is detected, but the response doens't work out as it should (the boxes intersect each other). I ended up using the current position and the center of the box for the line segment, which actually works fine. I would just continue using this method, but I'll run into problems when I implement ragdolls since they have no "center". I'm still confused on why using the old position isn't working (I'm probably missing something really obvious >_>). Also, I tried using the position of the particle next to the offending vertex as the endpoint of the line segment, but that didn't work either, and the boxes would be projected off each other extremly fast and would sometimes even collapse into an L. Thanks for any help.

Share this post

Link to post
Share on other sites
I haven't found something satisfactory concerning verlet systems collision and response.

here is a wild idea...

When you detect iontersection between two sticks, add two constrains, collision constraints, between the offending vertex (V) and the point on the stick [A, B] the closest to the offending vertex (call it point C). Resolve that constrain with length = 0 (obviously).

That's ok, now when C is solved (movinf towards position C'), it will have to influence provide a response on stick [A B]. so that A and B move to A' and B'.

Now, in what way A and B have to move? that's a bit tricky.

Share this post

Link to post
Share on other sites
Here's what I've used for a vertex (C) to line segment (AB) collision response. This method approaches a particle-particle collision when the impact point approaches either end of the line segment, while at the center of the segment it'll affect all three particles. Light particles are affected more than heavy ones.

Collect the following data:
p = the relative impact position along the line segment (0...1)
N = the normal vector of the line segment (pointing to the outside of the object)
d = penetration depth (along the normal)

A' = A - N*d*(1-p)*(C.mass / (A.mass + C.mass) )
B' = B - N*d*p*(C.mass / (B.mass + C.mass) )

Then project the position of C to the new line A'B'. You can use the N vector multiplied by a factor derived from the above, or the closest point or whatever as long as it gets the particle out to the "surface".

Note that this is not "physically correct", as you can see in the case of each particle having mass of 1 and the impact being in the dead center... The line segment will move in by 0.25*d while the impacting particle will move out by 0.75*d. The real values should be 0.333..*d and 0.666..*d. Nevertheless I think this is how I did it when I was experimenting with 2d verlet physics a while back and it looked just fine in action.

Share this post

Link to post
Share on other sites
actually, my main problem is actaully detecting the collision. It works fine when I test the line segment from the vertex to the center of the box against the contraints of another box, but it doesn't if I use the old position or the next vertex to form the line segment. I don't understand why they don't produce the same results, since I only use that line segment for collision detection, not the response part.


Share this post

Link to post
Share on other sites
Yes, I've seen that before. This is likely because the constrain you are testing against also move, so it could potentially move beyond the oldpos of your particle, so you wouldn't detect it.

To be prefectly accurate, you have to take into account the fact that the stick changes shape also, in equations, it would turn into something like this...

P' = P + Dp * t (particle)
A' = A + Da * t (start point on stick)
B' = B + Db * t (end point on stick)

N' = Perp(B - A) = Vector((A.y - B.y) + (Da.y - Db.y) * t, (B.x - A.x) + (Db.x - Da.x) * t)

collision when

(P' - A') . N' = 0

=> second order equation to solve for (t).

not that bad.

... that is if my maths are right :)

Share this post

Link to post
Share on other sites
I'm glad you actually stirred up that problem. Makes me wanna tinker with verlet again ;)

Share this post

Link to post
Share on other sites
Sorry, but could you explain that a bit more? I'm having a bit of trouble understanding it. Are the P', A', and B' supposed to stand for the current positions, and the P, A, and B for the old positions? So do you solve for the Dp, Da, and Db?

Thanks for all the help so far though

Share this post

Link to post
Share on other sites
P' is new position for P at the time of collision (t), which you try to find. same for A' for A, B' for B.

Dp, Da, and Db are the displacement. OK, let's call them Vp, Va, Vb, for velocity, even if it is displacement, not velocities, maybe it will look better.

P' will be between P and P + Vp, so 't' will be between [0, 1].

So, you solve for t. P, A, B, Vp, Va, Vb are known, you are left with t.

t has to be in the range [0, 1] obviously. If not, the particle does not collide.

I might as well solve it then...

ok, so you have a particle P moving from Pold to Pnew. You try to find Pcoll, the position of the particle at time of collision t. You also have a segment [A, B], and the segment ends move in a similar fashion. Aold -> Anew, Bold -> Bnew.

Pcoll = Pold + (Pnew - Pold) * t
Acoll = Aold + (Anew - Aold) * t
Bcoll = Bold + (Bnew - Bold) * t

and the point Pcoll will be on infinite line (Acoll, Bcoll) at time t if

or (Pcoll - Acoll).Cross(Bcoll - Acoll) = 0

(reminder. in 2D, A x B = (A.x*B.y - A.y*B.x)).
(equivalent to ((Pcoll - Acoll).Dot((Bcoll - Acoll).Perp()) = 0

Vector AP = Pold - Aold
Vector AB = Bold - Aold

Vector Vp = Pnew - Pold
Vector Va = Anew - Aold
Vector Vb = Bnew - Bold

Vector Vap = Vp - Va
Vector Vab = Vb - Va

(AP+Vap*t).Cross(AB+Vab*t) = 0

[(AP.x+Vap.x*t) * (AB.y+Vab.y*t)] - [(AP.y+Vap.y*t) * (AB.x+Vab.x*t)] = 0

expanding, this yields a second order equation in the form :

a.t^2 + b.t + c = 0

float a = (Vap.x * Vab.y) - (Vap.y * Vab.x)
float b = (AP.x*Vab.y + AB.y*Vap.x) - (AP.y*Vab.x + AB.x*Vap.y)
float c = (AP.x * AB.y) - (AP.y * AB.x)
float d = (b*b - 4*a*c)

if (d < 0.0f) no collision

t0 = (-b - sqrt(d)) / (2*a)
t1 = (-b + sqrt(d)) / (2*a)
tmax = max(t0, t1)
tmin = min(t0, t1)

if (tmin > 1.0f || tmax < 0.0f) no collision
t = (tmin > 0.0f)? tmin : tmax

plug t back in
=> Pcoll = Pold + (Pnew - Pold) * t
=> Acoll = Aold + (Anew - Aold) * t
=> Bcoll = Bold + (Bnew - Bold) * t

you need to check if Pcoll is on segment, not just on the infinite line.

=> float u = (Pcoll - Acoll) . (Bcoll - Acoll) / (Bcoll - Acoll) . (Bcoll - Acoll)
if (u < 0.0 || u > 1.0f) no collision

if all is OK, you will then have

Pnew = Pcoll
Anew = Acoll
Bnew = Bcoll

Hopefully, no typo :)

bool ParticleSegmentCollide(const Vector& Pold, Vector& Pnew,
const Vector& Aold, Vector& Anew,
const Vector& Bold, Vector& Bnew, float& t)
Vector AP = Pold - Aold;
Vector AB = Bold - Aold;
Vector Vp = Pnew - Pold;
Vector Va = Anew - Aold;
Vector Vb = Bnew - Bold;
Vector Vap = Vp - Va;
Vector Vab = Vb - Va;

float a = (Vap.x * Vab.y) - (Vap.y * Vab.x);
float b = (AP.x*Vab.y + Ab.y*Vap.x) - (AP.y*Vab.x + AB.x*Vap.y);
float c = (AP.x * AB.y) - (AP.y * AB.x);
float d = (b*b - 4*a*c);

if(d < 0.0f)
return false;

float t0 = (-b - sqrt(d)) / (2.0f * a);
float t1 = (-b + sqrt(d)) / (2.0f * a);
float tmin = (t1 < t0)? t1 : t0;
float tmax = (t1 > t0)? t1 : t0;

if(tmin > 1.0f || tmax < 0.0f)
return false;

float tcoll = (tmin < 0.0f)? tmax : tmin;

if(tcoll > 1.0f || tcoll < 0.0f)
return false;

Vector Pcoll = Pold + Vp * tcoll;
Vector Acoll = Aold + Va * tcoll;
Vector Bcoll = Bold + Vb * tcoll;

AP = Pcoll - Acoll;
AB = Bcoll - Acoll;

float u = (AP * AB) / (AB * AB); // '*' = dot product!

if (u < 0.0f || u > 1.0f)
return false;

Pnew = Pcoll;
Anew = Acoll;
Bnew = Bcoll;
t = tcoll;

return true;

[Edited by - oliii on September 26, 2006 4:44:44 AM]

Share this post

Link to post
Share on other sites
to put this thing (and my mind) to rest, I've cooked up a little demo.

Particle collision.cpp

you will need :

- Opengl GLUT.
- directX SDK if you want to use my direct input stuff (maybe they are provided with Visual Studio).

It calculate the collision between a particle and a segment.
1) If segment and particle are moving (the case I demonstrated in the post above)
2) if only the particle is moving (particle against a static segment)
3) none of the above (just push particle away from segment, to a safe distance).

drag points (arrow heads and start positions).
-> see intersection results.
'A' 'B' and 'P' to reset the displacement of particles.
' ' resets everything.

This is not included within a physics framework, just a demonstration of the collision detection.


Share this post

Link to post
Share on other sites
last update. I played around with a simple demo, with triangles. It's not working [crying].

I was hoping to get a system similar to when doing collision tests with static geometry only, where you can be guaranteed to never intersect, but it's not working at all.

Here is the code in any case.

'r' to reset
' ' to step by step
RETURN to unpause
hold mouse to drag points around.

and the two input files

Share this post

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

  • Advertisement