2
\$\begingroup\$

I know that it's possible to see if a line segment or a swept shape (to make a "fat" line segment) intersects objects using MPR and GJK. Is it possible in those situations to find out the distance down the ray cast that the collision occurred? Thanks!!

\$\endgroup\$
4
\$\begingroup\$

I don't believe there's an elegant solution to that problem. It's something I put a lot of time into investigating a few years ago writing my own collision detection.

The solution I ended up using was iterative:

  1. Simple (no sweeping) GJK to find the minimum distance between object A (the fat ray cast) and object B (the potential collider -- this is after culling candidates through simpler means, of course). Let's call that distance vector D;
  2. Calculate the maximum safe distance we can move A along sweep vector V without intersection given D -- that was something like D.SquareMagnitude/Dot(D, V.Normalised), I think. That is, if we're moving directly towards the target the result is just |D|, but if we're moving tangentially to the D, we get... well... divide by zero. But that's just because we'll never hit it, so you can catch that or a negative denominator before it happens and say, "No collision!"
  3. If we haven't covered the whole distance we want to sweep, then a collision is still possible. Move A the distance we just calculated in step 2 along V. Repeat from step 1 over remaining length along V until we know there's no collision, or we have come within a very small range of the target (let's call that the skin thickness). In the latter case, it's the distance covered to get there that your fat ray cast will return.

The lack of an elegant, exact way to calculate what you're looking for is at least part of the reason most physics engines have a skin width or skin thickness parameter, defining how close you want to get to something and call it a collision.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Do you know if there's a solution for a skinny ray cast? Great info thanks!! \$\endgroup\$ – Alan Wolfe Apr 18 '15 at 18:35
  • 1
    \$\begingroup\$ The above algorithm can be used for a skinny ray, with an infinitely small point P for object A (its support function would always return P). If object B has no curved faces, you'd sooner or later get the exact distance of the ray trace, and you'd get away with a very small skin thickness. I don't know of a better way to do a skinny ray cast, but I can imagine there would be some way to do it, especially if object B has no curved faces (not a sphere, capsule, cylinder, etc). \$\endgroup\$ – Jibb Smart Apr 19 '15 at 0:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.