# METHODS OF COLLIDING A SPHERE WITH A PLANE

### Two methods for colliding a plane and a sphere, as might be used in collision detection, with examples in JavaScript

There are multiple ways to collide a sphere with a plane, but I will discuss two approaches here.

Knowing one or both of these methods is useful for performing your own collision detection or physics systems, although there are also somewhat common applications in particle systems and pathfinding.

One method I will describe is rather complicated, but is more easily generalized into a collision of any shape on a plane, and can be bounded to certain points on the plane. The other is much simpler, but is only useful for either colliding a sphere with an infinite plane or for determining the distance from a plane to a point (which is actually the same operation as colliding a sphere with a plane, if you think about it).

I'll look at the more complex approach first, since it is the more general approach. The examples I will use are written in JavaScript, but most of the math is fairly straight forward and should be easily applied to other languages (for instance, I originally wrote this code in Java, and later translated it to both C and JavaScript).

Both approaches begin the same, with creating our definition of a plane.

To begin with, let's recall that the equation defining a plane is:

```A * X + B * Y + C * Z + D = 0
```

Where A, B, and C are the X, Y, and Z coordinates of a normal vector. That just means that if you move from 0, 0, 0 by A, B, C you will have moved either directly towards or directly away from the plane. In fact, if you moved by that amount exactly D times, you would be on the plane itself. This will be handy to keep in mind later, but not just yet.

Let's define a plane in this form starting with three points that lie on the plane. Take a three points to define the plane and determine the normal to the plane using these points.

For reference:
```function Point(x, y, z){
this.x = x;
this.y = y;
this.z = z;
}

function cross(a, b){ // This is the so-called Cross Product
let x = (a.y * b.z) - (a.z * b.y);
let y = (a.z * b.x) - (a.x * b.z);
let z = (a.x * b.y) - (a.y * b.x);
return new Point(x, y, z);
}

function subtract(a, b){
return new Point(a.x - b.x, a.y - b.y, a.z - b.z);
}

function normal(a, b, c){
let da =  subtract(a, c);
let db =  subtract(b, c);
return cross(da, db);
}
```

Then, determine the plane's D component which is the negative of the normal multiplied by one of the points.
That's just the plane equation solved for D, using one of the points as the X, Y, and Z.

```function multiply(a, b){
return new Point(a.x * b.x, a.y * b.y, a.z * b.z);
}

function plane_d(normal_cmp, point){
let d_vec = subtract(new Point(0, 0, 0), multiply(normal_cmp, point));
return d_vec.x + d_vec.y + d_vec.z;
}
```

So, to create a plane (we will want the normal vector to be normalized for later):
```function normalize(vec){
let m = Math.sqrt((vec.x * vec.x) + (vec.y * vec.y) + (vec.z * vec.z));
return new Point(vec.x/m, vec.y/m, vec.z/m);
}

function plane(a, b, c){
this.points = [a, b, c]; // It will be useful to know at least one point on the plane later.
this.normal = normalize(normal(a, b, c));
this.d = plane_d(this.normal, a);
}
```

Now comes the very difficult part, and the portion where the easy and complex methods actually diverge.

We need to multiply the inverse of a matrix composed on the lines and the plane's points with a difference matrix.

This could represented as:
```    Where the line is defined as points a and b, and the points on the plane as points 0, 1, 2:
[T]     [Xa - Xb, X1 - X0, X2 - X0]          [Xa - X0]
P [U] = ( [Ya - Yb, Y1 - Y0, Y2 - Y0] ^ -1 ) * [Ya - Y0]
[V]     [Za - Zb, Z1 - Z0, Z2 - Z0]          [Za - Z0]
```

There is a brief explanation of methods behind the inversion in the comments. Suffice it to say that matrix inversion is not very much fun to do by hand, and if you have a library which can do this for you no one would begrudge you using it.

```/* Accounting for inversion:
*   [ a b c ]          [ A D G ]          [  (ei-fh) -(bi-ch)  (bf-ce) ]
* P [ d e f ] = det(W) [ B E H ] = det(W) [ -(di-fg)  (ai-cg) -(af-cd) ]
*   [ g h i ]          [ C F I ]          [  (dh-eg) -(ab-bg)  (ae-bd) ]
* For the line of points A and B and the plane of points 0, 1, 2
*        [  (ei-fh) -(bi-ch)  (bf-ce) ] | [ (Xa-Xb) (X1-X0) (X2-X0) ]
* det(W) [ -(di-fg)  (ai-cg) -(af-cd) ] | [ (Ya-Yb) (Y1-Y0) (Y2-Y0) ] = W
*        [  (dh-eg) -(ab-bg)  (ae-bd) ] | [ (Za-Zb) (Z1-Z0) (Z2-Z0) ]
*
* det(W) = 1/(a * A + b * B + c * C)
* det(W) = 1/((Xa-Xb) * (ei-fh) + (X1-X0) * (ch-bi) + (X2-X0) * (bf-ce))
*                   [ Xa-X0 ]   [ T ]
* Thus, inverse J * [ Ya-Y0 ] = [ U ]
*                   [ Za-Z0 ]   [ V ]
* T is between 0 and 1 if the intersection is along the line.
* (U+V) <= 1 if the intersection is withing the three points.
*/

plane.prototype.collideSphereMatrixMethod = function(sphere){
line = {
};

let
a = line.x1 - line.x2, b = this.points[1].x - this.points[0].x, c = this.points[2].x - this.points[0].x,
d = line.y1 - line.y2, e = this.points[1].y - this.points[0].y, f = this.points[2].y - this.points[0].y,
g = line.z1 - line.z2, e = this.points[1].z - this.points[0].z, f = this.points[2].z - this.points[0].z;

// The commented out portions would only be useful if we wanted to determine if the intersection
//   was bound by the three input points.
let
A = ((e*i)-(f*h)), B = ((c*h)-(b*i)), C = ((b*f)-(c*e)),
D = ((f*g)-(d*i)), // E = ((a*i)-(c*g)), F = ((c*d)-(a*f)),
G = ((d*h)-(e*g)); // H = ((b*g)-(a*b)), I = ((a*e)-(b*d));
let Q = line.x1 - this.points[0].x, R = line.y1 - this.points[0].y, S = line.z1 - this.points[0].z;

// Inversion coefficient. Mismatched a*A, b*B, and c*C to match the final matrix rotation for inversion.
let det = 1 / ((a*A) + (b*D) + (c*G));
let T = ((A*Q)+(B*R)+(C*S)) * det;

// U and V are UV coordinates on the triangle along which we intersected. If you were ray-
//   tracing, for instance, this would be texture coordinates relative to the intersection.
// let U = (float)((D*R)+(E*S)+(F*T)) * det_a;
// let V = (float)((G*R)+(H*S)+(I*T)) * det_a;

// T is actually the T position along the line where the plane and the line intersect.
return T >= 0 && T <= 1;
}
```

That's the hard way. The very hard way, but there aren't a lot of ways that are particularly easier if you care about the UV coordinates. Fortunately, though, you usually will not need those.

Let's look at the easier way.

If the normal vector has been normalized (such that the length of a line going from 0, 0, 0 to the X, Y, Z of the normal is shrunk or extended to be of length 1) before D was calculated, then the D coordinate of the plane's equation is the distance from the point to the plane.

```plane.prototype.collideSphereFastMethod(sphere){
let point = multiply(sphere, this.normal);
let distance1 = point.x + point.y + point.z + this.d;