16/01/2016

Quake 3 Arena e o método Fast InvSqrt()

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).

ATENÇÃO: Antes de irmos com tanta sede ao código, que tal relembrarmos alguns detalhes básicos? Variáveis do tipo int correspondem a variáveis que armazenam números inteiros como valor. Já as variáveis do tipo float armazenam números flutuantes, que fazem parte justamente do formato de representação de números reais utilizado pelo computador. Parece bobagem, mas não precisaremos de muito mais do que isso para estudarmos esse interessantíssimo trecho de código.

Agora que terminamos essa pequena revisão, segue abaixo o método (que é uma função, ou seja, retorna o valor da variável) com os devidos comentários:

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

LOMONT, Chris. Fast inverse square root. Disponível em <http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf>. Acesso em: 5 de janeiro de 2016.

RYS. Origin of Quake3's Fast InvSqrt(). Disponível em <https://www.beyond3d.com/content/articles/8/>. Acesso em: 5 de janeiro de 2016.

Agradeço ao meu pai Jorge de Jesus Ganassim revisar o texto e apontar melhorias e aos meus amigos Adriano Rezende (engenheiro de software) e Heider Carlos (futuro engenheiro civil) o lerem e apoiarem e apontarem erros menores. Publicado originalmente neste endereço: https://jorgelucasti.blogspot.com/2016/01/quake-3-arena-e-o-metodo-fast-invsqrt.html