Congratulations on making it to the final chapter! Detecting collisions and building a physics engine is hard work. We have covered a lot of ground, but there is still more to learn. This chapter will provide an overview of some advanced features you can add to your physics engine and provide resources on where to go from here. In this chapter, the following topics will be covered:
Generic collisions
Stability improvements
Open source physics engines
Books
Online resources
Summary
We have covered a lot in this book; starting from 3D math, we worked our way up to simulating 3D physics.
There is still much room for improvement. This chapter is dedicated to give guidance on advanced concepts that you can research and implement to make your physics engine even better.
After covering some of these advanced topics, I will provide a list of books, open source projects, and online resources you can use to take your physics simulation to the next level!
A large part of this book was dedicated to finding the most efficient way of determining whether two shapes intersect. The most robust, general purpose algorithm we have talked about so far has been Separating Axis Theorem (SAT). SAT has several limitations, the biggest one being curved surfaces. The execution time of SAT also gets out of hand when a complex mesh has many faces.
In this section, we will discuss a different generic algorithm--the Gilbert Johnson Keerthi or GJK algorithm. GJK runs in near linear time, often outperforming SAT. However, it is difficult to achieve the stability SAT provides using GJK. GJK should be used to find intersection data with complex meshes that have many faces. The GJK algorithm needs a support function to work, and this support function is called Minkowski Sum.
For an algorithm to run in linear time, adding an iteration increases the execution time of the algorithm by the same amount every time, regardless of the size of the dataset. More information on runtimes is available online at https://en.wikipedia.org/wiki/Time_complexity.
The Minkowski Sum, also called Minkowski Addition, is an operation that we perform on two shapes; let's call them A and B. Given these input shapes, the result of the Minkowski Sum operation is a new shape that looks like shape A was swept along the surface of shape B. The following image demonstrates what this looks like:
We can describe this operation as every point in the Minkowski Sum is a point from shape A added to a point from shape B. We can express this with the following equation:
The preceding equation might be hard to read. The 
symbol means element of and the 
symbol means the direct sum of two groups. We are defining how to take the direct sum of two shapes that might not have the same number of vertices.
This means that we find the Minkowski Sum of two shapes by adding all the vertices of each shape together. If we take object B and reflect it around the origin, we effectively negate B:
We often refer to taking the Minkowski Sum of A + (–B) as the Minkowski Difference because it can be expressed as (A – B). The Minkowski Difference produces what is called a Configuration Space Object or CSO.
If two shapes intersect, their resulting CSO will contain the origin of the coordinate system (0, 0, 0). If the two objects do not intersect, the CSO will not contain the origin.
This property makes the Minkowski Sum a very useful tool for generic collision detection. The shape of each object does not matter; so long as the CSO of the objects contains the origin, we know that the objects intersect.
Taking the Minkowski Difference of two complex shapes can be rather time consuming. Checking whether the resulting CSO contains the origin can be time consuming as well. The Gilbert Johnson Keerthi, or GJK, algorithm addresses these issues. The most comprehensive coverage of GJK is presented by Casey Muratori, which is available on the Molly Rocket website at https://mollyrocket.com/849.
The GJK algorithm, like the SAT algorithm, only works with convex shapes. However, unlike the SAT, implementing GJK for curved shapes is fairly easy. Any shape can be used with GJK so long as the shape has a support function implemented. The support function for GJK finds a point along the CSO of two objects, given a direction. As we only need an object in a direction, there is no need to construct the full CSO using the Minkowski Difference.
GJK is a fast iterative method; in many cases, GJK will run in linear time. This means for many cases, GJK is faster than SAT. GJK works by creating a simplex and refining it iteratively. A simplex is the generalized notion of a triangle in any arbitrary dimensions. For example, in two dimensions, a simplex is a triangle. In three dimensions, a simplex is a tetrahedron and in four dimensions, a simplex is a five cell. A simplex in k-dimensions will always have k + 1 vertices:
Once the simplex produced by GJK contains the origin, we know that we have an intersection. If the support point used to refine the simplex is further from the origin than the previous closest point, no collision has happened. GJK can be implemented using the following nine steps:
Initialize the (empty) simplex.
Use some direction to find a support point on the CSO.
Add the support point to the simplex.
Find the closest point in the simplex to the origin.
If the closest point is the origin, return a collision.
Else, reduce the simplex so that it still contains the closest point.
Use the direction from the closest point to origin to find a new support point.
If the new support is further from origin than the closest point, return no collision.
Add the new support to the simplex and go to step 4.
The GJK algorithm is generic and fairly fast; it will tell us if two objects intersect. The information provided by GJK is enough to detect when objects intersect, but not enough to resolve that intersection. To resolve a collision, we need to know the collision normal, a contact point, and a penetration depth.
This additional data can be found using the Expanding Polytope Algorithm (EPA). A detailed discussion of the EPA algorithm is available on YouTube in the form of a video by Andrew at https://www.youtube.com/watch?v=6rgiPrzqt9w. Like the GJK, the EPA uses the Minkowski Difference as a support function.
The EPA algorithm takes the simplex produced by GJK as its input. The simplex is then expanded until a point on the edge of the CSO is hit. This point is the collision point. Half the distance from this point to the origin is the penetration depth. The normalized vector from origin to the contact point is the collision normal.
Using GJK and EPA together, we can get one point of contact for any two convex shapes. However, one point is not enough to resolve intersections in a stable manner. For example, a face to face collision between two cubes needs four contact points to be stable. We can fix this using an Arbiter, which will be discussed later in this chapter.
We can make several improvements to the stability of our physics engine. We fixed the problem of sinking using linear projection in Chapter 15, Manifolds and Impulses. Linear projection introduces its own flaws into our engine: jitter and object crawling. We used heavy friction to cover these issues up. Older physics engines had similar issues; they tended to use aggressive sleeping to cover these issues up. When a rigid body is asleep, it has no forces acting on it (including gravity) and therefore does not sink.
The more modern approach to fixing these issues is called Baumgarte Stabilization. Baumgarte Stabilization works by adding extra energy to physics resolution. This extra energy causes some jitter, but fixes the issues of sinking and crawling. We can add slop to the system, similarly to how we added slop to linear projections to fix the jitter issue.
Baumgarte Stabilization requires us to accumulate impulses over frames. In order to accumulate impulses, we need to keep track of collisions over several frames. This is where an Arbiter comes in. An arbiter can also be used to build up a collision manifest over several frames from the result of the GJK algorithm.
An arbiter is a data structure that keeps track of the contact points between two objects over several frames. It effectively contains almost the same data as a collision manifold. It needs to keep track of which objects are colliding, as well as the collision normal and depth of each collision point. They are built up over several frames, and the face-to-face collision of two boxes might look something like this:
To implement an arbiter system, we have to keep a list of active arbiters. For each frame we look for collisions between rigid bodies. If the colliding bodies do not have an arbiter in the list, we have to create a new arbiter for them and add it to the list. If the two objects have an arbiter in the list, we insert the contact point between the bodies into the list.
In each frame, we loop through every arbiter in the arbiter list. If an arbiter has more than four contact points, we need to take the furthest point and remove it from the arbiter. If any points are too far apart, we must remove those points from the arbiter. If an arbiter has no contact points left, we remove that arbiter from the list.
As an arbiter is built over several frames, it can be used with GJK and EPA to build a stable manifest over several frames. The GJK will produce a new contact in each frame, which will register with the arbiter system. After about four frames, any colliding objects should stabilize.
Using accumulated impulses will solve object crawling and help eliminate some jitter. The major advantage of using accumulated impulses is that the impulse of any single contact point can be negative. We still have to ensure that the total accumulated impulse of all the contact points is positive.
To implement accumulated impulses, we keep track of the sum of the impulses needed to resolve a collision in the arbiter. Then, once the impulse has been calculated for every contact point and summed up in the arbiter, we apply the impulse to the rigid body. Before applying the impulse, we need to ensure that the total impulse is positive. We just clamp the final impulse to zero if it is negative.
We briefly introduced springs in Chapter 16, Springs and Joints. We saw how we can use springs to create soft bodies like cloth. In this section, we will explore other uses of springs.
If we know the collision point, depth, and normal, we can use springs to resolve the collision. This method works by placing a temporary spring at the point of contact that will push objects apart in the direction of the contact normal. The spring should exert just enough force to push the two bodies apart.
The force that the spring exerts on the rigid bodies is called a penalty force. Due to this terminology, using springs to resolve collisions is often called penalty based collision resolution; the following image demonstrates this:
While this method can be used to create stable physics, finding the right k value for the springs often becomes a guessing game. Using the wrong k value can lead to excessive jitter and bouncy objects. Due to the difficulty in finding the right k value, penalty springs are rarely used in modern physics engines.
We created cloth using springs, and we can create other soft bodies using springs as well. For example, let's explore how we can use the same spring systems we used to build cloth to create a soft body cube. We start with eight points and the structural springs between them:
Next, we need to add shear springs to keep the object from collapsing. These springs look like an x on each face. The shear springs tend to keep the object somewhat rigid:
Finally, we need to add bend springs to keep the cube from folding over in its self. These bend springs look like x that cuts the cube diagonally in half:
With this configuration, eight particles are connected by twenty eight springs. This creates a soft body cube. If the springs are rigid, the cube acts like a rigid body. If the springs are loose, the cube acts like jello. We can use the same three spring systems to make other shapes, such as pyramids, into soft bodies.
One of the best ways to learn is to examine the existing technology. There are a large number of open source physics engines that we can study. I'm only listing open source engines, which means that closed source SDKs, such as Havok or PhysX, are left out of this list. Out of all the physics engines listed, you really need to go through the Box2D Lite source code.
This is, by far, the must-read physics engine! The project is small and easy to nagivate. The entire project consists of six .cpp and six .h files. Even though this is a 2D engine, it can easily be extended for 3D support. To download and have a look at Box2D Lite visit http://box2d.org/files/GDC2006/Box2D_Lite.zip
The most important thing about this engine is the arbiter implementation. Box2D Lite provides a full arbiter implementation. The engine uses a similar impulse solver to the one that we covered in this book; this makes the arbiter provided with Box2D Lite easy to use with our engine. There is a GDC presentation about the project available at http://box2d.org/files/GDC2006/GDC2006_Catto_Erin_PhysicsTutorial.ppt
Box2D is a 2D physics engine written in C++ that is developed by Erin Catto. Box2D powers some of the most popular 2D mobile games. This engine has been ported to many other languages, such as C#, Java, Java script, and Action script. It's worth reading through the source of Box2D Lite before getting into the advanced features of Box2D.
The dyn4j is a 2D collision detection and physics engine written in Java. The engine is robust and provides a feature set comparable to Box2D. What really sets this engine apart is the accompanying website. The dyn4j blog (http://www.dyn4j.org) provides clear and concise examples and tutorials for many advanced physics topics.
The Bullet physics engine is probably the most popular open source 3D physics engine out there. The engine implements many cutting-edge algorithms and techniques. Some of the more advanced features of the engine are hard to find documentation on; they are only described in academic papers. Bullet is large and feature rich, it is used in everything from games to robotics. http://bulletphysics.org/wordpress
The Open Dynamics Engine (ODE) is a high-performance physics library written in C++. ODE is an older engine, which receives infrequent updates. The source code for the engine is well written and easy to understand. ODE has been used to ship several AAA commercial games as well as robotics. http://www.ode.org
JigLib is an experimental physics engine that has a very clean, well-organized, and easy-to-follow source code. The engine has been ported to C#, Java, Java script, Action script, and other languages. The engine is stable; it runs well even on older hardware.
React3D is a C++ physics engine being developed by Daniel Chappuis. The source code of the engine is well organized, easy to follow and extremely well commented. The comments in the source code of this engine are better than some of the online tutorials. The engine is feature rich and runs very fast. http://www.reactphysics3d.com
The qu3e is a simple C++ physics engine being developed by Randy Gaul. The engine aims to strip a modern physics engine down to its minimal code. Only the cube primitive is supported, but many advanced features are implemented. The engine is a great example of the minimum code needed for modern physics simulation.https://github.com/RandyGaul/qu3e
Cyclone Physics is a 3D physics engine developed by Ian Millington for his book, Game Physics Engine Development. More information about the book is provided later in this chapter. https://github.com/idmillington/cyclone-physics
In general, books on modern game physics are hard to find. The technology and methods that are considered modern are constantly changing and evolving. This makes writing books for cutting edge physics simulation challenging. I want to provide a list of useful books that might cover additional topics. I will not provide a review of each book.
Most of these books cover overlapping topics. The basics of an impulse-based physics engine are the same; because of this, the books tend to cover similar topics. However, each of these books provides some unique details or algorithm that makes the book worth owning:
Physics Modeling for Game Programmers
Conger, D. (2004). Physics modeling for game programmers. Boston, MA: Thomson/Premier.
By David Cogner, ISBN-13: 978-1592000937
Physics for Game Developers
Bourg, D. M., & Bywalec, B. (2013). Physics for game developers. Sebastopol, CA: O'Reilly Media.
By David M Bourg and Bryan Bywalec, ISBN-13: 978-1449392512
Game Physics Engine Development
Millington, I. (2010). Game physics engine development: how to build a robust commercial-grade physics engine for your game. Burlington, MA: Morgan Kaufmann.
By Ian Millington, ISBN-13: 978-0123819765
Game Physics
Eberly, D. H. (2010). Game physics. Burlington, MA: Morgan Kaufmann/Elsevier.
By David H. Eberly, ISBN-13: 978-0123749031
Real-Time Collision Detection
Ericson, C. (2004). Real-time collision detection. San Francisco, CA: Elsevier.
By Christer Ericson, ISBN-13: 978-1558607323
Game Physics: A Practical Introduction
By Ben Kenwright, ISBN-13: 978-1471033971
In addition to open source physics engines and books, online resources are also a great place to research game physics. There are several blogs and publications available. I highly recommend publications from valve:
In addition to the mentioned blogs, there are several videos and presentations on various physics topics available on the GDC vault:
There is also a list of relevant GDC presentations hosted on the Box2D website at http://box2d.org/files.
Of course, everyone runs into issues writing code, and physics is an especially difficult topic. If you run into issues with your physics engine, you can always ask for help at the following Gamedev.net forum:
We covered a lot of ground in this book. I want to take a minute and reflect on all the topics we covered, and the learning that is still ahead.
Chapters 1, 2, and 3 covered the basics of Linear Algebra. Having this mathematical foundation is central to writing a physics engine!
Chapters 4, 5, and 6 covered what two-dimensional primitives are and how to detect intersections between them.
Chapters 8, 9, and 10 covered what three-dimensional primitives are and the most efficient way to determine intersections between them.
Chapters 11, 12, and 13 covered meshes, scenes, and scene organization. These skills become important as you construct larger and more elaborate scenes.
Finally, chapters 14, 15, and 16 covered physics. Throughout these three chapters, we built a very basic physics engine. Even though the engine is basic, we did some interesting things with it. We implemented particle physics, rigid body physics, and soft body physics (cloth), all in the same engine.
In the appendix, you were given several book and open source game engine references. Reading the source code of open source engines is very important. Topics covered in books and academic papers are often easier to understand when you can go through the code that is executing. I highly encourage for the first resource be reading through the Box2D Lite source code after reading this book.
© 2017 Packt Publishing Limited All Rights Reserved
