Graphics Reference
In-Depth Information
well studied in the field of computational geometry and a few reasonably efficient
implementations have been presented, including those of [Priest91], [Fortune93],
and [Shewchuk96a].
However, some applications rely on more than exact predicates. In particular,
collision detection applications typically require that intersection points be computed,
perhaps as a result of the intersection of a line segment and a plane. Representing
such an intersection point generally requires higher precision than that needed for the
endpoints of the segment or the plane equation coefficients. Further computations
with the intersection point will require still higher precision in subsequent intersection
calculations, and so on. To avoid requiring unbounded precision and to make the
computation feasible for a real-time application, it is clear that the intersection point
must be truncated or rounded in some fashion. Once this rounding takes place,
however, the computation is no longer exact!
The first of the following two sections discusses some of the issues involved in
performing exact computations using integers. The next section presents the scenario
in which a segment is intersected against a plane, and discusses how to deal with the
problem of truncating the intersection point to integer coordinates.
11.5.1
Exact Arithmetic Using Integers
As long as overflow does not take place, integer calculations using addition, subtrac-
tion, and multiplication are exact (division must be handled separately, as discussed
later). These three integer operations are also associative, unlike their floating-point
counterparts. Therefore, no special considerations are necessary to ensure, for exam-
ple, that shared edges are always treated as the same directed line segment in
intersection tests.
To avoid overflow, sufficient precision must be present in the integer type to which
the result of an operation is assigned. For addition and subtraction of two
n
-bit
numbers, representing the result requires
n
1 bits of precision, in general. The
multiplication of two
n
-bit numbers produces a result of 2
n
bits. For example, consider
exactly computing the dot product between two 3D vectors on a target CPU for which
the widest integer arithmetic supported is 64-bits. For the dot product result to stay
within 64 bits, the three products inside the dot product cannot exceed 62 bits, or
adding them up could cause an overflow. For the products not to exceed 62 bits, the
product terms cannot exceed 31 bits. Therefore, a 64-bit dot product will at most
support 31-bit vector components as input. If two dot products are added as part of
an expression, an additional bit disappears and the vector components can now at
most be 30 bits wide, without risking overflow. Similar reasoning applies to other
expressions.
Unless explicitly tested for, overflow will go undetected. A straightforward way
of detecting overflow is to cast the operands to a larger integer type, perform the
operation, and compare the result with the result in the lower precision. If they are
+
