Sphere Intersecting a Polygon

It had become clear that being able to detect the collision of a sphere with a polygon was an important concept in terms of 3D graphics. Many Collisions are optimized by the use of a sphere or some other similar object to represent one of the colliding objects. This simplifies calculations greatly. Now to learn how!

Firstly, for a simple test case of this concept, I used a simple triangle and a wireframe sphere drawn using glut. The wireframe makes it easier to see any intersections.

The previous posts documented methods for checking for different forms of collision. These techniques can be used for the sphere intersection and modified if necessary. In order to check for the sphere intersecting with the polygon, three checks were necessary:

1. Check if the sphere lies completely outside the plane formed by the polygon
2. Check whether the projection of the centre of the sphere onto the plane formed by the polygon lies within bounds of the polygon itself.
3. If the projection of the centre of the sphere does not lay inside the polygon, check that the sphere does not intersect with the edges of the polygon.

Performing these checks is enough to determine if the sphere intersects with the triangle.

1. Check if the sphere lies out the plane formed by the polygon


If the sphere has a radius of 1 metre and the centre of the sphere is 100 metres away from the plane formed by the polygon, it is obvious that no collision can occur. To determine whether this is the case, we use a technique I described in an earlier post. Firstly we calculate the distance that the centre of the sphere lies from the plane by utilising the plane equation.

We then make one minor change to see if the sphere is intersecting the plane. If the distance of the sphere centre from the plane is less than that of the sphere's radius then we have an intersecting. For this reason, we take the absolute value of the distance (as the sphere can be either in front of or behind the plane) and compare it with the sphere radius. If it is smaller, we continue onto step 2 otherwise there is no collision and we can return false.

2. Projection of Sphere lies inside polygon

If the sphere does indeed intersect the plane, we need to perform more checks. We first need to find whether the point at which the sphere intersects with the plane is within the bounds of the polygon or not. How do we determine the point at which the sphere intersects the plane? Well if the sphere is indeed intersecting the plane, the number of points on the plane it intersects with is infinite. For this reason, we project the sphere's centre onto the plane as whether it lies within the polygon.

To do this, we use the distance that the sphere's centre lies from the plane, which we calculated in step 1. We then multiply this by the normal of the plane. Remember that geometrically speaking, by multiplying a vector by a scalar, we are moving along the vector by a distance determined by the scalar. Since we start at the plane and move along the normal a distance equal to the distance of the sphere from the plane, we obtain a vector that represents the offset of the sphere's centre from the plane.

Because this vector goes from the plane to the centre of the sphere, we subtract this vector from the sphere's centre vector to obtain a new vector that goes from the sphere centre to a point on the plane. This is the projection of the sphere's centre onto the plane and serves as our intersection point on the plane.

This technique is illustrated above. We know from test 1 that the sphere is intersecting the plane so we want to find whether the centre of the sphere is inside the bounds of the polygon. The normal of the plane N is multiplied by the distance of the sphere centre from the plane to obtain the offset vector N * d. We can then subtract this vector from the sphere's centre to obtain the same vector in the opposite direction, finding the intersection point with the plane, i.

Now that we know the sphere centre's intersection point with the plane, we need to know whether that point is inside or outside of the polygon. If outside, there is no collision and we must proceed to step 3. In order to determine whether the point is inside the polygon, we use the same trick as before, constructing vectors between the intersection point and the polygon's vertices and summing up the interior angles. If equal to 360 degrees, the point is inside the polygon and we can return true for the collision, otherwise it is outside. I discussed this technique in more detail in the previous post.

3. Detecting Sphere-Edge Collisions

So, we know that the sphere intersects the plane but that the projection of the centre of the sphere onto the plane lies outside the polygon. Surely there is no collision? Well actually, there remains one case where the sphere could still be colliding with the polygon. Take a look at the figure below.

Here we can see that the sphere intersects the polygon and yet our previous test would have found the intersection point of the sphere centre and the plane to be outside of the polygon and would have ruled that no collision would have occurred. For this reason, we need to perform a final test checking for collisions with the edges of the polygon.

In order to do this, we construct vectors between each pair of vertices, starting with the most bottom-left vertex and proceeding in a clockwise fashion. For each vector we find the point on the vector that is closest to the sphere's centre and check the distance between them. If the distance is less than the sphere's radius, the sphere must be intersecting the polygon and we can return a true collision.

How do we find the closest point on the edge vector to the sphere's centre? The following technique does just that.

Firstly, we construct the edge vector by subtracting the current vertex from the next vertex in the polygon. This provides us with a vector representing an edge of the polygon. We also normalize this vector as we only care about its direction, not its magnitude for reasons I'll explain soon. We then construct a vector from the current vertex to the sphere centre by subtracting the current vertex coordinates from the sphere's centre coordinates. This is what we now have:

The distance along the edge vector E of the closest point on the edge vector to the sphere's centre (c) is found by performing a dot product operation using the two vectors we just created. This is cd. Why is this? Well, remember that geometrically, the dot product means this:

That is, the dot product is equal to the product of the magnitudes of both vectors multiplied by the cosine of the angle between them. By performing a dot product between E and P we obtain the following:

However, remember that we normalized the edge vector, meaning that it's magnitude is 1, so it drops out of the equation, leaving:

Remembering simple trigonometry and observing that the P vector and the distance to the closest point on the edge vector forms a triangle, we can see that the dot product will give us cd since the hypotenuse of the triangle multiplied by the cosine of the angle gives us the adjacent edge, i.e. cd.

Now that we have the distance along the edge vector to the closest point, we can find the coordinates of the closest point on the edge by taking the coordinates of the current vertex of the edge and adding on the the edge vector multiplied by the distance to the closest point.

Now that we know the closest point on the edge to the sphere's centre, we simply use the euclidean distance formula to find the distance between the two points (d in the diagram). 

we then compare this with the radius of the sphere and if it is smaller, we must be colliding. If the distance is greater, there is no collision and we move on to check the next edge in the polygon. 

By performing these 3 checks, we are able to fully determine if a sphere is intersecting with an arbitrary convex polygon.