VT-S5-BC-kmedellel-sipascal-Q_SQRT.mp4

L'objectif de ce mini film est d'expliquer un peu plus en détail la fonction de la racine carrée inverse rapide utilisée par John Carmack lors du développement du jeu Quake III Arena. Nous avons choisi d'expliquer cette fonction, car elle règle un problème de rapidité dans les moteurs de jeux à une époque où les ombres et détails étaient très peu gérés. Ce ralentissement était dû aux nombreuses divisions. Elle permet donc de calculer des vecteurs servant aux ombres, lumières ou autre qui utilise ce calcul : 1/sqrt(x) sans faire une seule division ce qui fera que cette fonction sera 4 fois plus rapide que celles normalement utilisé vers les années 90.

Effectivement, grâce à plusieurs astuces cette fonction est efficace en seulement 11 lignes : voir le code. Même si aujourd'hui, il n'est plus possible de l'utiliser en C++ car les valeurs sont stockées autrement dans des versions différentes.

L'algorithme se base surtout sur une constante : 0x5f3759df, qui serait une approximation de log(y). Aussi, d'après une formule que nous n'approfondirons pas dû à sa complexité, le log en base deux d'un entier en binaire serait approximativement égal à lui-même et le calcul auquel nous voulons aboutir sera donc log(1/sqrt(x)) qui est approximativement égal à -1/2*log(y). Cette approximation accompagnée d'un décalage de bit nous permet donc de pouvoir calculer cette formule sans division.

Enfin, afin d'avoir un résultat plus précis, même s'il l'est déjà assez, une seule itération de newton est suffisante. Il reste donc un dernier problème, il n'est pas possible de faire de décalage de bit sur un float. C'est pour cela que l'adresse de notre valeur est casté en long afin de pouvoir manipuler les bits sans changer la valeur.

John Carmack était donc le premier à réussir à utiliser cette fonction de manière efficace et Quake III Arena sera un jeu avec des graphismes très travaillés pour 1999. Aujourd'hui, cet algorithme devient légèrement obsolète puisque les processeurs modernes sont optimisés pour gérer les calculs de float.

Les deux personnages joués dans ce mini-film sont :

•  John Carmack, célèbre programmeur et cofondateur d'id Software et l'un des pionniers du développement des moteurs 3D. Il a participé à la création de multiples jeux cultes comme Doom, Quake ou encore Wolfenstein 3D et il est également connu pour être capable de réaliser des moteurs graphiques capables d'exploiter au maximum le matériel l'utilisant.
•  John Cash, développeur à id Software entre 1997 et 2000.

Étant donné que cette vidéo n'est là seulement à des fins explicatifs de la fonction. Son contexte ne correspond pas du tout à la réalité.

Si vous souhaitez avoir une version écrite, le script est disponible.