These recent days, I've been working on a collision detection + response system for my own game engine. I'm using the GJK algorithm, and while it wasn't too difficult to understand and implement, I've noticed that there are some glaring precision issues when the colliders are too different in size, leading to the algorithm incorrectly continuing to run when it should have exited. While I understand that this can be overcome in practice by switching to double-precision (or by simply forcing an exit whenever a degenerate simplex is detected, though this seems not-so-robust), I'm curious as to what other strategies there are to make the GJK algorithm viable in practice (perhaps without switching to double-precision?).

Floating point is by definition an estimate of the true value.

A real in math has infinitely many possible values. If you want to store that in a computer you would need an infinite amount of memory just for one real value, and that doesn't exist.

Switching to more precision reduces the problem (you can store more digits, leading to better approximations), but the root cause that you cannot represent 99.99% of the possible math real values remains.

The way to fix this is by allowing your computed results to be approximations rather than true answers. For example, consider comparisons v1 == v2 as ‘false’ by definition (although obviously it does hold for a small set of values in the real domain).

Thank you for your input, Alberth. I've been using epsilon values to allow for errors up to certain decimals. Interestingly enough, I tried my hand at switching to double precision, but the rounding errors persisted, making me believe that the error in my implementation must be elsewhere. 😄

Floating point math is an art. There is a whole body of literature on handling precision in such code.

Eg the order of summing a number of floating points is already influencing the result

There are a couple of approaches how this is addressed in practice:

1. You usually use only convex polytopes. Spheres and capsules are handled as points and segments with the radius being handled explicitly on the outside (eg target distance)
2. Use special care when computing the search direction. Eg utilize the simplex geometry instead of the difference of the current witness points
3. Look for singular determinants in the simplex solver and back up to the last simplex if you detect division by very small values
4. And even with this you can sometimes not make a conclusion if the returned distance is very small. Eg the origin could just be very close to an edge or triangle simplex. In this case you need another algorithm to confirm the result.
   
   Erin Catto gave a good presentation about this topic which also explains some of my points more exhaustively. In a nutshell GJK can be made robust in 32bit for the above shape types, but it takes some effort and solid understanding of the algorithm and how to handle its results.