i
i
i
i
i
i
i
i
760 16. Intersection Test Methods
The entire test starts with six determinant tests, and the first three share
the first arguments, so there is a lot to gain in terms of shared computations.
In principle, the determinant can be computed using many smaller 2 × 2
subdeterminants (see Section A.3.1),andwhentheseoccurinmorethan
one 4 ×4 determinant, the computations can be shared. There is code on
the web for this test [467], and it is also possible to augment the code to
compute the actual line segment of intersection.
If the triangles are coplanar, they are projected onto the axis-aligned
plane where the areas of the triangles are maximized (see Section 16.9).
Then, a simple two-dimensional triangle-triangle overlap test is performed.
First, test all closed edges (i.e., including endpoints) of T
1
for intersection
with the closed edges of T
2
. If any intersection is found, the triangles
intersect. Otherwise, we must test whether T
1
is totally contained in T
2
or vice versa. This can be done by performing a point-in-triangle test (see
Section 16.8) for one vertex of T
1
against T
2
,andviceversa.
Robustness problems may arise when the triangles are nearly coplanar
or when an edge is nearly coplanar to the other triangle (especially when
the edge is close to an edge of the other triangle). To handle these cases in
a reasonable way, a user-defined constant, EPSILON (), can be used.
12
For
example, if |[p
2
, q
2
, r
2
, p
1
]| <,thenwemovep
1
so that [p
2
, q
2
, r
2
, p
1
]=
0. Geometrically, this means that if a point is “close enough” to the other
triangle’s plane, it is considered to be on the plane. The same is done for
the points of the other triangle, as well. The source code does not handle
degenerate triangles (i.e., lines and points). To do so, those cases should
be detected first and then handled as special cases.
16.12 Triangle/Box Overlap
This section presents an algorithm for determining whether a triangle in-
tersects an axis-aligned box. Such a test can be used to build voxel-spaces,
test triangles against boxes in collision detection, and test polygons against
canonical view volumes (see Section 4.6), and thus potentially eliminate the
need for calls to clipping and lighting routines, etc.
Green and Hatch [441] present an algorithm that can determine whether
an arbitrary polygon overlaps a box. Akenine-M¨oller [11] developed a faster
method that is based on the separating axis test (page 731), and which we
present here.
We focus on testing an axis-aligned bounding box (AABB), defined by
a center c, and a vector of half lengths, h, against a triangle Δu
0
u
1
u
2
.
To simplify the tests, we first move the box and the triangle so that the
box is centered around the origin, i.e., v
i
= u
i
− c, i ∈{0, 1, 2}.This
12
For floating point precision, =10
−6
works for “normal” data.
i
i
i
i
i
i
i
i
16.12. Triangle/Box Overlap 761
Figure 16.18. Notation used for the triangle-box overlap test. To the left, the initial
position of the box and the triangle is shown, while to the right, the box and the
triangle have been translated so that the box center coincides with the origin.
translation and the notation used is shown in Figure 16.18. To test against
an oriented box, we would first rotate the triangle vertices by the inverse
box transform, then use the test here.
Based on the separating axis test (SAT), we test the following 13 axes:
1. [3 tests] e
0
=(1, 0, 0), e
1
=(0, 1, 0), e
2
=(0, 0, 1) (the normals of the
AABB). In other words, test the AABB against the minimal AABB
around the triangle.
2. [1 test] n, the normal of Δu
0
u
1
u
2
. We use a fast plane/AABB overlap
test (see Section 16.10.1), which tests only the two vertices of the box
diagonal whose direction is most closely aligned to the normal of the
triangle.
3. [9 tests] a
ij
= e
i
×f
j
, i, j ∈{0, 1, 2},wheref
0
= v
1
−v
0
, f
1
= v
2
−v
1
,
and f
2
= v
0
−v
2
, i.e., edge vectors. These tests are very similar and
we will only show the derivation of the case where i =0andj =0
(see below).
As soon as a separating axis is found the algorithm terminates and returns
“no overlap.” If all tests pass, i.e., there is no separating axis, then the
triangle overlaps the box.
Here we derive one of the nine tests, where i =0andj =0,inStep3.
This means that a
00
= e
0
×f
0
=(0, −f
0z
,f
0y
). So, now we need to project
the triangle vertices onto a
00
(hereafter called a):
p
0
= a ·v
0
=(0, −f
0z
,f
0y
) · v
0
= v
0z
v
1y
− v
0y
v
1z
,
p
1
= a ·v
1
=(0, −f
0z
,f
0y
) · v
1
= v
0z
v
1y
− v
0y
v
1z
= p
0
, (16.33)
p
2
= a ·v
2
=(0, −f
0z
,f
0y
) · v
2
=(v
1y
− v
0y
)v
2z
− (v
1z
− v
0z
)v
2y
.
i
i
i
i
i
i
i
i
762 16. Intersection Test Methods
Normally, we would have had to find min(p
0
,p
1
,p
2
)andmax(p
0
,p
1
,p
2
),
but fortunately p
0
= p
1
, which simplifies the computations. Now we only
need to find min(p
0
,p
2
)andmax(p
0
,p
2
), which is significantly faster be-
cause conditional statements are expensive on modern CPUs.
After the projection of the triangle onto a, we need to project the box
onto a as well. We compute a “radius,” r, of the box projected on a as
r = h
x
|a
x
| + h
y
|a
y
| + h
z
|a
z
| = h
y
|a
y
|+ h
z
|a
z
|, (16.34)
where the last step comes from that a
x
= 0 for this particular axis. Then,
this axis test becomes
if( min(p
0
,p
2
) >r or max(p
0
,p
2
) < −r) return false; (16.35)
Code is available on the web [11].
16.13 BV/BV Intersection Tests
A closed volume that totally contains a set of objects is (in most situations)
called a bounding volume (BV) for this set. The purpose of a BV is to
provide simpler intersection tests and make more efficient rejections. For
example, to test whether or not two cars collide, first find their BVs and
test if these overlap. If they do not, then the cars are guaranteed not to
collide (which we assume is the most common case). We then have avoided
testing each primitive of one car against each primitive of the other, thereby
saving computation.
Bounding volume hierarchies are often part of the foundation of colli-
sion detection algorithms (see Chapter 17). Four bounding volumes that
are commonly used for this purpose are the sphere, the axis-aligned bound-
ing box (AABB), the discrete oriented polytope (k-DOP), and the oriented
Figure 16.19. The efficiency of a bounding volume can be estimated by the “empty”
volume; the more empty space, the worse the fit. A sphere (left), an AABB (middle
left), an OBB (middle right), and a k-DOP (right) are shown for an object, where the
OBB and the k-DOP clearly have less empty space than the others.
i
i
i
i
i
i
i
i
16.13. BV/BV Intersection Tests 763
bounding box (OBB). A fundamental operation is to test whether or not
two bounding volumes overlap. Methods of testing overlap for the AABB,
the k-DOP, and the OBB are presented in the following sections. See Sec-
tion 16.3 for algorithms that form BVs around primitives.
The reason for using more complex BVs than the sphere and the AABB
is that more complex BVs often have a tighter fit. This is illustrated in
Figure 16.19. Other bounding volumes are possible, of course. For example,
cylinders, ellipsoids, and capsules are sometimes used as bounding volumes
for objects. Also, a number of spheres can be placed to enclose a single
object [572, 1137].
16.13.1 Sphere/Sphere Intersection
For spheres, the intersection test is simple and quick: Compute the dis-
tance between the two spheres’ centers and then reject if this distance is
greater than the sum of the two spheres’ radii. Otherwise, they intersect.
In implementing this algorithm the squared distances of the various quan-
tities are used, since all that is desired is the result of the comparison. In
this way, computing the square root (an expensive operation) is avoided.
Ericson [315] gives SSE code for testing four separate pairs of spheres si-
multaneously.
bool Sphere intersect(c
1
,r
1
, c
2
,r
2
)
returns({OVERLAP, DISJOINT});
1: h = c
1
− c
2
2: d
2
= h · h
3: if(d
2
> (r
1
+ r
2
)
2
) return (DISJOINT);
4: return (OVERLAP);
16.13.2 Sphere/Box Intersection
An algorithm for testing whether a sphere and an AABB intersect was
first presented by Arvo [34] and is surprisingly simple. The idea is to
find the point on the AABB that is closest to the sphere’s center, c.One-
dimensional tests are used, one for each of the three axes of the AABB. The
sphere’s center coordinate for an axis is tested against the bounds of the
AABB. If it is outside the bounds, the distance between the sphere center
and the box along this axis (a subtraction) is computed and squared. After
we have done this along the three axes, the sum of these squared distances
is compared to the squared radius, r
2
, of the sphere. If the sum is less
than the squared radius, the closest point is inside the sphere, and the box
i
i
i
i
i
i
i
i
764 16. Intersection Test Methods
overlaps. As Arvo shows, this algorithm can be modified to handle hollow
boxes and spheres, as well as axis-aligned ellipsoids.
Larsson et al. [734] present some variants of this algorithm, including a
considerably faster SSE vectorized version. Their insight is to use simple
rejection tests early on, either per axis or all at the start. The rejection
test is to see if the center-to-box distance along an axis is greater than the
radius. If so, testing can end early, since the sphere then cannot possibly
overlap with the box. When the chance of overlap is low, this early rejection
method is noticeably faster. What follows is the QRI (quick rejections
intertwined) version of their test. The early out tests are at lines 4 and 7,
and can be removed if desired.
bool SphereAABB intersect(c,r,A)
returns({OVERLAP, DISJOINT});
1: d =0
2: for each i ∈{x, y, z}
3: if ((e = c
i
− a
min
i
) < 0)
4: if (e<−r)return (DISJOINT);
5: d = d + e
2
;
6: else if ((e = c
i
− a
max
i
) > 0)
7: if (e>r)return (DISJOINT);
8: d = d + e
2
;
9: if (d>r
2
) return (DISJOINT);
10 : return (OVERLAP);
For a fast vectorized (using SSE) implementation, Larsson et al. propose
to eliminate the majority of the branches. The insight is to evaluate lines
3 and 6 simultaneously using the following expression:
e =max(a
min
i
− c
i
, 0) + max(c
i
− a
max
i
)). (16.38)
Normally, we would then update d as d = d + e
2
. However, using SSE, we
can evaluate Equation 16.38 for x, y,andz in parallel. Pseudo code for
the full test is given below.
bool SphereAABB intersect(c,r,A)
returns({OVERLAP, DISJOINT});
1: e =(max(a
min
x
− c
x
, 0), max(a
min
y
− c
y
, 0), max(a
min
z
− c
z
, 0))
2: e = e +(max(c
x
− a
max
x
, 0), max(c
y
− a
max
y
, 0), max(c
z
− a
max
z
, 0))
3: d = e ·e
4: if (d>r
2
) return (DISJOINT);
5: return (OVERLAP);
Note that lines 1 and 2 can be implemented using a parallel SSE max
function. Even though there are no early outs in this test, it is still faster
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.