Graphics Reference
In-Depth Information
fact, the determinant predicates given in Chapter 3 are examples of this type of
predicate. Consider, for example, the ORIENT2D(
A
,
B
,
C
) predicate. Recall that it
returns whether the 2D point
C
is to the left, to the right, or on the directed line
AB
.
When the three points lie on a line, the smallest errors in position for any one point
can throw the result either way. If the predicate is evaluated using floating-point arith-
metic, the predicate result is therefore likely completely unreliable. Similar robustness
problems occur for all other determinant predicates presented in Chapter 3.
Many algorithms are formulated — explicitly or implicitly — in terms of predi-
cates. When these predicates fail, the algorithm as a whole may fail, returning the
wrong result (perhaps an impossible result) or may even get stuck in an infinite loop.
Addressing degeneracy problems involves fixing the algorithms to deal gracefully
with predicates that may return the incorrect result, adjusting the input so that trou-
blesome cases do not appear or relying on extended or arbitrary precision arithmetic
to evaluate the predicate expressions exactly.
To fully understand and ultimately address robustness problems in collision
detection algorithms it is important to have a good understanding of the inherent
peculiarities and restrictions of limited-precision computer arithmetic. The remain-
der of this chapter focuses particularly on the floating-point representation of real
numbers and some measures that allow for robust usage of floating-point arithmetic.
11.2
Representing Real Numbers
Although there is an infinite number of real numbers, on a computer representa-
tions of real numbers must be finite in size. Consequently, a given representation
will not be able to represent all real numbers exactly. Those real numbers not
directly representable in the computer representation are approximated by the near-
est representable number. The real numbers that are exactly expressible are called
machine representable numbers
(or just
machine numbers
).
When talking about computer representations of real numbers it is important to
distinguish between the
precision
and the
accuracy
with which a number is given.
Precision specifies how many digits (binary, decimal, or otherwise) there are in the
representation. Accuracy concerns correctness and is related to how many digits of
an approximation are correct. Thus, it is not unreasonable for an inaccurate value to
be given precisely. For example, at 10 significant decimal digits, 3.123456789 is quite
a precise but very inaccurate approximation (two correct digits) of
(3.14159
...
).
There are two common computer representations for real numbers:
fixed-point
numbers
and
floating-point numbers
. Fixed-point numbers allocate a set number of
digits for the integer and the fractional part of the real number. A 32-bit quantity, for
example, may hold 16 bits for both the integer and fractional parts (a so-called 16.16
fixed-point number) or hold 8 bits for the integer part and 24 bits for the fractional
part (an 8.24 fixed-point number). Given a real number
r
, the corresponding fixed-
point number with
n
bits of fraction is normally represented as the integer part of 2
n
r
.
π
