Graphics Reference
In-Depth Information
an AABB. Let
f
(
x
,
y
,
z
)
0 be the implicit function defining the surface. Now evaluate
f
using interval arithmetic for the AABB intervals for
x
,
y
, and
z
. Let
=
[
r
1
,
r
2
]=
f
(
) denote the interval resulting from this evaluation. Because
all points outside
S
have
f
(
x
,
y
,
z
)
[
x
1
,
x
2
]
,
[
y
1
,
y
2
]
,
[
z
1
,
z
2
]
0, the conclusion is that the AABB and
S
cannot possibly be intersecting. If the bound has been tightly computed it is also
possible to conclude that the AABB is intersecting the boundary of
S
if
r
1
≤
>
0, if
r
1
>
0
≤
r
2
,
and lies fully inside
S
if
r
2
0. More concretely, consider the intersection of
B
,an
AABB defined by the minimum and maximum points (
a
x
,
a
y
,
a
z
) and (
b
x
,
b
y
,
b
z
) against
a sphere
S
given by the center point (
c
x
,
c
y
,
c
z
) and the radius
r
. The function
f
(
x
,
y
,
z
)
then becomes
<
)
2
)
2
)
2
2
.
f
(
x
,
y
,
z
)
=
(
x
−[
c
x
,
c
x
]
+
(
y
−[
c
y
,
c
y
]
+
(
z
−[
c
z
,
c
z
]
−[
r
,
r
]
Finally, compute
[
r
1
,
r
2
]=
f
(
[
a
x
,
b
x
]
,
[
a
y
,
b
y
]
,
[
a
z
,
b
z
]
). Because
[
a
x
,
b
x
]
,
[
a
y
,
b
y
]
, and
only occur once, the computed bound will be tight if the
n
2
terms are imple-
mented optimally (that is, not as
n
[
a
z
,
b
z
]
∗
n
). Thus,
B
lies outside
S
if
r
1
>
0 , intersects the
boundary of
S
if
r
1
0. For additional uses of
interval arithmetic in collision detection, see [Mitchell90], [Duff92], [Snyder93], and
[Redon02].
≤
0
≤
r
2
, and lies fully inside
S
if
r
2
<
11.5
Exact and Semi-exact Computation
Although floating-point numbers are convenient to work with, they are quite sus-
ceptible to rounding problems, as has been illustrated. To avoid these problems,
an alternative is to forego floating-point and instead work with
exact arithmetic
.
Arithmetic is exact if all bits of all values are retained throughout all calculations,
thus effectively avoiding robustness problems and facilitating exact decisions. How-
ever, for arbitrary computations to be exact the arithmetic must be performed with
arbitrary precision. At best, the solution is to use an arbitrary-precision arithmetic
library, but these are too slow for real-time use.
Fortunately, it turns out that arbitrary precision is not necessary. In many
cases, computations are performed only to ultimately partake in the evalua-
tion of Boolean expressions, or
predicates
. Examples of such predicates include
the ORIENT2D( ), ORIENT3D( ), INCIRCLE2D( ), and INSPHERE( ) determinant
expressions of Section 3.1.6. Because the expression of a predicate is of fixed com-
plexity, it is possible to set a limit on how many bits are required to evaluate the
entire expression exactly. Thus, the involved arithmetic only needs extended (but
nor arbitrary) precision, often no more than 64 or 128 bits of precision. For cer-
tain algorithms, use of exact predicates is all that is needed. For example, convex
hulls can be computed exactly using exact ORIENT2D( ) and ORIENT3D( ) pred-
icates. Evaluating predicates exactly using extended precision arithmetic has been
