Engine Work: Collision Wrap-up

Chen  —  1 month, 3 weeks ago [Edited 0 minutes later]
Hey guys, sorry for the inactivity. I have been making steady progress on Monter over the past couple of months, but couldn’t find any time to do a writeup about it. I try to make these writeups as high quality as possible, so I was reluctant to publish any article that just glosses over the details. And now I finally have the time to do another writeup on Monter. There’s a lot of stuff to cover, such as the new grass system, terrain system, and water shader. But for this post, let’s first wrap up the collision system that I promised months ago.

I’ve covered the theory of GJK in the last post, but there are a couple of implementation details that’s worth noting.

Optimizing GJK: support function

Recall that, in each iteration of GJK, we must need something called a support function. The support function’s job is to find the vertex that’s the furthest along the search direction. We could implement it with a simple linear search, but that means O(N) at each iteration of GJK. Although GJK is promised to take a low number of iteration before converging given our circumstances, we can do better than O(N).

A heuristic called Hill Climbing can be applied here. If we first store an adjacency list for each vertex, then we can start at a random vertex of the mesh, then slowly “climb” towards the extreme point by comparing with only its neighbors. This is significantly faster than a linear search, especially on big meshes.

However, Hill Climbing can get stuck at local maximas and be unable to reach the global maxima. In the context of implementing a support function, a local maxima can occur if there is a vertex with neighbors that are coplanar. However, this also means that there are unnecessary vertex in the geometry representation. Imagine if you take that problematic vertex out, would it change anything in the context of GJK? No it does not.

Therefore, it’s clear that a traditional 3D mesh representation is probably not the best candidates for GJK testing. Instead, you want a convex hull of the 3D mesh; only the points enough to enclose your geometry. If you can construct a minimal convex hull without any redundant vertex, then you don’t have to worry about the local maxima problem for our hill climbing support function, and searching will also be a lot faster.

Optimizing GJK: initial search direction

Recall that in GJK, a initial search direction must be seeded to start the entire algorithm. You could seed it with a random direction, but a good guess often means you instantly reject most collision pairings that are obviously not possible.

A good initial guess is simply a difference vector between the two objects’ centers. GJK will usually terminate after the first iteration with false if the objects are clearly separate.

Better yet, at each time GJK determines that the two objects are not colliding, you cache the last search direction. Then in the following frame, you use that as the initial guess. It would also cause GJK to terminate earlier if the two objects are indeed separate.

Optimizing the collision: error margin in bisection method

Recall in Monter’s collision system, bisection method is applied to find the legal interval of movement of the player. In order to achieve an accurate result, many iterations of the bisection method must be applied, somewhere around 35 tests. However, we could loosen up the error margin and only run a couple of iterations in the bisection method. This works surprisingly well if the test is conservatively picking the safest interval. The error margin is almost unnoticeable, but is significantly faster in comparison.


Ok, this wraps up the GJK section. Let’s move on to the terrain collision.

Terrain representation

The terrain system went through a lot of revisions, particularly because it has to interact with multiple components in the game engine. It has to interact with collision stuff, it also has to be easily modifiable by the world editor, and the grass system need to efficiently query the terrain heights to plant grass faster.

In the end, I picked a heightmap representation, storing the height of the terrain in a 2D array. A mesh can be easily constructed from this representation to render the terrain, and the heights at any point could also be efficiently queried with just a simple memory read.

Terrain collision

A desirable characstic of any terrain is continuity. When we play games, we all want a smooth terrain, so that when the characters walk on it, they won’t jitter like crazy or get stuck randomly. However, 2D heightmap is fundamentally discretized. Directly sampling it means jittered movements due to its discretized nature.


A continuous terrain translated into finitely many cells (heightmap)

However, we can try our best to reconstruct the smoothness using bilinear interpolation. By interpolating the four corners in some way, we can reconstruct a plausible smooth surface and use that to respond to terrain height queries. The following are two nice illustrations that I took from book of shader that demonstrates this technique:


Linear interpolation that reconstructs terrain’s continuity in value, but not its first derivatives (C0 continuity)


Cubic interpolation that not only reconstructs terrain’s continuity in value, but also its first derivatives (C1 continuity)

Although they are not perfect reconstructions, they are good enough to give the smoothness of the terrain.

With the above system, we can now query the height at any point within the heightmap. We can then use that to easily ensure the player is always above the ground. And that is the terrain collision system in a nutshell.

Reacting to collision: projected velocity

If you walk on a flat surface, then your can move just fine. But if you are climbing onto a steep ramp, then part of your movement contributes to lifting you up in height, and only the other part of it allows you to move towards the target direction.

This demonstrates that if your collision with other objects is not head-on, then only part of your movement will be absorbed by the collision. Essentially, when your movement is partially blocked by something, you can break it down into two parts. One part of the movement is completely negated due to collision, and the other part remain unaffected by the collision. In order to properly react to collisions, the system must be able to calculate what’s the part of the movement that remains unaffected.

Turned out, to compute this ratio, we need something called the contact normal. It’s the normal of the collision plane, which is a plane that completely separates the two colliding objects that prevents them from overlapping.

In the case with GJK, we already have a way of obtaining the contact normal. As for terrain, we could approximate it using central differences. Now, assume the height of the terrain is along Y axis, and the procedure is as follows. First, we take a close neighbor point that also lies on the terrain along the X axis, then we do the same for Z axis. We can take the differences between these two points and the center point to construct a tangent plane. The normal will just be their cross product.

Once we’ve obtained the contact normal, we can then project the movement onto the tangent plane. This way we eliminated the component of the movement that is directly opposing the contact force and leave the other component untouched.

By putting this in effect, we can simulate things like gliding and climbing a ramp, which is more realistic than just making the player stuck whenever he touches anything.
Log in to comment