The result of this could go two ways depending on how you implement your logic. If you started out saying, "Z>0 implies the point if to the left of the line," then all the floating point regions that are on the line (Z=0), will show up as little holes-regions where the collision fails. The quick solution here is to change the test to Z greater than or equal to 0. This eliminates the problem of holes but creates a new problem-the regions on the line (Z=0) are now shared by both triangles.

Problems can arise if the collision routine returns a list of all the triangles it detects a collision with. The logic might not be set up to deal with having contact with two different surfaces in the same logic frame, leading to problems such as sound effects being stuck on or events failing to trigger.

More commonly though, a line-environment collision test will return the closest collision point. Since both polygons will return the same point (which, as we see in the figures, is actually an overlapping region), then the polygon detected will be determined by the order in which the polygons are tested.

Historically, the polygons are tested in the same order. However, with the increasing prevalence of multi-core architectures, it's increasingly common for programmers to implement some kind of data-level parallelism, where the order in which the individual polygons are tested is not guaranteed and varies based on the way additional tasks use the cores and by the state of the memory cache, which varies from frame to frame.

The result can be that the same collision test performed on the same data might return either of two polygons in a seemingly random manner. Most likely, it will return one polygon 99.99 percent of the time, with the other polygon cropping up extremely rarely.

You might even find a Heisenbug, which can be incredibly difficult to track down, since a) it surfaces very rarely, b) the conditions can be impossible to replicate, and c) introducing test code can "fix" the problem.

There are a number of solutions. For one, you can change your multi-core data sharing algorithm so that polygons which might share an edge are always submitted in the same batch-but it would still leave you with the potential problem of two polygons being returned with the same collision point.

You could also try to guarantee that the regions on the line Z=0 always belong to one polygon of the other, which you could do by flagging the edges of a polygon so one side uses Z<0 and the other effectively uses Z greater than or equal to 0.

Pinning Down Drifters

Floats are a very useful way of representing numbers, but keep in mind that they do not perfectly represent the mathematical world that you use when creating algorithms. Floating point coordinates represent regions in space rather than points.

Those regions get a lot bigger as you move farther from the origin and eventually create noticeable artifacts such as jittering and visible seams. This is an important consideration if you are attempting to scale an existing engine to one that supports a much large world.

Floating point inaccuracies can lead to indeterminate boundary regions of variable size, and these need to be dealt with explicitly to avoid Heisenbugs.

References

Ericson, Christer. "Numerical Robustness" in Real-Time Collision Detection. San Francisco: Morgan Kaufmann, 2004.

Freese, Peter. "Solving Accuracy Problems in Large World Coordinates" in Game Programming Gems 4, Hingham, Mass.: Charles River Media, 2004.

[EDITOR'S NOTE: This article was independently published by Gamasutra's editors, since it was deemed of value to the community. Its publishing has been made possible by Intel, as a platform and vendor-agnostic part of Intel's Visual Computing microsite.]