Understanding Fast Inverse Square Root As Used In The Game Quake
“An article and research paper describe a fast, seemingly magical way to compute the inverse square root (1/sqrt(x)), used in the game Quake.
I’m no graphics expert, but appreciate why square roots are useful. The Pythagorean theorem computes distance between points, and dividing by distance helps normalize vectors. (Normalizing is often just a fancy term for division).
3D games like Quake divide by distance zillions (yes zillions) of times each second, so “minor” performance improvements help immensely. We don’t want to take the square root and divide the regular way: exponentiation and division are really, really expensive for the CPU.
Given these conditions, there is a magic formula to get 1/sqrt(x) found in the game Quake.”
float InvSqrt(float x){
float xhalf = 0.5f * x;
int i = *(int*)&x; // store floating-point bits in integer
i = 0x5f3759d5 - (i >> 1); // initial guess for Newton's method
x = *(float*)&i; // convert new bits into float
x = x*(1.5f - xhalf*x*x); // One round of Newton's method
return x;
}
|
Understanding Quake’s Fast Inverse Square Root (betterexplained.com)
Additional Resources: