Graphics Reference
In-Depth Information
11.5.2
Integer Division
When trying to perform exact computations, the presence of integer divisions poses
a serious problem. Consider yet again the problem of intersecting the line segment
S
(
t
)
=
A
+
t
(
B
−
A
), 0
≤
t
≤
1, against a plane
P
given by (
n
·
X
)
=
d
. Solving for
t
gives
A
)
(
n
t
nom
t
denom
.
t
=
(
d
−
n
·
·
(
B
−
A
))
=
With integer division rounding the result toward zero, naively determining if
S
intersects
P
by direct evaluation of the expression and then verifying if 0
≤
≤
1 leads
to failure. For instance, if
t
evaluates to, say, -0.4 or 1.2 in the reals, then the integer
evaluation gives 0 and 1, respectively, turning nonintersections into intersections.
To correctly (exactly) determine if
S
intersects
P
requires eliminating the division.
A division-free test can be obtained by multiplying all terms in the test expression
0
t
≤
t
≤
1 by the denominator
t
denom
, giving:
0
≤
t
nom
≤
t
denom
,
if
t
denom
>
0
0
≤−
t
nom
≤−
t
denom
, f
t
denom
<
0
0 the segment is parallel to the plane, which may be treated as nonin-
tersection, or as an intersection at
t
(If
t
denom
=
=
0 if and only if
t
nom
=
0. That is, this is the case
when the segment lies in the plane.)
All divisions that ultimately end up in a subexpression of a test can be eliminated
in a similar fashion. For example, using cross-multiplication the test
a
/
b
>
c
/
d
can
be turned into
ad
bc
(possibly with a less-than test, based on the signs of the
involved variables). The latter inequality is equivalent to
ad
>
−
bc
>
0, which in turn
is equivalent to computing the sign of the determinant:
ac
bd
.
An alternative to explicitly computing the sign of this determinant using extended
precision is to compute the sign using a
continued fractions expansion
, as suggested in
[Michelucci96]. Michelucci notes that for rational numbers 0
<
a
<
b
,0
<
c
<
d
,
because
order
d
order
d
c
,
b
a
,
order
a
d
b
,
c
c
,
b
d
mod
c
c
b
mod
a
a
=
=
+
+
a
