Sphere Collision Test
Without the Square Root
I came across this one when a guy on the #coders IRC channel showed me his bounding sphere collision code but couldn't explain how it worked. What was surprising was that there was no square root involved. Common sense tells us that this can't be right, since the Euclidean norm is defined using a square root, but in this case common sense is misleading.
The following equations handle the static bounding sphere collision test. The translating case is more involved, but similar optimizations can be applied (for more information, see Simple Bounding-Sphere Collision Detection, by Oleg Dopertchouk). We use the notation of figure 1 throughout.
 Figure 1: 2 Spheres in General Position |
Normally you test two bounding spheres for collision by taking the norm of the vector between them and comparing it to the sum of their radii. This requires a (generally) very slow square root operation to calculate the norm. We can avoid the square root by noticing that the equation:
can be written as:
So we get rid of a square root but gain some extra multiplies and adds. Coupled with a nice sweep-and-prune algorithm, you should get a hefty speedup in the narrow-phase collision detection for complex scenes.
See Also:
Sweep-and-Prune