Intersections And Collision Detection

Intersections

Finding intersections of lines and more specifically line segments can be part of a collision detection scheme. Imagine a collision between one very fast moving object as a bullet and another object say a target. In the span of one cycle of the game loop, the bullet may have moved from being on one side of the target to the other. If we do not check for the intersection of their paths from one time step to the next it may be possible for the bullet to pass completely through the target without detection. This would be bad.

Intersection of Two Lines in Standard Form

The intersection of two lines is the point that lies on the graph of both lines. Algebraically, it is the ordered pair $(x,y)$ that is a solution to both equations. So let us start with the equations of two arbitrary lines in standard form.

(1)

\begin{eqnarray} Ax+By=C\\ Dx+Ey=F\\ \end{eqnarray}

There are several techniques from Algebra for solving such a system. We will use elimination. First, we will eliminate the variable x, by multiplying the first equation by D and the second equation by -A. That gives us the following

(2)

\begin{eqnarray} ADx+BDy=CD\\ -ADx-AEy=-AF\\ \end{eqnarray}

Now add the two equations together,

(3)

\begin{equation} (BD-AE)y=(CD-AF) \end{equation}

And finally, dividing we get,

(4)

\begin{align} y=\frac{CD-AF}{BD-AE} \end{align}

Some of you may recognize this as the result of Cramer's Rule. Using the same process to eliminate y instead of x, we get

(5)

\begin{align} x=\frac{BF-CE}{BD-AE} \end{align}

Notice that we have the possibility of dividing by zero, in the case where $BD-AE=0$. This indicates that the lines are parallel and distinct and therefore do not intersect or that the two equations are for the same line. To determine which of these two cases has occured, one needs to examine the numerators of the two fractions. The details of which will be left for an exercise.

Intersection of Two Line Segments

If we do find that the lines intersect, we are not finished. The path of each object has a beginning and ending point at each step of the game loop, so we need to model this using line segments not lines. So once we have our point of intersection, we need to determine if it occurs within the bounds of our line segment.

Example
Determine if the line segment from (-1,1) to (3,3) intersects the line segment from (1,-2) to (2,5).

Solution

First we need the equation of the two lines in standard form.
Starting with the point slope equation of a line
$y-y_1=\frac{y_2-y_1}{x_2-x_1}(x-x_1)$
$(x_2-x_1)(y-y_1)=(y_2-y_1)(x-x_1)$
$(x_2-x_1)y-(x_2-x_1)y_1=(y_2-y_1)x-(y_2-y_1)x_1$
$(y_1-y_2)x+(x_2-x_1)y=(x_2-x_1)y_1+(y_1-y_2)x_1$
So our equations are:
$(1-3)x+(3+1)y=(3+1)1+(1-3)(-1)$ or simplified $-2x+4y=6$
$(-2-5)x+(2-1)y=(2-1)(-2)+(-2-5)1$ or simplified $-7x+1y=-9$
Which has solution:
$x=\frac{(4)(-9)-(6)(1)}{(4)(-7)-(-2)(1)}=\frac{-42}{-26}=\frac{21}{13}$
$y=\frac{(6)(-7)-(-2)(-9)}{(4)(-7)-(-2)(1)}=\frac{-60}{-26}=\frac{30}{13}$
Now we need to see if that point of intersection is within the bounds of our line segments.
$-1 \leq \frac{21}{13} \leq 3$ and $1 \leq \frac{21}{13} \leq 2$
$1 \leq \frac{30}{13} \leq 3$ and $-2\leq \frac{30}{13}\leq 5$
So indeed the two line segments intersect.

Intersections of Circles and Spheres

For the purposes of collision detection, it is computationally efficient to think of objects as being enveloped by a circle in the 2D case or by a sphere in the 3D case. Then collision detection becomes a matter of detecting when two circles or spheres have intersected. We will define both of these objects algebraically and then look at how to determine if two circles or spheres have intersected one another.

The image below shows two circles that are not overlapping. In terms of collision detection. These two objects have not collided.

Notice that the sum of the two radii is less than the distance between the two centers. If we call the distance between centers d, we have the conditions,

(6)

\begin{eqnarray} r_1+r_2<d& \mbox{ No Collision}\\ r_1+r_2 \geq d& \mbox{ Collision} \end{eqnarray}

Example
Determine if the circle with center (2.-3) and radius 5 intersects with the circle with center (4,5) and radius 2.

Solution

First we need the distance between the two centers:
$d=\sqrt{ (2-4)^2+(-3-5)^2}=\sqrt{4+64}=\sqrt{68} \approx 8.25$
Now we add the radii
$r_1 + r_2 = 5+2 = 7$
So our circles do not intersect because $d \approx 8.25 > 7 = r_1 + r_2$

Intersection of Axially Aligned Bounding Boxes

An axially aligned bounding box is a rectangle in 2D that has its sides parallel to the coordinate axes or a rectangular solid in 3D that has its sides parallel to the major planes of the coordinate system. The images below illustrate one of each.

In collision detection, the idea is to enclose an object with an AABB and then detect when the boxes overlap. Often an AABB can give a tighter envelope around the object then a circle or sphere, but an AABB detection algorithm is not as fast.
In order for two AABB's to overlap, the interval of x-values, y-values and in the 3D case the z-values for the two AABB's must all overlap. For the detection of overlap for intervals, the interval can be thought of as a 1D analog of a circle. Every interval has a center and a radius and two intervals overlap if $r_1+r_2 \geq d$.

Example
Determine if the AABB with extreme points (-1,-3) and (3,5) intersects the AABB with extreme points (2,-4) and (8,10).

Solution

In order to see if the range of x and y values overlap, we can treat them as a 1D analog of the sphere and just compare distance between centers to sum of radii.
Box 1:
For the first box we have $-1 \leq x \leq 3$ and $-2 \leq y \leq 6$
For the first box x interval we have a center of $C_{x1} = \frac{-1+3}{2} = 1$
For the first box x interval we have a radius of $r_{x1} = \frac{1}{2}\sqrt{ (-1-3)^2} =2$
For the first box y interval we have a center of $C_{y1} = \frac{-3+5}{2} = 1$
For the first box y interval we have a radius of $r_{y1} = \frac{1}{2}\sqrt{ (-3-5)^2} =4$
Box 2:
For the second box we have $2 \leq x \leq 8$ and $-4 \leq y \leq 10$
For the second box x interval we have a center of $C_{x2} = \frac{2+8}{2} = 5$
For the second box x interval we have a radius of $r_{x2} = \frac{1}{2}\sqrt{ (2-8)^2} =3$
For the second box y interval we have a center of $C_{y2} = \frac{-4+10}{2} = 3$
For the second box y interval we have a radius of $r_{y2} = \frac{1}{2}\sqrt{ (-4-10)^2} =7$
Now we check for overlap in the x intervals of the two boxes:
$d_x=\sqrt{(C_{x1}-C_{x2})^2}= \sqrt{(1-5)^2}=4$
$r_{x1}+r_{x2}=2+3=5$
Since 4<5, we do have overlap in the x intervals.
Now we check for overlap in the y intervals of the two boxes:
$d_y= \sqrt{(C_{y1}-C_{y2})^2}=\sqrt{(1-3)^2}=2$
$r_{y1}+r_{y2}=4+7=11$
Since 2<11, we do have overlap in the y intervals.
Conclusion:
Since we have overlap in both the x and y intervals, the two AABB are overlapping.

Exercises

1. Do $(x-4)^2+(y-3)^2=17$ and $(x+2)^2+(y-5)^2=33$ overlap?
2. Do $(x+2)^2+(y+5)^2+(z-1)^2=5$ and $(x-9)^2+y^2+(z+3)^2=7$overlap?
3. Find the point of intersection, if there is one, of the lines $2x+3y=8$ and $x-y=-1$.
4. Find the point of intersection, if there is one, of the lines $x+4y=6$ and $3x+12y=18$.
5. Find the point of intersection, if there is one, of the lines $2x-5y=1$ and $-4x+10y=-6$.
6. Does the line segment with endpoints (-2,-8) and (-4,0) intersect the line segment with endpoints (2,3) and (-3,-3)?
7. Does the line segment with endpoints (3,4) and (6,1) intersect the line segment with endpoints (1,-2) and (6,4)?
8. One AABB has extreme points (2, 5, 7) and (4, 9, 8). A second AABB has extreme points (–1, 5, 4) and (3, 6, 8). Do the boxes overlap?
9. One AABB has extreme points (-3, 1) and (5,-2). A second AABB has extreme points (8, 3) and (4,5). Do the boxes overlap?