The different protocols you might go through when figuring out how precise you want your collision detection.

Space-Coherent Data Structures

Quad-Tree

The basic idea of a quad-tree is we make a tree, where each node has up to four children, thereby subdividing space into quads as needed.

A quad tree is good for static spatial structures. We use it in collision detection, to store our collision boxes, since lookup in a range takes 𝒪(log n) time. We can create the tree once for static collision boxes, taking 𝒪(nlog n) time, however for the dynamic collision boxes, we have to recreate the tree for each update. This still gives a speedup from brute force of 𝒪(n²) to 𝒪(n⋅log n) for a collision check.

Collision Detection

Intervals

A start and end value. The following is the algorithm to determin overlap of two intervals a, b: $$ \begin{array} ~\qquad~~~ (a_{start} \leq b_{start} \quad \land \quad b_{start} \leq a_{end}) \newline \strut \quad \lor \ \ \ (a_{start} \leq b_{end} \quad \ \land \quad b_{end} \leq a_{end}) \newline \strut \quad \lor \ \ \ (a_{start} \leq b_{start} \quad \land \quad b_{end} \leq a_{end}) \newline \strut \quad \lor \ \ \ (b_{start} \leq a_{start} \quad \land \quad a_{end} \leq b_{end}) \end{array} $$

The four cases can be visualized as

If we generalize these intervals to two dimensional squares, we get the 16 cases

This is also sometimes called axis-aligned bounding boxes (AABB), since all collisions checks are for squares that are axis aligned.

Problem with AABB

The issue with AABB is when we introduce rotation, or non-square collision polygons, since we get false positives, where the bounding box says there is a collision, without there being an actual collision, see for an example.

Separating Axis Theorem (SAT)

The idea in the separating axis theorem, is that we handle collision by looking for overlap in (collision) in each dimension (of a selected basis, normally just axis aligned), and only if there is a collision in all dimensions, we get an actual collision.

Problems with SAT

The problem with SAT is that we might choose a bad axis to check for separation, meaning we will end up with a collision, where there should be none, see for an example. An alternative solution is to use each axis of one of the polygons as the basis, which will always find the separating axis, if it exists. However this increases the complexity of computing collision, since we now increment the collision time drastically, based on the complexity of the collision polygon.

With non-axis aligned projections

Using this alternative solution, with projecting onto each edge, we can see that there is no collision.

$$ \begin{array}{l} ae \leftarrow |x_1| \\ be \leftarrow |x_2| \\ a \leftarrow (x_1[i], y_1[i]) \\ b \leftarrow (x_2[i], y_2[i]) \\ a_{edges} = \mathtt{GetEdges}~(a) \\ a_{interval} = \mathtt{GetProjectedIntervals}~(~\mathtt{NormalVector}(a_{edges}[i])~,~a~) \\ b_{interval} = \mathtt{GetProjectedIntervals}~(~\mathtt{NormalVector}(a_{edges}[i])~,~b~) \\ \textbf{If}~{\textbf{not}~(a_{interval}[i].\mathtt{overlap}(b_{interval}[i]))} \\ \{ \textbf{Return}~\textbf{false} \} ~\\ \{ \textbf{Return}~\textbf{true} \} \end{array} $$

Minowski Difference

We can compute the Minowski difference between two convex polygons, by taking all points of the first polygon, and subtract all points of the other.

We can see that we can take the bounding area before or after the calculation without effecting the result. Meaning we can prune points by doing it before. We can now test for collision by checking whether the origin (0,0) is inside of the Minowski difference polygon. We can see it will not be the case by looking at the plot, however to be precise we try to calculate the smallest simplex containing the origin. We start by defining guessing on a support vector, here v₀ = ⟨ − 1, 0⟩. An iteration is then defining the inversion m_vk =  − v_k, we then find the point that is most in that direction h_pv and that is least in that direction h_qv, meaning most in the opposite direction. We then compute the difference w_k = h_pv − h_qv.

We then add the vector w_k to a list for each iteration, and then calculate the best simplex. In this example it is simply w_k with weight λ_wk = 1.0, since it is the only element in the list, meaning v₁ = w₀. We then compute the next h_qv, h_pv and w_k.

We then compute λ for w₁ and w₂. We call it with s₁ = w₂ and s₂ = w₁, we start by finding the coordinate with the largest distance: $$ \begin{align*} t &= s_2 - s_1 \\ p_O &= s_2 - \mathtt{proj}_{s_2}(t) \\[3mm] % 3.5, 3.5 % \mu^i &= s_2^i - s_1^i \\ \mu_{\mathtt{max}} &= \mu^I & \text{where}~|\mu^I| = \max_{i \in \{x,y,z\}} |\mu^i| \\[3mm] % 4.25 % M &= \begin{pmatrix} s_1^I & s_2^I \\ 1 & 1 \end{pmatrix} \\ P_O &= \begin{pmatrix} p_O^I \\ 1 \end{pmatrix} \\ % 3.5, 1 % C_1 &= det(M[1 = P_0]) \\ C_2 &= det(M[2 = P_0]) % C_1 = 1.75 % C_2 = -6 \end{align*} $$ If C₁ and C₂ have the same sign as μ_max =  − det(M), then we set $$\lambda_j = \frac{C_j}{\mu_{\mathtt{max}}}$$ and W = {s₁, s₂} otherwise we set λ₁ = 1, W = s₁. For our example we get the last case meaning the next iteration is v₂ = ⟨ − 2.5,  − 0.3⟩:

Gilbert - Johnson - Keerthi (GJK) distance

• https://en.wikipedia.org/wiki/Gilbert–Johnson–Keerthi_distance_algorithm
• https://en.wikipedia.org/wiki/Minkowski_Portal_Refinement

Real-time collision detection

We want collision detection, which does not just reject movement, but actually finds the correct position where a collision is initiated, and works from there, even if that is between two time steps. To do this we split our collision into a couple of phases:

• Proximity phase: Is there a possibility of a collision (close proximity)
• Broad phase: Is there even any collision
• Narrow phase: Check for collision with higher resolution, and find collision time
• Execution phase: Sort the collision events based on collision time, and handle one-by-one, updating collision events based on changes.

Proximity Phase

See Space-Coherent Data Structures. We also exclude all collision checks that we do not deem to be relevant, based on the collision categories, e.g. a player does not collide with his own weapons, or static terrain does not collide with different static terrain.

Broad Phase

Broad phase is done with AABB collision check, through time. What we do is take the bounding box, and see where it starts and ends for a time interval, giving us two structures that overestimate the positions occupied in the current collision check, meaning if these do not collide, then we are sure no collisions will occur. An example can be seen in .

Narrow Phase

In the narrow phase we use GJK / the Minowski difference to compute a distance function between the two polygons, which if we find all minimums will give us collision times. However we do binary search to find the collision point, since we do not want to compute this function, only a couple of values.

Execution Phase

In the execution phase, we sort all collision events based on collision time, so we can update based on a collision, and handle any new collision that might occur from that, by updating all relevant collision structures as we go. We then send the collision information to the agents, which do what they need to for that specific collision event / type.