   Swept Circle->Segment collisions/Step-by-step?
  I created a new thread even if it''s related to my other one (A bunch of 2D OBB questions) because it''s a pretty different topic.I''ve decided not to use OBB for my 2D physics engine which is using verlet-integration, and go with improving my particle->constraint collisions.I''ve been searching the internet for good resources, but I haven''t found any yet. I''d like advice on what''s best between using swept collisions (Which would require the ray to have a width so that the radius of the particle will matter), or going step by step as I''m doing now.Step-by-step is probably faster at low speeds because it only requires one step, but sometimes I might need up to 20 steps to make sure that it doesn''t go straight through constraints.So unless you believe step-by-step is better than doing a ray once from previous position to the target one, I''d be happy if you had links to some articles or something demonstrating how to do it.If you''re interested in seeing what I have now, here''s a couple of demos and screenshots (The archives with "exe" in the end of their names include executables, the others just include BlitzBasic source):http://www.highgearsolutions.com/nexus/upload/andreas/verlet2d/I know that the jeep is buggy at the moment, but I want to finish proper Particle->Constraint collisions before I release a new version.If you have any suggestions on features for it, please let me know!And while I''m ranting anyways, I''m going to implement a rest system into my physics engine, so does anyone have suggestions on how to do this? Should I just check how much it moved last loop and if it''s below a certain treshold, stop satisfying it''s constraints, moving it etc. But considering my engine can satisfy about 30 constraints 10 000 times in 100ms, and that moving the particles when it''s close to still generally involves just a few loops, I don''t think I''ll get a very large speed increase from deactivation... So does anyone have suggestions for what else I can do when deactivating it? I would still need to keep collisions between objects active because otherwise the object would never move again... 
  hey andreas,doing a swept sphere - segment is equivalent to doing a ray-capsule test, which is, a cylinder with hemispheric caps. there are several ways to do it. I''ll present one. for 2D.first, you test a ray against the segment planes, to find the point of collision.  * P0   ^ En  \|   \    |    \   |\ I0    |-----------+--------------------------- E0    \   E1-------*-----\------------*------------    \\ * P1you find I0, and I1. The intersection of the segment Seg[P0, P1] and planes Plane[+/-En, E0 (En*radius)] so, a point P is on segment Seg[P0, P1] if [eq1] P = P0 + (P1 - P0) * tP is on plane Plane[En, D] if [eq2] (P - D) * En = 0so, you replace P in [eq2] by [eq1] and you have an equation in the formt = (radius - (P0 - E0)*En) / ((P1 - P0) * En); //--------------------------------------------------------// calculate the intersection point of a capsule against// a segment.// capsule [E0, E1, r]// ray[P0, P1]// Pcoll = colliison point//--------------------------------------------------------bool CapsuleSegmentCollision(const Vector& E0, const Vector& E1, float radius, const Vector& P0, const Vector& P1, Vector& Pcoll){    //--------------------------------------------------------    // calculate edge parameters (precompute this)    //--------------------------------------------------------    Vector E(E1 - E0);    float  length = E.Length();    E  /= length;    //--------------------------------------------------------    // edge plane parameters    //--------------------------------------------------------    Vector D (P - E0);    Vector En(-E.y, E.x);    //--------------------------------------------------------    // flip normal depending on wich side the ray starts    //--------------------------------------------------------    if (D * En < 0.0f)    En  = -En;   Vector V(P1 - P0); // the ray direction   float numer = radius - D * En;    float denom = V * En;    //--------------------------------------------------------    // if we have an overlap    //--------------------------------------------------------    if (numer > 0.0f){   //-------------------------------------------------------   // project ray start on plane   //-------------------------------------------------------   Pcoll = P0 + En * numer;}else{   //------------------------------------------------------   // check divisions by 0, and sign of t   //------------------------------------------------------   if (denom > 0.00000001f)  return false;   float t = numer / denom;   //------------------------------------------------------   // segment too far away or behind the ray   //------------------------------------------------------   if (t < 0.0f || t > 1.0f)  return false;   //------------------------------------------------------   // calculate intersection point   //------------------------------------------------------   Pcoll = P0 + V * t;    }    //--------------------------------------------------------    // find the closest feature on the edge to Pcoll    //--------------------------------------------------------    D = Pcoll - E0;    float dist = D * E;   //--------------------------------------------------------    // closest feature is edge start    //--------------------------------------------------------    if (dist < 0.0f)   return CircleSegmentCollision(E0, radius, P0, P1, Pcoll);    //--------------------------------------------------------    // closest feature is edge end    //--------------------------------------------------------    else if (dist > length)   return CircleSegmentCollision(E1, radius, P0, P1, Pcoll);    //--------------------------------------------------------    // closest feature is edge itself (we have the colllision    // point already    //--------------------------------------------------------    else    return true;};  I'm in the process of trying out the code in BlitzBasic now, and I was wondering... Is E.Length() Ex * Ex + Ey * Ey   ? Or is it Sqr(Ex * Ex + Ey * Ey)   ?I guess it's the first one, because otherwise it should say E.SquaredLength() right?Oh, and CircleSegmentCollision() is just a function that returns true and sets the collision points if the specified point with radius is overlapping given segment I suppose?EDIT:I see you're using the vector P here:Vector D (P - E0);But I don't see it being set anywhere... Is it supposed to be P0 or P1?   [edited by - andreas_blixt on February 4, 2004 12:17:39 PM];quote:Original post by andreas_blixt  I''m in the process of trying out the code in BlitzBasic now, and I was wondering... Is E.Length() Ex * Ex + Ey * Ey? Or is it Sqr(Ex * Ex + Ey * Ey)?I guess it''s the first one, because otherwise it should say E.SquaredLength() right?Nope, it''s the second one, with the square root. It''s the length of the vector, not the length, squared. It''s a pain, (sqrt and all), but it''s inevitable. You can cache the value inside the constraint segment every frame. CircleSegmentCollision() would be a function that tests a segment''s vertex, expqnded by a radius, with the segment. quote:EDIT:I see you''re using the vector P here:Vector D (P - E0);  But I don''t see it being set anywhere... Is it supposed to be P0 or P1?  It''s P0.To remind you, P0 is the position of the particle, and P1 is the predicted position of the particle befor processing a collision. the CirleCollision Function...I''ll be using a second order equation solving.  bool CircleSegmentCollision(const Vector& C, float r, const Vector& P0, const Vector& P1, Vector& Pcoll){    Vector V = P1 - P0;    Vector D = P0 - C;    //----------------------------------------------------------    // overlap    //----------------------------------------------------------    if (c < 0.0f)    {    float d = D.Length();    float depth = r - d;    D *= depth / d;    Pcoll = P0 + D;    return true;}    float c = D * D - r*r;    float b = 2.0f * D * V;    float a = V * V;    float d = b*b - 4*a*c;   if (d < 0.0f)   return false;    d = sqrt(d);    float t0 = (-b - d) / (2.0f * a);    float t1 = (-b + d) / (2.0f * a);    if (t0 > t1)    {   float temp = t0; t0 = t1; t1 = temp;    }    if (t0 > 1.0f || t1 < 0.0f)   return false;    t = t0;    if (t0 < 0.0f)   t = t1;    if (t < 0.0f)   t = t1;    Pcoll = P0 + V * t;    return true;};  ok, the explain the circle / segment intersection test has been explain 100s of times in the forums. But if you have  a problem understanding how it''s done, ...It''s based on solvong a second order equationA point P is on segment [P0, P1] if [eq1] P = P0 + t.(P1 - P0), 0 <= t <= 1.a point P is on surface of a sphere (or circle) (C, r) if [eq2] (P - C)^2 = r^2replace P from [eq1] into [eq2]and you get((P0 - C) + t . (P1 - P0)) ^ 2 = r^2it''s an equation in the form (A + B.t)^2 = r^2develop and you get(B.B).t^2 + (2 * A.B) . t + (A.A - r^2) = 0it''s a second order in the form a.t^2 + b.t + c = 0wherea = (B.B)b = 2 . (B.A)c = A.A - r^2solving for t, d = b*b - 4*a*cif (d < 0) return no_intersection;t0 = (-b - sqrt(d)) / (2 * a)t1 = (-b + sqrt(d)) / (2 * a)take the first positive root between the two, and you get the parameter of intersection. plug t back into the first equation, and you get the point of collision. that is, the point both on the segment and the sphere surface. a word on optimisation. I think it would be faster to test constraint segments on one hand, and the particles on the other hand. Then you avoid duplicate tests. the code would look like  void CBody::Collide(CBody& Body){    for(int i = 0; i < m_iNumParticles; i++)    {    for(int j = 0; j < Body.m_iNumParticles; j ++)    {   m_xParticle[i].Collide(Body.m_xParticle[j]);    }    for(int j = 0; j < Body.m_iNumConstraints; j ++)   {  m_xParticle[i].Collide(Body.m_xConstraint[j]);   }    }    for(int j = 0; i < Body.m_iNumParticles; i++)    {   for(int i = 0; i < m_iNumConstraints; i ++)   {  Body.m_xParticle[j].Collide(m_xConstraint[i]);   }    }}and the particle particle collision would be that CircleCircle() collision detection code, while the constraint-particle collision would be the code I explained in the first post, without the need to test for end points. If the collision point is outside the edge, return false. The particle/particle collision will take care of it. {......    if (dist < 0.0f || dist > length) return false;    return true;} ;  Okay, thanks for the help!Now, I'm not particularily experienced in C, and I've always had problems with vectors... I've managed to convert everything, except things like these:float dist = D * E;if (D * En) < 0.0fetc.  How do I convert a vector into a single value? I'm currently using Dx,Dy and Ex,Ey instead of vectors.quote:To remind you, P0 is the position of the particle, and P1 is the predicted position of the particle before processing a collision.It can't be like that, because P0,P1 is the segment (constraint), not the moving particle.   [edited by - andreas_blixt on February 4, 2004 6:58:28 PM];  A * B is A ''dot'' B. It''s a dot product operator and is equal to A . B = A * B = DotProduct(A, B) = (A.x * B.x) + (A.y * B.y);;quote:Original post by andreas_blixt  It can''t be like that, because P0,P1 is the segment (constraint), not the moving particle.    I think I need to clarify. OK, you have a moving sphere. The sphere has a radius [r], a start position [P0] and a end position [P1]. The edge has end points [E0, E1], and also a radius [e].To do a moving sphere versus the edge, is equivalent to testing the segment [P0, P1] with the capsule [E0, E1, r+e]. the point of collision is where the particle''s position has to be moved so that the constraint and particle just touch. so,  bool CConstraint::Collide(Cparticle& Particle) const{    Vector Pcoll;    const Vector& E0 = m_pxParticle[0]->m_xP0;    const Vector& E1 = m_pxParticle[1]->m_xP0;    const Vector& P0 = Particle.m_xP0;    const Vector& P1 = Particle.m_xP1;    float radius= m_pxParticle[0]->m_fRadius + Particle.m_fRadius;    if (!CapsuleSegmentCollision(E0, E1, radius, P0, P1, Pcoll))   return false;    Particle.m_xP1 = Pcoll;    return true;}note that, to be more accurate, you should also consider the masses of the particles, and consequently move the constraint''s end points as well as the particle. So, if the particle is massive, and the constraint''s end points are light, the constraint extremities will be pushed too. This usually involves using the ratio of ''dist'' found at the end of the function, and the edge length. ''dist / length'' will give the interpolation factor (between 0 and 1), so you can apply weights appropriately to the particle, but also the particles at the end of the constraint. You''ve got to take a closer look at Jakobsen''s paper, near the end. It explains how to do it for a particle against an edge, it''s the same principle. ;  hi andreas, its me on the subject of finding your collisions stepwise or by solving their movement equations...ive done both for 2d, and they both have their pros and cons. stepwise, where the number of steps depends on the speed, is a little slower and in some cases inaccurate.youd be inclined to go for the other option then, but it gave me mayor headaches with rounding problems, ie when particles came to rest on another constraint things went wrong, and there were also problems with concavities in my geometry. besides that i also saw some more problems on the horizon regarding curved objects. im not saying these things cant be solved, quite obviously its possible, but all there things were not an issue when using the stepwise method.well, anyway, id give both methods a shot, and just see what works out best, because i wasnt using verlet, and that will probably make things different. all im saying is that you shouldnt disregard the stepwise collision detection altogether, because it has its merits.succes ;  Oliii, okay I understand now about the constraint having a radius instead of the particle in the code. I was just thinking logically And thanks for the explanation on how to convert vectors into single values, I was suspecting it''d be something like that.Hi Eelco, you made that bridge simulator right? The only issue I have with steps is that they''re slower. Otherwise they give better results, their accuracy is perfect, and they are easier (In my case anyways). I''m still thinking about the step-wise version, so we''ll just have to see how it turns out. 