﻿ Game Programming

Free JavaScript Editor     Ajax Editor ﻿

Main Page

### Distances

There are a number of distance-related computations, measures, and indices that can prove useful in your game programming.

#### Distance Between Two Points

The easiest way to compute the distance between two points is to use the Euclidean distance metric. Given P and Q in a 3D world, the distance is computed by:

Computing square roots can be costly. Moreover, in some cases (such as spatial sorting by distance), you will not need the distance itself, but just a way to measure objects according to their distance. In this case, you can override the square root and use the expression:

```distance_squared = (p.x–q.x)2+(p.y–q.y)2+(p.z–q.z)2
```

A third method is to use Manhattan distance metrics, which are defined as:

```distance_manhattan = abs(p.x–q.x)+abs(p.y-q.y)+abs(p.z-q.z)
```

Manhattan distances are the 0-level Euclidean norm, defined by the general expression:

Manhattan distances are used as very fast pseudodistances, especially to cull away distant objects. It is a very cheap test that can help us discard irrelevant primitives (both in terms of logic and presentation).

#### Distance Between Two Lines

Given two lines R and S in (origin, direction vector) form, we can compute the minimum distance between them easily. The lines have the following expression:

```R:
```

```S:
```

These are the parametric equations of the lines, and they are very easy to construct from game data structures. The distance between them is computed with the following:

This formula can be somehow sped up. For crossing lines, the numerator will always be zero, and thus we can save the division and modulo operations in the denominator.

#### Distance from a Point to a Line

The distance from a point P to a line in parametric form (defined by Org and Dir) can easily be computed with the following:

By storing a normalized direction vector, we can save the divide, thus speeding up the computation.

#### Distance from a Point to a Plane

Distance from a point P to a plane in 3D space can be computed easily using the normal distance to origin plane representation. A plane can be represented as:

```N.x*X+N.y*Y+N.z*Z+D=0
```

where N is the normal to the plane and D is the minimum distance from the plane to the origin. Assuming this representation, the distance is computed as follows:

As usual, keeping the plane's normal as a unit vector speeds the formula, so we can save the modulo and division in the denominator.

#### Distance Between Two Planes

Finding the distance between two planes is pretty straightforward:

1. Test if the two normal vectors are the same; if they are, the planes are parallel. If they are not, distance is 0 (they intersect).

2. Select a point in one of the planes.

3. Perform point-plane distance as shown earlier using that point and the opposite plane.

﻿

Ajax Editor     JavaScript Editor