Game Development Reference
In-Depth Information
chosen for both of the terms containing zero dot products. For instance, if
0
SN
=
and
TN
=
0
, then the vertices
C ,
C , C , and
C of the face in contact
with the plane are given by
]
()
(
)
C
=
Q
t
1
[
sgn
R N R
±
S
±
T .
(12.19)
1, 2 ,3, 4
2
12.1.3 Spatial Partitioning
Being able to determine whether an object collides with a plane is essential to
fast collision detection in a spatially partitioned environment. Since regions of
octrees and BSP trees are separated by planes, we can usually tell that a moving
object does not collide with large parts of the world without having to perform
collision detection tests with the actual geometry in those regions.
Suppose that an object moves from the point P to the point P during a single
frame. Let
L N represent a plane that partitions the world geometry in
some way, and suppose that the moving object has an effective radius of ef r with
respect to that plane. We say that the object lies completely on the positive side
of the plane L if its position P satisfies
=
, D
L P
⋅≥
r
,
(12.20)
eff
and we say that the object lies completely on the negative side of the plane L if
its position P satisfies
L P
⋅≤−
r
.
(12.21)
eff
If both of the points P and P represent positions of the object for which it lies
completely on the positive side of the plane, then we know that no part of the
object ever crosses into the negative side of the plane L . Similarly, if both of the
points P and P represent positions of the object for which it lies completely on
the negative side of the plane, then we know that no part of the object ever cross-
es into the positive side of the plane L . When these cases occur, we can avoid
performing collision detection calculations between the moving object and any
geometry that lies on the opposite side of the plane L .
12.2 General Sphere Collisions
We now study a powerful technique for determining when a moving sphere col-
lides with an arbitrary static environment. The method presented in this section is
quite capable of serving as the entire collision detection system for a 3D game