- 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.
Today I watched a good conference talk about collision detection problem solving technique. Here you can read my words about the video, and if you want to watch it:
There are two types of collision detection; one is discrete and other 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?
As you can imagine, discrete collision detection is faster (cheaper) than continuous collision detection; but it “teleports” between each frames. Which means that this calculation is done “separately” in frames. Other faulty side of this application is that fast objects can tunnel through thin objects. Because -for example- you may not detect the moment of 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 same as translation in this approach.
In Titanfall 2, creators used similar approach like continuous detection in translation and discrete detection in rotation. They also did discrete test at 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 box of boxes.
We also should touch 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’s volume because flat boxes still has areas.
Simple idea of AABB Test is that you “cull” if line segment misses AABB. Our desired behavior is that there is no gap between two touching AABBs. You can think this as two walls touching each other: if there is a gap between them, you face problem when you shoot contact points of them. Let us try to show important points in the algorithm from Earl Hammon’s notes:
- 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.