Nothing super major to report, I am just curious about this point:

On 10/20/2018 at 11:45 AM, Dirk Gregorius said:

GJK computes the closest points between two *disjoint* convex shapes.

Given that you felt the need to bold this sentence and asterisk the word disjoint, am I to infer that the distance version of this algorithm is not reliable for determining intersections as well? I was messing around and noticing that indeed it appears in certain circumstances to report a distance ever so slightly greater than zero while intersecting. I assume this is likely due to floating point error, but it would make me feel more comfortable knowing that for sure. If it is the case that it isn't reliable for that, I can just use the bastardized version for checking that prior to a full-on distance check. I just want to be sure I'm not overlooking something.

In colliding cases my implementation snaps the vertices together and manually sets the distance to zero.

GJK is perfectly good at detecting intersection. It does get a little difficult in the “almost intersecting with a tiny distance”, but this kind of problem can be successfully mitigated.

Yes, your implementation certainly does that when it returns from the tetrahedral case. If, however, the origin were enclosed within a triangle they are not set to be explicitly equal, which could lead to error. Unless of course I'm missing something.

And these may or may not be leading to issues with the TOI solver; I noticed in yours you never check for the velocity bound being 0. In a test case I'm running, what appears to be the correct time is found in the first iteration, then the small amount of distance between my witness points happens to be perpendicular to my velocity vector, leading to the following delta value being infinity.

If I check for the velocity bound being 0 and exit out (or reduce my accuracy) your TOI solver works wonderfully (thanks so much for that resource), but I can't help but feel that this shouldn't be happening in the first place.

Thanks again for all your help so far; I'd really be lost in the weeds without you!

Oh my old 3D code doesn't do that snapping thing. I suggest looking at my 2D stuff I linked earlier -- it does the snapping thing there. My old code is nice to see as a general idea of what 3D can look like, but I haven't touched it for a long time. Actually not that long ago (like 5 months ago) someone pointed out a bug in my old 3D code! The bug was like 3 years old.

So to reiterate, I would put trust in Erin's resources, and then expand from there (which sounds like what you're doing, so that's great).

I still need to do more testing with my linear CA implementation, like checking for 0 velocity bound, make sure the end conditions are strong. My tolerance can also probably be reduced further. I might want to shrink or expand the collision shapes by a radius factor. I'm not sure yet.

Does it? Looking over the c2GJK method, I only see 'snapping' when the variable hit is non-zero (which only occurs if the simplex is a triangle) or if you're using radii and the distance is less than their sum (I'm having enough trouble with cubes and rectangles, thanks). So if the origin were to lie on a 2-simplex in your case, the precision may get a little screwy.

I'm testing the TOI solver in the 2D case, and it seems to be having that issue; a mysterious inaccuracy of something in the vicinity of 3.05176e-05 in a direction perpendicular to the velocity, specifically when evaluating witness points on a 2-simplex. Checking if the velocity bound is zero and breaking out works for this situation, but unfortunately would cause the algorithm to return a false positive in the case where the shape really is moving perpendicular to the other shape's witness point.

In a bit of messing around, I changed the grouping of multiplications when calculating witness points. It worked for the case I was testing, but made it break in other cases. That leads me back to the floating point precision theory and the depths of madness. You're clearly more experienced with this particular algorithm than I am; if you believe you can reduce your tolerance below 1.0e-5 (which I am using based on your example), there must be something I am missing to make this thing more numerically stable. Or perhaps I'm just not recognizing the 'snapping' code that you mentioned earlier.

You're right, I was just referring to the triangle case.

I suspect a common thing to do for TOI solvers is to apply a buffer radius around each shape for the GJK function to work with. This can give GJK some breathing room. In effect, this applies a tolerance buffer zone around shapes that counts as colliding as far as the TOI solver goes.

I personally haven't tried getting into this kind of tuning very in-depth yet, so maybe Dirk can have some more specific advice for you.

You say 'you suspect'; have you not had issues with this sort of thing in your implementations?

Well, the issue is not strictly with collisions; it appears that the witness points were slightly off to start, throwing the entire TOI solver off. Which is weird, because the case I'm testing right now is two 2D axis aligned squares, one moving horizontally into the other. There should be no y difference in the witness points at all, and yet one arrives out of thin air. It's minuscule, but enough to break everything. No sources I can find online mention anything about improving numeric stability in this algorithm, so I am currently at a bit of a loss. It is possible I'm just screwing up something very subtle, but I look at all publicly available implementations of GJK I can find, and I don't see any sort of fudging or tricks with regards to barycentric coordinates stuff.

I looked a bit further into Erin's code. After plugging in my values (and unfortunately finding the same inaccuracy), I looked in the main method and found a variable called 'shouldBeZero'. As you can probably guess by the fact I'm bringing it up, it isn't. It evaluates to 3.24570510e-06. I'm hoping beyond hope that this means there is an issue I can actually fix, rather than having the TOI solver just randomly fail on occasion.

It does seem weird that I'm having these issues with such small values. For reference, I am reproducing this issue by performing GJK on a point at (835.0f, 445.0f) and a line segment from (895.0f, 425.0f) to (895.0f, 475.0f). I realize the further you get from 0 the more inaccurate things get, but I thought it would take more. Especially since this algorithm seems commonly used.

This issue is turning into a bit of a show-stopper right now; if just the distance were slightly off I think I could somewhat manage. The direction being off just breaks everything, though. I suppose I could just put the tolerance to 1.0 or something, but that seems rather excessive. I'm just not entirely sure how I can progress at this time.