Racine carrée inverse rapide

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Les calculs de lumière (ici dans OpenArena, un jeu de tir en vue subjective) utilisent la racine carrée inverse rapide pour calculer les angles d'incidence et de réflexion.

La racine carrée inverse rapide (en anglais Fast inverse square root, parfois abrégé Fast InvSqrt() ou par la constante 0x5f3759df en hexadécimal) est une méthode pour calculer x−½, l'inverse de la racine carrée d'un nombre à virgule flottante à simple précision sur 32 bits. L'algorithme a probablement été développé chez Silicon Graphics au début des années 1990. Il a entre autres été utilisé dans le code source de Quake III Arena, un jeu vidéo sorti en 1999[1]. À l'époque, le principal avantage de cet algorithme était d'éviter d'utiliser des coûteuses opérations à virgules flottantes en préférant des opérations sur entiers. Les racines carrées inverses sont utilisées pour calculer les angles d'incidence et la réflexion pour la lumière et l'ombre en imagerie numérique.

L'algorithme prend en entrée des flottants de 32 bits non-signés et stocke la moitié de cette valeur pour l'utiliser plus tard. Ensuite, il traite le nombre à virgule flottante comme un entier et lui applique un décalage logique (en) à droite d'un bit et le résultat est soustrait à la valeur « magique » 0x5f3759df. Il s'agit de la première approximation de la racine carrée inverse du nombre passé en entrée. En considérant de nouveau les bits comme un nombre à virgule flottante et en appliquant au nombre la méthode de Newton, on améliore cette approximation. Bien que n'assurant pas la précision la plus fine possible, le résultat final est une approximation de la racine carrée inverse d'un nombre à virgule flottante qui s'exécute quatre fois plus vite qu'une division d'un tel nombre.

Motivation[modifier | modifier le code]

Les normales à une surface sont largement utilisées dans les calculs d'éclairage et d'ombrage, ce qui nécessite le calcul des normes des vecteurs. Ici on montre un champ de vecteurs normaux à la surface.

Les racines carrées inverses d'un nombre à virgule flottante sont utilisées pour calculer un vecteur normalisé[2]. En synthèse d'image 3D, ces vecteurs normalisés sont utilisés pour déterminer l'éclairage et l'ombrage. Des millions de ces calculs sont ainsi nécessaires chaque seconde. Avant l'apparition de matériel dédié au TCL, ces calculs pouvaient être lents. Ce fut particulièrement le cas lorsque cette technique a été développée au début des années 1990 où les opérations sur les nombres à virgule flottante étaient plus lentes que les calculs sur entiers[1].

Aperçu du code[modifier | modifier le code]

Le code source suivant est l'implémentation de la racine carrée inverse dans Quake III Arena dont on a retiré les directives du préprocesseur C mais qui contient les commentaires originaux[3]

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;
}


Histoire et enquête[modifier | modifier le code]

John Carmack, cofondateur d'id Software, est souvent associé à cette fonction, même s'il ne l'a pas écrite.

Le code source de Quake III a été diffusé après la QuakeCon 2005, mais des copies de la racine carrée inverse rapide sont apparues sur Usenet et d'autres forums dès 2002/2003[1]. Les spéculations à l'époque pointent John Carmack comme auteur probable de la fonction. Mais ce dernier dément la chose et suggère que la fonction a été écrite par Terje Mathisen, un programmeur assembleur talentueux qui a assisté les développeurs d'id Software pour optimiser Quake. Mathisen a effectivement écrit une fonction similaire à la fin des années 1990, mais les auteurs originaux remontent à plus loin dans l'histoire de l'infographie 3D avec l'implémentation faite par Gary Tarolli pour un SGI Indigo (en) qui serait l'une des premières utilisations connues. Rys Sommefeldt, auteur de l'enquête, finit par conclure que l'algorithme original est l'œuvre de Greg Walsh de Ardent Computer (en) en collaboration avec Cleve Moler (en), fondateur de MathWorks. Cependant, aucune preuve concluante concernant l'auteur n'existe[4].

On ne sait pas comment la valeur exacte du nombre magique a été déterminée. Chris Lomont a développé une fonction pour minimiser l'erreur d'approximation en choisissant le nombre magique R dans un intervalle. Il calcule d'abord la constante optimale pour l'étape approximation linéaire, il obtient 0x5f37642f qui est proche de 0x5f3759df, mais avec cette nouvelle constante il obtient une précision moindre après une itération de la méthode de Newton[5]. Il cherche alors une constante optimale même après une ou deux itérations de la méthode de Newton et obtient la valeur 0x5f375a86 qui se révèle plus précise que l'originale, même après chaque étape d'itération[5]. Il conclut alors en se demandant si la valeur originale a été choisie par dérivation ou par essai-erreur[6]. Dans la lancée, Lomont indique aussi que la valeur magique pour flottant double précision 64-bits IEEE 754 est 0x5fe6ec85e7de30da, mais il a été démontré que la valeur exacte était 0x5fe6eb50c7b537a9[7]. Charles McEniry a effectué une optimisation similaire mais plus sophistiquée sur les valeurs probables pour R. Il cherche d'abord par une méthode par force brute et obtient la valeur déterminée par Lomont[8]. Il a ensuite essayé de rechercher cette valeur par une méthode de dichotomie et obtient alors la valeur utilisée initialement dans la fonction, ce qui conduit McEniry à penser que cette constante a probablement été obtenue par cette méthode[9].

Note et références[modifier | modifier le code]

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Fast inverse square root » (voir la liste des auteurs)

  1. a, b et c (en) Origin of Quake3's Fast InvSqrt() Beyond3D.com, consulté le 16 septembre 2012
  2. (en) Jim Blinn, Jim Blinn's Corner: Notation, Notation, Notation, Morgan Kaufmann,‎ 2003 (ISBN 978-1-55860-860-3, lire en ligne), p. 130
  3. quake3-1.32b/code/game/q_math.c id Software consulté 16 septembre 2012
  4. Origin of Quake3's Fast InvSqrt() - Part Two Beyond3D.com, consulté le 17 septembre 2012
  5. a et b Lomont 2003, p.10
  6. Lomont 2003, p. 10–11
  7. (en) Matthew Robertson, « A Brief History of InvSqrt », UNBSJ,‎ 24 avril 2012
  8. McEniry 2007, p. 11-12
  9. McEniry 2007, p. 16

Liens externes[modifier | modifier le code]