Game Engine Architecture

625

objects in the collision world. If it intersects any of them, the contact point or
points are returned.
Ray casting systems typically describe the line segment via its start point
p 0 and a delta vector d that, when added to p 0 , yields the end point p 1. Any
point on this line segment can be found via the following parametric equation ,
where the parameter t is permitt ed to vary between zero and one:

p pd( )t=+ 0 t^ , t∈[0 , 1].

Clearly, p 0 = p(0) and p 1 = p(1). In addition, any contact point along the seg-
ment can be uniquely described by specifying the value of the parameter t cor-
responding to the contact. Most ray casting APIs return their contact points as
“t values,” or they permit a contact point to be converted into its correspond-
ing t by making an additional function call.
Most collision detection systems are capable of returning the earliest con-
tact —i.e., the contact point that lies closest to p 0 and corresponds to the small-
est value of t. Some systems are also capable of returning a complete list of all
collidables that were intersected by the ray or line segment. The information
returned for each contact typically includes the t value, some kind of unique
identifi er for the collidable entity that was hit, and possibly other information
such as the surface normal at the point of contact or other relevant properties
of the shape or surface that was struck. One possible contact point data struc-
ture is shown below.

struct RayCastContact

{

F32 m_t; // the t value for this

// contact

U32 m_collidableId; // which collidable did we

// hit?

Vector m_normal; // surface normal at

// contact pt.

// other information...

};

Applications of Ray Casts

Ray casts are used heavily in games. For example, we might want to ask the
collision system whether character A has a direct line of sight to character B.
To determine this, we simply cast a directed line segment from the eyes of
character A to the chest of character B. If the ray hits character B, we know that
A can “see” B. But if the ray strikes some other object before reaching character
B, we know that the line of sight is being blocked by that object. Ray casts

12.3. The Collision Detection System