Collision Detection
scet_02_img0115.jpg

Learning Objectives

Create code that will detect and/or locate collisions of some basic mathematical objects.

Introduction

In many action games, collisions abound. The ability to mathematically detect these collisions quickly and accurately is of utmost importance. In this lab, we will investigate some of the simpler cases of colliding objects.

Mathematical detection of collisions requires mathematical descriptions of the objects. At this point, we will oversimplify, and work with objects that are mathematically elementary.

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:

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

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

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

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

Now add the two equations to get

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

(6)
\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.

Circles

The standard form of the equation of a circle is:

(7)
\begin{equation} (x-x_1)^2+(y-y_1)^2=r^2 \end{equation}

Similarly, the standard form of the equation of a sphere is:

(8)
\begin{equation} (x-x_1)^2+(y-y_1)^2+(z-z_1)^2=r^2 \end{equation}

To determine the overlap of two circles or sphere one simply needs to compare the distance between the two centers with the sum of the radii.

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 coordinates of two vertices of each box. In 2D, the vertices are:

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

(10)
\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.

Laboratory Procedures

I. Spheres.

A. Write code for a function that will determine if two spheres overlap, given the center and radius of each sphere.
B. Test your code with the following situations.

  1. center (2,7,6), radius 4; and center (8,1,2), radius 5
  2. center (–6,3,2), radius 10; and center (1,–1,6), radius 1
  3. center (4,5,7), radius 1; and center (3,6,2), radius 5

C. Execute the code for your instructor’s verification (initials) .
D. Print a copy of the code and attach it to your lab report.

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

A. Write code for a function that will determine if two axially aligned bounding boxes overlap, given 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 (initials) .
D. Print a copy of the code and attach it to your lab report.

III. Line Segments.

A. Write code for a function that will determine the intersection, if any, of two line segments given 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 (initials) .
D. Print a copy of the code and attach it to your lab report.

Postlab Questions

  1. What adjustments would you have to make to your program that detected overlap in spheres so it could handle circles in 2D?
  2. Would it be better to use AABB’s or spheres in collision detection? Why?
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License