i
i
i
i
i
i
i
i
16.13. BV/BV Intersection Tests 765
than the other techniques. This is because branches have been eliminated
and parallel computations used.
Another approach to SSE is to vectorize the object pairs. Ericson [315]
presents SIMD code to compare four spheres with four AABBs at the same
time.
For sphere/OBB intersection, first transform the sphere’s center into
the OBB’s space. That is, use the OBB’s normalized axes as the basis
for transforming the sphere’s center. Now this center point is expressed in
terms of the OBB’s axes, so the OBB can be treated as an AABB. The
sphere/AABB algorithm is then used to test for intersection.
16.13.3 AABB/AABB Intersection
An AABB is, as its name implies, a box whose faces are aligned with the
main axis directions. Therefore, two points are sufficient to describe such a
volume. Here we use the definition of the AABB presented in Section 16.2.
Due to their simplicity, AABBs are commonly employed both in colli-
sion detection algorithms and as bounding volumes for the nodes in a scene
graph. The test for intersection between two AABBs, A and B,istrivial
and is summarized below:
bool AABB intersect(A, B)
returns({OVERLAP, DISJOINT});
1: for each i ∈{x, y, z}
2: if(a
min
i
>b
max
i
or b
min
i
>a
max
i
)
3: return (DISJOINT);
4: return (OVERLAP);
Lines 1 and 2 loop over all three standard axis directions x, y,andz.
Ericson [315] provides SSE code for testing four separate pairs of AABBs
simultaneously.
Another approach to SSE is to vectorize the object pairs. Ericson [315]
presents SIMD code to compare four spheres with four AABBs at the same
time.
16.13.4 k-DOP/k-DOP Intersection
The bounding volume called a discrete orientation polytope or k-DOP was
named by Klosowski et al. [672]. A k-DOP is a convex polytope
13
whose
faces are determined by a small, fixed set of k normals, where the outward
half-space of the normals is not considered part of the BV. Kay and Kajiya
were the first to introduce this kind of BV, and they used them in the
13
A (convex) polytope is the convex hull of a finite set of points (see Section A.5.3).
i
i
i
i
i
i
i
i
766 16. Intersection Test Methods
context of ray tracing. Also, they called the volume between two oppositely
oriented normals on parallel planes a bounding slab and used these to keep
the intersection cost down (see Section 16.7.1). This technique is used for
the k-DOPs for the same reason. As a result the intersection test consists
of only k/2 interval overlap tests. Klosowski et al. [672] have shown that,
for moderate values of k, the overlap test for two k-DOPs is an order of a
magnitude faster than the test for two OBBs. In Figure 16.4 on page 730,
a simple two-dimensional k-DOP is depicted. Note that the AABB is a
special case of a 6-DOP where the normals are the positive and negative
main axis directions. Also note that as k increases, the BV increasingly
resembles the convex hull, which is the tightest-fitting convex BV.
The intersection test that follows is simple and extremely fast, inexact
but conservative. If two k-DOPs, A and B (superscripted with indices A
and B), are to be tested for intersection, then test all pairs of slabs (S
A
i
,S
B
i
)
for overlap; s
i
= S
A
i
∩S
B
i
is a one-dimensional interval overlap test, which is
solved with ease.
14
If at any time s
i
= ∅ (i.e., the empty set), then the BVs
are disjoint and the test is terminated. Otherwise, the slab overlap tests
continues. If and only if all s
i
= ∅,1≤ i ≤ k/2, then the BVs are considered
to be overlapping. According to the separating axis test (see Section 16.2),
one also needs to test an axis parallel to the cross product of one edge from
each k-DOP. However, these tests are often omitted because they cost more
than they give back in performance. Therefore, if the test below returns
that the k-DOPs overlap, then they might actually be disjoint. Here is the
pseudocode for the k-DOP/k-DOP overlap test:
kDOP intersect(d
A,min
1
,...,d
A,min
k/2
,
d
A,max
1
,...,d
A,max
k/2
,d
B,min
1
,...,d
B,min
k/2
,
d
B,max
1
,...,d
B,max
k/2
)
returns({OVERLAP, DISJOINT});
1: for each i ∈{1,...,k/2}
2: if(d
B,min
i
>d
A,max
i
or d
A,min
i
>d
B,max
i
)
3: return (DISJOINT);
4: return (OVERLAP);
Note that only k scalar values need to be stored with each instance of
the k-DOP (the normals, n
i
, are stored once for all k-DOPs since they
are static). If the k-DOPs are translated by t
A
and t
B
, respectively, the
test gets a tiny bit more complicated. Project t
A
onto the normals, n
i
,
e.g., p
A
i
= t
A
·n
i
(note that this is independent of any k-DOP in particular
14
This is indeed an example of dimension reduction as the rules of thumb recom-
mended. Here, a three-dimensional slab test is simplified into a one-dimensional interval
overlap test.
i
i
i
i
i
i
i
i
16.13. BV/BV Intersection Tests 767
and therefore needs to be computed only once for each t
A
or t
B
)andadd
p
A
i
to d
A,min
i
and d
A,max
i
in the if-statement. The same is done for t
B
.In
other words, a translation changes the distance of the k-DOP along each
normal’s direction.
16.13.5 OBB/OBB Intersection
In this section, a fast routine by Gottschalk et al. [433, 434] will be derived
for testing whether two OBBs, A and B, overlap. The algorithm uses
the separating axis test, and is about an order of magnitude faster than
previous methods, which use closest features or linear programming. The
definition of the OBB may be found in Section 16.2.
The test is done in the coordinate system formed by A’s center and
axes. This means that the origin is a
c
=(0, 0, 0) and that the main axes in
this coordinate system are a
u
=(1, 0, 0), a
v
=(0, 1, 0), and a
w
=(0, 0, 1).
Moreover, B is assumed to be located relative to A, with a translation t
and a rotation (matrix) R.
According to the separating axis test, it is sufficient to find one axis that
separates A and B to be sure that they are disjoint (do not overlap). Fifteen
axes have to be tested: three from the faces of A, three from the faces of
B,and3· 3 = 9 from combinations of edges from A and B. This is shown
in two dimensions in Figure 16.20. As a consequence of the orthonormality
of the matrix A =(a
u
a
v
a
w
), the potential separating axes that should
be orthogonal to the faces of A are simply the axes a
u
, a
v
,anda
w
.The
same holds for B. The remaining nine potential axes, formed by one edge
each from both A and B,arethenc
ij
= a
i
× b
j
, ∀i ∈{u, v, w} and
∀j ∈{u, v, w}.
m
n
Figure 16.20. To determine whether two OBBs A and B overlap, the separating axis
test can be used. Here, it is shown in two dimensions. The separating axes should be
orthogonal to the faces of A and B.Theaxesm and n are orthogonal to the faces of A,
and p and q are orthogonal to the faces of B. The OBBs are then projected onto the
axes. If both projections overlap on all axes, then the OBBs overlap; otherwise, they do
not. So it is sufficient to find one axis that separates the projections in order to know
that the OBBs do not overlap. In this example, the n axis is the only axis that separates
the projections.
i
i
i
i
i
i
i
i
768 16. Intersection Test Methods
s
s
Figure 16.21. The separating axis test illustrated. The two OBBs, A and B,aredisjoint,
since the projections of their “radii” on the axis determined by s are not overlapping.
(Illustration after Gottschalk et al. [433].)
Assume that a potential separating axis is denoted as s, and adopt the
notation from Figure 16.21. The “radii,” d
A
and d
B
, of the OBBs on the
axis, s, are obtained by simple projections, as expressed in Equation 16.42.
Remember that h
A
i
and h
B
i
are always positive, and so their absolute values
do not need to be computed:
d
A
=
i∈{u,v,w}
h
A
i
|a
i
·s|,
d
B
=
i∈{u,v,w}
h
B
i
|b
i
·s|.
(16.42)
If, and only if, s is a separating axis, then the intervals on the axis should
be disjoint. That is, the following should hold:
|t · s| >d
A
+ d
B
. (16.43)
Derivations and simplifications of Equation 16.43 for three cases follow—
one for an edge of A, one for an edge of B, and one for a combination of
edges from A and B.
First, let s = a
u
. This gives the expression below:
|t · s| = |t · a
u
| = |t
x
|. (16.44)
The last step comes from the fact that we are operating in the coordinate
system of A, and thus a
u
=(100)
T
. In Equation 16.45, the expressions
i
i
i
i
i
i
i
i
16.13. BV/BV Intersection Tests 769
for d
A
and d
B
are simplified:
d
A
=
i∈{u,v,w}
h
A
i
|a
i
·s| =
i∈{u,v,w}
h
A
i
|a
i
·a
u
| = h
A
u
,
d
B
=
i∈{u,v,w}
h
B
i
|b
i
· s| =
i∈{u,v,w}
h
B
i
|b
i
· a
u
|
= h
B
u
|b
u
x
| + h
B
v
|b
v
x
| + h
B
w
|b
w
x
| = h
B
u
|r
00
| + h
B
v
|r
01
| + h
B
w
|r
02
|.
(16.45)
The resulting equation for d
A
comes from the orthonormality of A,and
in the last step in the derivation of d
B
,notethat
R =
⎛
⎝
r
00
r
01
r
02
r
10
r
11
r
12
r
20
r
21
r
22
⎞
⎠
=(b
u
b
v
b
w
), (16.46)
since R is the relative rotation matrix. The disjointedness test for the axis
l = a
u
becomes
|t
x
| >h
A
u
+ h
B
u
|r
00
|+ h
B
v
|r
01
| + h
B
w
|r
02
|, (16.47)
and if this expression is true, then A and B are disjoint. Similar test
expressions are derived in the same manner for s = a
v
and s = a
w
.
Second, let s = b
u
, for which the derivation follows:
|t · s| = |t · b
u
| = |t
x
b
u
x
+ t
y
b
u
y
+ t
z
b
u
z
| = |t
x
r
00
+ t
y
r
10
+ t
z
r
20
|,
d
A
=
i∈{u,v,w}
h
A
i
|a
i
· s| =
i∈{u,v,w}
h
A
i
|a
i
· b
u
|
= h
A
u
|b
u
x
| + h
A
v
|b
u
y
|+ h
A
w
|b
u
z
| = h
A
u
|r
00
|+ h
A
v
|r
10
| + h
A
w
|r
20
|,
d
B
=
i∈{u,v,w}
h
B
i
|b
i
· s| =
i∈{u,v,w}
h
B
i
|b
i
·b
u
| = h
B
u
.
(16.48)
This leads to the disjointedness test in Equation 16.49 for s = b
u
:
|t
x
r
00
+ t
y
r
10
+ t
z
r
20
| >h
A
u
|r
00
|+ h
A
v
|r
10
| + h
A
w
|r
20
|+ h
B
u
. (16.49)
Again, for the remaining axes, b
v
and b
w
, similar tests are derived in
the same manner.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.