Graphics Reference
In-Depth Information
data operated on. Unfortunately, in reality these assumptions are wrong. First,
computations — performed predominantly using floating-point arithmetic — are
not exact, but suffer from, for example, rounding errors. Second, degenerate situa-
tions occur all the time, in many cases deliberately by design (for example, collinear
points caused by aligning architectural designs to a grid).
The presence of problems from either category can give rise to, for example,
conflicting results from different computations, outright incorrect answers, and
even algorithms crashing or getting stuck in infinite loops. Numerical imprecision
originates from several identifiable sources.
1.
Conversion and representation errors.
Many errors stem from decimal numbers, in
general, not being exactly representable as binary numbers, which is the typical
radix used in fixed-point or floating-point arithmetic. Irrational numbers, such as
√
2, are not representable in any (integral) number base, further compounding
the problem.
2.
Overflow and underflow errors.
Numbers that become too large to be expressed in
the given representation give rise to overflow errors (or underflow errors when
the numbers are too small). These errors typically occur in multiplying two large
(or small) numbers or dividing a large number by a small one (or vice versa).
3.
Round-off errors.
Consider the multiplication operation: in multiplying two real
numbers the product
c
ab
requires higher precision to represent than either
a
or
b
themselves. When the exact representation of
c
requires more than the
n
bits the
representation allows,
c
must be rounded or truncated to
n
bits and consequently
will be inexact in the last representable digit. Most operations cause round-off
errors, not just multiplication.
4.
Digit-cancellation errors.
Cancellation errors occur when nearly equal values are
subtracted or when a small value is added or subtracted from a large one.
=
5.
Input errors.
Errors may also stem from input data. These errors may be modeling
errors, measurement errors, or errors due to previous inexact calculations.
Issues that would never arise in working with exact arithmetic must in finite-
precision arithmetic be identified and dealt with properly. For example, the computed
intersection point of a line with a triangle may actually lie slightly outside the triangle.
Similarly, the midpoint of a line segment is unlikely to lie on the supporting line of
the segment.
Degeneracies refer to special cases that in some way require special treatment.
Degeneracies typically manifest themselves through predicate failures. A
predicate
is an elementary geometric query returning one of a small number of enumer-
ated values. Failures occur when a predicate result is incorrectly computed or when
it is not correctly handled by the calling code. In geometrical algorithms, predi-
cates commonly return a result based on the sign of a polynomial expression. In
