Graphics Reference
In-Depth Information
for (int k = p.numVerts,i=0,j=k-1;i
<
k;j=i,i++) {
float t;
Point q;
// Test if edge (p.v[j], p.v[i]) intersects s
if (IntersectRaySphere(p.v[j], p.v[i] - p.v[j], s, t, q) && t <= 1.0f)
return 1;
}
// Test if the orthogonal projection q of the sphere center onto m is inside p
Point q = ClosestPtPointPlane(s.c, m);
return PointInPolygon(q, p);
}
As an optimization, for steps 2 and onward it is possible to project the sphere and
polygon into the principal plane where the polygon has the largest area and treat the
problem as the 2D test of a circle against a polygon. This reduces the overall number
of arithmetic operations required for the test.
5.2.9
Testing AABB Against Triangle
The test of a triangle
T
intersecting a box
B
can be efficiently implemented using a
separating-axis approach ([Eberly01], [Akenine-Möller01]). There are 13 axes that
must be considered for projection:
1. Three face normals from the AABB
2. One face normal from the triangle
3. Nine axes given by the cross products of combination of edges from both
As before, as soon as a separating axis is found the test can immediately exit with
a“no intersection”result. If all axes are tested and no separating axis is found, the box
and the triangle must be intersecting. It has been suggested that the most efficient
order in which to perform these three sets of tests is 3-1-2 [Akenine-Möller01].
The same 13 axis tests apply to both OBBs and AABBs. However, for an AABB
(because the local axes of the box are known) some optimizations can be made to
speed up the runtime calculations required for the test. Here, only the AABB test is
presented, but to better illustrate the similarities — as well as to facilitate the AABB-
specific optimizations — the AABB is assumed to be given in a form commonly
used for OBBs. That is, by a center
C
; local axes
u
0
=
(1,0,0),
u
1
=
(0, 1, 0), and
=
u
2
(0, 0, 1); and extents
e
0
,
e
1
, and
e
2
. The triangle it is tested against is given by
points
V
0
=
=
=
(
v
0
x
,
v
0
y
,
v
0
z
),
V
1
(
v
1
x
,
v
1
y
,
v
1
z
), and
V
2
(
v
2
x
,
v
2
y
,
v
2
z
).
