#### Archived

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

# Ragdoll Physics and Collision Response

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

## Recommended Posts

I've successfully implemented the verlet and constraint system described in http://www.ioi.dk/Homepages/thomasj/publications/gdc2001.htm. Now, I know a little bit about collision detection and even less about collision response. I was wondering if anyone has successfully implemented true collision detection (perhaps swept-sphere...somehow?) into this system? ... [edited by - mattbbangin on February 22, 2004 7:44:08 AM] [edited by - mattbbangin on February 22, 2004 7:44:59 AM]

##### Share on other sites
Oops I forgot...

I have something that appears to work halfway...

static inline void AMParticleSystem_SatisfyConstraints(AMParticleSystem *system, Trianglef *worldTriangles, int numTriangles){    int numIterations = system->numIterationsPerStep;    int i, j;    for(j=0;j<numIterations;j++)    {	// satisfy world->particle constraints	for(i=0;i<numTriangles;i++)	{	    for(j=0;j<system->numParticles;j++)	    {		Vector3f possibleIntersection;				Vector3f a,b,c;		a = system->particles[j].position;		b = system->particles[j].oldPosition;		c = ISOMath_Vector3fOpSub(c,b);		b = ISOMath_Vector3fOpMult(b,c);				BOOL spanIntersects = ISOMath_TrianglefContainsLinef(worldTriangles[i], a, b, &possibleIntersection);				if(spanIntersects)		{		    Vector3f motionVector = ISOMath_Vector3fOpSub(system->particles[j].position,system->particles[j].oldPosition);		    motionVector = ISOMath_Vector3fInverted(motionVector);		    		    Vector3f oldTemp = system->particles[j].oldPosition;		    system->particles[j].oldPosition = possibleIntersection;		    system->particles[j].position = oldTemp;		}	    }	}		// satisfy "stick" constraints	for(i=0;i<system->numConstraints;i++)	{	    AMParticleConstraint c = system->constraints[i];	    	    Vector3f x1 = system->particles[c.particleA].position;	    Vector3f x2 = system->particles[c.particleB].position;	    Vector3f delta = ISOMath_Vector3fOpSub(x2,x1);	    float deltalength = ISOMath_Vector3fLength(delta);	    if(deltalength<0.0000001)	    {		system->particles[c.particleA].position = ISOMath_Vector3fOpMult(system->particles[c.particleA].position,ISOMath_Vector3fNormalize(ISOMath_MakeVector3f(((random()%100)-50)/500.0,((random()%100)-50)/500.0,((random()%100)-50)/500.0)));		system->particles[c.particleB].position = ISOMath_Vector3fOpMult(system->particles[c.particleB].position,ISOMath_Vector3fNormalize(ISOMath_MakeVector3f(((random()%100)-50)/500.0,((random()%100)-50)/500.0,((random()%100)-50)/500.0)));				delta = ISOMath_Vector3fOpSub(x2,x1);		deltalength = ISOMath_Vector3fLength(delta);	    }	    	    float inverseMass1 = system->particles[c.particleA].mass;	    float inverseMass2 = system->particles[c.particleB].mass;	    float stiffRestLength = c.restLength;	    	    // apply mass and "stiffness" (for soft-body dynamics)	    delta = ISOMath_Vector3fScalarOpMult(delta,((deltalength-stiffRestLength)/(deltalength*(inverseMass1+inverseMass2))*c.stiffness));	    	    system->particles[c.particleA].position = ISOMath_Vector3fOpAdd(x1,ISOMath_Vector3fScalarOpMult(delta,inverseMass1));	    system->particles[c.particleB].position = ISOMath_Vector3fOpSub(x2,ISOMath_Vector3fScalarOpMult(delta,inverseMass2));	}		// satisfy box constraints	for(i=0;i<system->numParticles;i++)	{	    Vector3f x = system->particles[i].position;	    system->particles[i].position = ISOMath_Vector3fMin(ISOMath_Vector3fMax(x, system->container.min), system->container.max);	}		// keep static particles in place	for(i=0;i<system->numStatic;i++)	{	    system->particles[system->staticParticles[i].index].position = system->staticParticles[i].position;	}    }}

Now if I let my "body" fall freely upon the "world" (consisting of triangles), it collides fine. However, if I place my "body" under the "world", invert gravity, and let the "body" fall freely (into the sky!), when a collision occurs between a particle and a triangle, the particle gets sent flying in the same direction its moving...

[edited by - mattbbangin on February 21, 2004 2:50:36 AM]

[edited by - mattbbangin on February 21, 2004 2:52:22 AM]

##### Share on other sites
in your code, I don''t see anywhere any kind of response, you just put the particle on the surface of the triangle, which is good.

so, at first glance the problem must be in

BOOL spanIntersects = ISOMath_TrianglefContainsLinef(worldTriangles, a, b, &possibleIntersection);

it probably does not return an intersection if the segment is direction is aligned with the triangle normal, or if the segment start position is under the triangle.

##### Share on other sites
>>In your code, I don''t see anywhere any kind of response, you just put the particle on the surface of the triangle, which is good.

I know, I believe that''s the problem. I''ve tried various different things with moving the particle.position and particle.oldPosition (and also messing around with particle.force). Nothing seems to work.

>>it probably does not return an intersection if the segment is direction is aligned with the triangle normal, or if the segment start position is under the triangle.

Here is the function (courtesy of Paul Bourke):

static inline BOOL ISOMath_TrianglefContainsLinef(Trianglef t, Vector3f a, Vector3f b, 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(abs(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);        return(TRUE);}

##### Share on other sites
I think I found what I needed at: http://www.gamasutra.com/features/20000208/lander_02.htm

So, here's my take on implementing this:

		if(spanIntersects)		{		    Vector3f motionVector = ISOMath_Vector3fOpSub(system->particles[j].oldPosition,system->particles[j].position);		    		    Vector3f planeNormal = worldTriangles[i].normal;		    Vector3f planeCo = worldTriangles[i].vertex[0];		    		    float relative = ISOMath_Vector3fDotProduct(planeNormal, motionVector);		    		    if(relative<0)		    {			float kR = 0.5; //resititition 1.0 elastic, 0 stick			Vector3f vN = ISOMath_Vector3fScalarOpMult(planeNormal,relative);			Vector3f vT = ISOMath_Vector3fOpSub(motionVector,vN);			Vector3f vP = ISOMath_Vector3fOpSub(vT,ISOMath_Vector3fScalarOpMult(vN,kR));			system->particles[j].oldPosition = possibleIntersection;			system->particles[j].position = ISOMath_Vector3fOpAdd(possibleIntersection,vP);		    }		}

It appears to work fine for one side of my triangles. Particles get shot somewhat perpendicular to the triangle's normal when collided from the other side, but I guess that's fine..

[edited by - mattbbangin on February 21, 2004 7:56:14 AM]

##### Share on other sites
the thing with the jakobsen method, you don;t need any kind of response for particles. the constraints will provide the response to the whole system.

##### Share on other sites
Well, then what am I supposed to do when there is a collision?

##### Share on other sites
just put the particle at the surface of the triangle.

in your particle system you have a oldpos, and a newpos. the newpos is like where the particle will be if there are no collisions. it''s simply a matter of constraining the newpos of the particle against the triangles. Once you found a collision, move the particle to the surface of the triangle, plus a small threshold, just to make sure.

here are the steps I do

1) add gravity, and calculate newpos using the verlet integration

while (iteration < 5)

----2) satisfy the stick constraints, will will push the newpos of particles through the triangles
----3) calculate collisions of particles against triangles, using a segment / tri intersection test (segment will be, from oldpos to newpos of particle).
----4) if intersection occurs with a triangle, put newpos to the surface of the triangle, plus a small push up value along the normal.
----5) from there, the newpos of particles should not interfere with any triangles. as a debug check, you can check this.

wend

6) back to step 1

you can move steps 3), 4) and 5) outside the iteration loop.

##### Share on other sites
Awesome. It works near perfect now. I'm amazed how all of this was able to fall together so perfectly...

Anyway, thanks for your help. I really appreciate it.

P.S. Just one more quick question:
When a collision hit is detected, and I project particle.position onto the triangle (plus a little for good luck), should I be doing anything to particle.oldPosition? It seems like I would have to if I want to implement friction into the system (right now, collision is tight, but everything just keeps on sliding).

[edited by - mattbbangin on February 21, 2004 11:02:37 AM]

##### Share on other sites
Oops, wait. It appears that if I use particle.oldPosition->particle.position as the line-segment for the triangle intersection test, the particles just pass right through the triangle. However, if I use the line-segment particle.position->particle.position-Vector3f(0.0,5.0,0.0), it _appears_ to work fine. What's up with that!?

P.S. Never mind! I forgot to move the collision checking outside of the iteration loop. Works fine now, (previous question about friction still applies. :D )

[edited by - mattbbangin on February 21, 2004 11:29:26 AM]

1. 1
Rutin
70
2. 2
3. 3
4. 4
5. 5

• 21
• 10
• 33
• 20
• 9
• ### Forum Statistics

• Total Topics
633430
• Total Posts
3011826
• ### Who's Online (See full list)

There are no registered users currently online

×