Graphics Reference
In-Depth Information
The need for extended-precision arithmetic can be greatly reduced by postponing
the evaluation of expressions until absolutely needed, and then shifting the calcu-
lations to evaluate them centered on zero. As an example, consider the problem of
determining if a point
P
lies inside a triangle
T
by testing if
P
lies to the left (or right)
of all three triangle edges (see Section 5.3.4). The farther away from the origin
P
and
T
lie the larger the values used in the left-of tests and the greater the chance
of the tests overflowing. Because
P
only lies in
T
if
P
also lies in the AABB of
T
, the
tests can be postponed (or avoided completely) by first testing
P
against the AABB
(Figure 11.11a). This early AABB test cannot cause overflows to occur because AABB
tests do not involve any arithmetic operations, only compares.
If
P
and
T
pass the AABB test, both
P
and
T
are translated into a new coordinate
system centered on the AABB of
T
(Figure 11.11b). Assuming the triangle is small
with respect to the coordinate space, the coordinate components of
T
(and therefore
of
P
, in that it lies inside the AABB of
T
) are small enough that the left-of tests can be
performed without risk of overflow.
It should be noted that a single-precision floating-point number can represent
integers in the range
2
24
,2
24
accurately. Thus, floating-point arithmetic on integer
values is exact (for addition, subtraction, and multiplication) as long as the input
and output values lie within this range. Similarly, double-precision floating-point
numbers can represent integers in the range
[−
]
2
53
,2
53
accurately. Doubles therefore
allow the exact multiplication of 26-bit integers and can exactly compute a 3D dot
product involving 25-bit integers.
Whereas additions, subtractions, and multiplications are easy to deal with, divi-
sions remain a problem in working with integer arithmetic. Some approaches to
dealing with division are outlined in the next section. A more involved example is
presented in Section 11.5.3.
[−
]
P
P
T
T
(a)
(b)
Figure 11.11
(a) Reducing the amount of precision needed for a point-in-triangle test begins
with testing the point
P
against the AABB of triangle
T
. (b) If
P
passes the test,
P
and
T
are
tested for intersection in a new coordinate system centered on the AABB of
T
.
