For those of you who are unaware of the dot product, it’s a quick little operation that can find how close any two vectors (direction + magnitude) are in pointing in the same direction. Assuming the vectors’ lengths are both 1, if they are pointing in the exact same direction, their dot product will result in 1. A dot product of opposite-facing vectors will return a -1. Finally, if two vectors are perpendicular, their dot product will give back a 0.
So, while on my quest to find out how to do proper collision detection and response, I was given a link (http://www.blackpawn.com/texts/pointinpoly/default.html) that explained the concept that any edge of a convex object divides the world in two halves: one in which the entire object lies, and one in which it… doesn’t.
If that’s the case, I figured that if I use the dot product between any point relative to the edge and a vector perpendicular to the edge facing outward (a normal), I can determine in which half of the world the point lies. We do this by comparing the dot product’s result to zero; if it’s less than zero, it’s on the side with the object, and if it’s greater than zero, it isn’t.
If the point is on the side that the object lies, it could be colliding with it. To determine if it really is, we simply do this check on all the other edges. If they all indicate that the point is on the side the object is on, that means the point is inside the object. We have collision!
Now comes the trickier part. Once I had detected the point had collided, I had to figure out how I wanted to respond to that collision. One way that came to mind was to find out which edge the point is closest to and push it outward until it’s touching that edge.
So, how do we find what the closest edge is? Well, I figured that since we used the dot product to find which side of the edge the point was on, I could use it again to compare how close it was to the edge itself. The edge is perpendicular to the normal, so whichever edge’s dot product with the point is closest to 0 will be the edge the point is closest to.
Finally, I wanted to push the point out in the direction of the edge’s normal until it was on edge. Once again, I turned to my trusty dusty dot product for inspiration. Suddenly, I had remembered another application of the dot product: component. Basically, if you dot a 1-lengthed vector with a non-1-lengthed vector, you get the amount that the non-1-lengthed vector goes in the direction of the 1-lengthed vector. That was a disgusting sentence.
So, we multiply the component of how far along the edge that the point was (from one of the edge’s ends) by the direction of one of the edge’s ends to the other (the 1-lengthed vector). The result is a vector pointing from one edge to the other with the amount that the point was offset in the edge’s direction. All we need to do is set the point’s position to that result, and bam! It’s on the edge now.
Hopefully you followed most of that. I just wanted to share this with you guys because I feel pretty proud that I came up with this mostly on my own and I felt like bragging about it to someone.