The inverse square root function (1/sqrt(x)) is used heavily during a game engine’s draw loop to normalize vectors into “unit” vectors with a length of 1. Normalized vectors are important because when you take the dot product of two of them (Ax*Bx + Ay*By + Az*Bz), the result is the cosine of the angle between the two vectors.
So imagine you have a vector that describes the way a surface is facing (its surface normal) and a second vector that describes the direction of sunlight. If the sunlight vector is parallel to your surface normal, which is to say the surface is facing the sun, the dot product of the two normalized vectors is the cosine of 0, which is 1. If the surface is 90 degrees from the sun, the dot product is the cosine of 90, which is 0. Anything in between and you get a value between 0 and 1, which essentially allows you to describe how brightly you should light that surface.
Now, you run this calculation on every triangle visible in a 3D game, and you do all that 30 or more times a second, and you have a basic point-source lighting effect! Recall, however, that you need that inverse square root function to calculate unit vectors for each of those triangles. The square root operation is slow. Do it thousands of times per draw loop, and you have yourself a slow game.
But if you don’t mind throwing away a marginal bit of accuracy, there’s a faster way.
There’s an inverse square root function that a lot of game engines use that is rumored to have originated in Quake III by Nvidia programmer Gary Tarolli. It looks like this:
float InvSqrt(float x)
{
float xhalf = 0.5f*x;
int i = *(int*)&x; // get bits for floating value
i = 0x5f3759df - (i>>1); // gives initial guess y0
x = *(float*)&i; // convert bits back to float
x = x*(1.5f-xhalf*x*x); // Newton step, repeating increases accuracy
return x;
}
Hold on, what was that?!?!
So way back when, Newton came up with a clever way of approximating the inverse square root. First, you divide the original number x by two. Lets call that “xhalf”. Then, you make a reasonably close guess at the inverse square root. Let’s call that g. Then, you take those two variables and perform this calculation (which you’ll recognize as the last step in the InvSqrt function):
g = g*(1.5 – xhalf * g *g)
If you do that over and over, substituting in the updated g on each iteration, g will quickly hone in on the inverse square root of x! In fact, if you pick a decent g to start with, a single iteration or two will get you very close to the correct value.
The question is, how do you find that initial guesstimate for the first g? The game engine coders use trick with how floating point numbers are represented in binary, with the exponent and mantissa broken up similar to scientific notation. In a 32-bit float, the left-most bit is a sign bit and is 0 for positive numbers. That’s followed by 8 bits of exponent (biased by 127 to represent negative and positive exponents), and the final 23 bits represent the mantissa.
Well, to do an inverse square root, you basically need to multiply the exponent by -1/2.
When you shift those bits to the right (a very fast operation), the effect on the exponent is to divide it by 2. You still need to subtract the exponent from 0 to change it’s sign, though, and what do you do about the mantissa which was also affected in the bit shift operation?
This is where the magic 0x5f3759df number comes in. It’s absolutely bonkers, but by subtracting the bit shift result from 0x5f3759df, the mantissa is reset to near to it’s original state and the exponent is subtracted from 0 (taking into account it’s bias of 127).
The result is very close to the inverse square root. Close enough for a single pass through Newton’s equation to end up with a value precise enough for practical purposes.
Understanding Quake’s Fast Inverse Square Root
Fast Inverse Square Root – details and math behind the magic number (PDF)
ADVERTISEMENT
