i
i
i
i
i
i
i
i
730 16. Intersection Test Methods
Figure 16.3. A three-dimensional OBB, B, with its center point, b
c
, and its normalized,
positively oriented side vectors, b
u
, b
v
,andb
w
. The half-lengths of the sides, h
B
u
, h
B
v
,
and h
B
w
, are the distances from the center of the box to the center of the faces, as shown.
A three-dimensional OBB and its notation are depicted in Figure 16.3.
Definition. A k-DOP (discrete oriented polytope) is defined by k/2(wherek
is even) normalized normals (orientations), n
i
,1≤ i ≤ k/2, and with each
n
i
two associated scalar values d
min
i
and d
max
i
,whered
min
i
<d
max
i
.Each
triple (n
i
, d
min
i
, d
max
i
) describes a slab, S
i
, which is the volume between
the two planes, π
min
i
: n
i
· x + d
min
i
=0andπ
max
i
: n
i
· x + d
max
i
=0,
and where the intersection of all slabs,
1≤l≤k/2
S
l
, is the actual k-DOP
volume. The k-DOP is defined as the tightest set of slabs that bound the
object [315].
Figure 16.4 depicts an 8-DOP in two dimensions.
min
max
Figure 16.4. An example of a two-dimensional 8-DOP for a tea cup, with all normals,
n
i
, shown along with the zero’th slab, S
1
, and the “size” of the slab: d
min
1
and d
max
1
.
i
i
i
i
i
i
i
i
16.2. Definitions and Tools 731
A separating axis specifies a line in which two objects that do not over-
lap (are disjoint) have projections onto that line that also do not overlap.
Similarly, where a plane can be inserted between two three-dimensional
objects, that plane’s normal defines a separating axis. An important tool
for intersection testing [433, 451] follows, one that works for convex polyhe-
dra such as AABBs, OBBs, and k-DOPs. It is an aspect of the separating
hyperplane theorem [135].
2
Separating Axis Test (SAT). For any two arbitrary, convex, disjoint polyhe-
dra, A and B, there exists at least one separating axis where the projections
of the polyhedra, which form intervals on the axis, are also disjoint. This
does not hold if one object is concave. For example, the walls of a well and
a bucket inside may not touch, but no plane can divide them. Further-
more, if A and B are disjoint, then they can be separated by an axis that
is orthogonal (i.e., by a plane that is parallel) to either
1. A face of A,
2. A face of B,or
3. An edge from each polyhedron (e.g., cross product).
This test is illustrated for two boxes in Figure 16.21 on page 768. Note
that the definition of a convex polyhedron is very liberal here. A line
segment and a convex polygon such as a triangle are also convex polyhedra
(though degenerate, since they enclose no volume). A line segment A does
not have a face, so the first test disappears. This test is used in deriving the
box/line segment overlap test in Section 16.7.2, the triangle/box overlap
test in Section 16.12, and the OBB/OBB overlap test in Section 16.13.5.
To return to the discussion of methods that can be brought to bear, a
common technique for optimizing intersection tests is to make some simple
calculations early on that can determine whether the ray or object totally
misses the other object. Such a test is called a rejection test,andifthe
test succeeds, the intersection is said to be rejected.
Another approach often used in this chapter is to project the three-
dimensional objects onto the “best” orthogonal plane (xy, xz,oryz), and
solve the problem in two dimensions instead.
Finally, due to numerical imprecision, we often use a very small num-
ber in the intersection tests. This number is denoted (epsilon), and its
value will vary from test to test. However, often an epsilon is chosen that
works for the programmer’s problem cases (what Press et al. [1034] call a
“convenient fiction”), as opposed to doing careful roundoff error analysis
2
This test is sometimes known as the “separating axis theorem” in computer graphics,
a misnomer we helped promulgate in previous editions. It is not a theorem itself, but is
rather a special case of the separating hyperplane theorem.
i
i
i
i
i
i
i
i
732 16. Intersection Test Methods
and epsilon adjustment. Such code used in another setting may well break
because of differing conditions. Ericson’s book [315] discusses the area of
numerical robustness in depth in the context of geometric computation.
This caveat firmly in place, we sometimes do attempt to provide epsilons
that are at least reasonable starting values for “normal” data, small scale
(say less than 100, more than 0.1) and near the origin.
16.3 Bounding Volume Creation
Given a collection of objects, finding a tight fitting bounding volume is
important to minimizing intersection costs. The chance that an arbitrary
ray will hit any convex object is proportional to that object’s surface area
(see Section 16.4). Minimizing this area increases the efficiency of any
intersection algorithm, as a rejection is never slower to compute than an
intersection. In contrast, it is often better to minimize the volume of each
BV for collision detection algorithms. This section briefly covers methods
of finding optimal or near-optimal bounding volumes given a collection of
polygons.
AABB and k-DOP Creation
The simplest bounding volumes to create is an AABB. Take the minimum
and maximum extents of the set of polygon vertices along each axis and
the AABB is formed. The k-DOP is an extension of the AABB: Project
the vertices onto each normal, n
i
,ofthek-DOP, and the extreme values
(min,max) of these projections are stored in d
i
min
and d
i
max
.Thesetwo
values define the tightest slab for that direction. Together, all such values
define a minimal k-DOP.
Sphere Creation
Bounding sphere formation is not as straightforward as determining slab
extents. There are a number of algorithms that perform this task, and
these have speed versus quality tradeoffs. A fast, constant-time single pass
algorithm is to form an AABB for the polygon set and then use the center
and the diagonal of this box to form the sphere. This sometimes gives a
poor fit, and the fit can often be improved by another quick pass: Starting
with the center of the AABB as the center of the sphere BV, go through
all vertices once again and find the one that is farthest from this center
(comparing against the square of the distance so as to avoid taking the
square root). This is then the new radius.
Ritter [1070] presents a simple algorithm that creates a near-optimal
bounding sphere. The idea is to find the vertex that is at the minimum
and the vertex at the maximum along each of the x, y,andz axes. For
i
i
i
i
i
i
i
i
16.3. Bounding Volume Creation 733
these three pairs of vertices, find the pair with the largest distance between
them. Use this pair to form a sphere with its center at the midpoint
between them and a radius equal to the distance to them. Go through all
the other vertices and check their distance d to the center of the sphere. If
the vertex is outside the sphere’s radius r, move the sphere’s center toward
the vertex by (d − r)/2, set the radius to (d + r)/2, and continue. This
step has the effect of enclosing the vertex and the existing sphere in a new
sphere. After this second time through the list, the bounding sphere is
guaranteed to enclose all vertices. Code is available on the web.
Welzl [1339] presents a more complex algorithm, which is implemented
by Eberly [294, 1131] and Ericson [315], with code on the web. This algo-
rithm is expected to be linear for a randomized list of vertices (random-
ization helps find a good sphere quickly on average). The idea is to find a
supporting set of points defining a sphere. A sphere can be defined by a
set of two, three, or four points on its surface. When a vertex is found to
be outside the current sphere, its location is added to the supporting set
(and possibly old support vertices removed from the set), the new sphere
is computed, and the entire list is run through again. This process repeats
until the sphere contains all vertices. While more complex than the previ-
ous methods, this algorithm guarantees that an optimal bounding sphere
is found.
OBB Creation
OBB formation, with its arbitrary basis orientation, is even more involved
than finding a reasonable bounding sphere. One method by Gottschalk [434]
will be presented, followed by a brief explanation of another method by
Eberly [294].
It has been shown that a tight-fitting OBB enclosing an object can
be found by computing an orientation from the triangles of the convex
hull [433, 434]. The convex hull is used because it avoids using points in
the interior of the object that should not affect the orientation of the box.
Also, an integration is performed over each triangle of the convex hull. This
is done since using the vertices of the convex hull can make for bad-fitting
boxes, if, for example, several vertices clump in a small region. Here, we
will present the formulae for computing a good-fit OBB using a statistical
method. The derivation is found in Gottschalk’s Ph.D. thesis [434].
First, the convex hull of an object must be computed. This can be
done with, for example, the Quickhull algorithm [62]. This gives us, say,
n triangles defined as p
k
q
k
r
k
,wherep
k
, q
k
,andr
k
are the vertices of
triangle k,0≤ k<n. We also denote the area of triangle k as a
k
,andthe
total area of the convex hull as a
H
=
n−1
k=0
a
k
. Furthermore, the centroid
of triangle i is m
i
=(p
i
+ q
i
+ r
i
)/3, that is, the mean of the vertices.
The centroid of the whole convex hull, m
H
, is the weighted mean of the
i
i
i
i
i
i
i
i
734 16. Intersection Test Methods
triangle centroids, as shown in Equation 16.5:
m
H
=
1
a
H
n−1
k=0
a
k
m
k
. (16.5)
With the use of these definitions, we will present a formula that com-
putes a 3 × 3 covariance matrix, C, whose eigenvectors (see Section A.3.1
on how to compute the eigenvectors) are the direction vectors for a good-fit
box:
C =[c
ij
]=
!
1
a
H
n−1
k=0
a
k
12
(9m
k
i
m
k
j
+ p
k
i
p
k
j
+ q
k
i
q
k
j
+ r
k
i
r
k
j
)
− m
H
i
m
H
j
"
,
0 ≤ i, j < 3. (16.6)
After computing C, the eigenvectors are computed and normalized.
These vectors are the direction vectors, a
u
, a
v
,anda
w
, of the OBB. We
must next find the center and the half-lengths of the OBB. This is done
by projecting the points of the convex hull onto the direction vectors and
finding the minimum and maximum along each direction. These will de-
termine the size and position of the box, i.e., will fully specify the OBB
according to its definition (see Section 16.2).
When computing the OBB, the most demanding operation is the convex
hull computation, which takes O(n log n) time, where n is the number of
primitives of the object. The basis calculation takes, at most, linear time,
and the eigenvector computation takes constant time, which means that
computing an OBB for a set of n triangles takes O(n log n)time.
Eberly [294] presents a method for computing a minimum-volume OBB
using a minimization technique. An advantage is that the convex hull need
not be computed. This is an iterative algorithm, and so the initial guess of
the box determines how fast the solution converges to the minimum box.
For a box with the axes a
u
, a
v
,anda
w
, the points are projection onto
these axes. The min, k
u
min
,andmax,k
u
max
,alonga
u
are found. Then k
v
min
,
k
v
max
, k
w
min
,andk
w
max
are computed similarly. The center of this box is then
a
c
=
k
u
min
+ k
u
max
2
a
u
+
k
v
min
+ k
v
max
2
a
v
+
k
w
min
+ k
w
max
2
a
w
. (16.7)
The half-lengths of the sides of the box are then h
l
=(k
l
max
− k
l
min
)/2,
for l ∈{u, v, w}. Eberly samples the set of possible directions of the box,
and uses the axes whose box is smallest as a starting point for the numeric
minimizer. Then Powell’s direction set method [1034] is used to find the
minimum volume box. Eberly has code for this operation on the web [294].
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.