Graphics Reference
In-Depth Information
Removing the assumption of
|
x
|≤|
y
|
turns the expression into its final form:
if (Abs(x - y) <= epsilon * Max(Abs(x), Abs(y))) ... // Relative tolerance comparison
Note that it is important for the comparison for the relative test to be less-equal
and not less-than. Otherwise, the test fails when both numbers are exactly zero.
The relative test is also not without problems. Note that the test expression behaves
as desired when Abs(x) and Abs(y) are greater than 1, but when they are less than 1
the effective epsilon is made smaller, and the smaller the numbers get the more digits
of them are required to agree. A solution to the problems of both tests is therefore to
combine the two tests, using the relative test when the magnitudes of the numbers
are greater than 1 and the absolute test when they are smaller than 1:
if (Abs(x - y) <= epsilon * Max(Abs(x), Abs(y), 1.0f)) ... // Combined comparison
This expression can be expensive to compute if Max() is not available as a machine
instruction. An approximate expression that is cheaper to compute is
if (Abs(x - y) <= epsilon * (Abs(x) + Abs(y) + 1.0f)) ...
// Combined comparison
Because the relative tests are more complex than the absolute tolerance test, an
absolute tolerance test is typically preferred whenever applicable.
The value of epsilon is often taken to be some small multiple of the machine
epsilon. By setting epsilon to the square root of the machine epsilon, the numbers
are required to agree to roughly half the number of positions available in the given
machine representation.
Although the use of tolerances is often frowned upon in theoretical computa-
tional geometry papers, in which it is somewhat derogatorily referred to as “epsilon
tweaking” and a “programming trick,” it largely remains the only feasible practical
approach to robustness for floating-point arithmetic in real-time applications. For
collision detection applications, using tolerances works well in practice. With large
enough tolerance values, error buildup can be ignored. However, using tolerances
does assume an active understanding of the problems involved and is far from an
automatic process. A good presentation of tolerances is given in [Knuth97].
It is worth noting that in using tolerances equality is no longer a transitive property.
Thus, with A equaling B and B equaling C , under a tolerance comparison this no longer
implies that A equals C . Without the transitive property, sorting (for example) breaks
down and may give different results based on the order in which elements are given.
When working with tolerances, it is therefore possible for inconsistencies to arise.
Robust code must consider and deal with such inconsistencies.
 
Search WWH ::




Custom Search