Collision detection: coping with precision errors

Quote:

Original post by jmakitalo I finally got my collision detection to work properly. It is based on the wonderful paper General Collision Detection for Games Using Ellipsoids by Paul Nettle.

I'll go ahead and mention that the original version of this paper has been superseded by a paper by Kasper Fauerby called 'Improved Collision Detection and Response using Ellipsoids', and perhaps also by later versions of Paul Nettle's source code.

The original paper had some algorithmic errors, I believe, that caused erroneous behavior under certain circumstances. I never bothered to review the paper myself, so I can't tell you what exactly these errors were or whether the problems you're having could be a result of them. I know others here are more familiar with the paper than I am though, and they may be able to give you some more info in that area.

Anyway, this type of collision detection and response can be tricky to debug and to implement correctly. Based on your description I can only guess at what the problem is, but I would suggest adding plenty of debug diagnostics and ouput, both text-based and graphical, to help give you an idea of what is actually occurring.

One thing I found useful when implementing this algorithm was to have available a discrete (static) test as well. This was useful for debugging, as it could be used to report whether the ellipsoid was intersecting any polygons at the end of the update, and also served as an extra step to resolve any interpenetrations resulting from precision errors.

Again though, I'd recommend getting ahold of Kasper's paper and reviewing the algorithm described therein, as it's at least a possibility that the problems you're running into are a result of problems with the original paper.

Actually I havent implemented the algorithm by strictly following the pseudo code, I marely studied the ideas and made an implementation of my own. However, I'm quite sure the collision detection is correct, at least in a simple case such as a simple inclide, and I get proper point of collision and collision plane.

Neither of those papers handle the collision responce in such a great detail that precision errors are taken into account. There's just something wrong in my responce code. It should work in a simple incline with no complex geometry but a simple box, in a way that the ellipsoid should move down the incline due to gravity. Insted I get a jerky movement which ends in fallthrough.

I think the basic algorithm is flawed anyway. Finding the closest point and tracing back is not correct. That only works for intereference detection.

As for precision errors,

- Stop search when velocity reaches a threshold magnitude (you do that already).
- Stop search when the timestep reaches a threshold (call it t_threshold).
- Instead of moving EXACTLY to the time of collision, move to (tcoll - t_threshold / 2). Assert if it's >= t_threshold / 2, in case.
- use doubles. That's more for reducing the jitter, because the bugs will still be there, but won't happen as often.
- When you reflect the velocity, add a tiny amount that goes along the normal of collision. That will possibly cause more jitter, but it's tweakable, and you can try and remove it later and see if it still works.
- add a static test (this time, the closest point algo will be useful). If you do not want a static test, use it as a debug feature, to make sure it never triggers.

I got the thing fixed pretty well, it seems that adding a static test at the end of the primary collision detection routine is actually necessary. Without it, for example in a terrain scene where the polygons are very small compared to the ellipsoid, there is a high probability that the edge collision is detected and a vertical'ish plane is selected when a triangle area collision would be correct. But the static test at the end can effectively cancel out any/most errnous moves cause by this.

as I said, I think the basic algorithm is flawed. If the test was properly done, you could potentially not need the static test. But whatever works. True, large descrepancies in size will generate larger FP innacuracies, or the objects are both very large or very small.

I've also tried implementing this algorithm. It seems to work great with the sphere, but when I try making it ellipsoidal I run into problems with sliding. When running over small objects, or a ramp, the tangent plane to the contact point on the ellipsoid is not generally aligned with the normal of the plane of the colliding object (as is the case with the sphere). This basically launches my ellipsoid into mid air whenever it tries to go over anything. Am I missing something?