抱歉,您的浏览器无法访问本站
本页面需要浏览器支持(启用)JavaScript
了解详情 >

单位向量时需要用到平方根倒数,而计算单位向量在游戏引擎中会大量使用,属于底层代码,因此其效率将会直接影响游戏体验。

雷神之锤3中使用了以下代码

1
2
3
4
5
6
7
8
9
10
11
12
float Q_rsqrt(float number) {
long i;
float x2, y;
const float threehalfs = 1.5F;
x2 = number * 0.5F;
y = number;
i = *(long *) &y;
i = 0x5F3759DF - (i >> 1);
y = *(float *) &i;
y = y * (threehalfs - (x2 * y * y));
return y;
}

本文将分析上述代码的含义

float内存结构

float类型总共占用32位,其内存结构采用科学计数法表示。第一位表示符号,接下来8位表示指数,后23位表示尾数

以4.25为例,其内存中的结构为
0 10000001 00010000000000000000000
第一位0表示这个数是正数.

接下来的8位表示指数,其指在0-255之间,但是这样就无法表示负指数了,因此规定正指数第一位是1,负指数第一位是0,将这8位转换成10进制后减去127就是实际的指数。这里的10000001转换成10进制后是129,因此表示2^2 = 4.

接下来的23位表示尾数。前面提到float在内存中是以科学计数法形式表示,在十进制中,科学计数法的个位数一定在1-9之间,因此在二进制中,科学计数法的个位数一定是1,既然一定是1,那就没有必要保存了,因此尾数0001实际上是1.0001,转换成十进制就是1.0625.

所以最终十进制数字就是1.0625 * 2^2 = 4.25.

等价无穷小方法

我们令8位指数转换成为十进制后为E,23位尾数转换成十进制后为W.

则原float数字可以表示为
DearXuan
取2为底的对数,得
DearXuan
在上面的分析中,我们知道M/2^23一定小于1,此时对数公式满足log(1+x)等价无穷小模型.

我们用x+μ来近似代替2为底的对数。现在上述表达式可以写成
DearXuan
提出1/2^23,得
DearXuan

位操作

float无法进行位操作,而long可以,并且都是4字节,因此可以把float*转换成long*来进行位操作.

1
2
float y = number;
long i = *(long *) &y;

计算y的平方根倒数,就是计算y的-0.5次方,直接计算的效率低下,但是我们已经发现可以用log的方法来加速计算.


将y用上面的表达式替换


DearXuan
取对数
DearXuan
带入上面的表达式
DearXuan
化简
DearXuan
可以看到右边的式子是一个常数减去一个变量的一半,这个变量就是代码中的number.

如何求μ的值?


观察函数图像
DearXuan
我们希望y=x+μ尽可能均分红色和黄色曲线,因此我们可以作红色曲线的切线,求出它和y轴的交点.
DearXuan
DearXuan
代进原方程,得到y≈0.528766,x≈0.442695

相减,得到μ=(y-x) / 2 = 0.0430355

将这个μ的值代入表达式,计算结果转换为十六进制,就是0x5F3759DF

1
i = 0x5F3759DF - (i >> 1);

由于float无法进行位运算,所以将它转换成long后再位移,虽然这样会损失精度,但是影响可以忽略不计.

此时已经运算完成,再把long转换回float

1
y = *(float *) &i;

牛顿迭代法

当前得到的y仍然是一个近似值.

设y是x的平方根倒数,则函数表达式为
DearXuan
转换为x关于y的函数,得到
DearXuan
利用牛顿迭代法
DearXuan
带入Xn=y,得到
DearXuan
化简
DearXuan
DearXuan
DearXuan
得到最后一行代码.

1
y = y * (threehalfs - (x2 * y * y));

评论