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

Search Nedrilad ::

Custom Search