抱歉,您的浏览器无法访问本站
本页面需要浏览器支持(启用)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,因此表示22=42^2 = 4.

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

所以最终十进制数字就是1.062522=4.251.0625 \cdot 2^2 = 4.25.

近似替换

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

则原float数字可以表示为

(1+M223)×2E127\left(1+\frac{M}{2^{23}}\right) \times 2^{E-127}

取2为底的对数,得

log2(1+M223)+E127\log_2 \left(1+\frac{M}{2^{23}}\right)+E-127

在上面的分析中,我们知道M223\LARGE \frac{M}{2^{23}}一定小于1,因此上述表达式可以近似写成

M223+E+μ127\frac{M}{2^{23}}+E+\mu-127

提出1223\frac{1}{2^{23}},得

1223(M+223E)+μ127\frac{1}{2^{23}}\left(M+2^{23} \cdot E\right)+\mu-127

位操作

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

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

现在开始正式计算yy的平方根倒数,直接计算的效率低下,而通过上面的分析,我们可以用log的方法来加速计算.

yy的平方根倒数为

S=1ylog2S=12log2yS=\frac{1}{\sqrt y}\rightarrow\log_2{S}=-\frac12\log_2y

因为上面的代码将yy变成了longlong类型,所以用MyM_yEyE_y替换上面的M,EM,E,分别表示yy的低23位和高9位,所以y=223Ey+Myy=\textcolor{red}{2^{23}\cdot E_y+M_y},同理S=223ES+MSS=\textcolor{green}{2^{23}\cdot E_S+M_S}

log2(223ES+MS)=12log2(223Ey+My)\log_2{\left(\textcolor{green}{2^{23}\cdot E_S+M_S}\right)}=-\frac12\log_2{\left(\textcolor{red}{2^{23}\cdot E_y+M_y}\right)}

使用之前提到的近似替换方法,替换两个对数,得

1223(223ES+MS)+μ127=12[1223(223Ey+My)+μ127]\frac1{2^{23}}{\left(\textcolor{green}{2^{23}\cdot E_S+M_S}\right)}+\mu-127=-\frac12\left[\frac1{2^{23}}{\left(\textcolor{red}{2^{23}\cdot E_y+M_y}\right)}+\mu-127\right]

化简,得到

223ES+MS=32223(127μ)12(223Ey+My)\textcolor{green}{2^{23}\cdot E_S+M_S}=\frac32\cdot 2^{23}(127-\mu)-\frac12 \left(\textcolor{red}{2^{23}\cdot E_y+M_y}\right)

上面说过y=223Ey+My,S=223ES+MSy=\textcolor{red}{2^{23}\cdot E_y+M_y},S=\textcolor{green}{2^{23}\cdot E_S+M_S},所以我们再替换回去

S=32223(127μ)y2\textcolor{green}{S}=\frac32\cdot 2^{23}(127-\mu)- \textcolor{red}{\frac y2}

所以S=numbery2S=number-\frac y2,其中numbernumber是一个常数,右移一位即可实现除以2,这就对应了下一行代码

1
i = number - (i >> 1);

常数的由来

实际上该常数的由来目前还是未知的,David Eberly博士曾经做出了最接近的解释,但实际上是错误的.不同的论文给出了不同的取值,并且都有各自的理由,而且一致认为源代码里的值是不好的,这里不做讨论,直接使用源代码的值代入

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

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

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

1
y = *(float *) &i;

牛顿迭代法

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

yyxx的平方根倒数,则函数表达式为

1+x=1ln21+x=\frac{1}{\ln 2}

转换为x关于y的函数,得到

y=1xy=\frac{1}{\sqrt x}

利用牛顿迭代法

f(y)=1y2x=0f(y)=\frac 1{y^2}-x=0

带入Xn=yX_n=y,得到

xn+1=xnf(xn)f(xn)x_{n+1}=x_n -\frac{f(x_n)}{f^{'}(x_n)}

化简

yn+1=yf(y)f(y)=y1y2x2y3=y+yy3x2\begin{array}{ll} y_{n+1} &=y-\frac{f(y)}{f^{'}(y)} \\\\ &=y-\frac{ \frac{1}{y^2}-x }{ -\frac{2}{y^3} } \\\\ &=y+\frac{y-y^3 \cdot x}{2} \end{array}

得到最后一行代码.

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

评论