Graphics Reference
In-Depth Information
(that is, vertices
A
and
D
). The remaining vertices are also swapped to ensure that
A
and
D
lie above the plane of the other triangle (viewing the other triangle in its
counterclockwise order).
After the triangles have been brought into the canonical form, the edges incident
to
A
and
D
(that is,
AB
and
AC
, and
DE
and
DF
, respectively) are now guaranteed to
intersect the line
L
of intersection between the two planes. Furthermore, the overlap
of the intersection intervals on
L
can now be determined through two scalar triple
product tests on the vertices, without explicitly computing the intervals themselves.
Overall, the logic for Devillers' test is more involved than the other methods pre-
sented here, but if implemented correctly the authors suggest the resulting code
becomes somewhat faster as well as more robust. Refer to the original presentation
for full implementational details.
5.3
Intersecting Lines, Rays, and (Directed) Segments
Tests involving lines, rays, and segments are frequently used, for example, to simulate
bullets fired or for testing line of sight. Line tests are sometimes used instead of more
complicated queries. For example, the contact of a hand or foot of a player character
against the environment or the contact of a vehicle wheel against the ground can often
be efficiently modeled with a simple line test. The following sections explore efficient
tests of lines, rays, and segments against various common collision primitives.
5.3.1
Intersecting Segment Against Plane
Let a plane
P
be given by (
n
·
X
)
=
d
and a segment by the parametric equation
S
(
t
)
1 (Figure 5.20). The
t
value of intersection of the
segment with the plane is obtained by substituting the parametric equation for
X
in
the plane equation and solving for
t
:
=
A
+
t
(
B
−
A
) for 0
≤
t
≤
(
n
·
(
A
+
t
(
B
−
A
)))
=
d
(substituting S
(
t
)
=
A
+
t
(
B
−
A
)
for X in
(
n
·
X
)
=
d)
n
·
A
+
t
n
·
(
B
−
A
)
=
d
(expanding the dot product)
t
n
·
(
B
−
A
)
=
d
−
n
·
A
(moving scalar term to RHS)
A
)
(
n
t
=
(
d
−
n
·
·
(
B
−
A
))
(dividing both sides by
n
·
(
B
−
A
)
to isolate t)
The expression for
t
can now be inserted into the parametric equation for the seg-
ment to find the actual intersection point
Q
:
A
)
(
n
Q
=
A
+[
(
d
−
n
·
·
(
B
−
A
))
]
(
B
−
A
).
