Jump to content
  • Advertisement
Sign in to follow this  

Collision Response Question

This topic is 3438 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 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))

// 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
Sign in to follow this  

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!