Arrel quadrada inversa ràpida

Els càlculs d'il·luminació i reflex, com en el videojoc OpenArena, utilitzen el codi d'arrel quadrada inversa ràpida per calcular els angles d'incidència i de reflexió.

Les normals superficials s'utilitzen àmpliament en els càlculs d'il·luminació i ombrejat, i requereixen el càlcul de normes per a vectors. Aquí es mostra un camp de vectors normals a una superfície.

L'arrel quadrada inversa ràpida, de vegades anomenada Fast InvSqrt() o per la constant hexadecimal 0x5F3759DF, és un algorisme que estima ${\frac {1}{\sqrt {x}}}$, el recíproc (o invers multiplicador) de l'arrel quadrada d'un nombre de coma flotant de 32 bits $x$ en format de coma flotant IEEE 754. Aquesta operació s'utilitza en el processament de senyal digital per normalitzar un vector, com ara escalar-lo a la longitud 1. Per exemple, els programes de gràfics per ordinador utilitzen arrels quadrades inverses per calcular angles d'incidència i reflexió per a la il·luminació i l'ombrejat. Predatat per algorismes de videojocs similars, aquest és més conegut per la seva implementació l'any 1999 a Quake III Arena, un videojoc de trets en primera persona basat en gran manera en gràfics 3D. L'algoritme només va començar a aparèixer als fòrums públics entre el 2002 i el 2003. El càlcul d'arrels quadrades depèn generalment de moltes operacions de divisió, que per als números de coma flotant són computacionalment costoses. El quadrat invers ràpid genera una bona aproximació amb només un pas de divisió.

L'algorisme accepta un nombre de coma flotant de 32 bits com a entrada i emmagatzema un valor reduït a la meitat per al seu ús posterior. Aleshores, tractant els bits que representen el nombre de coma flotant com un nombre enter de 32 bits, es realitza un desplaçament lògic d'un bit a la dreta i el resultat es resta del nombre 0x5F3759DF, que és una representació de coma flotant d'una aproximació de ${\sqrt {2^{127}}}$. Això resulta en la primera aproximació de l'arrel quadrada inversa de l'entrada. Tractant els bits de nou com un nombre de coma flotant, executa una iteració del mètode de Newton, donant una aproximació més precisa.

Un exemple bidimensional d'ús del normal $C$ trobar l'angle de reflexió a partir de l'angle d'incidència; en aquest cas, sobre la llum que es reflecteix d'un mirall corbat. L'arrel quadrada inversa ràpida s'utilitza per generalitzar aquest càlcul a l'espai tridimensional.

L'algoritme es va atribuir sovint erròniament a John Carmack, però de fet el codi es basa en un article inèdit de William Kahan i KC Ng distribuït el maig de 1986. La constant original es va produir a partir d'una col·laboració entre Cleve Moler i Gregory Walsh, mentre treballaven per a Ardent Computing a finals dels anys vuitanta.

Amb els avenços posteriors del maquinari, especialment la instrucció x86 SSErsqrts, aquest mètode no és generalment aplicable a la informàtica de propòsit general, encara que segueix sent un exemple interessant tant històricament com per a màquines més limitades, com ara sistemes encastats de baix cost. Tanmateix, més fabricants de sistemes encastats inclouen acceleradors trigonomètrics i altres matemàtics com CORDIC, evitant la necessitat d'aquests algorismes.

Motivació

L'arrel quadrada inversa d'un nombre de coma flotant s'utilitza per calcular un vector normalitzat. Els programes poden utilitzar vectors normalitzats per determinar angles d'incidència i reflexió. Els programes de gràfics 3D han de realitzar milions d'aquests càlculs cada segon per simular la il·luminació. Quan el codi es va desenvolupar a principis de la dècada de 1990, la majoria de la potència de processament de coma flotant es va endarrerir amb la velocitat del processament dels nombres enters. Això era problemàtic per als programes de gràfics en 3D abans de l'arribada del maquinari especialitzat per gestionar la transformació i la il·luminació. La longitud del vector es determina calculant la seva norma euclidiana: l'arrel quadrada de la suma de quadrats de les components del vector. Quan cada component del vector es divideix per aquesta longitud, el nou vector serà un vector unitari apuntant en la mateixa direcció. En un programa de gràfics 3D, tots els vectors es troben en un espai tridimensional, per tant ${\boldsymbol {v}}$ seria un vector $(v_{1},v_{2},v_{3})$.

$\|{\boldsymbol {v}}\|={\sqrt {v_{1}^{2}+v_{2}^{2}+v_{3}^{2}}}$

és la norma euclidiana del vector.

${\boldsymbol {\hat {v}}}={\frac {\boldsymbol {v}}{\left\|{\boldsymbol {v}}\right\|}}$

és el vector (unitat) normalitzat, utilitzant $\|{\boldsymbol {v}}\|^{2}$ representar $v_{1}^{2}+v_{2}^{2}+v_{3}^{2}$ .