Graphics Reference
In-Depth Information
Projecting
T
onto a given axis
n
results in the projection interval
min(
p
0
,
p
1
,
p
2
), max(
p
0
,
p
1
,
p
2
)
, where
p
0
,
p
1
, and
p
2
are the distances from the origin to the
projections of the triangle vertices onto
n
.For
n
=
a
00
this gives:
p
0
=
V
0
·
a
00
=
V
0
·
(0,
−
f
0
z
,
f
0
y
)
=−
v
0
y
f
0
z
+
v
0
z
f
0
y
=−
v
0
y
(
v
1
z
−
v
0
z
)
+
v
0
z
(
v
1
y
−
v
0
y
)
=−
v
0
y
v
1
z
+
v
0
z
v
1
y
p
1
=
V
1
·
a
00
=
V
1
·
(0,
−
f
0
z
,
f
0
y
)
=−
v
1
y
f
0
z
+
v
1
z
f
0
y
=−
v
1
y
(
v
1
z
−
v
0
z
)
+
v
1
z
(
v
1
y
−
v
0
y
)
=
v
1
y
v
0
z
−
v
1
z
v
0
y
=
p
0
p
2
=
V
2
·
a
00
=
V
2
·
(0,
−
f
0
z
,
f
0
y
)
=−
v
2
y
f
0
z
+
v
2
z
f
0
y
=−
v
2
y
(
v
1
z
−
v
0
z
)
+
v
2
z
(
v
1
y
−
v
0
y
)
r
,
r
] and
min(
p
0
,
p
1
,
p
2
), max(
p
0
,
p
1
,
p
2
)
are disjoint
for the given axis, the axis is a separating axis and the triangle and the AABB do not
overlap.
For this axis,
n
If the projection intervals [
−
=
a
00
, it holds that
p
0
=
p
1
and the projection interval for the triangle
simplifies to
min(
p
0
,
p
2
), max(
p
0
,
p
2
)
. The triangle projection intervals simplify in the
same manner for all nine projection axes, as they all contain one zero component.
Here, the AABB and triangle projection intervals are therefore disjoint if max(
p
0
,
p
2
)
<
−
r
. If min() and max() operations are available as native floating-
point instructions on the target architecture, an equivalent expression that avoids one
(potentially expensive) comparison is max(
r
or min(
p
0
,
p
2
)
>
r
. The latter
formulation is especially useful in an SIMD implementation (see Chapter 13 for more
on SIMD implementations).
The following code fragment illustrates how this test can be implemented.
−
max(
p
0
,
p
2
), min(
p
0
,
p
2
))
>
int TestTriangleAABB(Point v0, Point v1, Point v2, AABB b)
{
float p0, p1, p2, r;
// Compute box center and extents (if not already given in that format)
Vector c = (b.min + b.max) * 0.5f;
float e0 = (b.max.x - b.min.x) * 0.5f;
float e1 = (b.max.y - b.min.y) * 0.5f;
float e2 = (b.max.z - b.min.z) * 0.5f;
// Translate triangle as conceptually moving AABB to origin
v0=v0-c;
v1=v1-c;
v2=v2-c;
// Compute edge vectors for triangle
