Graphics Reference
In-Depth Information
Table 5.1
The six separating axes for testing intersection between a segment and an AABB.
d
s
>
r
b
+
r
s
v
i
d
s
r
b
r
s
d
x
e
0
+
d
x
|
m
x
|
>
(1,0,0)
m
x
e
0
d
y
m
y
>
e
1
+
d
y
(0,1,0)
m
y
e
1
d
z
+
d
z
(0,0,1)
m
z
e
2
|
m
z
|
>
e
2
m
z
d
y
)/
d
(
e
1
d
z
+
e
2
d
y
)/
d
m
y
d
z
−
m
z
d
y
>
e
1
d
z
+
e
2
d
y
d
×
(1,0,0)
(
m
y
d
z
−
0
m
x
d
z
)/
d
(
e
0
d
z
+
e
2
d
x
)/
d
m
z
d
x
−
m
x
d
z
>
e
0
d
z
+
e
2
d
x
d
×
(0,1,0)
(
m
z
d
x
−
0
m
y
d
x
)/
d
(
e
0
d
y
+
e
1
d
x
)/
d
m
x
d
y
−
m
y
d
x
>
e
0
d
y
+
e
1
d
x
d
×
(0,0,1)
(
m
x
d
y
−
0
There are six axes that must be tested as separating axes: three corresponding to
the AABB face normals (
v
0
(0, 0, 1)) and three
corresponding to cross products between the segment direction vector and the face
normals (
v
3
=
(1,0,0),
v
1
=
(0, 1, 0), and
v
2
=
=
d
×
(1,0,0),
v
4
=
d
×
(0, 1, 0), and
v
5
=
d
×
(0, 0, 1)). Table 5.1 gives
the results of working out the expressions for
d
s
,
r
b
,
r
s
, and
d
s
>
r
b
+
r
s
for these six
axes.
The expressions for separation given in Table 5.1 directly translate into an efficient
implementation.
// Test if segment specified by points p0 and p1 intersects AABB b
int TestSegmentAABB(Point p0, Point p1, AABB b)
{
Point c = (b.min + b.max) * 0.5f;
// Box center-point
Vector e = b.max - c;
// Box halflength extents
Point m = (p0 + p1) * 0.5f;
// Segment midpoint
Vectord=p1-m;
// Segment halflength vector
m=m-c;
// Translate box and segment to origin
// Try world coordinate axes as separating axes
float adx = Abs(d.x);
if (Abs(m.x) > e.x + adx) return 0;
float ady = Abs(d.y);
if (Abs(m.y) > e.y + ady) return 0;
float adz = Abs(d.z);
if (Abs(m.z) > e.z + adz) return 0;
// Add in an epsilon term to counteract arithmetic errors when segment is
// (near) parallel to a coordinate axis (see text for detail)
adx += EPSILON; ady += EPSILON; adz += EPSILON;