0x5f3759df

Izračunavanja osvetljenja i refleksija (ovde prikazani u pucačini iz prvog lica OpenArena) koriste brzi inverz kvadratnog korena za nalaženje upadnog ugla.

Brzi inverz kvadratnog korena (poznat i kao Fast InvSqrt() ili po heksadekadnoj konstanti 0x5f3759df) je metod za računanje x^−½, multiplikativnog inverza kvadratnog korena broja zapisanog u 32-bitnoj preciznosti pokretnog zareza u IEEE 754 formatu. Algoritam je verovatno razvijen u kompaniji Silikon grafiks početkom 1990-ih, a njegova implementacija se javila 1999. u izvornom kodu igrice Quake III Arena, ali sam metod se nije pojavio na javnim forumima kao što je Usenet sve do 2002 ili 2003. U to vreme, prvenstvena prednost algoritma se sastojala u izbegavanju računski skupih aritmetičkih operacija u pokretnom zarezu, umesto kojih se koriste celobrojne operacije. Inverzni kvadratni koren se koristi u računanju upadnih uglova i refleksije svetlosti i senki u računarskoj grafici.

Algoritam uzima 32-bitni broj u pokretnom zarezu kao ulaz, i skladišti njegovu polovinu za kasniju upotrebu. Zatim se, posmatrajući bitove koji predstavljaju broj u pokretnom zarezu kao 32-bitni ceo broj, sprovodi operacija logičkog šiftovanja udesno za jedan bit, a rezultat te operacije se oduzima od „magične“ konstante 0x5f3759df. Ovo je prva aproksimacija inverznog kvadratnog korena ulaza. Zatim se bitovi ponovo posmatraju kao broj u pokretnom zarezu i sprovodi se jedna iteracija Njutnovog metoda kako bi se dobila preciznija aproksimacija. Ovo računa aproksimaciju inverza kvadratnog korena broja u pokretnom zarezu otprilike četiri puta brže nego korišćenjem deljenja brojeva u pokretnom zarezu.

Algoritam je prvobitno pripisivan Džonu Karmaku, ali je istraživanje pokazalo da ovaj kod ima dublje korene u hardverskoj i softverskoj strani računarske grafike. Prilagođavanja i izmene su prolazile kroz kompanije Silikon grafiks i 3dfx Interactive, a implementacija Garija Tarolija za SGI Indigo predstavlja najraniju poznatu upotrebu algoritma. Nije poznato kako je konstanta prvobitno otkrivena, mada je istraživanje navelo na neke moguće metode.

Motivacija

Površinske normale imaju čestu primenu u izračunavanjima osvetljavanja i senki, što zahteva izračunavanje normi vektora. Na slici je prikazano polje vektora normalnih na površinu.

Inverz kvadratnog korena broja u pokretnom zarezu se koristi u računanju normalizovanog vektora. Kako programi koji rade sa 3D grafikom koriste ove normalizovane vektore za određivanje osvetljenja i refleksija, neophodno je izvršiti milione ovakvih računanja u sekundi. Pre nego što je razvijen specijalizovani hardver koji se bavi transformacijama i osvetljenjem, softversko izračunavanje je moglo da bude vrlo sporo. Konkretno, kada je ovaj algoritam razvijen ranih 1990-ih, većina procesora je bila mnogo sporija u računanju operacija sa pokretnim zarezom nego u računanju celobrojnih operacija.

Kako bi se normalizovao vektor, određuje se dužina vektora računanjem njegove euklidske norme: kvadratni koren zbira kvadrata koordinata vektora. Kada se svaka koordinata vektora podeli tom dužinom, vektor postaje jedinični vektor sa istim pravcem.

$\|{\boldsymbol {v}}\|={\sqrt {v_{1}^{2}+v_{2}^{2}+v_{3}^{2}}}$ je euklidska norma vektora, analogna euklidskom rastojanju između dve tačke u euklidskom prostoru.

${\boldsymbol {\hat {v}}}={\boldsymbol {v}}/\|{\boldsymbol {v}}\|$ je normalizovani (jedinični) vektor. Ako se sa ${\boldsymbol {x}}$ predstavi $v_{1}^{2}+v_{2}^{2}+v_{3}^{2}$, dobije se

${\boldsymbol {\hat {v}}}={\boldsymbol {v}}/{\sqrt {x}}$, što povezuje jedinični vektor sa inverzom kvadratnog korena komponenti razdaljine.

Quake III Arena je koristila algoritam za brzi inverz kvadratnog korena kako bi ubrzala izračunavanje u grafičkoj procesnoj jedinici, ali ovaj algoritam je u međuvremenu implementiran u specijalnim hardverskim verteks šejderima koji koriste FPGA.

Pregled koda

Sledi izvorni kod implementacije algoritma za brzi inverz kvadratnog korena korišćen u igrici Quake III Arena, sa uklonjenim C preprocesorskim direktivama, ali sa očuvanim neizmenjenim originalnim komentarima:

float Q_rsqrt( float number )
{
	long i;
	float x2, y;
	const float threehalfs = 1.5F;

	x2 = number * 0.5F;
	y = number;
	i = * ( long * ) &y; // evil floating point bit level hacking
	i = 0x5f3759df - ( i >> 1 ); // what the fuck?
	y = * ( float * ) &i;
	y = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration
// y = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed

	return y;
}

Kako bi se odredio inverz kvadratnog korena, polazi se od aproksimacije za $x^{-1/2}$, koju određuje softver, a zatim se primenjuje neka numerička metoda da bi se aproksimacija popravljala sve dok ne dođe u opseg prihvatljivog odstupanja od tačnog rešenja. Uobičajeni softverski metodi sa početka 1990-ih su prvu aproksimaciju izvlačili iz predefinisanih tablica. Gorenavedeni kod se u praksi pokazao bržim od tablica, i otprilike četiri puta brži nego kad bi se koristilo uobičajeno deljenje u pokretnom zarezu. Dolazilo je do izvesnog gubitka u preciznosti, ali je on nadomešćen značajnim napretkom u performansama. Algoritam je razvijen za IEEE 754-1985 32-bitne brojeve u pokretnom zarezu, ali ispitivanje Krisa Lomonta i kasnije Čarlsa MakEnirija je pokazalo da bi mogao da bude implementiran i u drugim formatima brojeva u pokretnom zarezu.

Prednosti u brzini koje pruža ovaj algoritam se između ostalog zasnivaju na „dosetki“ da se 32-bitni broj u pokretnom zarezu tretira kao ceo broj i oduzme od specifične konstante, 0x5f3759df. Svrha konstante nije odmah jasna nekome ko pregleda kod, pa se stoga, kao i druge slične konstante koje se koriste u programiranju, često naziva „magičnim brojem“. Ovo celobrojno oduzimanje i bitovsko šiftovanje daje 32-bitnu vrednost koja se zatim ponovo posmatra kao broj u pokretnom zarezu, i predstavlja grubu aproksimaciju inverza kvadratnog korena početnog broja. Primenjuje se jedna iteracija Njutnovog metoda kako bi se dobilo na preciznosti, i tu se kod završava. Algoritam generiše razumno precizne rezultate koristeći jedinstvenu prvu aproksimaciju za Njutnov metod. Međutim, ovo je znatno sporije i manje precizno nego korišćenje SSE instrukcije rsqrtss na x86 procesorima, koja je takođe objavljena 1999.

Literatura

• Kushner, David (2002). „The wizardry of Id”. IEEE Spectrum. 39 (8): 42—47. doi:10.1109/MSPEC.2002.1021943. 
• Blinn, Jim (2003). Jim Blinn's Corner: Notation, notation notation. Morgan Kaufmann. str. 130. ISBN 978-1-55860-860-3. 
• Eberly, David (2001). 3D Game Engine Design. Morgan Kaufmann. str. 504. ISBN 978-1-55860-593-0. 

Spoljašnje veze

• Kratka istorija InvSqrt, Metju Robertson
• Brzi inverz kvadratnog korena, Kris Lomont
• Poreklo brzog InvSqrt() igrice Quake3
• Quake III Arena izvorni kod
• Margolin, Tomer (27. 08. 2005). „Magical Square Root Implementation In Quake III”. CodeMaestro. The Coding Experience. Arhivirano iz originala 14. 04. 2012. g. Pristupljeno 10. 11. 2012.  Arhivirano na sajtu Wayback Machine (14. april 2012)