Fast inverse square root – An quake III algorithm and why it is Ingenious, how it Works
Gamer or not, everyone must have heard of the legendary Quake games. In fact, Quake II is the first game that I ever played, I was so fascinated by it that I became a perpetual gamer for life. ID Software (developer of Quake franchise) , made their engine open source in 2005. The fans of the franchise found this algorithm which happens to be a genius way to quickly calculate the inverse square root.
So why is this algorithm genius and what is the relevance?
In terms of math, we use the function:
To calculate inverse square root. When it comes to coding, it can easily be calculated by importing the math library in C Language (Quake III was actually coded in C) :
But it’s a totally different story in the Quake III Code. Below is the actual code from the game(trust me I didn’t photoshop this :P)
So what does this have to do with a game?
In order to implement physics and reflections in the game engine, it is important to compute normalized vectors. But the computing process needs to be very quick for the game to run smoothly. John Carmack developed an algorithm for this computation and it is called Fast Inverse Square Root (q_rsqrt)
Inverse square roots are essential in video game graphics particularly in 3D game engines. Path finding, lighting, reflections and many other game programming techniques require vector normalization, which involves an inverse square root operation.
Video games in 90’s
90’s nostalgia floats often on the internet. Everything that made up the past decade is being relived; Television shows, cartoons, fashion, you name it. Most importantly 90’s endowed us with epic video games. What has now evolved into a full blown multi-billion market of high tech gaming consoles saw the day of light in the 90’s.
Most popular games included super Mario, pac-man, street fighter from 90’s made our childhood more exciting. It was surely a remarkable decade. In 90’s, 3D games were in early stage, and the ability to render 3D graphics was constrained by hardware. Therefore it led to programmers to devise creative ways to get around hardware limitations.
One such creative and excellent attempt was fast inverse square root algorithm.
It was not the era of high tech gaming or high speed internet, now we see numerous stakeholders in the gaming industry; for example gaming youtube channels, you can find numerous gamers with extremely successful youtube channels with millions of subscribers.
Quake III Arena, the first person shooter video game used the fast inverse square root algorithm to accelerate graphics computation.
But the algorithm since been implemented in dedicated hardware vertex shaders using field programmable gate arrays (FGPA).
Relevance in contemporary times
With subsequent hardware advancements, fast inverse square root algorithm is not generally applicable to modern computing, though it remains an interesting breakthrough example both historically, and for more limited machines, such as low cost embedded systems.
In conclusion, Quake III Arena, the first person shooter video game is renowned for heavy use of 3D graphics.
