-
Quake-III
Arena
(
雷神之锤
3)
是
90<
/p>
年代的经典游戏之一。
该系列的游戏不但画
面和内容不错,而且即使计算机配置低,也能极其流畅地运行。这要归功于它
3
D
引擎的开发者约翰
-
卡马克(
John
Carmack
)。事实上早在
90
年代初
DOS
p>
时
代,只要能在
PC
上搞个小动画都能让人惊叹一番的时候,
John
Carm
ack
就推
出了石破天惊的
Castl
e
Wolfstein,
然后再接再励,
doom,
doomII,
Quake...
每
次都把
3-D
技术推到极致。他的
p>
3D
引擎代码资极度高效,几乎是在压榨
P
C
机
的每条运算指令。当初
MS
的
Direct3D
也得听取他的意见,修改
了不少
API
。
最近,
QUAKE
的开发商
ID
SOFTWARE
遵守
GPL
协议,公开了
QUAKE-III
的原代码,让世人有幸目睹
Carmack
传奇的
3D
引擎的原码。
这是
QUAKE-
III
原代码的下载地址:
/file.x?fid=7547
(
下面是官方的下载网址,
搜索
“quake3
-1.32b-
”
可以找到一大堆中文
网页的
ftp:///idstuff/source/
)
我们知道,越底层的函数,调
用越频繁。
3D
引擎归根到底还是数学运算。那
么找到最底层的数学运算函数(在
game/code/q_math.c
p>
),
必然是精心编写
的。里面有很多有趣的函数,很多都令人惊奇,估计我们几年时间都学不完。
p>
在
game/code/q_math.c
里发现了这样一段代码。
它的作用是将一个数开平方并
取倒,经
测试这段代码比
(float)(1.0/sqrt(x))
快
4
倍:
float
Q_rsqrt(
float
number
)
{
long
i;
float
x2,
y;
const
float
threehalfs
=
1.5F;
x2
=
number
*
0.5F;
y
=
number;
i
=
*
(
long
*
)
&y;
//
evil
floating
point
bit
level
hacking
i
=
0x5f3759df
-
(
i
>>
1
);
//
what
the
fuck?
y
=
*
(
float
*
)
&i;
y
=
y
*
(
threehalfs
-
(
x2
*
y
*
y
)
);
//
1st
iteration
//
y
=
y
*
(
threehalfs
-
(
x2
*
y
*
y
)
);
//
2nd
iteration,
this
can
be
re
moved
#ifndef
Q3_VM
#ifdef
__linux__
assert(
!isnan(y)
);
//
bk010122
-
FPE?
#endif
#endif
return
y;
}
函数返回
1/sqrt(x)
,这个函数在图像处理中比
sqrt(x)
更有用。
注意到这个函
数只用了一次叠代!(其实就是根本没用叠代,直接运算)。
编译,实验,这个函数不仅
工作的很好,而且比标准的
sqrt()
函数快
4
倍!要知
道,编译器自带的函数,可是经过严格仔细
的汇编优化的啊!
p>
这个简洁的函数,最核心,也是最让人费解的,就是标注了
“
what
the
fuck?”
的一句
i
=
0x5f3759df
-
(
i
>>
1
);
再加上
y
=
y
*
(
threehalfs
-
(
x2
*
y
*
y
)
);
两句话就完成了开方运算!而且注意到,核心那句是定点
移位运算,速度极快!
特别在很多没有乘法指令的
RISC
p>
结构
CPU
上,这样做是极其高效的。
p>
算法的原理其实不复杂
,
就是牛顿迭代法
,
用
x-f(
x)/f'(x)
来不断的逼近
f(x)=a
< br>的
根。
简单来说比如求平方根
,f(x)=x^2=a
,f'(x)=
2*x,f(x)/f'(x)=x/2,<
/p>
把
f(x)
代入
x-f(x)/f'(x)
后有
(x+a/x)/2
,现在我们选
a=5,
选一个猜测值比如
2
,
那么我们可以这么算
5/2
=
2.5;
(2.5+2)/2
=
2.25;
5/2.25
=
xxx;
(2.25+xx
x)/2
=
xxxx ...
这样反复迭代
下去,结果必定收敛于
sqrt(5)
,没错,一般的求
平方根都是这么算的但是卡马克
(quake3
作者
)
真正牛
B
的地方是他选择了一个
神秘的常数
0x5f3759df
来计算那个猜测值就是我们加注释的那一行
,
< br>那一行算
出的值非常接近
1/sqrt(n),
这样我们只需要
2
次牛
顿迭代就可以达到我们所需
要的精度
.
好吧
如果
这个还不算
NB,
接着看
:
普渡大学的数学家
Chris
p>
Lomont
看了以后觉得有趣,决定要研究一下卡马克弄
出来的这个猜测值有什么奥秘。
Lomont
也
是个牛人,在精心研究之后从理论上
也推导出一个最佳猜测值,
和卡马克的数字非常接近
,
0x5f37642f
。
卡马克真牛,
他是外星人吗?
< br>
传奇并没有在这里结束。
Lomont
计算出结果以后非常满意,于是拿自己计算出
p>
的起始值和卡马克的神秘数字做比赛,
看看谁的数字能够更快更精确
的求得平方
根。结果是卡马克赢了
...
谁也不知道卡马克是怎么找到这个数字的。
最后
Lo
mont
怒了,采用暴力方法一个数字一个数字试过来,终于找到一个比卡
马克数
字要好上那么一丁点的数字,虽然实际上这
两个数字所产生的结果非常
近似,这个暴
力得出的数字是
0x5f375a86
。
< br>
Lomont
为此写下一篇论文,
Inverse
Square
Root
。
-
-
-
-
-
-
-
-
-
上一篇:apa 规范具体中文要求及例子
下一篇:英语专业毕业论文撰写规范