Computing Distance

Learning Objectives

Create code that will compute the distance and squared-distance between two points, the in a 3D space.

Introduction

The shortest distance between two points is a straight line. Often, one will need the distance between two objects for various reasons in a game, whether it's to know the distance between the player's vehicle and a waypoint, or as a proximity check to see if an event should be triggered. Computing this distance is simple enough if you know the coordinates for the two points in question.

Distance in 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$. By applying this relationship a couple of times, our formula from 2D can be extended 3D. 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.

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

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);

As you will learn this semester, for the purposes of collision detection, we will need to compare distances. 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

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

Write code that will take the cartesian coordinates for two points in 3D.
Write a function that will calculate the distance between the two points.
Write a function that will return the squared distance between the two points.

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