churchvilla.blogg.se

1. #Quake 3 inverse square root for free#
2. #Quake 3 inverse square root software#
3. #Quake 3 inverse square root code#

>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

#Quake 3 inverse square root software#

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.

#Quake 3 inverse square root code#

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.

#Quake 3 inverse square root for free#

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.