5 ms·
Understanding Quake's Fast Inverse Square Root
- ComputerGuru 18y agoJohn Carmack FTW.
- jmagar 18y agoCarmack or Michael Abrash? Read Graphics Programming Black Book ( http://www.amazon.com/Michael-Abrashs-Graphics-Programming-Special/dp/1576101746 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 18y agoOr none of the above? http://www.beyond3d.com/content/articles/8/ http://www.beyond3d.com/content/articles/8/
- gcv 18y agoAccording to this article, neither of them: http://www.beyond3d.com/content/articles/8/ http://www.beyond3d.com/content/articles/8/ That article also links to a paper (http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf) analyzing the initial approximation constant.
- andrewf 18y agoThe Black Book is available as PDFs from http://www.gamedev.net/reference/articles/article1698.asp 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 18y agoThe 486!? Wow
- MikeCapone 18y agoYeah, I actually played it (choppily) for a while on my 486.
- weavejester 18y agoI 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.
- snprbob86 18y agoAlthough 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...
- nihilocrat 18y agoFor 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.
- FlorinAndrei 18y agoMaybe his bet is that CPUs will become massively multicore "soon enough".
- snprbob86 18y ago
- russell 18y agoIIRC (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 18y agoI didn't know that Crays could split timber!
- marcus 18y agoActually it didn't http://klausler.com/cray2.txt 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 18y agoNot 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 18y agoIt's really easy to understand if you know what the Newton Method for computing roots of a polynomial is.
- statictype 18y agoIts easy to understand the algorithm. But that initial guess there is where the magic is. Thats what makes the algorithm work so efficiently.
- jballanc 18y agoCool, but if you really want to blow your mind, look at some of the tricks for diagonallizing Hessians!