Graphics Reference
In-Depth Information
In addition, squaring a number using the special operator
x
2
is tight, whereas using
x
x
is not. Of course, rewriting an expression to remove multiple occurrences of a
variable can introduce other problems, such as susceptibility to cancellation errors
(which is not further addressed here). Overall, it is best to avoid long computation
chains because they tend to exaggerate the dependency problem.
At some computational cost, tighter intervals can be obtained by splitting the
input intervals into subintervals, evaluating the function for all subintervals and then
taking the union of the partial results as the final function result. (The idea of splitting
into subintervals is also used in the
interval Newton method
, a powerful method for
robustly finding the roots of a function over a given interval [Hansen92].) As an
example of how splitting into subintervals may give tighter bounds, consider again
the evaluation of
x
(6
∗
−
x
), now for the two subintervals
x
=[
1, 2
]
and
x
=[
2, 3
]
. The
former interval gives
x
(6
−
x
)
=[
1, 2
]
(
[
6, 6
]−[
1, 2
]
)
=[
1, 2
][
4, 5
]=[
4, 10
]
,
and the latter gives
−
=[
]
[
]−[
]
=[
][
]=[
]
x
(6
x
)
2, 3
(
6, 6
2, 3
)
2, 3
3, 4
6, 12
.
The union of these two intervals is
[
4, 12
]
, tighter than the
[
3, 15
]
bound obtained
for
x
.
The computer implementation of interval arithmetic using floating-point arith-
metic is straightforward. Intervals are represented as pairs of values and operations
take pairs as arguments and produce pairs as a result. The only caveat is that it is
important to round the interval bounds of all results outward to maintain the correct
answer within the bounds, in that the interval endpoints may not be machine rep-
resentable. This additional rounding, coupled with the fact that two numbers rather
than one are stored and operated on, makes software-implemented interval arith-
metic operations up to a magnitude slower than corresponding native floating-point
operations. However, interval arithmetic is parallelizable, and therefore amenable to
SIMD optimizations.
The implementation of interval arithmetic operations in IEEE-754 floating-point
arithmetic is covered in [Walster98] and [Hickey01]. Robust rounding of interval
arithmetic operations is discussed in [Abrams98].
=[
1, 3
]
11.4.2
Interval Arithmetic in Collision Detection
Interval arithmetic has practical applications in collision detection. For example,
consider the problem of detecting intersection between an implicit surface
S
and
