Numerical Robustness - Real-Time Collision Detection - page 447

L L

Π 1

C

Π 2

B B

P 2

P 1

D

A A

(a) (b)

Figure 11.9 Floating-point inaccuracies may have (a) the intersection point P 1 between L and
plane π 1 lie outside triangle ABC and (b) the intersection point P 2 between L and π 2 lie outside
triangle ADB . Thus, any test based on first computing the intersection point with the plane of
a triangle and then testing the point for containment in the triangle is inherently nonrobust.

unlikely to be the same point. It is therefore quite possible for P 2 to lie to the left of
AB and thus outside triangle ADB (Figure 11.9b). Consequently, the test may fail to
detect intersection against both triangles, even though real arithmetic guarantees an
intersection.
There are two main reasons for the test failing.

1. Information is discarded. Precision is lost as P 1 and P 2 are computed and expressed
in machine-representable numbers. The discarded information makes the triangle
containment test unreliable.

2. Information is not shared between successive, related tests. P 1 and P 2 should be the
same point P , but are not, as two subtly different calculations are used for comput-
ing the intersection point. Decisions that should be consistent between the tests
— such as whether P lies to the left or right of AB — therefore will not be.

One robust method of intersecting a line against a triangle is the test presented in
Section 5.3.4, based on computing scalar triple products to determine if L lies inside
all edges of the triangle. Assuming L passes through points P and Q , the sign of the
scalar triple product indicates on which side of edge AB the line L lies.

Floating-point errors can change the sign of the scalar triple product when it is
near zero. However, because the same expression is computed for both triangles
when testing L against AB , the sign test must indicate that L intersects either of
the triangles. In other words, the shared calculation guarantees that L intersects
one of the triangles even though it may not strictly be the same triangle given by

[ PQ PB PA ]