verlet object-object collision

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.

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)

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

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.

Thanks

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

I'm glad you actually stirred up that problem. Makes me wanna tinker with verlet again ;)

also, if this solves nicely in 2D, I'm then thinking... 3D!

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

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]

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.

Enjoy!

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
source
header