Understanding Quake's Fast Inverse Square Root

http://betterexplained.com/articles/understanding-quakes-fast-inverse-square-root/

by ed • 18 years ago

88 23 18 years ago

John Carmack FTW.

jmagar• 18 years ago

Carmack or Michael Abrash? Read Graphics Programming Black Book ( http://www.amazon.com/Michael-Abrashs-Graphics-Programming-S... )

Abrash did amazing things with assembly to get Quake to run on the 486.

I don't know if Carmack, Abrash, or someone at SGI (it's in OpenGL source code too) came up with it; but it seems like witch craft to me.

thisisnotmyname• 18 years ago

Or none of the above? http://www.beyond3d.com/content/articles/8/

gcv• 18 years ago

According to this article, neither of them: http://www.beyond3d.com/content/articles/8/

That article also links to a paper (http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf) analyzing the initial approximation constant.

andrewf• 18 years ago

The Black Book is available as PDFs from http://www.gamedev.net/reference/articles/article1698.asp

Byte.com hosted a copy for a long time, but that seems to have issues atm.

dangrover• 18 years ago

The 486!? Wow

weavejester• 18 years ago

I had a 486 when Quake came out. The framerate was far too low to make it playable. I remember trying to play the demo, and I had to cut the screen down to the size of a postcard (something like 160x100) to get a framerate of 25fps.

The first Pentiums, on the other hand, were more than up to the job.

snprbob864• 18 years ago

Although Carmack developed some incredible tech in the past and has a successful (I think?) rocket building team now, he seems to have missed the mark the last few times in graphics. He also deserves some praise for the open sourcing of his old engines, but there are definitely people who have made greater contributions to graphics in recent times.

The Quake 3 engine added procedural curved surfaces which were computed on the CPU. Meanwhile, the Unreal engine simply optimized the rendering of arbitrary meshes which allowed artists to build any shaped surface they want and then let the GPU brute force it.

The Doom 3 engine added a unified lighting model based on stencil shadows. Again, this was a heavily CPU based technique while the industry was trending towards being CPU-bound. Additionally, the chosen lighting equations created a very plastic-like look. Competitors used shadow maps which are generated by the GPU and these are still the standard in speed and quality for most games today.

The latest engine he is working on is pushing "mega textures" which effectively emulate a hardware paging technique in software. "Mega textures" is the next logical step in mip-mapping, but mip-mapping has been performed by the graphics card for over a decade now. The SeaDragon team over at Microsoft Research and Live Labs built a superior version of this idea before Carmack started on this and are working actively with hardware vendors and the Direct3D team to speed it up for use in games.

Once again, Carmack has opted to trade precious CPU cycles -- better budgeted for game logic, physics, and AI -- for generality. He seems to be fighting a crusade against special cases in his engines at the expense of the games made with that engine.

There is a great reason why the Unreal Engine has been the most popular middleware platform since Quake 3...

FlorinAndrei• 18 years ago

Maybe his bet is that CPUs will become massively multicore "soon enough".

whatusername• 18 years ago

I'm talking without much experience here

"Again, this was a heavily CPU based technique while the industry was trending towards being CPU-bound." -- isn't the industry now trending in the opposite way? ie - everything is becoming a CPU (and it has more and more cores)

nihilocrat• 18 years ago

For a guy that got his name by cutting corners in clever ways (2.5d engines we see in Wolfenstein and DooM) I find it really odd that he's sort of going the other way.

russell• 18 years ago

IIRC (it's been a long time) the Cray 1 could do inverse, multiply, and square root in single cycle instructions. Isqrt would take two cycles as wood divide. (Back to the rocking chair.)

Jebdm• 18 years ago

I didn't know that Crays could split timber!

marcus• 18 years ago

Actually it didn't http://klausler.com/cray2.txt it had a command for a square root approximation and a command to iteratively get closer to the real square root.

But even if a certain computer did compute a square root (or even an approximation) in a single cycle, that would mean CPU speed was reduced by slowing down the clock to enable a more complex action to complete within the timeframe of a single cycle, and other simpler actions like adding/subtracting/moving memory we're sacrificed in its favor.

wwalker3• 18 years ago

Not necessarily. The square root hardware could be heavily pipelined to get each stage short enough for one cycle. This increases latency, but lets you keep a one-per-cycle throughput without slowing down the clock.

nx• 18 years ago

It's really easy to understand if you know what the Newton Method for computing roots of a polynomial is.

statictype• 18 years ago

Its easy to understand the algorithm. But that initial guess there is where the magic is. Thats what makes the algorithm work so efficiently.

jballanc• 18 years ago

Cool, but if you really want to blow your mind, look at some of the tricks for diagonallizing Hessians!

Understanding Quake's Fast Inverse Square Root

Related Stories