Archived

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

Ragdoll Physics and Collision Response

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

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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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]

Share this post


Link to post
Share on other sites
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 e1

Vector dn1; // d1, projected on the normal of collision

Vector dt1; // d1, projected on the triangle plane


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;


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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
Oh my. I am cursed.

I've made these changes:

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

//Intersection

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-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);
}

//Collision

static 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 this post


Link to post
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.

Share this post


Link to post
Share on other sites
A swept sphere is just a sphere moving along a line.

This sphere usually represents more detailed geometry (as to keep the collision tests fast and simple), hence the term "bounding sphere".

Ellipsoids can be used to provide a tighter fit around the contents of the bounding volume.

The basic swept-sphere coldet routine tests if a sphere has collided with the plane a triangle lays on; if so, then it tests if the intersection point lays on the triangle; if so, then a collision has most likely occurred; the sphere then "slides" along the collision plane. I like to think of it more as: keeping a little space between the object and it''s environment.

Share this post


Link to post
Share on other sites
matt, sorry for not replying, I forgot to mention that I was on holiday last week

you can check this, which is an implementation of what I''m talking about. it''s in 2D, but in 3D, it''s exactly the same. look at the animate() function, the SatisfyConstraints() functions, and the Collide() functions. the steps are important, you have to take them in order. And I haven''t seen any floating point issues so far.

Verlet Vehicles

the friciton stuff is far from perfect, due to the threshold you have to use. It makes the wheel bounce a little above the plane, thus the particles keep on slipping / sliding due to the slight bounce. However, to have no friciton at all, it works fine. It''s just that the friction is lower than it should be.

The bounce has to be there, to avoid the numerical innacuracies you talk about, but to improve the friciton model and keep that working, you''ll have to trick the velocity in the particle update itself.

Share this post


Link to post
Share on other sites
>>>matt, sorry for not replying, I forgot to mention that I was on holiday last week
It''s all gravy. I learned a lot trying to fix this on my own.

It turns out I was forgetting to test if the collision time is 0. After some slight tweaking, it works beautifully. Friction apparently works fine, with no bouncing and whatnot. I am in awe, really.

Oliii, you are my savior.

Share this post


Link to post
Share on other sites
Sorry to hijack a bit, but i was wondering if you can help.

I have a simple system working, but was wondering about elastic collisions. As it stands at the moment, my particle will hit the constraining cube and stop, as i test for the constraint (in this case the "ground", with the particle only havein a -ve y force on it) and set the relavent y positions to zero.

However, I am a little confused how an elastic collision with the constraint should be modelled, e.g. the particle has enought velocity and the constraint is made of rubber, therefore the particle will bounce. Is there an easy way to represent this uisng the Jakobsen method, and any pointers would be greatly appreciated.

Thanks for your time,

Matt

[edited by - msm on March 7, 2004 5:12:17 PM]

Share this post


Link to post
Share on other sites