realtimecollisiondetection.net

For several years now I've participated in the physics tutorial session at GDC (along with Jim Van Verth, Gino van den Bergen, Erin Catto, Brian 'Squirrel' Eiserloh, and Marq Singer). One section I've covered in some detail is robustness and within this area I've stressed (amongst other things) the importance of distinguishing between absolute and relative tolerances when performing comparisons of floating-point numbers.

I won't go into details about why you would want to care about how your floating-point numbers are compared. (Detailed information can be found in part in my slides from these GDC presentations and in more depth in my book.) Here I will assume you already know why you care, and I will just note that absolute and relative tolerances are tested as

// Absolute tolerance comparison of x and y
if (Abs(x – y) <= EPSILON) …

and

// Relative tolerance comparison of x and y
if (Abs(x – y) <= EPSILON * Max(Abs(x), Abs(y)) …

The absolute tolerance test fails when x and y become large, and the relative tolerance test fails when they become small. It is therefore desired to combine these two tests together in a single test. Over the years at GDC, as well as in my book, I've suggested the following combined tolerance test:

if (Abs(x – y) <= EPSILON * Max(1.0f, Abs(x), Abs(y)) …

This typically works fine, but Erin Catto pointed out to me that it may sometimes be hard to control the desired behavior with just a single EPSILON that controls both the absolute and the relative tolerance at the same time. When better control is desired we can instead look at the combining of tolerances in the following way.

What we are really looking for in terms of equality of x and y is the following combined test:

Abs(x - y) <= absTol, OR
Abs(x - y) <= relTol * Max(Abs(x), Abs(y))

These two expressions can be captured in a single formula as

Abs(x - y) <= Max(absTol, relTol * Max(Abs(x), Abs(y)))

or equivalently

Abs(x - y) <= absTol * Max(1.0f, relTol/absTol * Max(Abs(x), Abs(y)))

In my book and in my GDC presentations I have simplified this expression by assuming relTol = absTol, which gives my original formula:

Abs(x - y) <= absTol * Max(1.0f, Abs(x), Abs(y))

In the cases where the assumption relTol = absTol is not desirable it makes sense to stay with the formula

Abs(x - y) <= Max(absTol, relTol * Max(Abs(x), Abs(y)))

because here one can tweak absTol and relTol independently of each other.

I've avoided going into this much detail in my GDC presentations because they tend to be cramped for time and the important message to take home is really "absolute tolerance often bad, relative tolerance mostly good." As such, I felt it was important to document this additional information about floating-point comparisons somewhere, thus this short article!