Now suppose we're testing for collision between a ball (of radius R) and this convex obstacle. All we must do is keep the center of the ball at least a distance R from the obstacle. For example, in the following picture, the center of the ball must be kept outside the grey area.
The (approximating) technique I described in my last post was to move the planes (invisibly) outward by R, and make sure the center of the ball is outside those planes. With a skinny triangle like this, the result prevents the ball from occupying the empty space above the triangle's point, as shown here:
This would make the player think there was an "invisible wall" extending above the triangle. That's bad. What we can do however is add some additional planes like thus:
This is a much better approximation. The extra planes do not affect the visual appearance of the obstacle, because the do not cut through it. They only affect the collision detection. You could always add additional planes to make the collision more and more accurate (at the cost of memory and speed), but the approximation using one extra plane at each corner is good enough that the player probably won't notice that it isn't quite right. In fact, this is the approximation used by the Quake 3 & Doom 3 engines. It has been standard since Quake 1. You will notice that the approximation is only inaccurate when there are skinny wedges. (Also note that, although here we added extra planes at the corners, in 3D, we'd instead be adding extra planes that lie on the *edges* of the obstacle.) With Quake-style engines, you use an editor to create a world with these convex obstacles (they call them “brushes”), and the map compiler will automatically add these extra, invisible, planes.
Now that we have a way of checking for intersections, the next problem to tackle is how to do collision between a moving point and the obstacle.
