Graphics Reference
In-Depth Information
11.3.3
Robustness Through Sharing of Calculations
To illustrate how failure to share calculations across related computations can cause
robustness problems, consider a commonly suggested method of detecting intersec-
tion between a line (or segment)
L
and a triangle
T
. The test begins with computing
the intersection point
P
between
L
and the supporting plane of
T
. Once
P
is obtained,
it is tested for containment in
T
, for example by testing if
P
lies on the same side of all
triangle edges when considered counterclockwise. (For efficiency, the point contain-
ment step is often performed by projecting
T
and
P
to the principal plane where
T
has
the largest area. An inexpensive 2D point-triangle test then suffices for determining
containment. This step is ignored here, as it does not affect the robustness problem
discussed.)
Unfortunately, implemented using floating-point arithmetic this test is not robust.
To illustrate the problem, consider the intersection of a line
L
against two triangles
ABC
and
ADB
(Figure 11.8).
π
π
2
are the supporting planes of
ABC
and
ADB
,
respectively. Let
L
pass infinitesimally to the left of the middle of edge
AB
. Because
edge
AB
is shared between the triangles, in real arithmetic
L
would intersect triangle
ABC
and not triangle
ADB
. However, using the previous intersection test inaccuracies
caused by floating-point arithmetic may have that
neither
triangle is intersected by
L
. To see why, consider first the intersection of
L
with
1
and
π
1
, resulting in an intersection
point
P
1
. However, floating-point errors may cause
P
1
to lie slightly to the right of
the edge
AB
and therefore outside triangle
ABC
. This case is shown (exaggerated)
in Figure 11.9a. Next
L
is intersected against plane
π
2
, intersecting in some point
P
2
. Because
π
2
are different planes, represented by different plane equations
whose components are subject to floating-point inaccuracies,
P
1
and
P
2
are highly
π
1
and
Π
1
L
C
Π
2
B
P
D
A
Figure 11.8
The line
L
is intersected against triangles
ABC
and
ADB
. Because
L
is passing
through the edge
AB
common to both triangles, the intersection test is susceptible to inaccu-
racies due to floating-point errors. A poorly implemented test may fail to detect intersection
with both triangles.
