Graphics Reference
In-Depth Information
// Try cross products of segment direction vector with coordinate axes
if (Abs(m.y * d.z - m.z * d.y) > e.y * adz + e.z * ady) return 0;
if (Abs(m.z * d.x - m.x * d.z) > e.x * adz + e.z * adx) return 0;
if (Abs(m.x * d.y - m.y * d.x) > e.x * ady + e.y * adx) return 0;
// No separating axis found; segment must be overlapping AABB
return 1;
}
As written, the expressions for
e
,
d
, and
m
all have a factor 0.5 that can be removed,
allowing the first five lines of initial setup code to be simplified to:
Vector e = b.max - b.min;
Vectord=p1-p0;
Pointm=p0+p1-b.min - b.max;
Remaining to address is the robustness of the code for when the segment direction
vector
d
is parallel to one of the coordinate axes, making the three cross products give
a zero vector result. If the segment does not intersect the AABB, the first three
if
tests
will correctly detect this. If the segment does intersect, the latter three
if
statements
correspond to 0
0 tests. To avoid rounding errors causing the axis to be incorrectly
interpreted as separating, a small epsilon term can be added to the
adx
,
ady
, and
adz
values to bias the comparison, similar to what was done for the OBB-OBB test in
Chapter 4.
>
5.3.4
Intersecting Line Against Triangle
The intersection of lines (as well as rays and segments) against triangles is a very
common test. For this reason, this test is discussed in detail in this and the two fol-
lowing sections. Starting with the test involving lines, let a triangle
ABC
and a line
through the points
P
and
Q
be given. The line
PQ
intersects
ABC
if the point
R
of inter-
section between the line and the plane of
ABC
lies inside the triangle (Figure 5.24).
One solution to the intersection problem is therefore to compute
R
and perform a
point-in-triangle test with it. Note that if
ABC
is arranged counterclockwise from
a given viewing direction
R
is inside
ABC
if
R
lies to the left of the triangle edges
AB
,
BC,
and
CA
(where the edges are considered as directed line segments). Simi-
larly, if
ABC
is arranged clockwise
R
is inside
ABC
if
R
is to the right of all triangle
edges.
Instead of explicitly computing
R
for use in the sidedness test, the test can be
performed directly with the line
PQ
against the triangle edges. Consider the scalar
triple products:
=[
]
u
PQ PC PB