Shortly after posting that I wondered why the hell I hadn't asked Terje! With Doom3 recently finished and published to critical acclaim, hacking minds turned to id to ask when Q3's fairly ancient (by current 3D standards) renderer would be available for people to look at, learn from and work with.ĭuly released in the week following Quakecon, Slashdot picked up the obvious story where the question of who wrote that implemenation of fast inverse square root came up again. During John's Quakecon keynote speech this year he mentioned the opening of the complete Quake3 v1.32 source under the General Public License, including the 3D renderer, to big cheers from the assembled crowd. The rebuttal was posted in the B3D thread along with Terje as a potential author and was then pretty much forgotten about by all until recently. Terje Matheson perhaps?ĭespite having the noodle for it, John says nay and isn't sure if it's Michael either. >you know who's responsible, possibly with a history of sorts? >Most people say it's your work, a few say it's Michael Abrash's. >extremely clever in its method and supposedly from the Q3 source. >Is that something we can attribute to you? Analysis shows it to be >There's a discussion on 's forums about who the author of Subject: Re: Origin of fast approximated inverse square root Michael stands up here as x86 assembly optimiser extraordinaire, author of the legendary Zen of Assembly Language and Zen of Graphics Programming tomes, and employee of id during Quake's development where he worked alongside Carmack on optimising Quake's software renderer for the CPUs around at the time.Īsking John whether it was him or Michael returned a "not quite". Michael Abrash was mooted as a possible author too. While discussing NV40's render path in the Doom3 engine as mentioned previously, the code was brought up and attributed to John Carmack and he's the obvious choice since it appears in the source for one of his engines. The paper's summary wonders who wrote it and whether they got there by guessing or derivation. Suffice to say the constant used to start the Newton iteration is a very clever one. Chris's analysis for his paper explains it for those interested in the base math behind the implementation. He'd seen the code on the forums and that's probably also where DemoCoder saw it before commenting in the first NV40 Doom3 thread on B3D. Using the integer cast of the seeded value, i is reused and the initial guess for Newton is calculated using the magic seed value minus a free divide by 2 courtesy of the CPU.īut why that constant to start the guessing game? Chris Lomont wrote a paper analysing it while at Purdue in 2003. The right shift drops the least significant bit of i, essentially halving it. i is then set to 0x5f3759df, minus itself shifted one bit to the right. Taking advantage of the nature of 32-bit x86 processors, i, an integer, is initially set to the value of the floating point number you want to take the inverse square of, using an integer cast. Simplified, Newton-Raphson is an approximation that starts off with a guess and refines it with iteration. The magic of the code, even if you can't follow it, stands out as the i = 0x5f3759df - (i>1) line. Most of you will know that you can calculate a square root using Newton-Raphson iteration and essentially that's what the code above does, but with a twist. Without something like the nrm instruction in a modern fragment processor where you can get normalisation of an fp16 3-channel vector for free on certain NVIDIA hardware if you're (or the compiler is!) careful, or if you need to do it outside of a shader program for whatever reason, inverse square root is your friend. It might even make some sense.įinding the inverse square root of a number has many applications in 3D graphics, not least of all the normalisation of 3D vectors. To the Beyond3D crowd it might ring a bell or two. To most folks the following bit of C code, found in a few places in the recently released Quake3 source code, won't mean much. So if timeframes appear a little wonky, it's entirely on purpose! One for the geeks, enjoy. Note! This article is a republishing of something I had up on my personal website a year or so ago before I joined Beyond3D, which is itself the culmination of an investigation started in April 2004.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |