I really struggled to find good resources on collision detection and collision response so hopefully my post can serve as somewhat of a starting point if you want to implement your own collision system.
Collision object representation
When you render a game scene, almost all the objects are represented by a triangle meshes. They help provide fine-grained details that you see on the screen. However, they aren’t always the best candidates to represent objects in a collision algorithm due to performance implications. Even when they are used, there are strict requirements on what type of mesh they have to be; maybe they have to be convex or have a low polygon count for the algorithm to work well. It is much more common to use a simple primitive shape, such as a sphere or ellipsoid, to approximate complex geometry instead. However, it requires artists and game world editors to manually fit primitives onto meshes, which is a lot of hassle.
In my implementation, the player is approximated by an ellipsoid and the scene is represented by the same triangle mesh I use to draw it. That’s really convenient because player’s ellipsoid can be automatically generated by bounding the player’s mesh and the scene’s triangle mesh representation is already loaded into the game anyway. I don’t really have to do any manual work here, and that’s great.
Finding time of impact (TOI)
So let me present what the problem is first. Every frame, the player will move along a certain direction by a certain amount, let’s call it velocity vector. Our job here is to ensure no matter what, the player won’t be able to move through a solid wall, clip through terrain, or do any other weird stuff. In order to do that, we need to obtain the initial time of impact (TOI) along this velocity vector when our player first collides with the scene geometry. Let’s call this time TOI, and it has a range of [0, 1]. TOI is how much percentage of the velocity vector we are allowed to travel and not penetrate the environment, hence it’s normalized.
For example, say our player is walking up a staircase. In the illustration below, vector V is obviously too big and we can only travel a portion of it. TOI will be the how much of V we can travel, and TOI * V will be the adjusted vector.
How do we obtain TOI? We can iterate over each triangle in the triangle mesh and obtain their own respective TOI, then compare all of them to find the minimum TOI. That minimum TOI is the TOI with respect to the entire mesh. So if we have a way to find the TOI of a moving ellipsoid to a triangle, we can find the TOI of a moving ellipsoid to an entire triangle mesh.
Simplify the problem by change of basis
This problem could be a lot easier if we had a moving sphere instead. Well, we can easily scale all points and vectors in our collision space by a certain amount so that our original ellipsoid turns into a unit sphere. What that basically does is transforming all our geometry into a different basis where our ellipsoid is a unit sphere. Let’s call this new basis eSpace. Then, we can find TOI in eSpace, multiply TOI to the motion vector in eSpace, then transform the result vector back to default basis. We lost our TOI, but we have the correct motion vector instead. [Edit: We actually haven’t lost our TOI yet. TOI is the same in both basis since it’s a scaling factor]
In preparation for collision response
This is all good if we just have to detect the collision and stop our player from penetrating. But just doing that will result in player stuck in wall or a slope where they should be able to slide along them. This “sliding” process is called collision response. In order to handle it correctly, we need the intersection point of the collision in addition to the TOI. It will make sense when we get to the collision response part.
Moving (swept) unit sphere vs triangle collision detection
If a sphere were to intersect with the triangle along its way, then there are three ways they could intersect each other:
Sphere touches triangle’s plane and simultaneously touches the inside that triangle’s area
Sphere touches one of triangle’s vertices
Sphere touches one of triangle’s edges
In his paper, Fauerby called the first case “inside the triangle”, which I think is a very bad way to word it. If we count triangle’s vertices and edges as insides, then inclusively, all three cases are collision “inside the triangle”. Just want to emphasize it here for those who are going to read his paper.
These cases aren’t mutually exclusive. You can imagine a sphere first touches the inside of a triangle within the same plane, then sinks through it and touches its edge. One interesting observation is that if case 1 were to occur at all, it must occur before case 2 and case 3. Therefore, if case 1 happens, then we can assume it’s the minimal TOI and return. Testing case 2 and case 3 would be unnecessary at this point.
So how can we test them?
For case 1, we can construct a plane out of the triangle. Its normal can be computed by the cross product of its edges in its winding order, and project any of its vertices onto the normal to obtain the plane constant, i.e. distance from plane to origin. Having acquired our plane, we can test intersection by finding TOI when the distance between sphere’s center and the plane is exactly 1.
Here’s the derivation for TOI:
If TOI is within [0, 1], that means sphere collides with the plane. Let’s name the collision point CP. We can derive CP as follows:
After acquiring CP, we can test whether or not it’s within the triangle by using barycentric coordinate and cramer’s rule:
The test above does not always succeed. When plane is completely horizontal, the determinant used as denominator will be zero. In that case, different axis must be chosen to solve with cramer’s rule. As an alternative, you can also use the test in Fauerby’s paper, but he never explains how it works.
If CP is within the triangle, then we can early exit and say this is the TOI with respect to this certain triangle. If not, we must proceed to case 2 and case 3.
For case 2, you simply find TOI when sphere collides against a vertex and determine if it’s within [0, 1]. Again, collision occurs when the distance between sphere’s center and the vertex is sphere’s radius, which is 1. Derivation:
CP is just the vertex in this case.
For case 3, it’s really the same thing. You first find the TOI when sphere is 1 unit away from the infinite edge made up of any two vertices. Then, check if the collision point is between these two vertices, if so, then that TOI is valid. CP can be acquired by using that result to interpolate between the two vertices. Do it for all edges and pick the minimum. Case 3’s derivation follows the same procedure as case 2 but is substantially more work than case 2, and I’m pretty drained at this point, so solve it as an exercise :), or you can cheat by looking at Fauerby’s answers.
Repeat this procedure for all triangles inside the mesh, and we will obtain time of impact and the collision point if a collision occurs.
Collision response
Fauerby proposes a pretty good way to resolve collisions. His idea is project the remaining velocity onto the tangent plane that collision point makes on the unit sphere’s surface. Now, the procedure will recurse and use the new sliding vector as its new input. Recursion stops when input vector is too small or it reaches the recursion limit. It achieves smooth gliding even in extreme situations, such as climbing stairs.
First we acquire the normal of this tangent plane. It’s just the normalized vector from collision point to sphere’s center. Then we can use this normal to construct a reflecting vector by using the remaining velocity. Adding the reflecting vector to the remaining vector, we achieve the sliding vector.
Numerical Robustness
This algorithm is perfectly fine on paper. It ensures sphere never penetrates the triangle mesh and smoothly glide it along the mesh. However, if you implement the algorithm just like that, your character would still frequently get stuck and fall through the ground. Why?
The reason is because we cannot store numbers at infinite precisions on a computer. Floating point numbers only have limited precisions and gives imprecise results. If we apply an algorithm that pushes the sphere to exactly touches the triangle mesh at one single point, then the actual point stored in the computer might be too much into the mesh due to floating-point errors. If any penetration happens, then the algorithm fails.
Code that anticipates and mitigates this type of error is called numerically robust. In order to make my code numerically robust, I had to make some adjustments. I first pushed sphere to when it initially collides with the mesh, then pull it back by a tiny amount. This way, I would ensure that floating point error is handled by this tiny adjustment.
Results
I loaded in some extra asset just to test out the collision system. So far the collision system is handling them pretty well. Player nicely glide along edges and it doesn’t awkwardly get stuck on edgy surfaces.
However, the performance is terrible. When I load the entire scene into collision mesh, each frame took about 30-40ms to process, which is unacceptable given that Monter is expected to run at 120 FPS. (but in the video you will notice Monter runs smoothly. How I achieved that will be the topic of my next blog post)
Here’s a recording demonstrating the collision system:
