Continuous Collision Detection

Exploring a basic implementation of continuous collision detection using circles.
Figure 1 - An object tunnels through another object with no collision detected (top). CCD is used to detect the collision (bottom).

Continuous collision detection (CCD) is a method of detecting collisions between objects by considering the path of an object's movement within a given time and comparing that path, rather than the object's position at certain steps, to the position or path of other objects.

A common problem encountered by other collision detection methods is the object tunnelling problem (Figure 1), also commonly referred to as the "bullet through paper" problem. This problem occurs in methods such as discrete collision detection - a method that moves an object to a new position and then checks that position for overlaps. If the acting object's movement is too large, or the blocking object is too small (imagine a bullet moving toward a piece of paper), then the acting object could skip past, or tunnel through, the blocking object without triggering a collision. This can become a problem in many games and simulations.

CCD presents a solution to the object tunnelling problem by projecting the path of the acting object and checking that path for collision. If the projected path overlaps another object, then a collision will occur when the acting object moves. The entire continuum between the start and end points is checked instead of discrete positions; hence the name continuous collision detection.

Detecting a Collision

Detecting a collision by projecting an object's path can be complicated, as rotation of the object must be taken into account. That being outside of the scope of this article, circles will be used as the acting and blocking objects. This keeps the math relatively simple, as it eliminates the need to take rotation into account.

In order to derive an algorithm for collision detection, consider the following variables:

Using these variables, let's determine the conditions under which a collision will occur:

Let's explore each condition individually.

Condition 1: Is $C_1$ moving toward $C_2$?

Figure 2 - An object at $p_1$ moves toward an object at $p_2$. The red section represents when $θ \lt 90°$.

The value that needs to be found is the value of the angle $θ$ between $v$ and $u$, the vector pointing from $p_1$ to $p_2$. If $θ \lt 90°$, then $p_1$ is roughly moving toward $p_2$. If $θ \gt 90°$, then $p_1$ is moving away from $p_2$. Knowing this, the condition can be rephrased to the following: is $θ \lt 90°$?

Finding the value of $θ$ can be done in a number of ways, but an effective method is to use the dot product of vectors $u$ and $v$. The dot product of two vectors can be defined as follows:

$u \cdot v = u_x v_x + u_y v_y = ||v|| \ ||u|| \ cos(θ)$

The exact value of $θ$ could be found by solving for it using the above definition. However, the exact value of $θ$ does not need to be known. Instead, all that needs to be known is whether or not $θ \lt 90°$. The $cos(θ)$ in the latter definition of dot product helps to determine this; because $||v||$ and $||u||$ are always positive, $cos(θ)$ controls the sign of the dot product. When $θ \gt 90°$, the value of $cos(θ)$ is negative, which means that $u \cdot v$ is also negative. When $θ \lt 90°$, the value of $cos(θ)$ is positive, which means that $u \cdot v$ is also positive.

This provides the solution to condition 1: if $u_x v_x + u_y v_y \gt 0$, then $p_1$ is moving toward $p_2$.

Condition 2: Is $C_2$ in the path of $C_1$?

Figure 3 - The red area represents the potential path of the object at $p_2$.

The value that needs to be determined is the perpendicular distance from $p_2$ to the line described by $v$. This is represented by the vector $u_2$ (Figure 3). If $||u_2|| \lt r_1 + r_2$, then $C_2$ is in the path of $C_1$. To find this value, vector projection, and subsequently vector rejection, can be used.

The projection of $u$ onto $v$ is represented by $u_1$. Vector projection can be defined as follows:

$u_1 = \frac {u \cdot v}{||v||^2} v$

The rejection of $u$ from $v$ is represented by $u_2$. Vector rejection can be defined as follows:

$u_2 = u - \frac {u \cdot v}{||v||^2} v = u - u_1$

With that, the solution to condition 2 is as follows: if $||u_2|| \lt r_1 + r_2$, then $p_2$ is in the path of $p_1$.

Condition 3: Is the distance from $C_1$ to the point of collision less than the $||v||$?

Figure 4 - .

Reusing the variables defined in the previous conditions, the following variables are known:

The value that needs to be found is the magnitude of vector $v_f$, the final velocity vector that will put $p_1$ at the point of collision with $p_2$. To find this, the value of $b$ needs to be determined, as $v_f$ can be defined as follows:

$v_f = \frac {||u_1|| - b} {||v||} v \ \longrightarrow \ ||v_f|| = ||u_1|| - b$

Since $u_1$ and $v$ are already known, all that needs to be found is $b$. Due to the triangle described by $a$, $b$, and $c$ being a right triangle, the Pythagorean theorem can be used:

$a^2 + b^2 = c^2 \ \longrightarrow \ b = \sqrt{c^2 - a^2}$

Substituting in their values, the value of $b$ can be rewritten as follows:

$b = \sqrt{(r_1 + r_2)^2 - ||u_2||^2}$

Now that the value of $b$ is known, the magnitude of $v_f$ is also known, which leads to the solution to condition 3: if $||v_f|| \le ||v||$, then a collision has occurred. The point of collision can then be found by adding $v_f$ to $p_1$

Implementation in JavaScript

For this particular algorithm, I will use Javascript and assume we have a class Vec2 that describes a two-dimensional vector.

First, let's define a class that will represent our objects.



            
Next, let's define a class that will represent a collision.


            


            
Finally, let's use these to create our algorithm for CCD.


            


            
            
Example