Collision Detection Part II
scet_02_img0115.jpg

Learning Objectives

Create code that will detect collisions of some basic mathematical objects.

Introduction

Previously we encapsulated our objects in circles (2D) and spheres (3D), now we will look at some other collision detection schemes. We can divide our collision detection schemes into two main categories. Methods that look for collisions at a particular point in time are called discrete detection methods, while those that check for collisions between two points in time are called continuous detection methods. Our circles and spheres were examples of discrete collision detection. We will add to that list Axially-Aligned Bounding Boxes (AABB), circle/line, and plane/sphere collision detection. We will also look at a continuous method that looks for collisions between two line segments in 2D.

Discrete Collision Detection

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:

(1)
\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:

(2)
\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

Previously, you modeled collision detection between two moving objects in 2D using circles, now we will look for 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.

(3)
\begin{align} \vec{S}=\vec{P}+\mbox{Proj}_{\vec{d}}\vec{PQ} \end{align}
(4)
\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.

(5)
\begin{align} \vec{S}=\vec{Q}-\mbox{Proj}_{\vec{n}}\vec{PQ} \end{align}
(6)
\begin{align} |\vec{QS}|\leq r \end{align}

Continuous Collision Detection

Lines

Lines (which can model the path of a bullet or ray) are one such type of object. The most remembered equation for a line is the slope-intercept form:

(7)
\begin{equation} y=mx+b \end{equation}

But the slope-intercept form does not work for lines which have an undefined slope. Another style of equation for a line is standard form:

(8)
\begin{equation} Ax+By=C \end{equation}

Every line does have an equation in this form, however, the equation will not be unique.

Finding the point of intersection of two lines is equivalent to finding the solution of a system of two equations in two variables. Let us find the point of intersection of two arbitrary lines given in standard form.

(9)
\begin{eqnarray} Ax+By&=&C\\ Dx+Ey&=&F\\ \end{eqnarray}

Now we will use the process of elimination to get rid of the variable y. Multiply the first equation by E and the second equation by -B

(10)
\begin{eqnarray} AEx+BEy&=&CE\\ -BDx-BEy&=&-BF\\ \end{eqnarray}

Now add the two equations to get

(11)
\begin{eqnarray} (AE-BD)x&=&CE-BF\\ x&=&\frac{CE-BF}{AE-BD}\\ \end{eqnarray}

If we repeat the process and eliminate x instead of y, we get

(12)
\begin{align} y=\frac{AF-CD}{AE-BD} \end{align}

Line Segments

For high-velocity objects like bullets, a collision may be missed between frames. A line segment may be used to join the positions of an object in two consecutive frames. The intersection of that line segment with the line segment of another object may indicate that there had been a collision between frames.
To determine the intersection of two line segments, simply find the point of intersection of the two corresponding lines and then determine if the point of intersection is contained in both segments.

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
  5. In 3D, the closest point on a plane from a given point

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

A. Write code for a function that will determine if two axially aligned bounding boxes overlap when a user provides two opposite vertices of each box.
B. Test your code with the following situations.

  1. vertices (2,5) and (4,7); and vertices (3,8) and (5,2)
  2. vertices (3,10) and (1,4); and vertices (5,1) and (10,3)
  3. vertices (3,7,8) and (9,2,10); and vertices (6,4,5) and (7,8,6)
  4. vertices (2,4,5) and (3,6,7); and vertices (3,5,2) and (6,6,5)

C. Execute the code for your instructor’s verification.

II. Line/Circle Collision

A. Write code that will determine if a circle is colliding with a line using a user-supplied center and radius for the circle and point and direction for the line.
B. For troubleshooting purposes, your code should output to the screen the closest point on the line as well as the distance between that point and the center of the circle.
C. Test your code with the following:

  1. Circle: Center (1,2) and Radius 5 / Line: Point (6,4) Direction: <1,-2>
  2. Circle: Center (-2,0) and Radius 3 / Line: Point (-4,-4) Direction: <2,1>

D. Execute the code for your instructor's verification.

III. Plane/Sphere Collision

A. Write code that will determine if a sphere is colliding with a plane using a user-supplied center and radius for the sphere and three points on the plane.
B. For troubleshooting purposes, your code should output to the screen the plane normal, the closest point on the plane, and the distance between that point and the center of the sphere.
C. Test your code with the following:

  1. Sphere: Center (7,4,4) and Radius 2 / Plane: Points (6,2,3), (-1,4,0), and (5,8,5)
  2. Sphere: Center (5,5,5) and Radius 3 / Plane: Points (2,0,-1), (4,1,6), and (8,-2,4)

D. Execute the code for your instructor's verification.

IV. Line Segments.

A. Write code for a function that will determine the intersection, if any, of two line segments when a user provides each of their endpoints.
B. Test your code with the following pairs of endpoints

  1. (3,2),(3,9) and (-1,6),(8,6)
  2. (-2,-5),(6,3) and (5,-5),(5,1)
  3. (-4,4),(4,-4) and (-8,-2),(10,1)
  4. (2,9),(4,6) and (3,2),(5,5)

C. Execute the code for your instructor’s verification.

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?
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License