Smallest Circle Enclosing a Triangle: an Application

Clive Townsend made this interesting contribution following a discussion at one of the CTK Exchange forums.

Just wanted to explain how I was first introduced to this problem.

It doesn't change the question, but may be of interest to show how a small improvement in method can have important results. I'm a programmer of computer games, and quite often need to decide whether a laser beam has hit a player, whether an enemy can 'see' you, and many other situations requiring the computer to draw a line between two points and decide whether or not the line passes through a wall or other scenery.

In most 3D games the 'world' consists of areas and objects made from triangles, although these days computers are powerful enough to draw so many triangles that a surface made from them can look quite curved. Clever lighting can make this smoothness even more realistic, but even so they are still usually made from triangles.

To test whether a line segment passes through every single triangle in a scene would be wasteful, so every opportunity is taken to reject ones which are 'nowhere near' the line.

Don't test the line against enemies or objects in a different room, for example. And divide your landscape into chunks and only test against the chunks that the line passes through. Store the co-ordinates of a sphere which encloses an object and see if the line passes through the sphere - if it doesn't then you don't need to test against any of the object's triangles. Etc.

Once you've rejected as many triangles as possible, you then have to do some more serious calculation. For each triangle you need to find the point where the line intersects the plane of the triangle. You then have to find out whether this point is inside the triangle or not.

This issue is discussed in Irina Mikheeva's archive question entitled 'Point inside a triangle'. As Alexander wisely pointed out, to save computation time we stored the formulae for each side and used them to test whether the point was inside the triangle or not. (As the triangle was at an arbitrary 3D angle, we actually stored the formulae for the planes passing through each edge and perpendicular to the plane).

To speed things up, I also wanted to reject triangles that were far enough away from the line to be irrelevant. By storing a bounding sphere for each triangle (computer memory wasn't an issue) I was able to discard triangles whose sphere-centre was more than the sphere-radius from the line.

Sometimes the line would pass through the sphere without actually touching the triangle, and I'd have to do all the line-intersecting-plane and point-outside-triangle calculations for no reason. Making the bounding sphere as small as possible (hence my question) it makes this process as efficient as possible.

By giving each triangle it's own bounding sphere, we were able to avoid un-needed calculation, and speed up collision testing and screen drawing.

With the large amount of graphics we were using, this made the difference between a jerky, unplayable game and a smooth playable one.

Result!

Copyright © 1996-2008 Alexander Bogomolny