Graphics Reference
In-Depth Information
exact arithmetic. Because the line can no longer pass between the triangles in the
presence of floating-point errors, the test is now robust.
It is important that the shared calculation be performed exactly the same from one
triangle to the next. That is, the edge
AB
cannot also be treated as the edge
BA
in
the neighboring triangle. Otherwise, the tested scalar triple products would involve
[
PQ PB PA
]
and
[
PQ PA PB
]
, which although identical in reals are not identical under
floating-point arithmetic.
For indexed vertices, treating shared edges as the same directed segments is easily
done by ordering the edge vertices on their indices. Nonindexed vertices are ordered
by listing the vertex with the smaller
x
component (then
y
, then
z
component) before
the other vertex (lexicographical ordering).
Only after
L
has been determined to intersect one of the triangles is the intersection
point
P
with the plane of that triangle computed. It is important to note that this point
may lie outside the triangle. Any subsequent processing of the point must take this
into account, which is nontrivial in itself. A solution that circumvents both problems
is to forego line and segment tests completely and instead use fat objects for testing.
This approach is discussed next.
11.3.4
Robustness of Fat Objects
As indicated in the previous, tests involving the intersection of lines and segments are
extra sensitive to floating-point issues. Points have similar problems. One solution to
the robustness problems with points, lines, and segments is to avoid them altogether
and instead only rely on tests involving
fat
objects. For this discussion, an object is
considered fat if it has a radius of at least
r
over all directions. For points, lines, and
segments their fat counterparts are spheres, (infinite) cylinders, and capsules.
As shown in the previous section, subtle errors may cause a line to pass between
the shared edge of two triangles even though the triangles correctly share the end
vertices of this edge. However, by turning the line into a cylinder or capsule even an
outright gap between the two triangles can be accommodated as long as the capsule
radius
r
is greater than
e
/2, where
e
is the width of the largest gap in the geometry. In
practice,
r
is much greater than
e
, dwarfing all errors due to floating-point arithmetic,
making fat tests extremely robust. Figure 11.10 illustrates the difference between
these two types of tests. A drawback with fat tests is that they are generally much
more expensive than their “thin” counterparts, in that they effectively amount to a
distance calculation rather than just an intersection test.
11.4
Interval Arithmetic
One way of tracking the error bounds of floating-point calculations is to perform
the calculations using
interval arithmetic
(
interval analysis
) [Moore66]. In interval
