A raiz quadrada inversa é uma função matemática extremamente útil e com muitas aplicações em diversas áreas. Na área da informática este cálculo também pode ser utilizado para solucionar os mais variados problemas. Entretanto, destaca-se a sua aplicação em jogos eletrônicos para determinar ângulos de incidência e reflexão, muito úteis para gerar iluminação e sombras em ambientes tridimensionais.

Entretanto, alcançar a raiz quadrada inversa durante a execução de iluminação dinâmica em um jogo criava uma situação bastante desconfortável aos programadores, que já lutavam contra os limites de hardware e de programação da época. Realizar este cálculo inúmeras vezes por segundo exigia muito do processador, por isso os programadores buscavam soluções a qualquer custo para minimizar o seu alto custo de processamento e conseguir um resultando ao menos semelhante. E é justamente aí que entra o jogo Quake 3 Arena, lançado em 1999.

Observe o tiro indo em direção à entrada, iluminando a estátua e o chão. Isso é iluminação dinâmica! Clique na imagem para vê-la em tamanho maior :)

A função Fast InvSqrt (abreviação de Fast inverse square root - "Raiz quadrada inversa rápida" ) apareceu pela primeira vez no código fonte do viciante jogo Quake 3 Arena. O método consegue com apenas seis linhas de código;retornar um valor bastante aproximado da raiz quadrada inversa, façanha esta que reduz custos de processamento e roda pelo menos quatro vezes mais rapidamente do que qualquer outro algoritmo que tente encontrar a raiz quadrada inversa de um número, como o (float)(1.0/sqrt(x)), recurso nativo e popular da década de noventa (LOMONT, 2003).

1. float InvSqrt (float x){ // Função do tipo float recebe a váriável x do tipo float
2.    float xhalf = 0.5f*x; // inicializa a variável xhalf com o valor de x * 0.5f
3.    int i = *(int*)&x; // armazena os bits do ponto flutuante como inteiro
4.    i = 0x5f3759df - (i>>1); // estimativa inicial para a Aproximação de Newton
5.    x = *(float*)&i; // converte bits de volta em ponto flutuante
6.    x = x*(1.5f - xhalf*x*x); // rodada da Aproximação de Newton-Raphson
7.    return x; // retorna o valor armazenado na variável x
8. }

Excluindo o cabeçalho do método (a primeira linha) e a chave que o fecha (última linha), sobram seis linhas de lógica. É incrível como o algoritmo não utiliza divisões e expoentes, apenas multiplicação e deslocamento de bits. A função estima a raiz inversa e utiliza o Método de Aproximação de Newton-Raphson (Aproximação de Newton), uma fórmula empregada para encontrar um valor aproximado de uma raiz de qualquer função matemática. Repetir a Aproximação de Newton refina a acurácia (precisão) do valor, fazendo com que ele se aproxime cada vez mais da raiz. Curiosamente, o método Fast InvSqrt() utiliza apenas uma rodada da Aproximação de Newton.

Mesmo com os comentários acrescidos, algumas linhas ainda nos deixam com algumas dúvidas, por isso tratarei de explicá-las neste parágrafo. Depois da variável xhalf receber o valor de x multiplicado por 0.5f (é a adaptação de uma passagem da Aproximação de Newton, o resultado - produto - será reaproveitado na sexta linha), a terceira linha faz uma conversão (cast) de ponto flutuante para inteiro e armazena o valor na variável i (ok, eu sei que agora foi um pouco pesado, mas garanto que se você tentar ler pausadamente, vai entender muito bem). A quarta linha é uma das mais importantes, tendo a responsabilidade de fazer a estimativa inicial para a Aproximação de Newton. Devido a sua alta complexidade, vamos atentar aos detalhes de sua funcionalidade e não como os autores desta heurística adaptaram essas fórmulas matemáticas.

A linha utiliza um número mágico: 0x5f3759df. É difícil abstrair o que o código faz com facilidade, mas através dessa constante que subtrai o trecho "i>>1" deslocam-se os bits uma posição para a direita, fazendo o último bit significativo cair, o que resulta em uma divisão por 2. Com isso, chegamos a um valor muito próximo da raiz quadrada inversa. A quinta linha converte os bits para ponto flutuante novamente e a sexta linha, a mais importante, é uma adaptação da Aproximação de Newton em linha de código. É através dela que o valor torna-se ainda mais preciso e próximo da raiz quadrada inversa. Por último, na sétima linha, o valor adquirido retorna ao código que chamou a função, chegando ao fim do método Fast InvSqrt().

Autoria da heurística

Diversos sites e portais dão os créditos desta solução ao genial programador John Carmack (Carmack), desenvolvedor de engines de jogos como Commander Keen, Wolfenstein 3D, Doom e Quake. De fato, o trecho citado nesse artigo aparece dentro do código-fonte de Quake 3 Arena, que teve a sua engine desenvolvida por ele. Outro possível autor seria Michael Abrash, conhecido como um dos mais extraordinários otimizadores de assembly x86. Entretanto, o próprio Carmack já negou sua participação e afirmou não acreditar que tenha sido o Michael quando respondeu a um e-mail do portal Beyond3D: "Não fui eu, e não acho que foi o Michael. Terje Mathison talvez?".

Terje Mathison é outro mestre em otimização de código para microprocessadores x86. O portal Beyond3D também entrou em contato com ele, que respondeu agradecendo por ter sido considerado um possível autor, e disse que escreveu um código para calcular a raiz quadrada inversa "uns 5 anos atrás" (possivelmente entre 1999 e 2000), tendo o intuito de solucionar o problema de um sueco com fluídos químicos. Todavia Terje negou sua autoria, apontando as diferenças no Fast InvSqrt() ausentes na solução que ele havia criado. Ele também confirmou que o código não foi escrito por ele.

Após mais um período de pesquisas, o Beyond3D conseguiu a informação com um funcionário da NVIDIA de que o nome mais provável de merecer autoria era Gary Tarolli (Tarolli), um dos fundadores da 3dfx Interactive, empresa pioneira em gráficos 3d para computadores domésticos. É importante mencionar que o método Fast InvSqrt() foi implementado posteriormente em hardware nas placas gráficas 3dfx, o que tornou a pista de Tarroli ainda mais "quente". Em resposta, apesar de afirmar não merecer os créditos, Tarolli confirmou ter usado o algoritmo muitas vezes (o que contribuiu para a popularização e longevidade desta heurística) e mostrou bastante familiaridade com ele, explicando as passagens difíceis bem como a origem de cada um delas. Tarolli também afirmou ter "mexido" no número mágico (a constante utilizada na Aproximação de Newton, quarta linha) para refinar a precisão do resultado. Com isso, é possível concluir que, apesar de não ter todo o crédito, Gary Tarolli foi uma das últimas pessoas a refinar o método Fast InvSqrt()(RYS, 2004).

Conclusão

Em um período de grandes avanços dos ambientes tridimensionais em jogos eletrônicos, a heurística Fast InvSqrt() mostrou-se extremamente útil para minimizar esforços desnecessários de processamento e permitir a criação de jogos com visuais estonteantes. Embora não seja mais utilizado, o recurso foi tão útil que chegou a ser implementado em hardware nas placas gráficas 3dfx (RYS, 2004). A constante utilizada no algoritmo original pode ser substituída por "0x5f375a86", resultando em desempenho ligeiramente melhor (LOMONT, 2003).

Referências