Game Programming Algorithms and Techniques: A Platform-Agnostic Approach (2014)

Chapter 7. Physics

Although not every game needs physics, the ones that do implement collision detection and movement at a minimum. Collision detection enables the game to determine whether or not two game objects intersect with each other. A variety of different algorithms can be used to detect these collisions, and the first part of this chapter covers some of the more basic ones.

The movement part of physics takes into account force, acceleration, mass, and the other properties inherit in classical mechanics to determine where objects go from frame to frame. The only way this can be done is by using calculus, specifically the numeric integration methods covered in the second part of this chapter.

Planes, Rays, and Line Segments

Before we broach the topic of how we might represent characters and other game objects in the world for the purposes of collision detection, we need to discuss a couple of additional mathematical topics useful for physics systems. You may have learned about these objects in a high school algebra course, but now that you have familiarity with linear algebra we can approach them from a slightly different perspective.

Planes

A plane is a flat, two-dimensional surface that extends infinitely, much like a line is a one-dimensional object that extends infinitely. In games, we may commonly use planes as abstractions for the ground or walls, though there are also other uses. A plane can be represented in a few different ways, but game programmers prefer

where P is any arbitrary point on the plane, is the normal to the plane, and the absolute value of d is the minimum distance between the plane and the origin.

Recall that a triangle is guaranteed to lie on a single plane. One reason the preceding plane representation is popular is because given a triangle, it is possible to quickly construct the equation of the plane that triangle is on. Once we’ve computed both and d, we can then test if any arbitrary point, P, also satisfies the equation, in which case this arbitrary point is also on the plane.

Suppose we have the triangle ΔABC expressed in a clockwise winding order (see Figure 7.1). In order to create the equation of the plane the triangle is on, we first need to calculate the normal of the triangle. Hopefully you remember that you can take the cross product between two edge vectors to determine the normal of the triangle—if you don’t, you should review Chapter 3, “Linear Algebra for Games,” before you go any further.

Figure 7.1 Triangle ABC in a clockwise winding order.

Don’t forget that the order of the cross product matters, so it’s important to look at the winding order. Because ΔABC has a clockwise winding order, as illustrated in Figure 7.1, we want to construct vectors from A to B and B to C. Once we have these two vectors, we take the cross product between them and normalize the result to end up with .

Once we have , we need a point somewhere on the plane to solve for d, because

Luckily, it turns out we have three points that we absolutely know are on the same plane as the triangle: A, B, and C. We can dot product any of these points with and we will end up with the same value of d.

All the points on the plane will yield the same d value because it’s a scalar projection: is normalized and P is unnormalized, so what we get is the minimum distance from the origin to the plane in the direction of . This minimum distance will be the same regardless of which vertex we select, because all of them are on the same plane.

Once we’ve solved for and d, we can then store these values in our Plane data structure:

struct Plane
Vector3 normal
float d
end

Rays and Line Segments

A ray starts at a specific point and extends infinitely in one particular direction. In games, it’s typical to represent a ray using a parametric function. Recall that a parametric function is one that is expressed in terms of an arbitrary parameter, generally by the name of t. For a ray, the parametric function is

where R₀ is the starting point of the plane and is the direction the ray is travelling in. Because a ray starts at a specific point and extends infinitely, for this representation of a ray to work properly, t must be greater than or equal to 0. This means that when t is 0, the parametric function will yield the starting point R₀.

A line segment is similar to a ray, except it has both a start and end point. We can actually use the same exact parametric function to represent a line segment. The only difference is we now also have a maximum value of t, because a line segment has a discrete end point.

Technically, a ray cast involves firing a ray and checking whether or not the ray intersects with one or more objects. However, what is confusing is that most physics engines, including Havok and Box2D, use the term “ray cast” when in actuality they are using a line segment, not a ray. The reason for this is that game worlds usually have constraints, so it typically makes sense to use the more constrained line segment.

I admit that this terminology might be confusing. However, I wanted to be consistent with the terminology I’ve seen used in the game industry. So keep in mind as you continue reading the book that whenever you see the term “ray cast,” we are actually using a line segment.

So what are these ray casts used for anyways? It turns out they’re actually quite ubiquitous in 3D games. One very common example is firing a bullet that travels in a straight line. Although some games do simulate actual projectiles for their bullets, it may be appropriate to perform a ray cast instead, because the bullet travels so quickly. But there are other uses of a ray cast. Some examples include a reticule that changes red or green depending on friend or foe (covered in Chapter 10, “User Interfaces”), an AI that needs to determine whether an enemy is visible, Fresnel acoustic diffraction (covered in Chapter 6, “Sound”), and using the mouse to click objects in a 3D world (covered in Chapter 8, “Cameras”). All of these scenarios and many more use ray casts in one way or another.

Because a ray cast request uses a line segment, at a minimum we need two parameters—the start point and the end point of the ray cast:

struct RayCast
Vector3 startPoint
Vector3 endPoint
end

To convert startPoint and endPoint to the parametric form of a line segment is fairly straightforward. R₀ is identical to startPoint, and is endPoint - startPoint. When the conversion is done in this manner, the t values from 0 to 1 will correspond to the range of the ray cast. That is to say, a t of 0 will yield startPoint whereas a t of 1 will yield endPoint.

Collision Geometry

In modern 3D games, it’s very common for human characters to be composed of 15,000+ polygons. When a game needs to determine whether or not two characters collide, it wouldn’t be terribly efficient to check against all these triangles. For this reason, most games utilize simplifiedcollision geometry, such as spheres and boxes, to test for collisions. This collision geometry isn’t drawn to the screen, but only used to check for collisions efficiently. In this section we cover some of the most common collision geometries used in games.

It’s also worth noting that it’s not uncommon for games to have multiple levels of collision geometry per object. This way, a simple collision check (such as with spheres) can be performed first to check whether there’s any possibility whatsoever that two objects collided. If the simple collision check says there might be a collision, we can then perform calculations with more complex collision geometry.

Bounding Sphere

The simplest type of collision geometry is the bounding sphere (or in 2D games, a bounding circle). A sphere can be defined with only two variables—a vector representing the center of the sphere, and a scalar for the radius of the sphere:

class BoundingSphere
Vector3 center
float radius
end

As illustrated in Figure 7.2, certain objects, such as an asteroid, fit well with bounding spheres. But other types of objects, including humanoid characters, end up with a lot of empty space between the edge of the character and the sphere. This means that for many types of objects, bounding spheres can have a large number of false positives. This happens when two game objects have intersecting collision geometry, yet the game objects themselves are not actually intersecting. False positives can be really frustrating for the player, because it will be apparent if the two game objects aren’t actually intersecting when a collision is detected.

Figure 7.2 Bounding spheres for different objects.

Because of the relative inaccuracy of bounding spheres for most game objects, it usually is not appropriate to use bounding spheres as the only collision geometry. But the big advantage of bounding spheres is that instantaneous collision detection between two spheres is very simple, so this representation may be a great candidate for a first-line collision check.

Axis-Aligned Bounding Box

For a 2D game, an axis-aligned bounding box (or AABB) is a rectangle where every edge is parallel to either the x-axis or y-axis. Similarly, in 3D an AABB is a rectangular prism where every side of the prism is parallel to one of the coordinate axis planes. In both 2D and 3D, an AABB can be represented by two points: a minimum and a maximum point. In 2D, the minimum corresponds to the bottom-left point whereas the maximum corresponds to the top-right point.

class AABB2D
Vector2 min
Vector2 max
end

Because an AABB must keep its sides parallel to the coordinate axes, if an object is rotated the AABB may have to stretch, as demonstrated in Figure 7.3. But for 3D games, humanoid characters will typically only rotate about the up axis, and with these types of rotations the bounding box for the character may not change at all. Because of this, it’s very common to use AABBs as a basic form of collision representation for humanoid characters, especially because collision detection between AABBs, as with spheres, is not particularly expensive.

Figure 7.3 Axis-aligned bounding boxes for different orientations of a character.

Oriented Bounding Box

An oriented bounding box is similar to an axis-aligned bounding box, but with the parallel restrictions removed. That is to say, it is a rectangle (in 2D) or a rectangular prism (in 3D) with sides that may not necessarily be parallel to the coordinate axes/planes. The big advantage of an OBB is that it can rotate as the game object rotates; therefore, regardless of the orientation of the game object, the OBB will have the same degree of accuracy. But this increased accuracy comes with a price; compared to an AABB, the collision calculations for an OBB are far more complicated.

An OBB can be represented in a game in multiple ways, including eight vertexes or six planes. But the OBB calculations are complex enough that this book does not outline any algorithms related to them. However, if you’d like to use them in your game, take a look at Real-time Collision Detection in the references at the end of this chapter.

Capsule

In 2D, a capsule can be thought of as an AABB with two semicircles (half circles) attached to the top and bottom. It’s called a capsule because it looks very similar to a medicine capsule. If we expand the capsule to 3D, it becomes a cylinder with two hemispheres attached to the top and bottom. Capsules are also a popular form of collision representation for humanoid characters because they are slightly more accurate than an AABB, as illustrated in Figure 7.4(a).

Figure 7.4 Humanoid surrounded by a capsule (a), and a chair surrounded by a convex polygon (b).

Another way to think of a capsule is as a line segment that has a radius, which actually corresponds to the representation of it in a game engine:

struct Capsule2D
Vector2 startPoint
Vector2 endPoint
float radius
end

Convex Polygons

Another option is to use an arbitrary convex polygon (or in 3D, a convex hull) to represent the collision geometry. As you might expect, using an arbitrary convex polygon will be less efficient than the other options, but it also can be more accurate. Figure 7.4(b) shows a chair represented by a convex polygon. Although there still will be many false positives, the number of false positives is less than in alternative representations.

List of Collision Geometries

One last option to increase the accuracy of collision checks is to have an actual list of collision geometries to test against. So in the case of a human, we could have a sphere for the head, an AABB for the torso, and maybe some convex polygons for the hands/legs, and so on. By using several different types of collision geometries, we can almost completely eliminate false positives.

Although testing against a list of collision geometries is going to be faster than testing against the actual triangles of a model, it’s slow enough that you may not want to do it as a primary collision check. In the case of a humanoid, you should do a first-pass collision check against an AABB or capsule. Then only if that collision check passes should you bother checking against the list of collision objects. This, of course, assumes you even need that level of accuracy—you might need such accuracy to test for bullets colliding with the player, but you don’t need it to see whether or not the player is trying to walk into the wall.

Collision Detection

Now that we’ve covered some of the most common types of collision geometries used in games, we can take a look at actually testing for intersections between said objects. Any game that needs to respond to two objects colliding with each other must use some type of collision detection algorithm. Although some might find the amount of math in this section a bit off-putting, know that it is absolutely something that is used in a large number of games. Therefore, it’s very important to understand this math—it’s not covered just for the sake of being covered. This section won’t cover every permutation of every geometry colliding with every other geometry, but it does go over the most common ones you might use.

Sphere versus Sphere Intersection

Two spheres intersect if the distance between their center points is less than the sum of their radii, as shown in Figure 7.5. However, computing a distance requires the use of a square root, so to avoid the square root, it is common instead to check the distance squared against the sum of the radii squared.

Figure 7.5 Two spheres intersect (a) and do not intersect (b).

The algorithm for this is only a couple of lines of code, as shown in Listing 7.1. It’s also extremely efficient, which is what makes using spheres a very popular basic collision detection option.

Listing 7.1 Sphere versus Sphere Intersection