Collision Detection Part I

Learning Objectives

Create code that will determine whether two objects enveloped in circles in 2D or spheres in 3D are colliding.

Introduction

In order to determine if two objects are colliding, there are several approaches that can be taken depending on the dimensionality of the game and the shape of the object. These approaches all forgo the immense task of checking for collision between the actual area or volume of the object by looking for the collision of some enveloping regular geometric shape. In this case, you will be using a circle in 2D and a sphere in 3D to envelope two objects.

Distance in 2 and 3 Dimensions

From algebra, you may remember that the distance between any two points can be determined by using the Pythagorean Theorem, $a^2 + b^2 = c^2$. In two dimensions this leads directly to the distance equation,

(1)

\begin{align} d=\sqrt{(x_2-x_1)^2+(y_2-y_1)^2} \end{align}

By applying this relationship a couple of times, our formula from 2D can be extended to 3D resulting in the formula,

(2)

\begin{align} d=\sqrt{(x_2-x_1)^2+(y_2-y_1)^2+(z_2-z_1)^2} \end{align}

One may wish to have separate 2D and 3D tools for calculating distance, but for our purposes here, we can simply apply the 3D formula in either case by simply setting $z = 0$ for the 2D case.

As we will see often throughout this course, the fastest way to code up a process isn't always the fastest way for the code to execute. Since our objective is to produce smooth motion in a gaming environment where new data and a new frame must be generated every 1/120th of a second, we will need to think carefully about what computational steps we are asking the CPU to perform. For example, let's take a look at a very straightforward way in which we can encode the above distance formula,

double Distance = sqrt(pow(((x2-x1),2) + pow((y2-y1),2) + pow((z2-z1),2));

It's a single line that does the job simply and elegantly, right? Well, let's take a look at exactly what is happening when we call the pow(argument, exponent) function. Take a look at the source code of the actual pow.c function here: http://www.open64.net/doc/db/d6e/pow_8c-source.html. Seems mightily complex for the simple task of taking a number times itself, doesn't it? If you need to raise a number to an arbitrary fractional power, this function is quite useful, but it's definitely overkill for simply squaring a value. Why use pow(x,2) when simply using x*x will work just as well and work significantly faster? So let's take another stab at our distance formula.

double Distance = sqrt((x2-x1)*(x2-x1) + (y2-y1)*(y2-y1) + (z2-z1)*(z2-z1));

This takes a bit longer to write, but it executes a lot faster! There's still some more efficiency we can find, though, if we look carefully. Notice that we're repeating the same calculation of (x2-x1) twice, and the same for the y and z coordinates. It will take just a little bit more memory, but it will eliminate a lot of computational repetition if we define the differences as a new variable and use that in our distance calculation.

double dx = x2 - x1;
double dy = y2 - y1;
double dz = z2 - z1;
double Distance = sqrt(dx*dx + dy*dy + dz*dz);

Lastly, we can think about how much memory we're using. By default, most people define floating-point numbers as double-precision, and where this is fine if you actually need fifteen significant figures, in a game environment this is rarely the case. The seven digits of precision in a single-precision float is good enough and uses half the memory, four bytes instead of eight, to store the data. Since the sqrt function takes double-precision values by default, we can force a single-precision implementation by using the sqrtf function. Since by now you should be very familiar with the Unity3D game engine, you will note that by default it uses floats, not doubles, for this very reason.

float dx = x2 - x1;
float dy = y2 - y1;
float dz = z2 - z1;
float Distance = sqrtf(dx*dx + dy*dy + dz*dz);

Collision Detection

We can use these distance calculations in a collision detection method using circles in 2D and spheres in 3D. We can determine whether they have collided or not by comparing the distance between their centers to the sum of their radii.

(3)

\begin{align} D<R_1+R_2 \implies \mbox{Collision} \end{align}

In a game with $n$ moving objects the number of collision checks that need to be done is on the order of $n^2$. Luckily knowing the relationship between two distances-squared tells us the relationship between the distances themselves. That is to say

(4)

\begin{align} D_1^2>D_2^2 \implies D_1 > D_2 \end{align}

By computing the distance-squared, we avoid two expensive square root calculations.

float dx = x2 - x1;
float dy = y2 - y1;
float dz = z2 - z1;
float DistanceSquared = dx*dx + dy*dy + dz*dz;

Now we have two nice bits of code that are miserly in both their use of memory and of CPU time. There are additional savings that can be found in writing a custom sqrtf, but those methods are beyond what we will be doing in this class. For now, this is good enough. If you're interested in these faster but less precise, methods of calculating roots, you can find a nice discussion here, http://www.codeproject.com/

Laboratory Procedures

1. Write code that will take the cartesian coordinates for the center of two circles in 2D or two spheres in 3D along with their radii.
2. Write a function that will calculate the distance squared between the two centers and display it to the screen.
3. Write a function that will determine if the circles or spheres are colliding and output the conclusion to the screen

Postlab Questions

1. What precautions if any should be taken when working with the square root function?
2. What is the advantage of having a distance squared function?