i
i
i
i
i
i
i
i
780 16. Intersection Test Methods
of plane/AABB (Section 16.10) or plane/sphere (Section 16.14.2) tests.
While it is possible for false hits to be generated when doing shaft/sphere
testing, shaft/box testing is exact.
Haines and Wallace discuss optimizations for shaft formation and culling,
and code is available on the web [483, 486].
16.16 Line/Line Intersection Tests
In this section, both two- and three-dimensional line/line intersection tests
will be derived and examined. Lines, rays, and line segments will be inter-
sected, and methods that are both fast and elegant will be described.
16.16.1 Two Dimensions
First Method
From a theoretical viewpoint, this first method of computing the intersec-
tion between a pair of two-dimensional lines is truly beautiful. Consider
two lines, r
1
(s)=o
1
+ sd
1
and r
2
(t)=o
2
+ td
2
.Sincea ·a
⊥
= 0 (the perp
dot product [551] from Section 1.2.1), the intersection calculations between
r
1
(s)andr
2
(t) become elegant and simple. Note that all vectors are two
dimensional in this subsection:
1: r
1
(s)=r
2
(t)
⇐⇒
2: o
1
+ sd
1
= o
2
+ td
2
⇐⇒
3:
sd
1
·d
⊥
2
=(o
2
− o
1
) · d
⊥
2
td
2
·d
⊥
1
=(o
1
− o
2
) · d
⊥
1
⇐⇒
4:
⎧
⎪
⎪
⎨
⎪
⎪
⎩
s =
(o
2
− o
1
) · d
⊥
2
d
1
·d
⊥
2
t =
(o
1
− o
2
) · d
⊥
1
d
2
·d
⊥
1
(16.55)
If d
1
·d
⊥
2
= 0, then the lines are parallel and no intersection occurs. For
lines of infinite length, all values of s and t are valid, but for line segments
(with normalized directions), say of length l
1
and l
2
(starting at s =0and
t = 0 and ending at s = l
1
and t = l
2
), we have a valid intersection if and
only if 0 ≤ s ≤ l
1
and 0 ≤ t ≤ l
2
.Or,ifyouseto
1
= p
1
and d
1
= p
2
−p
1
(meaning that the line segment starts at p
1
and ends at p
2
) and do likewise
for r
2
with startpoints and endpoints q
1
and q
2
, then a valid intersection
occurs if and only if 0 ≤ s ≤ 1and0≤ t ≤ 1. For rays with origins, the
i
i
i
i
i
i
i
i
16.16. Line/Line Intersection Tests 781
valid range is s ≥ 0andt ≥ 0. The point of intersection is obtained either
by plugging s into r
1
or by plugging t into r
2
.
Second Method
Antonio [29] describes another way of deciding whether two line segments
(i.e., of finite length) intersect by doing more compares and early rejec-
tions and by avoiding the expensive calculations (divisions) in the previous
formulae. This method is therefore faster. The previous notation is used
again, i.e., the first line segment goes from p
1
to p
2
and the second from q
1
to q
2
. This means r
1
(s)=p
1
+s(p
2
−p
1
)andr
2
(t)=q
1
+t(q
2
−q
1
). The
result from Equation 16.55 is used to obtain a solution to r
1
(s)=r
2
(t):
⎧
⎪
⎪
⎪
⎪
⎨
⎪
⎪
⎪
⎪
⎩
s =
−c · a
⊥
b · a
⊥
=
c · a
⊥
a · b
⊥
=
d
f
,
t =
c · b
⊥
a · b
⊥
=
e
f
.
(16.56)
In Equation 16.56, a = q
2
− q
1
, b = p
2
− p
1
, c = p
1
− q
1
, d = c · a
⊥
,
e = c · b
⊥
,andf = a · b
⊥
. The simplification step for the factor s comes
from the fact that a
⊥
·b = −b
⊥
·a and a ·b
⊥
= b
⊥
·a.Ifa ·b
⊥
=0,then
the lines are collinear. Antonio [29] observes that the denominators for
both s and t are the same, and that, since s and t are not needed explicitly,
the division operation can be omitted. Define s = d/f and t = e/f.To
test if 0 ≤ s ≤ 1 the following code is used:
1:if(f>0)
2: if(d<0 or d>f) return NO
INTERSECTION;
3:else
4: if(d>0 or d<f) return NO
INTERSECTION;
After this test, it is guaranteed that 0 ≤ s ≤ 1. The same is then
done for t = e/f (by replacing d by e in the code). If the routine has not
returned after this test, the line segments do intersect, since the t-value is
then also valid.
Source code for an integer version of this routine is available on the
web [29], and is easily converted for use with floating point numbers.
16.16.2 Three Dimensions
Say we want to compute in three dimensions the intersection between two
lines (defined by rays, Equation 16.1). The lines are again called r
1
(s)=
o
1
+ sd
1
and r
2
(t)=o
2
+ td
2
, with no limitation on the value of t.The
three-dimensional counterpart of the perp dot product is, in this case, the
i
i
i
i
i
i
i
i
782 16. Intersection Test Methods
cross product, since a × a = 0, and therefore the derivation of the three-
dimensional version is very similar to that of the two-dimensional version.
The intersection between two lines is derived below:
1: r
1
(s)=r
2
(t)
⇐⇒
2: o
1
+ sd
1
= o
2
+ td
2
⇐⇒
3:
sd
1
× d
2
=(o
2
− o
1
) × d
2
td
2
× d
1
=(o
1
− o
2
) × d
1
⇐⇒
4:
s(d
1
× d
2
) · (d
1
× d
2
)=((o
2
− o
1
) × d
2
) · (d
1
× d
2
)
t(d
2
× d
1
) · (d
2
× d
1
)=((o
1
− o
2
) × d
1
) · (d
2
× d
1
)
⇐⇒
5:
⎧
⎪
⎪
⎪
⎪
⎨
⎪
⎪
⎪
⎪
⎩
s =
det(o
2
− o
1
, d
2
, d
1
× d
2
)
||d
1
× d
2
||
2
t =
det(o
2
− o
1
, d
1
, d
1
× d
2
)
||d
1
× d
2
||
2
(16.58)
Step 3 comes from subtracting o
1
(o
2
)frombothsidesandthencross-
ing with d
2
(d
1
), and Step 4 is obtained by dotting with d
1
×d
2
(d
2
×d
1
).
Finally, Step 5, the solution, is found by rewriting the right sides as de-
terminants (and changing some signs in the bottom equation) and then by
dividing by the term located to the right of s (t).
Goldman [411] notes that if the denominator ||d
1
×d
2
||
2
equals 0, then
the lines are parallel. He also observes that if the lines are skew (i.e., they
do not share a common plane), then the s and t parameters represent the
points of closest approach.
If the lines are to be treated like line segments, with lengths l
1
and
l
2
(assuming the direction vectors d
1
and d
2
are normalized), then check
whether 0 ≤ s ≤ l
1
and 0 ≤ t ≤ l
2
both hold. If not, then the intersection
is rejected.
Rhodes [1064] gives an in-depth solution to the problem of intersecting
two lines or line segments. He gives robust solutions that deal with special
cases, and he discusses optimizations and provides source code.
16.17 Intersection Between Three Planes
Given three planes, each described by a normalized normal vector, n
i
,and
an arbitrary point on the plane, p
i
, i = 1, 2, and 3, the unique point, p,of
intersection between those planes is given by Equation 16.59 [410]. Note
i
i
i
i
i
i
i
i
16.18. Dynamic Intersection Testing 783
that the denominator, the determinant of the three plane normals, is zero
if two or more planes are parallel:
p =
(p
1
·n
1
)(n
2
× n
3
)+(p
2
·n
2
)(n
3
× n
1
)+(p
3
· n
3
)(n
1
× n
2
)
|n
1
n
2
n
3
|
.
(16.59)
This formula can be used to compute the corners of a BV consisting of a
set of planes. An example is a k-DOP, which consists of k plane equations.
Equation 16.59 can calculate the corners of the polytope if it is fed with
the right planes.
If, as is usual, the planes are given in implicit form, i.e., π
i
: n
i
·x+d
i
=
0, then we need to find the points p
i
in order to be able to use the equation.
Any arbitrary point on the plane can be chosen. We compute the point
closest to the origin, since those calculations are inexpensive. Given a ray
from the origin pointing along the plane’s normal, intersect this with the
plane to get the point closest to the origin:
r
i
(t)=tn
i
n
i
·x + d
i
=0
⇒
n
i
· r
i
(t)+d
i
=0
⇐⇒
tn
i
·n
i
+ d
i
=0
⇐⇒
t = −d
i
⇒
p
i
= r
i
(−d
i
)=−d
i
n
i
.
(16.60)
This result should not come as a surprise, since d
i
in the plane equation
simply holds the perpendicular, negative distance from the origin to the
plane (the normal must be of unit length if this is to be true).
16.18 Dynamic Intersection Testing
Upuntilnow,onlystatic intersection testing has been considered. This
means that all objects involved are not moving during testing. However,
this is not always a realistic scenario, especially since we render frames
at discrete times. For example, discrete testing means that a ball that is
on one side of a closed door at time t might move to the other side at
t +Δt (i.e., the next frame), without any collision being noticed by a static
intersection test. One solution is to make several tests uniformly spaced
between t and t+Δt. This would increase the computational load, and still
the intersection could be missed. A dynamic intersection test is designed
i
i
i
i
i
i
i
i
784 16. Intersection Test Methods
to cope with this problem. This section provides an introduction to the
topic. More information can be found in Ericson’s [315] and Eberly’s [294]
books.
Methods such as shaft culling (Section 16.15) can be used to aid in
intersection testing of moving AABBs. The object moving through space
is represented by two AABBs at different times, and these two AABBs are
joined by a shaft. However, intersection algorithms usually become simpler
and faster if the moving object is contained in a bounding sphere. In fact,
it is often worthwhile to use a set of a few spheres to tightly bound and
represent the moving object [1137].
One principle that can be applied to dynamic intersection testing sit-
uations where only translations (not rotations) take place is the fact that
motion is relative. Assume object A moves with velocity v
A
and object B
with velocity v
B
, where the velocity is the amount an object has moved
during the frame. To simplify calculations, we instead assume that A is
moving and B is still. To compensate for B’s velocity, A’s velocity is then:
v = v
A
−v
B
. As such, only one object is given a velocity in the algorithms
that follow.
16.18.1 Sphere/Plane
Testing a sphere dynamically against a plane is simple. Assume the sphere
has its center at c and a radius r. In contrast to the static test, the sphere
also has a velocity v during the entire frame time Δt.So,inthenextframe,
the sphere will be located at e = c +Δtv. For simplicity, assume Δt is
1 and that this frame starts at time 0. The question is: Has the sphere
collided with a plane π : n · x + d = 0 during this time?
The signed distance, s
c
, from the sphere’s center to the plane is ob-
tained by plugging the sphere center into the plane equation. Subtracting
the sphere radius from this distance gives how far (along the plane normal)
the sphere can move before reaching the plane. This is illustrated in Fig-
ure 16.28. A similar distance, s
e
, is computed for the endpoint e.Now,if
the sphere centers are on the same side of the plane (tested as s
c
s
e
> 0),
and if |s
c
| >rand |s
e
| >r, then an intersection cannot occur, and the
sphere can safely be moved to e. Otherwise, the sphere position and the
exact time when the intersection occurs is obtained as follows [420]. The
time when the sphere first touches the plane is t,wheret is computed as
t =
s
c
− r
s
c
− s
e
. (16.61)
The sphere center is then located at c + tv. A simple collision response
at this point would be to reflect the velocity vector v around the plane
normal, and move the sphere using this vector: (1 − t)r,where1−t is the
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.