- There are more collision detection algorithms than continuous and discrete
- Bad sides of discrete collision detection
- There is a good data structure called AABB Tree for collision detection.
Update from Future!
I created this post from GDC talk; then shared it in one of my other blogs. Then I thought that this blog’s purpose is more suitable for this post. Therefore, I publish this post here with humble modifications and addons! If you want to read more of my posts about technical stuff related to games, don’t forget to check the Technical Spot of Games Category.
Today I watched a good conference talk about a technique of collision detection algorithm. Here you can read my words about the video, and if you want to watch it:
Dynamic collision detection is a problem using so many resources of computers. Therefore optimized collision detection should be achieved. Whether it is dynamic or discrete detection, game engine developers should be aware of its importance and cost.
Types of Collision Detection
There are two types of collision detection; one is discrete and another one is continuous. Discrete collision detection is simple: are they intersecting right now? Imagine that you do this in every frame. However continuous collision detection is a bit harder: When did two objects first hit each other?
Cheaper or Accurate Detection? Which To Choose?
As you can imagine, discrete collision detection is faster (cheaper) than continuous collision detection; but it “teleports” between each frame. This means that this calculation is done “separately” in different frames. Another faulty side of this application is that fast objects can tunnel through thin objects. Because -for example- you may not detect the moment of the intersection if the object is before the wall in frame 58 and after the wall in frame 59. Because of that, it ignores in-between states; rotation is also the same as translation in this approach.
What About Titanfall 2?
In Titanfall 2, creators used a similar approach like continuous detection in translation and discrete detection in rotation. They also did a discrete test at the initial position. However, with their different new algorithm, they managed to double their performance. They used AABB Tree Collision Detection. This tree can be thought as a box of boxes.
We also should touch on the point of SAH (Surface Area Heuristic). This is assuming of probability that a ray hits a box (surface area). This approach is better than using box volume because flat boxes still have areas.
What is AABB Test?
The simple idea of the AABB Test is that you “cull” if the line segment misses AABB. Our desired behavior is that there is no gap between two touching AABBs. You can think of this as two walls touching each other: if there is a gap between them, you face a problem when you shoot contact points of them.
Final Notes of The Optimized Collision Detection Algorithm Used in Titanfall 2
Let us try to show important points in the algorithm from Earl Hammon’s notes:
- You Find when AABB around swept capsule first hits the plane for each node AABB face.
- Find enter and leave times for each axis independently.
- Find latest time we enter any existing AABB plane (tMin), and the earliest time we leave any existing AABB plane (tMax).
- If we enter before we leave, we hit the box; if we leave before entering, we miss the box.