• ### What is your GameDev Story?

#### Archived

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

# Ragdoll Physics and Collision Response

This topic is 5430 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

you don't have to do anything as soon as you found a collision.

From my understanding, you should never have access to the oldpos particle, because it's what ensures that the particle will never go through triangles. oldpos should always be 'valid' at all times. it also controls the actual momentum of the particle, so messing around with it could maybe mess up the energy of the system. But what you can try is, if you have a collision, flag the particle has collided, and in the next integration step, move the oldpos, not onto the newpos, but slightly before, which should account for friction.

anway, by just constraining newpos to the triangle surfaces, you'll see that you'll already have some friction going on, because you'll loose whatever part of the segment that ends up on the other side of the triangle. The only way to have a friction-less system and stop loosing energy, would be to slide the particle on the triangles, as shown below.

think of the test as a swept particle test, without considering constraints. so you can imagine the particle bouncing from triangle to triangle, on its own, with some elasticity and friction.

that would be the steps to take inside the triangle / particle collision detection loop (the for() loop).

1) integrate all particles

while (iteration < 5)
----2) satisfy the stick constraints, can eventualy push the newpos of particles through the triangles.
wend

for (each particle)
----3) create a segment (e0, e1) with vectors (oldpos, newpos)
do
--------4) find first intersection of segment and triangles
--------5) if no intersection, break the loop
--------6) move e0 to the surface of triangle, plus exta bit
--------7) REFLECT e1 off the triangle surface
while (num collision iterations < 10)
----8) newpos = e1
end for

9) goto 1

and you can control the friction and possibly some extra bounciness with the REFLECT function.

the reflect step is basically some collision response, a bit like

Vector d1;  // vector from pcoll to end point e1Vector dn1; // d1, projected on the normal of collisionVector dt1; // d1, projected on the triangle planed1  = e1 - pcoll;e0  = pcoll;      // move end point to point of collisiondn1 = (d1 * ncoll) * ncoll; // d1 along nromal of collisiondt1 = d1 - dn1; // d1 on plane of collision//------------------------// compute the response//------------------------d1 = dn1 * (-elasticity) + dt1 * (1.0f - friction);//------------------------// calculate the end point of segment after response//------------------------e1 = e0 + d1;

well, I'd try that at least. So, you can end up doing several tests per particle, per frame. So you'll need an even faster cullinf method to get the triangles close to the particle, to reduce the number of tests. You can have a large bounding box around the particle, to account for every eventual particle movements, ect...

[edited by - oliii on February 21, 2004 12:38:26 PM]

##### Share on other sites
I''m not sure I follow you completely...

So I would keep my integration function and my stick-constraints loop the same.
I keep my collision loop separate (but following) the stick-constraints loop.

The new collision loop you describe confuses me...

Iterate through all particles
{
----Segment L = particle.oldPos to particle.position
----Iterate 10 times

##Is there a reason you chose 10 instead of 5?

----{
--------Iterate through all _nearby_ triangles
--------{
------------Test intersection of Segment L and current triangle

##This is where I get confused:

------------If no intersection is found, break the loop.

##So you''re saying, if no intersection is found with ANY of the _nearby_ triangles, stop the ENTIRE collision loop? Or just stop one of the embedded loops? Or is it, if no intersection is found with the FIRST of the _nearby_ triangles, ....?

##### Share on other sites
Yeah, it''s only in the collision loop that it needs changing. To clarify, here is the pseudo code

bool CSegment::Intersect(const CTerrain* pxTerrain, float& tcoll, Vector& Ncoll, Vector& Pcoll){    bool bCollided = false;    for(int i = 0; i < pxTerrain->m_iNumTriangles; i ++)    {         float ttri;         Vector Ptri;         Vector Ntri;         if (Intersect(pxTerrain->m_xTriangle[i], ttri, Ntri, Ptri))         {             if (ttri < tcoll)             {                 bCollided = true;                 tcoll = ttri;                 Pcoll = Ptri;                 Ncoll = Ntri;             }         }    }    return bCollided;}void CSegment::Slide(const Vector& pcoll, const Vecor& ncoll, float tcoll, float friction=0.01f, float elasticity = 0.5f){    Vector d;  // vector from pcoll to end point e1    Vector dn; // d1, projected on the normal of collision    Vector dt; // d1, projected on the triangle plane    Vector& e0 = m_xStartPoint;    Vector& e1 = m_xEndPoint;    d1 = e1 - pcoll;    e0 = pcoll; // move end point to point of collision    dn1 = (d1 * ncoll) * ncoll; // d1 along nromal of collision    dt1 = d1 - dn1; // d1 on plane of collision    //------------------------    // compute the response    //------------------------    d1 = dn1 * (-elasticity) + dt1 * (1.0f - friction);    //------------------------    // calculate the end point of segment after response    //------------------------    e1 = e0 + d1;}void CSegment::CollideAndSlide(const CTerrain* pxTerrain, float fFriction=0.01f, float fElasticity = 0.5f){    int iMaxIterations = 8;    for(int i = 0; i < iMaxIterations; i ++)    {        Vector Pcoll, Ncoll;        float  tcoll = 1.0f;        if (Intersect(pxTerrain, tcoll, Ncoll, Pcoll) == false)        {            return;        }                Slide(Pcoll, Ncoll, tcoll, fFriction, fElasticity);    }}void ParticleSystem::FindColisions(const CTerrain* pxTerrain){    for(int i = 0; i < m_iNumParticles; i ++)    {         CSegment Segment(m_xParticle[i].m_xOldPos, m_xParticle[i].m_xNewPos);         Segment.CollideAndSlide(pxTerrain);             m_xParticle[i].m_xNewPos = Segment.m_xEndPoint;    }}

##### Share on other sites
I notice in your CSegment::Intersect function you have:

if (Intersect(pxTerrain->m_xTriangle[i], ttri, Ntri, Ptri))...

Is this "Intersect" function another function or the same (recursive) function?
If it's simply to determine if the segment intersects the triangle, can you please post this function as well, as my Line-Triangle intersect function doesn't take the extra parameters you have here. Thank you.

EDIT:
Okay. Obviously its to test line-triangle intersection. I've tried modifying my function to match it, but it doesn't appear to work. An explanation of what ttri, Ntri, and Ptri are would help.

[edited by - mattbbangin on February 22, 2004 8:43:49 AM]

##### Share on other sites
Oliii- I''m curious, in practice does your method of collision response with non-zero elasticity work very well?

And to clarify, you place e0 on the surface (at the collision point), e1 is reflected and newpos is set to e1 while oldpos is left alone.

Doesn''t this mean that on the next frame the implicit velocity has the direction e1-oldpos instead of e1-e0? Does that work, or does it at least appear to provide an acceptable appearance of bounciness?

Also does adding collision response in this manner affect objects that are at rest? The problem with standard dynamics solutions that don''t specifically handle resting contact (which is a hard problem in and of itself) is that objects at rest tend to vibrate a bit. The nice thing about this verlet integration is it would appear that objects at rest are naturally rock solid. It would be a shame to loose that feature.

##### Share on other sites
Just to make sure, I''m still in need of an explanation of how you get tcoll, Pcoll, and Ncoll out of your CSegment-Triangle Intersection function. I think I''ve figured out what each variable is (tcoll = time of collision, Pcoll = collision/intersection point, Ncoll = collision normal...right?). I''ve tried modifying my ISOMath_TrianglefContainsLinef function to spit out these results, but I can''t seem to get it right.

##### Share on other sites
*sigh* Okay. I figured all of the above out. It was a combination of my long break from programming (newbie errors ) and not knowing how to derive ttri (or tcoll?) It almost works, but there's one problem. The body now falls freely towards the triangle; collides; then friction appears to be applied during the collision as the body slowly passes through the triangle and continues through the other side. Here's what I'm doing:

static inline void AMParticleSystem_TimeStep(AMParticleSystem *system, float timePassed, Trianglef *worldTriangles, int numTriangles){    system->fTimeStep = timePassed;    AMParticleSystem_AccumulateForces(system);    AMParticleSystem_VerletStep(system);    AMParticleSystem_SatisfyConstraints(system, worldTriangles, numTriangles);    AMParticleSystem_FindCollisions(system, worldTriangles, numTriangles);}static inline void AMParticleSystem_FindCollisions(AMParticleSystem *system, Trianglef *worldTriangles, int numTriangles){    int i;        for(i=0;i<system->numParticles;i++)    {	Rayf segment = ISOMath_MakeRayf(system->particles[i].oldPosition, system->particles[i].position);		AMParticleSystem_Rayf_CollideAndSlide(system, &segment, worldTriangles, numTriangles, 0.0, 1.0);		system->particles[i].position = segment.finish;    }}static inline void AMParticleSystem_Rayf_CollideAndSlide(AMParticleSystem *system, Rayf *ray, Trianglef *worldTriangles, int numTriangles, float friction, float elasticity){    int maxIterations = 8;        int i;        for(i=0;i<maxIterations;i++)    {	Vector3f Pcoll, Ncoll;	float tcoll = 1.0;		if(AMParticleSystem_Rayf_Intersect(system, ray, worldTriangles, numTriangles, &tcoll, &Ncoll, &Pcoll)==FALSE)	    return;		AMParticleSystem_Rayf_Slide(ray, &Pcoll, &Ncoll, tcoll, friction, elasticity);    }}static inline void AMParticleSystem_Rayf_Slide(Rayf *ray, Vector3f *pcoll, Vector3f *ncoll, float tcoll, float friction, float elasticity) //friction = 0.01, elast = 0.5{    Vector3f pcollNR = ISOMath_MakeVector3f(pcoll->x,pcoll->y,pcoll->z), ncollNR = ISOMath_MakeVector3f(ncoll->x,ncoll->y,ncoll->z);        Vector3f d1;    Vector3f dn1;    Vector3f dt1;    Vector3f e0 = ray->start;    Vector3f e1 = ray->finish;        d1 = ISOMath_Vector3fOpSub(e1,pcollNR);    e0 = pcollNR; ray->start = e0;        //dotproduct? scalar?    dn1 = ISOMath_Vector3fScalarOpMult(ncollNR, ISOMath_Vector3fDotProduct(d1,ncollNR));    dt1 = ISOMath_Vector3fOpSub(d1,dn1);        d1.x = dn1.x*(-elasticity)+dt1.x*(1.0-friction);    d1.y = dn1.y*(-elasticity)+dt1.y*(1.0-friction);    d1.z = dn1.z*(-elasticity)+dt1.z*(1.0-friction);        e1 = ISOMath_Vector3fOpAdd(e0,d1);    ray->finish = e1;}static inline BOOL AMParticleSystem_Rayf_Intersect(AMParticleSystem *system, Rayf *ray, Trianglef *worldTriangles, int numTriangles, float *tcoll, Vector3f *Ncoll, Vector3f *Pcoll){    BOOL collided = FALSE;        int i;    for(i=0;i<numTriangles;i++)    {	float ttri;	Vector3f Ptri;	Vector3f Ntri;		if(!ISOMath_TrianglefContainsLinef(system->fTimeStep, worldTriangles[i], ray->start, ray->finish, &ttri, &Ntri, &Ptri))	    continue;		if(ttri<*(tcoll))	{	    *tcoll = ttri;	    *Pcoll = Ptri;	    *Ncoll = Ntri;		    collided = TRUE;	}    }        return(collided);}static inline BOOL ISOMath_TrianglefContainsLinef(float tDelta, Trianglef t, Vector3f a, Vector3f b, float *tcoll, Vector3f *ncoll, Vector3f *i){    Vector3f p1 = a;    Vector3f p2 = b;    Vector3f pa = t.vertex[0];    Vector3f pb = t.vertex[1];    Vector3f pc = t.vertex[2];        float d;    float a1,a2,a3;    float total,denom,mu;    Vector3f n,pa1,pa2,pa3;        n.x = (pb.y-pa.y)*(pc.z-pa.z)-(pb.z-pa.z)*(pc.y-pa.y);    n.y = (pb.z-pa.z)*(pc.x-pa.x)-(pb.x-pa.x)*(pc.z-pa.z);    n.z = (pb.x-pa.x)*(pc.y-pa.y)-(pb.y-pa.y)*(pc.x-pa.x);    n = ISOMath_Vector3fNormalize(n);    d = -n.x*pa.x-n.y*pa.y-n.z*pa.z;        denom = n.x*(p2.x-p1.x)+n.y*(p2.y-p1.y)+n.z*(p2.z-p1.z);    if(fabsf(denom)<EPSILON)	return(FALSE); // line and plane dont intersect        mu = -(d+n.x*p1.x+n.y*p1.y+n.z*p1.z)/denom;    i->x = p1.x+mu*(p2.x-p1.x);    i->y = p1.y+mu*(p2.y-p1.y);    i->z = p1.z+mu*(p2.z-p1.z);    if(mu<0||mu>1) // intersection not along line segment	return(FALSE);        pa1.x = pa.x-i->x;    pa1.y = pa.y-i->y;    pa1.z = pa.z-i->z;    pa1 = ISOMath_Vector3fNormalize(pa1);    pa2.x = pb.x-i->x;    pa2.y = pb.y-i->y;    pa2.z = pb.z-i->z;    pa2 = ISOMath_Vector3fNormalize(pa2);    pa3.x = pc.x-i->x;    pa3.y = pc.y-i->y;    pa3.z = pc.z-i->z;    pa3 = ISOMath_Vector3fNormalize(pa3);    a1 = pa1.x*pa2.x+pa1.y*pa2.y+pa1.z*pa2.z;    a2 = pa2.x*pa3.x+pa2.y*pa3.y+pa2.z*pa3.z;    a3 = pa3.x*pa1.x+pa3.y*pa1.y+pa3.z*pa1.z;    total = (acos(a1)+acos(a2)+acos(a3))*RTOD;    if(abs(total-360)>EPSILON)	return(FALSE);        Vector3f iTemp = ISOMath_MakeVector3f(i->x,i->y,i->z);    float timeToIntersect = ISOMath_Vector3fLength(ISOMath_Vector3fOpSub(iTemp, a)); //a = starting point?    float originalSpeed = ISOMath_Vector3fLength(ISOMath_Vector3fOpSub(b,a))/tDelta;    float timeToIntersectCorrect = timeToIntersect/originalSpeed;        *tcoll = timeToIntersect;    *ncoll = n;        return(TRUE);}

So to sum it up. The particle appears to be colliding correctly with the triangle, but it's being pushed through (or allowed to fall through) for some reason. Please help! This is too exciting!

P.S.
I know very little about C++ really. I believe I might be having a problem with porting your C++ Vector class operators into my own little scheme (ie, * for dotproduct, etc. All that kind of stuff confuses me ) Take a look at my AMParticleSystem_Rayf_Slide() function where I have a comment "//dotproduct? scalar?" to see what I mean.

P.P.S.
    #define _PI 3.1415926535897    #define EPSILON 0.0000001    #define RTOD 180.0/_PI    world = (Trianglef*)malloc(2*sizeof(Trianglef));    numWorldTriangles = 2;    world[0] = ISOMath_MakeTrianglef(ISOMath_MakeVector3f(30.0,10.0,30.0), ISOMath_MakeVector3f(0.0,15.0,30.0), ISOMath_MakeVector3f(0.0,10.0,0.0));    world[1] = ISOMath_MakeTrianglef(ISOMath_MakeVector3f(30.0,10.0,30.0), ISOMath_MakeVector3f(0.0,10.0,0.0), ISOMath_MakeVector3f(30.0,5.0,0.0));

[edited by - mattbbangin on February 23, 2004 11:51:24 AM]

[edited by - mattbbangin on February 23, 2004 11:55:24 AM]

[edited by - mattbbangin on February 23, 2004 11:57:45 AM]

[edited by - mattbbangin on February 23, 2004 12:02:30 PM]

##### Share on other sites
Just to clarify, when you say:

>>dn1 = (d1 * ncoll) * ncoll;

(d1 * ncoll) is the dot-product, correct?
and (d1 * ncoll) * ncoll would be a scalar component multiplication?

##### Share on other sites
Oh my. I am cursed.

---
In my ISOMath_TrianglefContainsLinef() function, changed if(my<0||mu>1) to if(mu<0-EPSILON||mu>1+EPSILON) . (Someone told me I needed to "test a range a of values", this is how I interpreted that.) Also changed the 360 in if((total-360) to 360.0 (not sure if it matters..)

I am now extending the line-segment (particles movement) going through the segment's end point and passing it's start point a little bit (0.098 to be exact).

(Collision Step) Friction is 0.01, Elasticity is 0.1

system->numIterationsPerStep (Linear Constraints Step) is 10, maxIterations (Collision Step) is 5.

For debugging purposes, fTimePassed is now always 0.01.
---

Now, the body doesn't fall through the triangles anymore. HOWEVER , the body now becomes STUCK to the triangle. It does however, slide along the triangle very nicely (ala gravity), and eventually become un-stuck when it reaches the edge of the triangle. Woe is me! (heh) ;P

P.S.
Here's my latest code:
//Intersectionstatic inline BOOL ISOMath_TrianglefContainsLinef(float tDelta, Trianglef t, Vector3f a, Vector3f b, float *tcoll, Vector3f *ncoll, Vector3f *i){    Vector3f p1 = a;    Vector3f p2 = b;    Vector3f pa = t.vertex[0];    Vector3f pb = t.vertex[1];    Vector3f pc = t.vertex[2];        float d;    float a1,a2,a3;    float total,denom,mu;    Vector3f n,pa1,pa2,pa3;        n.x = (pb.y-pa.y)*(pc.z-pa.z)-(pb.z-pa.z)*(pc.y-pa.y);    n.y = (pb.z-pa.z)*(pc.x-pa.x)-(pb.x-pa.x)*(pc.z-pa.z);    n.z = (pb.x-pa.x)*(pc.y-pa.y)-(pb.y-pa.y)*(pc.x-pa.x);    n = ISOMath_Vector3fNormalize(n);    d = -n.x*pa.x-n.y*pa.y-n.z*pa.z;        denom = n.x*(p2.x-p1.x)+n.y*(p2.y-p1.y)+n.z*(p2.z-p1.z);    if(fabsf(denom)<EPSILON)	return(FALSE); // line and plane dont intersect        mu = -(d+n.x*p1.x+n.y*p1.y+n.z*p1.z)/denom;    i->x = p1.x+mu*(p2.x-p1.x);    i->y = p1.y+mu*(p2.y-p1.y);    i->z = p1.z+mu*(p2.z-p1.z);    if(mu<0-EPSILON||mu>1+EPSILON) // intersection not along line segment	return(FALSE);        pa1.x = pa.x-i->x;    pa1.y = pa.y-i->y;    pa1.z = pa.z-i->z;    pa1 = ISOMath_Vector3fNormalize(pa1);    pa2.x = pb.x-i->x;    pa2.y = pb.y-i->y;    pa2.z = pb.z-i->z;    pa2 = ISOMath_Vector3fNormalize(pa2);    pa3.x = pc.x-i->x;    pa3.y = pc.y-i->y;    pa3.z = pc.z-i->z;    pa3 = ISOMath_Vector3fNormalize(pa3);    a1 = pa1.x*pa2.x+pa1.y*pa2.y+pa1.z*pa2.z;    a2 = pa2.x*pa3.x+pa2.y*pa3.y+pa2.z*pa3.z;    a3 = pa3.x*pa1.x+pa3.y*pa1.y+pa3.z*pa1.z;    total = (acos(a1)+acos(a2)+acos(a3))*RTOD;    if(abs(total-360.0)>EPSILON)	return(FALSE);        Vector3f iTemp = ISOMath_MakeVector3f(i->x,i->y,i->z);    float timeToIntersect = ISOMath_Vector3fLength(ISOMath_Vector3fOpSub(iTemp, a)); //is this supposed to be a or b?    float originalSpeed = ISOMath_Vector3fLength(ISOMath_Vector3fOpSub(b,a))/tDelta; //again, a or b?    float timeToIntersectCorrect = timeToIntersect/originalSpeed;        *tcoll = timeToIntersectCorrect;    *ncoll = n;        return(TRUE);}//Collisionstatic inline void AMParticleSystem_FindCollisions(AMParticleSystem *system, Trianglef *worldTriangles, int numTriangles){    int i;        float range = 0.098;    for(i=0;i<system->numParticles;i++)    {	Vector3f v = ISOMath_Vector3fOpSub(system->particles[i].position,system->particles[i].oldPosition);	Vector3f a = system->particles[i].oldPosition;	a = ISOMath_Vector3fOpAdd(a,ISOMath_Vector3fInverted(ISOMath_Vector3fWithLength(v,range)));	Vector3f b = system->particles[i].position;	Rayf segment = ISOMath_MakeRayf(a,b);		AMParticleSystem_Rayf_CollideAndSlide(system, &segment, worldTriangles, numTriangles, 0, 0.5);		system->particles[i].position = segment.finish;    }}static inline BOOL AMParticleSystem_Rayf_CollideAndSlide(AMParticleSystem *system, Rayf *ray, Trianglef *worldTriangles, int numTriangles, float friction, float elasticity){    int maxIterations = 5;    BOOL collisionOccurred = FALSE; // added this for debug purposes        int i;        for(i=0;i<maxIterations;i++)    {	Vector3f Pcoll, Ncoll;	float tcoll = 1.0;		if(AMParticleSystem_Rayf_Intersect(system, ray, worldTriangles, numTriangles, &tcoll, &Ncoll, &Pcoll)==FALSE)	    return;		AMParticleSystem_Rayf_Slide(ray, &Pcoll, &Ncoll, tcoll, friction, elasticity);	collisionOccurred = TRUE;    }        return(collisionOccurred);}static inline void AMParticleSystem_Rayf_Slide(Rayf *ray, Vector3f *pcoll, Vector3f *ncoll, float tcoll, float friction, float elasticity) //friction = 0.01, elast = 0.5{    Vector3f pcollNR = ISOMath_MakeVector3f(pcoll->x,pcoll->y,pcoll->z), ncollNR = ISOMath_MakeVector3f(ncoll->x,ncoll->y,ncoll->z);        Vector3f d1;    Vector3f dn1;    Vector3f dt1;    Vector3f e0 = ray->start;    Vector3f e1 = ray->finish;        d1 = ISOMath_Vector3fOpSub(e1,pcollNR);    e0 = pcollNR;     ray->start = e0;    Vector3f d2 = ncollNR;        dn1 = ISOMath_Vector3fScalarOpMult(ncollNR, ISOMath_Vector3fDotProduct(d1,ncollNR));    dt1 = ISOMath_Vector3fOpSub(d1,dn1);        d1.x = dn1.x*(-elasticity)+dt1.x*(1.0-friction);    d1.y = dn1.y*(-elasticity)+dt1.y*(1.0-friction);    d1.z = dn1.z*(-elasticity)+dt1.z*(1.0-friction);        e1 = ISOMath_Vector3fOpAdd(e0,d1);    ray->finish = e1;}static inline BOOL AMParticleSystem_Rayf_Intersect(AMParticleSystem *system, Rayf *ray, Trianglef *worldTriangles, int numTriangles, float *tcoll, Vector3f *Ncoll, Vector3f *Pcoll){    BOOL collided = FALSE;        int i;    for(i=0;i<numTriangles;i++)    {	float ttri;	Vector3f Ptri;	Vector3f Ntri;	//possible problem here?		if(!ISOMath_TrianglefContainsLinef(system->fTimeStep, worldTriangles[i], ray->start, ray->finish, &ttri, &Ntri, &Ptri))	    continue;		float tcolltemp = *(tcoll);        // test another "range" here?	if(ttri<tcolltemp)	{	    *tcoll = ttri;	    *Pcoll = Ptri;	    *Ncoll = Ntri;		    collided = TRUE;	}    }        return(collided);}

P.P.S.
>>Doesn't this mean that on the next frame the implicit velocity has the direction e1-oldpos instead of e1-e0? Does that work, or does it at least appear to provide an acceptable appearance of bounciness?

I just tried this. I may be doing something wrong, but everything appears to just move in slow-motion.

[edited by - mattbbangin on February 26, 2004 6:31:36 AM]

##### Share on other sites
My thoughts:

- Maybe my original implementation of oliii''s coldet example didn''t work because of floating point error. Maybe if I change everything to double, this wouldn''t happen?

- Implementing a minimum-distance linear constraint into the coldet might work. But I''d rather figure out why I can''t get what everybody else is doing to work.

- My current implementation isn''t correct.

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 28
• 16
• 10
• 10
• 11
• ### Forum Statistics

• Total Topics
634113
• Total Posts
3015570
×