Sign in to follow this  
Steve_Segreto

Collision Response Question

Recommended Posts

I am still confused about Collision Detection/Response. I'm talking specifically about sphere with triangle soup collision det/res. I've read many of the back-posts on this topic and most seem to be pointing towards accumulating all triangles that the sphere collides with in a time interval and handling the "response" portion afterwards, by doing something like averaging all the plane normals of the collided triangles and projecting the sphere's velocity along that. I've implemented Kasper Fauerby's improved collision detection/response algorithm (the one with the swept sphere recursively testing against triangle plane, vertices and edges and all the quadratic equations). As near as I can tell that algorithm adjusts the velocity against only the nearest hit triangle's plane normal. So my question is: Is that the reason Kasper's algorithm has to recurse, because it only tracks closest hit, not all collided triangles? If I just record all triangle hits do I still have to do the recursion? Also is it fine just to average all the plane normals of the hit triangle list? Any advice or insight from someone who has actually made this stuff work would be appreciated. Kasper's algorithm is working, in the sense that I never fall through geometry or get stuck, but it jitters like crazy whenever there are multiple collisions.

Share this post


Link to post
Share on other sites
the recursion is part of the algorithm.

1) you want to check the path a sphere for a time (dt).

2) you find the first colliding triangle among the triangles at time (t).

3) you move the sphere to the time (t).

4) you calculate the response (reflect velocity) against that triangle.

5) the interval of time is now reduced : dt = (dt - t).

6) you find the next colliding triangle within that time step.

and so on until no collisions are found, or (dt) falls below a very low threshold, or if you want to avoid too many recursions (recursionDepth < 10 for example).

You would consider averaging the collisions when for example, you find multiple simultaneous collisions (when you have several triangles colliding at the same time step, or when you have an intersection).

For intersections, I would do something different than averaging.

you find the sphere intersecting with a number of triangles :

1) cache the current position of the sphere Pcache = sphere.Position;

2) you move the sphere (sphere.Position) about so that the sphere stops intersecting (or reduce intersections as best as possible) with those triangles.

3) Use the vector (P - Pcache).Direction() as your average plane of collision, to reflect the sphere velocity.

4) repeat collision detection, up to a maximum number of iterations.

Share this post


Link to post
Share on other sites
Ok that makes a little more sense, so what people have proposed is basically to account for multiple triangle hits or interpenetration with multiple triangles in the same time step rather than just "closest" hit. But the recursion (my recursionDepth is < 5) is necessary no matter what.

Another question:

Does this whole scheme prevent me from using some type of smoothing interpolation like a Verlet integration for example on the player's movement? I tried a quick-n-dirty Verlet on player's positions *AFTER* the adjusted velocity came back from the collision det/res algo and it made him interpenetrate geometry (albeit smoothly).

If I use this whole swept sphere idea where does smoothing fit in (if at all?) I also briefly tried keeping two world matrices for the player, an actual one for collision det/res and a "fake" one for display purposes only and smoothing that one each frame with the last one, but the results looked very odd and disorienting.

Share this post


Link to post
Share on other sites
with velocity Verlet, the velocity is implicit. Basically, I would work on 'displacement' vector instead of velocity itself.

That is, use the vector (newpos - pos) as your 'velocity', and a dt = 1.0f.

Then you can reflect / slide your sphere along the surfaces, giving you your newpos after collision. That should give you a smooth result.

BTW, by just sliding on surfaces (coeffients of restitution = 0.0f), the algorithm should be relatively simple. Here's a crude example.


struct CollisionInfo
{
float m_tcoll; // time of collision (0.0f when we found intersections).
Vector m_ncoll; // normal of collision.
Vector m_dcoll; // push vector to move away from intersections (Vector(0, 0, 0) for collisions, where tcoll > 0.0f).
};

struct Body
{
Vector m_accel; // acceleration.
Vector m_oldpos; // previous position.
Vector m_pos; // new position after integration and collision.

void integrate(float dt)
{
// velocity verlet integration.
Vector temp = m_pos;
m_pos += (m_pos - m_oldpos) + m_accel * (dt*dt);
m_oldpos = temp;
}

// find first collision or intersections. Work out the collision info parameters.
bool findFirstContacts(const StaticObjects* objects, int objectCount, const float tmax, CollisionInfo& collInfo)
{
// blah blah blah....
}

void collide(const StaticObjects* objects, int objectCount)
{
float dt = 1.0f; // scan along vector (m_pos - m_oldpos) and no further.
int iterations = 5; // maximum of 5 iterations for collision attempts.

while(dt > 0.000000001f && ((iterations--) > 0))
{
// find a collision (or intersections).
CollisionInfo collInfo;
if(!findFirstContacts(objects, objectCount, dt, collInfo))
break;

// move sphere to time of collision.
Vector pcoll = m_oldpos + info.m_tcoll * (m_pos - m_oldpos);

// move sphere away from intersections if we found any.
pcoll += info.m_dcoll;

// delta vector from position to the point of collision.
Vector delta = (m_pos - pcoll);

// arbitrary of restitution (0.0f for a perfect slide, 1.0f for a perfect bounce).
const float g_cor = 0.3f;

// reflect m_pos on the plane composed of (pcoll, info.m_ncoll).
m_pos = pcoll + ((1.0f + g_cor) * delta.DotProduct(info.m_ncoll)) * info.m_ncoll;

// reduce interval for next collision
dt -= info.m_tcoll;
}
}
};

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this