Point-Plane Collision Detection Explained

In my previous post I presented a function for detecting collision of a point in 3D space with a plane (surface of an object). It works well enough in my SkyCop demo because all I need to check is if the tip of the primary ship intersects the surface of other ships. Here's a description of the code, broken into seven steps to help you understand this basic form of collision detection.

1)	Understand the Plane Equation: Ax + By + Cz + D = 0
	The plane equation tells us that a point (x,y,z) is on a plane having normal vector (A,B,C) and distance D from the origin when Ax + By + Cz + D = 0. If we plug in A, B, C, D, x, y, z and get any value other than zero, the point (x,y,z) is not on the plane. Also note that since the dot product of vectors (A,B,C) and (x,y,z) equals Ax + By + Cz, we can rewrite the Plane Equation as DotProduct(N, P) + D = 0 for N=(A,B,C) and P=(x,y,z).
2)	Get the collision surface's normal vector.
	As noted above, in order to detect if a point is on our collision surface (such as a wall we want to prevent the player from running through), we need to know the normal vector perpendicular to the surface. A normal vector is computed by taking the cross product of two vectors on the plane. The simplest 2D plane we can create in 3D space is a triangle with three vertices (call them vP1, vP2, and vP3) and I will focus on a triangular collision surface for simplicity. We compute the normal vector by generating a vector from vP1 to vP2 and another from vP2 to vP3 and then take the cross product of those two vectors to obtain the normal vector. Finally, the normal vector is normalized (made to have a length of 1.0) to simplify calculations. vN1 = (vP2 - vP1); vN2 = (vP3 - vP2); D3DXVec3Cross(&vNormal, &vN1, &vN2); D3DXVec3Normalize(&vNormal, &vNormal);
3)	Get plane distance using the Plane Equation.
	Using our revision of the Plane Equation, DotProduct(N, P) + D = 0, we can solve for D to get D = -DotProduct(N, P). So we compute D by plugging in the normal vector and any point on the plane; any of the triangle surface's three vertices will suffice. d = - D3DXVec3Dot(&vP1, &vNormal);
4)	Classify the start and destination points.
	Now that we've determined the collision surface's normal vector and distance from the origin (A, B, C, and D) we can use the Plane Equation for something really cool: determining if a given point lies on the plane! When we plug a point P=(x,y,z) into the left side of our revised plane equation DotProduct(N, P) + D we get a result value, p. If p > 0, the point is in front of the plane. If p < 0, the point is behind the plane. And of course we know that if p = 0 the point lies on the plane. Since we're only concerned with detecting collisions for moving objects, there must be a start position where the object moved from (pstart) and a destination position (pdest) to which the object is moved. The trick is realizing that a collision only occurs if these two positions have different locations in relation to the plane -- if they're both in front of or both behind the plane, no collision occurred and we can return from the function. p = (D3DXVec3Dot(&vNormal, &pStart) + d); if ( p > 0.0f ) pStartLoc = PlaneFront; else if ( p < 0.0f ) pStartLoc = PlaneBack; else pStartLoc = OnPlane; p = (D3DXVec3Dot(&vNormal, &pDest) + d); if( p > 0.0f ) pDestLoc = PlaneFront; else if (p < 0.0f ) pDestLoc = PlaneBack; else pDestLoc = OnPlane; if (pStartLoc == pDestLoc) return false;
5)	Get the ray.
	At this point we know that an intersection did occur! Great, but there is a small problem; we don't know where it occurred, which is equally important. The plane that was crossed is an infinitely expanding plane in 3D space, often called a hyperplane, so we need to check if the collision occurred within the bounds of our collision surface's borders. Computing the vector, called a "ray", from our object's start position (pstart) to its destination position (pdest) helps determine where the collision occurred. The vector is normalized to simplify calculations. ray = pDest - pStart; D3DXVec3Normalize(&ray, &ray);
6)	Get the intersection point.
	Vector math tells us that we can access points along a ray from pstart to pdest using the formula (pstart + ray * t). Since we know that a point along our ray from pstart to pdest definitely intersects the plane, we use the plane equation to determine the value of t below. Note that I've plugged the intersection point (pstart + ray * t) into the Plane Equation instead of a generic (x,y,z) because we know that point lies on the plane. I've also renamed pstart to "s" and the ray to "r" for brevity. A(sx + rx*t) + B(sy + ry*t) + C(sz + rz*t) + D = 0 A*sx + A*rx*t + B*sy + B*ry*t + C*sz + C*rz*t + D = 0 DotProduct(N, s) + t*DotProduct(N, r) + D = 0 t = - (DotProduct(N, s) + D) / DotProduct(N, r) We've already computed the normal vector N=(A,B,C) as well as the plane distance D and the ray so we can calcuate t. Then we plug it into our formula to get the actual intersection point on the plane. t = - (d + D3DXVec3Dot(&vNormal, &pStart)) / D3DXVec3Dot(&vNormal, &ray); intersect = pStart + (ray * t);
7)	Determine if intersection hit the collision surface!
	We're almost there! We determined the intersection point where our object collided on a hyperplane corresponding to the collision surface. So the final question is, "Does the intersection point fall within the bounds of our collision surface?" In order to answer that question we compute vectors from the intersection point to the surface vertices and measure the angles between those vectors. If we form a complete circle, we know the point lies within the bounds of our collision surface! v1 = intersect - vP1; v2 = intersect - vP2; v3 = intersect - vP3; D3DXVec3Normalize(&v1, &v1); D3DXVec3Normalize(&v2, &v2); D3DXVec3Normalize(&v3, &v3); // Angles around intersection should total 360 degrees (2 PI) thetaSum = acos(D3DXVec3Dot(&v1, &v2)) + acos(D3DXVec3Dot(&v2, &v3)) + acos(D3DXVec3Dot(&v3, &v1)); if (fabs(thetaSum - (2 * D3DX_PI)) < 0.1) return true; else return false;

There are a couple caveats to this method of collision detection. The first is that the triangle surface vertices vP1-vP3 must be specified in clockwise order so the surface normal vector is computed correctly. We also have to allow for a small margin of error in the calculation of the sum of angles due to the lack of floating-point precision. Finally, I've read that this method should only be used on convex (as opposed to concave) polygons which do not curve inward on themselves.

I know this is very low-level and there are probably simpler ways to do it (bounding boxes/spheres come to mind...), but it's kinda neat to see how the math makes it work! Please feel free to post comments/questions to let me know what you think of this tutorial. I hope it provides a clearer understanding of what's going on under-the-hood in basic point-plane collision detection.