Collision Detection And Resolution

Learning Objectives

• Create code that will detect collisions of some basic mathematical objects.
• Determine the velocity of an object after collision
• Define the terms momentum and impulse.
• Explain what the coefficient of restitution is and how it affects colliding objects.
• Compare the differences and similarities between elastic and inelastic collisions
• Implement the concepts of momentum and energy to model the collision between objects.

Introduction

Previously you created a simulation of motion using Forward Euler. Now we want to check for collisions after each update of position in our Forward Euler. We will check for a collision between two spheres, two circles, or two AABB's that are moving under constant velocity. We will also check for collision between a circle or sphere moving at constant velocity with a stationary boundary defined as a line or plane. In this case we will also resolve the new velocity after the collision.

Discrete Collision Detection

Circles and Spheres

It is very computationally efficient to check for collision between two circles in 2D or two spheres in 3D. We will already know the position of the two circles or spheres, call them $\vec{p_1}$ and $\vec{p_2}$. From this we can determine the distance between them by computing the magnitude of their difference.

(1)

\begin{align} |\vec{d} |= |\vec{p_2}-\vec{p_1}| \end{align}

The two circles or spheres will have pre-defined radii to ensure that their corresponding game objects are completely encapsulated. Let's call those $r_1$ and $r_2$. Two determine if they are colliding with one another we simply need to check if the sum of the radii is larger than the distance between the two positions.

(2)

\begin{align} |\vec{d}| < r_1+r_2 \implies \mbox{ Collision} \end{align}

As we know, that square root in the magnitude calculation is expensive, so we can square both sides to make an equivalent comparison.

(3)

\begin{align} |\vec{d}|^2 < \left ( r_1+r_2 \right ) ^2\implies \mbox{ Collision} \end{align}

Axially-Aligned Bounding Boxes

A box is also a standard computer graphics object, though it is handled somewhat differently in mathematics. For axially aligned boxes, either 2D or 3D, it is sufficient to know the coordinates of two diagonally opposite vertices of each box. In 2D, the vertices are:

(4)

\begin{align} \left ( x_{\mbox{min}},y_{\mbox{min}} \right ) , \left ( x_{\mbox{max}},y_{\mbox{max}} \right ) \end{align}

or in 3D, the vertices are:

(5)

\begin{align} \left ( x_{\mbox{min}},y_{\mbox{min}},z_{\mbox{min}} \right ) , \left ( x_{\mbox{max}},y_{\mbox{max}},z_{\mbox{max}} \right ) \end{align}

Two boxes will fail to overlap if the interval of just one coordinate from one box does not overlap with the interval of the corresponding coordinate from the other box. When looking to determine if two intervals overlap, one can think of the intervals as analogous to two spheres. The overlap can be determined by comparing the distance between the two centers to the sum of the radii of the two intervals. Alternatively, you could determine overlap in each variable via a series of inequalities of the maxes and mins.

Line/Circle Collision

Now we will look for a collision between a moving object enclosed in a circle and a static boundary represented by a line. We will have the center $\left ( x_c,y_c \right )$ and radius $r$ of the circle as well as a point $\left ( x_0 , y_0 \right )$ and direction $\vec{d} = <d_x, d_y >$ for the boundary line. We can then use our closest point formulas to determine if the distance to the point on the line closest to the circle is less than the radius of the circle or not.

(6)

\begin{align} \vec{S}=\vec{P}+\mbox{Proj}_{\vec{d}}\vec{PQ} \end{align}

(7)

\begin{align} |\vec{QS}| \leq r \end{align}

Plane/Sphere Collision

This scheme is similar to the line/circle collision detection method but in 3D. We are interested in determining if the sphere is in collision with a boundary plane. We will have the center $\left ( x_c,y_c ,z_c\right )$ and radius $r$ of the sphere as well as a point $\left ( x_0 , y_0 ,z_0\right )$ and normal $\vec{n} = <n_x, n_y,n_z >$ of the plane. We then use our closest point formula to determine if the distance to the closest point on the plane is less than the radius of the sphere or not.

(8)

\begin{align} \vec{S}=\vec{Q}-\mbox{Proj}_{\vec{n}}\vec{PQ} \end{align}

(9)

\begin{align} |\vec{QS}| = |\mbox{Proj}_{\vec{n}}\vec{PQ}| \leq r \end{align}

Continuous Collision Detection

It is possible for a fast-moving object to completely pass through another object between frames. To catch this you need to check for collision along the path that was formed from the previous position to the new position. In 2D this is done by looking for line-segment intersections and in 3D this is done by looking for capsule intersections. We will not be looking at continuous collision detection in this lab.

Resolving Collisions

Momentum is the measure of a body’s tendency to remain in motion. This quantity is proportional to both the mass and the velocity of the object. Mathematically, it is the product of the mass and the velocity.

(10)

\begin{align} \vec p = m \vec v \end{align}

Notice that this is a vector equation! In this way, momentum is different from kinetic energy, which is a scalar. When Newton wrote his 2nd Law of motion, he was really meaning something more general than $\vec F = m \vec a$. Here’s a excerpt from Newton’s famous book Philosophiae Naturalis Principia Mathematica where Newton describes his 2nd Law of Motion:

“The alteration of motion is ever proportional to the motive force impressed; and is made in the direction of the right line in which that force is impressed.”

We can use this notion of momentum to rewrite our previous notion of Newton’s 2nd Law as

(11)

\begin{align} \vec F = \frac { \Delta \vec p } { \Delta t } \end{align}

When two objects collide, momentum may be transferred from one to the other. The total momentum of the system, however, will always remain the same. If one object loses momentum, the other object must gain momentum. Furthermore, the amount that one loses and the other gains must be equal. This is the foundation for the Conservation of Linear Momentum. This conservation law states that the total momentum of a system before a collision must equal the total momentum of a system afterwords. In the language of algebra, this is

(12)

\begin{equation} m_1 v_{1i} + m_2 v_{2i} = m_1 v_{1f} + m_2 v_{2f} . \end{equation}

There are two different types of collisions, elastic and inelastic. The most important difference between the two is that elastic collisions conserve kinetic energy. Elastic collisions involve two objects that collide and bounce off of each other while retaining their original shapes. No physical collision between two objects is ever exactly elastic, but two billiard balls colliding would be a great approximation of an elastic collision. Inelastic collisions involve a change in the system's total kinetic energy. With most physical collisions, the kinetic energy is used to deform the two object, create sound waves, and increase the temperature of the two object. An example of this type of collision would be the collision between a two pieces of putty or an automobile accident. Part of the system’s original kinetic energies used to deform the shape of the objects, generate sound, or to increase the temperature of the two objects. A perfectly inelastic collision is a special case in which the two colliding bodies stick together after the collision. They then move off as a single unit with the same velocity. Mathematically, this means the final velocities in Eq.(12) are equal and the equation can be rewritten as

(13)

\begin{align} m_1 v_{1i} + m_2 v_{2i} = \left( m_1 + m_2 \right) v_{f} . \end{align}

Real collisions are typically somewhere between the two cases of a perfectly elastic and perfectly elastic collision. The degree to which the collision is elastic can be described by the coefficient of restitution, $\varepsilon$. For a perfectly elastic collision, the total amount of kinetic energy is conserved. In a real collision, some of this kinetic energy is lost. By using the conservation of momentum and kinetic energy for an elastic collision, one can derive what’s called the Velocity Equation

(14)

\begin{equation} v_{2f} - v_{1f} = v_{1i} - v_{2i} . \end{equation}

When the collision is not precisely elastic, the right side of Eq.(14) is multiplied by coefficient of restitution. If $\varepsilon = 1$, the collision is perfectly elastic. If $\varepsilon = 0$, the collision is perfectly inelastic.

(15)

\begin{align} v_{2f} - v_{1f} = \varepsilon \left( v_{1i} - v_{2i} \right) . \end{align}

This means that one can use the same equation for both elastic and inelastic collisions, and therefore the same function block. You won’t need two separate routines by using the coefficient of restitution.
So far, only one-dimensional collisions have been detailed, but multi-dimensional collisions are simply a superposition of the two or three orthogonal directions. Eqs. (12) and (15) can be used to evaluate the final velocities in the x, y, and z directions separately. So long as the components of the initial velocities are known, finding the three-dimensional final velocities is simply a matter of applying Eqs. (12) and (15) three times, once for each direction.

	Elastic	Inelastic
Momentum	$\vec{p_i} = \vec{p_f}$	$\vec{p_i} = \vec{p_f}$
Kinetic Energy	${KE_i} = {KE_f}$	${KE_i} \neq {KE_f}$
Coefficient of Restitution	$\varepsilon = 1$	$\varepsilon \neq 1$

One special type of collision is the reflection. Imagine a billiard ball colliding with a rail and bouncing off. Figure 1 shows a diagram of this type of collision. Here we assume the mass of the rail is vastly greater than the mass of the ball. In the case of the rail being aligned with a coordinate axis, as is shown in Figure 1, then Eq. (15) in the direction perpendicular to the rail becomes

(16)

\begin{align} v_{1i} = - \varepsilon \cdot v_{1f} \end{align}

The parallel velocity will remain the same. This is a special case. The surface with which an object collides is not always going to be aligned with a coordinate axis. To address the more general problem of an object bouncing off of a surface with any given orientation, we will need to do some more geometry, see Figure 2. As with the ball-rail problem, the component of the velocity parallel to the surface remains unchanged, while the velocity perpendicular to the surface is inverted as described in Eq. (16). Using this notion of parallel and perpendicular velocities, we can write the initial and final velocities as such,

(17)

\begin{align} \vec v_{i} = \left( \begin{array}{cc} v_{\parallel} \\ v_{\perp} \end{array} \right) , \end{align}

and

(18)

\begin{align} \vec v_{f} = \left( \begin{array}{cc} v_{\parallel} \\ - \varepsilon \cdot v_{\perp} \end{array} \right) . \end{align}

The change in velocity, given the above, is

(19)

\begin{align} \Delta \vec v = \vec v_{f} - \vec v_{i} = \left( \begin{array}{cc} 0 \\ - \left( \varepsilon + 1 \right) \cdot v_{\perp} \end{array} \right) , \end{align}

such that

(20)

\begin{align} \vec v_f = \vec v_i + \Delta \vec v \end{align}

The more general case of Eqs. (19) and (20) involve using the normal vector to the surface to find the perpendicular projection of the initial velocity vector.

(21)

\begin{align} \vec v_{\perp} = Proj_{\hat n} \vec v_i \end{align}

(22)

\begin{align} \vec v_{\perp} = \left( \frac {\left( \vec v_i \cdot \hat n \right)} { \left| \hat n \right| ^2} \right) \hat n \end{align}

However, since $\hat n$ is a unit vector, its magnitude is exactly one. This means we can simplify the above equation.

(23)

\begin{align} \vec v_{\perp} = \left( \vec v_i \cdot \hat n \right) \hat n \end{align}

The general form of Equation 10 now becomes

(24)

\begin{align} \vec v_f = \vec v_i - \left( \varepsilon + 1 \right) \left( \vec v_i \cdot \hat n \right) \hat n \end{align}

where $\hat n$ is the unit vector normal to the surface. This equation will work for either the 2D or 3D case since it’s only the perpendicular velocity that is changing.

Laboratory Procedures

I. Extending the Vector3D class

A. Add the following methods to your Vector3D class to help with the line/circle and plane/sphere collision detection

1. parallel projection
2. perpendicular projection
3. cross product of two vectors
4. In 2D, the closest point on a line from a given point. (Involves three vectors: Point on the line, Direction of the line, Point off the line)
5. In 3D, the closest point on a plane from a given point (Involves three vectors: Point on the plane, Normal for the plane, Point off the plane)

II. Circles and Spheres

A. Write code for a method that will determine if two circles have collided based on their current positions and their radii.
B. Write code for a method that will determine if two spheres have collided based on their current positions and their radii.

III. Axially-Aligned Boxes (2D and 3D).

A. Write code for a method that will determine if two 2D axially-aligned bounding boxes have collided based on their current positions and their extent in the $x$ and $y$ dimensions.
B. Write code for a method that will determine if two 3D axially-aligned bounding boxes have collided based on their current positions and their extent in the $x$, $y$, and $z$ dimensions.

IV. Line/Circle & Plane/Sphere Collision

A. Write code for a method that will determine if a circle is colliding with a line based on the position and radius of the circle and a point and direction defining the line.
B. Write code for a method that will determine if a sphere is colliding with a plane based on the position and radius of the sphere and a point and normal defining the plane.

V. Collision Resolution

A. Write code for a method that when a collision is detected between a circle and a line returns the new velocity of the circle after the collision.
B. Write code for a method that when a collision is detected between a sphere and a plane returns the new velocity of the sphere after the collision.

VI. Simulation with Detection and Resolution

A. Ask the user which type of collision detection will be implemented.

1. AABB in 3D
2. Sphere and Sphere
3. Circle and Line
4. Sphere and Plane

B. Ask the user for the appropriate parameters for the simulation

1. AABB(3D)
   1. Initial position of both boxes.
   2. The extent of each box in each dimension.
   3. Initial velocity of both boxes.
2. Two Spheres
   1. Initial position of both objects
   2. Radii of both spheres
   3. Initial velocity of both objects
3. Line/Circle
   1. Initial position of the circle
   2. Radius of the circle
   3. Initial velocity of the circle
   4. Direction of the line
   5. Point on the line
   6. Coefficient of Restitution of the collision
4. Plane/Sphere
   1. Initial position of the sphere
   2. Radius of the sphere
   3. Initial velocity of the sphere
   4. Three noncolinear points on the plane
   5. Coefficient of Restitution of the collision

C. Propogate the motion of the objects using the Forward Euler Method

1. Output positions of moving objects to the screen at each timestep.

D. Check for collision

1. Output a statement to the screen if a collision is detected.

E. Resolve the Collision

1. In the case of line/circle and plane/sphere collision, output the velocity of the object after the collision.

F. Demonstrate the execution of your code to your instructor

Postlab Questions

1. Would it be better to use AABB’s or spheres in collision detection? Why?
2. Imagine a scenario where a 2D game is using a mixture of AABBs and circles. If you wanted to check for a collision between an AABB and a circle, how might you go about that?
3. The code produced to resolve collisions between a sphere and a plane is applicable to the collision of two spheres in 3D space as well. When two spheres collide, the two centers of the spheres define a line of action. The final velocities along the line of action can be found using the same method used in Procedure 3, and the velocities perpendicular to the line of action remain unchanged. Describe a qualitative method for defining the line of action, and finding the parallel and perpendicular velocities for two spheres colliding in 3D space.
4. Explain the behavior of two objects when they collide with a coefficient of restitution greater than one.
5. If the coefficient of restitution is less than one, then kinetic energy is lost. Energy cannot be created nor destroyed, though, so where does this lost kinetic energy go?