Jeffrey Cross
Jeffrey Cross

Raiz quadrada inversa rápida do Quake

A função de raiz quadrada inversa (1 / sqrt (x)) é usada intensamente durante o ciclo de tração de um mecanismo de jogo para normalizar vetores em vetores “unitários” com um comprimento de 1. Vetores normalizados são importantes porque quando você pega o produto escalar de dois eles (Ax * Bx + Ay * Por + Az * Bz), o resultado é o cosseno do ângulo entre os dois vetores.

Portanto, imagine que você tenha um vetor que descreva a maneira como uma superfície está voltada (sua superfície normal) e um segundo vetor que descreva a direção da luz do sol. Se o vetor de luz solar é paralelo à sua superfície normal, o que significa que a superfície está voltada para o sol, o produto de ponto dos dois vetores normalizados é o cosseno de 0, que é 1. Se a superfície estiver a 90 graus do sol, o produto escalar é o cosseno de 90, que é 0. Qualquer coisa entre e você obtém um valor entre 0 e 1, que essencialmente permite que você descreva com que intensidade você deve iluminar essa superfície.

Agora, você executa este cálculo em todos os triângulos visíveis em um jogo 3D, e faz tudo isso 30 ou mais vezes por segundo, e você tem um efeito de iluminação de fonte de ponto básico! Lembre-se, no entanto, que você precisa dessa função de raiz quadrada inversa para calcular vetores unitários para cada um desses triângulos. A operação de raiz quadrada é lenta. Faça isso milhares de vezes por loop de sorteio e você terá um jogo lento.

Mas se você não se importa em jogar fora um pouco de precisão, há um caminho mais rápido.

Há uma função de raiz quadrada inversa que muitos mecanismos de jogos usam e que, segundo boatos, foram originados no Quake III pelo programador da Nvidia, Gary Tarolli. Se parece com isso:

float InvSqrt (flutuante x) {float xhalf = 0.5f * x; int i = * (int *) & x; // obtém bits para o valor flutuante i = 0x5f3759df - (i >> 1); // dá palpite inicial y0 x = * (float *) & i; // converte bits de volta para float x = x * (1.5f-xhalf * x * x); // Newton step, a repetição aumenta a precisão return x; }

Espere, o que foi isso?!?!

Então, quando Newton surgiu com uma maneira inteligente de aproximar a raiz quadrada inversa. Primeiro, você divide o número original x por dois. Vamos chamar isso de "xhalf". Então, você faz um palpite razoavelmente próximo da raiz quadrada inversa. Vamos chamar isso de g. Em seguida, você pega essas duas variáveis ​​e executa esse cálculo (que você reconhecerá como a última etapa na função InvSqrt):

g = g * (1,5 - xhalf * g * g)

Se você fizer isso repetidas vezes, substituindo o g atualizado em cada iteração, g irá aprimorar rapidamente a raiz quadrada inversa de x! Na verdade, se você escolher um g decente para começar, uma ou duas iterações o aproximará do valor correto.

A questão é: como você acha essa primeira estimativa para o primeiro g? Os codificadores de mecanismo de jogo usam truque com como os números de ponto flutuante são representados em binário, com o expoente e a mantissa quebrados, semelhante à notação científica. Em um float de 32 bits, o bit mais à esquerda é um bit de sinal e é 0 para números positivos. Isso é seguido por 8 bits de expoente (inclinado por 127 para representar expoentes negativos e positivos), e os 23 bits finais representam a mantissa.

Bem, para fazer uma raiz quadrada inversa, você basicamente precisa multiplicar o expoente por -1/2. Quando você desloca esses bits para a direita (uma operação muito rápida), o efeito sobre o expoente é dividi-lo por 2. Você ainda precisa subtrair o expoente de 0 para alterar seu sinal, e o que você faz sobre o mantissa que também foi afetada na operação bit shift?

É aí que entra o número mágico 0x5f3759df. É absolutamente insensato, mas ao subtrair o resultado do bit shift de 0x5f3759df, a mantissa é redefinida para perto de seu estado original e o expoente é subtraído de 0 (considerando o viés de 127) .

O resultado é muito próximo da raiz quadrada inversa. Perto o suficiente para uma única passagem pela equação de Newton, para chegar a um valor preciso o suficiente para fins práticos.

Compreender a raiz quadrada inversa rápida do quake Raiz quadrada inversa rápida - detalhes e matemática por trás do número mágico (PDF)

Ação

Deixar Um Comentário