i
i
i
i
i
i
i
i
16.10. Plane/Box Intersection Detection 755
The advantages of the crossings test is that it is relatively fast and
robust, and requires no additional information or preprocessing for the
polygon. A disadvantage of this method is that it does not yield anything
beyond the indication of whether a point is inside or outside the polygon.
Other methods, such as the ray/triangle test in Section 16.8.1, can also
compute barycentric coordinates that can be used to interpolate additional
information about the test point [482]. Note that barycentric coordinates
can be extended to handle convex and concave polygons with more than
three vertices [346, 566].
16.10 Plane/Box Intersection Detection
One way to determine whether a box intersects a plane, π : n · x + d =0,
is to insert all the vertices of the box into the plane equation. If both
a positive and a negative result (or a zero) is obtained, then vertices are
located on both sides of (or on) the plane, and therefore, an intersection
has been detected. There are smarter,fasterwaystodothistest,which
are presented in the next two sections, one for the AABB, and one for
the OBB.
The idea behind both methods is that only two points need to be in-
serted into the plane equation. For an arbitrarily-oriented box, intersecting
a plane or not, there are two diagonally opposite corners on the box that
are the maximum distance apart, when measured along the plane’s normal.
Every box has four diagonals, formed by its corners. Taking the dot prod-
uct of each diagonal’s direction with the plane’s normal, the largest value
identifies the diagonal with these two furthest points. By testing just these
two corners, the box as a whole is tested against a plane.
16.10.1 AABB
Assume we have an AABB, B, defined by a center point, c, and a positive
half diagonal vector, h.Notethatc and h caneasilybederivedfrom
the minimum and maximum corners, b
min
and b
max
of B,thatis,c =
(b
max
+ b
min
)/2, and h =(b
max
− b
min
)/2.
Now, we want to test B against a plane n · x + d =0. Thereisa
surprisingly fast way of performing this test, and the idea is to compute
the “extent,” here denoted e, of the box when projected onto the plane
normal, n. In theory, this can be done by projecting all the eight different
half diagonals of the box onto the normal, and picking the longest one. In
practice, however, this can be implemented very rapidly as
e = h
x
|n
x
|+ h
y
|n
y
|+ h
z
|n
z
|. (16.28)
i
i
i
i
i
i
i
i
756 16. Intersection Test Methods
Why is this equivalent to finding the maximum of the eight different half
diagonals projections? These eight half diagonals are the combinations:
g
i
=(±h
x
, ±h
y
, ±h
z
), and we want to compute g
i
· n for all eight i.The
dot product g
i
·n will reach its maximum when each term in the dot product
is positive. For the x-term, this will happen when n
x
has the same sign as
h
i
x
, but since we know that h
x
is positive already, we can compute the max
term as h
x
|n
x
|.Doingthisfory and z as well gives us Equation 16.28.
Next, we compute the signed distance, s, from the center point, c,to
the plane. This is done with: s = c · n + d.Boths and e are illustrated
in Figure 16.14. Assuming that the “outside” of the plane is the positive
half-space, we can simply test if s − e>0, which then indicates that the
box is fully outside the plane. Similarly, s + e<0 indicates that the box
is fully inside. Otherwise, the box intersects the plane. This technique
is based on ideas by Ville Miettinen and his clever implementation [864].
Pseudo code is below:
PlaneAABBIntersect(B, π)
returns({OUTSIDE, INSIDE, INTERSECTING});
1: c =(b
max
+ b
min
)/2
2: h =(b
max
− b
min
)/2
3: e = h
x
|n
x
|+ h
y
|n
y
|+ h
z
|n
z
|
4: s = c · n + d
5: if(s − e>0) return (OUTSIDE);
9: if(s + e<0) return (INSIDE);
10 : return (INTERSECTING);
n
h
s
g
1
g
2
g
3
g
4
e
c
positive
half space
x
y
Figure 16.14. An axis-aligned box with center, c, and positive half diagonal, h,istested
against a plane, π. The idea is to compute the signed distance, s, from the center of
the box to the plane, and compare that to the “extent,” e, of the box. The vectors g
i
are the different possible diagonals of the two-dimensional box, where h is equal to g
1
in this example. Note also that the signed distance s is negative, and its magnitude is
larger than e, indicating that the box is inside the plane (s + e<0).
i
i
i
i
i
i
i
i
16.11. Triangle/Triangle Intersection 757
16.10.2 OBB
Testing an OBB against a plane differs only slightly from the AABB/plane
test from the previous section. It is only the computation of the “extent”
of the box that needs to be changed, which is done as
e = h
B
u
|n · b
u
|+ h
B
v
|n · b
v
|+ h
B
w
|n · b
w
|. (16.30)
Recall that (b
u
, b
v
, b
w
) are the coordinate system axes (see the definition
of the OBB in Section 16.2) of the OBB, and (h
B
u
,h
B
v
,h
B
w
)arethelengths
of the box along these axes.
16.11 Triangle/Triangle Intersection
Since graphics hardware uses the triangle as its most important (and opti-
mized) drawing primitive, it is only natural to perform collision detection
tests on this kind of data as well. So, the deepest levels of a collision de-
tection algorithm typically have a routine that determines whether or not
two triangles intersect.
The problem is: Given two triangles, T
1
= p
1
q
1
r
1
and T
2
= p
2
q
2
r
2
(which lie in the planes π
1
and π
2
, respectively), determine whether or not
they intersect.
Note that the separating axis test (see page 731) can be used to derive
a triangle/triangle overlap test. However, here we will present a method
called the interval overlap method, introduced by M¨oller [891], because it
is faster than using SAT. We will then present a further optimization by
Guigue and Devillers [467], which also makes the algorithm more robust.
Other algorithms exist for performing triangle-triangle intersection, includ-
ing a similar test by Shen et al. [1162], and one by Held [539]. Architectural
and compiler differences, as well as variation in expected hit ratios, make
it difficult to single out a single algorithm that always performs best.
From a high level, the interval overlap method starts by checking
whether T
1
intersects with π
2
, and whether T
2
intersects with π
1
.Ifboth
these tests fail, there can be no intersection. Assuming the triangles are
not coplanar, we know that the intersection of the planes, π
1
and π
2
, will
be a line, L. This is illustrated in Figure 16.15. From the figure, it can
be concluded that if the triangles intersect, their intersections on L will
also have to overlap. Otherwise, there will be no intersection. There are
different ways to implement this, and in the following, we will present the
method by Guigue and Devillers [467].
i
i
i
i
i
i
i
i
758 16. Intersection Test Methods
Figure 16.15. Triangles and the planes in which they lie. Intersection intervals are
marked in red in both figures. Left: The intervals along the line L overlap, as well as
the triangles. Right: There is no intersection; the two intervals do not overlap.
In this implementation, there is heavy use of 4 × 4 determinants from
four three-dimensional vectors, a, b, c,andd:
[a, b, c, d]=−
#
#
#
#
#
#
#
#
a
x
b
x
c
x
d
x
a
y
b
y
c
y
d
y
a
z
b
z
c
z
d
z
1111
#
#
#
#
#
#
#
#
=(d −a) ·((b −a) ×(c −a)). (16.31)
Note that we do not use the standard notation for determinants (Sec-
tion A.3.1), because the vectors are three dimensional, but the determinant
is 4×4. Geometrically, Equation 16.31 has an intuitive interpretation. The
cross product, (b − a) × (c − a), can be seen as computing the normal of
a triangle, Δabc. By taking the dot product between this normal and the
vector from a to d, we get a value that is positive if d is in the positive
half space of the triangle’s plane, Δabc. An alternative interpretation is
that the sign of the determinant tells us whether a screw in the direction of
b −a turns in the same direction as indicated by d −c. This is illustrated
in Figure 16.16.
a
b
c
d
Figure 16.16. Illustration of the screw a vector b − a in the direction of d − c.
i
i
i
i
i
i
i
i
16.11. Triangle/Triangle Intersection 759
p
2
p
1
q
2
r
2
q
1
r
1
L
π
2
π
1
i
j
k
l
Figure 16.17. Two intersecting triangles with their intersection shown on the line of
intersection, L.TheintervalsonL are also shown and are represented by i, j, k,andl.
Now, with interval overlap methods, we first test whether T
1
intersects
with π
2
, and vice versa. This can be done using the specialized determi-
nants from Equation 16.31 by evaluating [p
2
, q
2
, r
2
, p
1
], [p
2
, q
2
, r
2
, q
1
], and
[p
2
, q
2
, r
2
, r
1
]. The first test is equivalent to computing the normal of T
2
,
and then testing which half-space the point p
1
is in. If the signs of these
determinants are the same and non-zero, there can be no intersection, and
the test ends. If all are zero, the triangles are coplanar, and a separate test
is performed to handle this case. Otherwise, we continue testing whether
T
2
intersects with π
1
,usingthesametypeoftest.
Guigue and Devillers assume that no triangle vertex or edge is exactly
on the plane of the other triangle. If this occurs, they perturb the vertices
in such a way that the intersection with L is preserved. The algorithm then
proceeds by changing the order of the triangle vertices so that p
1
(p
2
)is
the only vertex that lies in that half space. At the same time, the other
vertices (q
2
and r
2
)areswappedsothatp
1
“sees” the vertices p
2
, q
2
,
and r
2
in counterclockwise order (and similarly for p
2
). The vertex order
has been arranged in this way in Figure 16.17. Let us denote the scalar
intersections on L with i, j, k,andl,fortheedgesp
1
q
1
, p
1
r
1
, p
2
q
2
,and
p
2
r
2
. This is also shown in Figure 16.17. These scalars form two intervals,
I
1
=[i, j]andI
2
=[k, l], on L.IfI
1
overlaps with I
2
, then the two triangles
intersect, and this occurs only if k ≤ j and i ≤ l. To implement k ≤ j,we
can use the sign test of the determinant (Equation 16.31), and note that
j is derived from p
1
r
1
,andk from p
2
q
2
. Using the interpretation of the
“screw test” of the determinant computation, we can conclude that k ≤ j
if [p
1
, q
1
, p
2
, q
2
] ≤ 0. The final test then becomes
[p
1
, q
1
, p
2
, q
2
] ≤ 0and[p
1
, r
1
, r
2
, p
2
] ≤ 0. (16.32)
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.