AvisChen's profileavis每天都想些啥?PhotosBlogListsMore Tools Help

Blog


    April 04

    转自好友shark曾经的一篇:谈论 Quake-III原代码里的神奇的浮点开方函数!

     

    引用

    Quake-III原代码里的神奇的浮点开方函数!
    Quake-III Arena (雷神之锤3)是我大学时期爱玩的经典游戏之一。喜爱这个系列的游戏,不仅因为画面和内容,更重要的是我得计算计配置低,但Q3A却能极其流畅地运行。这要归功于它3D引擎的开发者约翰-卡马克(John Carmack)。事实上早在90年代初DOS时代,只要能在PC上搞个小动画都能让人惊叹一番的时候,John Carmack就推出了石破天惊的Castle Wolfstein, 然后再接再励,doom, doomII, Quake...每次都把3-D技术推到极致。他的3D引擎代码资极度高效,几乎是在压榨PC机的每条运算指令。当初MS的Direct3D也得听取他的意见,修改了不少API。

      最近,QUAKE的开发商ID software 遵守GPL协议,公开了QUAKE-III的原代码,让世人有幸目睹Carmack传奇的3D引擎的原码。
      这是QUAKE-III原代码的下载地址:
      http://www.fileshack.com/file.x?fid=7547
      注意下载时,第一次弹出页面要求登陆,选择上面的不登陆(速度受限制),然后选择“download now”,弹出窗选左边排队等待。我运气好,第二次就下到了,速度还很快。

      我们知道,越底层的函数,调用越频繁。3D引擎归根到底还是数学运算。那么找到最底层的数学运算函数(在game/code/q_math.c), 必然是精心编写的。里面有很多有趣的函数,很多都令人惊奇,估计我们几年时间都学不完。

      最令人惊讶的是平方根函数sqrt()。课本里说的,基本上是牛顿跌代法,通过若干步的叠代,结果越来越接近真实结果。
      但q_math.c里面却给出了这样奇异的平方根函数:(我的注释)
    float Q_rsqrt( float number )
    {
      long i;
      float x2, y;
      const float threehalfs = 1.5F;
      x2 = number * 0.5F;
      y  = number;
      i  = * ( long * ) &y;         // 浮点数按BIT强行赋给长整形
      i  = 0x5f3759df - ( i >> 1 ); // 没天理!!!!!
      y  = * ( float * ) &i;
      y  = y * ( threehalfs - ( x2 * y * y ) ); // 第1次叠代
      // y  = y * ( threehalfs - ( x2 * y * y ) ); // 第2次叠代,可以删除
      #ifndef Q3_VM
      #ifdef __linux__
        assert( !isnan(y) ); // bk010122 - FPE?
      #endif
      #endif
      return y;
    }
       函数返回1/sqrt(x),这个函数在图像处理中比sqrt(x)更有用。
       注意到这个函数只用了一次叠代!(其实就是根本没用叠代,直接运算)。编译,实验,这个函数不仅工作的很好,而且比标准的sqrt()函数快4倍!要知道,编译器自带的函数,可是经过严格仔细的汇编优化的啊!
      
      这个简洁的函数,最核心,也是最让人费解的,就是标注了“没天理”那句:(原代码的注释是 what the fu*ck ?)
         i  = 0x5f3759df - ( i >> 1 ); // 没天理!!!!!

    再加上y  = y * ( threehalfs - ( x2 * y * y ) );
    两句话就完成了开方运算!而且注意到,核心那句是定点移位运算,速度极快!特别在很多没有乘法指令的RISC结构CPU上,这样做是极其高效的。

      最让人感兴趣的,是那个常数0x5f3759df。我的猜测是这样的:牛顿叠代法用1/2作为初始点进行N步叠代得到精确结果。这里计算一个最佳猜测值i,然后,以i为起始点,只需要做1步叠代,就可以得到相当精确的结果。如果做2次叠代,就更为精确了(屏蔽掉那句)。


       搜索包含关键字“0x5f3759df”的文章,找到普渡大学数学系的Chris Lomont的一篇论文,专门对这个函数研究,尝试用严格的方法推导出这个常数(他还提到有人认为这个函数是在NVidia工作过的Gary Tarolli写的)。Chris推出的常数是0x5f37642f),和Q_rsqrt里的稍有不同,而且实际表现也稍有不如。卡马克到底怎么推出这个常数的就是谜了。

    论文下载地址:
    http://www.math.purdue.edu/~clomont/Math/Papers/2003/InvSqrt.pdf

    最后,给出最精简的1/sqrt()函数:
    float InvSqrt(float x)
    {
      float xhalf = 0.5f*x;
      int i = *(int*)&x; // get bits for floating value
      i = 0x5f375a86- (i>>1); // gives initial guess y0
      x = *(float*)&i; // convert bits back to float
      x = x*(1.5f-xhalf*x*x); // Newton step, repeating increases accuracy
      return x;
    }  

      大家可以尝试在PC机、51、AVR、430、ARM、上面编译并实验,惊讶一下它的工作效率。

       技术方面就说到这,看看别人对一个最普通函数都压榨到这种地步,再对比国内不求甚解的所谓“搞技术”,再看自己浮躁的心态,自觉惭愧不已...

    Comments

    Please wait...
    Sorry, the comment you entered is too long. Please shorten it.
    You didn't enter anything. Please try again.
    Sorry, we can't add your comment right now. Please try again later.
    To add a comment, you need permission from your parent. Ask for permission
    Your parent has turned off comments.
    Sorry, we can't delete your comment right now. Please try again later.
    You've exceeded the maximum number of comments that can be left in one day. Please try again in 24 hours.
    Your account has had the ability to leave comments disabled because our systems indicate that you may be spamming other users. If you believe that your account has been disabled in error please contact Windows Live support.
    Complete the security check below to finish leaving your comment.
    The characters you type in the security check must match the characters in the picture or audio.

    To add a comment, sign in with your Windows Live ID (if you use Hotmail, Messenger, or Xbox LIVE, you have a Windows Live ID). Sign in


    Don't have a Windows Live ID? Sign up

    Trackbacks

    The trackback URL for this entry is:
    http://avischen82.spaces.live.com/blog/cns!8D42178A2EE9F6C4!186.trak
    Weblogs that reference this entry
    • None