Heim kommt man nie. Aber wo befreundete Wege zusammenlaufen, da sieht die ganze Welt für eine Stunde wie Heimat aus.

– Hermann Hesse, Demian

The Intersection Problem

In this tutorial, we want to improve on the collision detection algorithm used in the Kicker-demo from previous tutorials. The issue can easily be restated as a line, or segment, intersection problem: As an object moves with a certain velocity, the velocity vector, with origin at the current position of the moving object, leads the way to wherever the object is going to.

Once we know that two line segments actually intersect, computing the intersection point is as trivial as solving a system of two linear equations. The hard part is to determine whether two line segments actually intersect, as segments are finite, thus, while the lines they run along on might intersect, the actual segments might not, as shown in the next figure:

Parametric Representation

To facilitate working with line segments, we will use the parametric representation of lines and segments. Basically, you can imagine a segment as the way between two points. Let be the start of a segment and the vector joining the point to its designated end point, also called a direction vector, think of your home and a grocery store, for example, then, at the time you are at home and at the time you are at the grocery store. For all values in between, you are en route to the store. In formulas, this idea looks as follows:

basically defines an offset, i.e. where the segment starts, away from the centre of the coordinate system, and encodes how far we have to run along a given direction vector. Refer to this GeoGebra applet by Tim Brzezinski to see a parametric representation in action.

Intersection

To figure out whether two segments and , with and are intersecting each other, it is enough to solve the equation and check whether and are both between and :

In matrix notation, this reads as follows: , where , with , , and .

Colinearity

Now if and are linearly dependent, there is no need to test for intersection if and aren’t already on the same line. It is thus enough to check whether lies on or vice versa, which means that it is enough to check whether there exists a such that , i.e. it is enough to check whether the directional vector between the two points and is collinear with the vector .

If the determinant of the matrix is not zero, then the vectors can’t be collinear. If the determinant is zero, all that is left to do is to check whether there exists such a between and .

Linear Independence

Now if the two directional vectors are linearly independent, the matrix is regular and the above matrix equation can easily be solved by computing the inverse of the matrix :

Example

Let , , and , as depicted in the figure below:

In this example, we have and . The inverse of is

thus

Plugging into the equation of , we get

as desired, which tells us that if we run three quarters of the length of the segment from to its end point, we intersect the other segment .

Implementation

To define line segments in C++, we use a small class:

Both constructors compute the directional vector and the first constructor computes the normal vector (clockwise) as well:

The recomputeDirectionalVector method is used to get the direction vector from the centre of a ball to the edge of its radius:

Note the negative sign in the normalization of the vector. This is due to the base change between standard coordinates and screen coordinates.

The actual test for intersecting between two segments follows the mathematics explained above:

And all of this greatly simplifies the collision detection test of the Kicker-demo:

While these new ideas greatly improved on the previous algorithms, this is far from being the entire story. In a later series of tutorials about Computational Geometry, we will explore topics such as this in greater mathematical detail.

References

Geogebra

Tricks of the Windows Programming Gurus, by A. LaMothe