游戏技术宝典：游戏编程炫酷算法合集
招聘信息：
本文整理自知乎，文/我挑一些有趣的算法，希望尽量提及相关算法在游戏中的应用。光栅化 [1]：经典的绘画直线算法，后来还可以稍作修改用于绘画圆弧[2]，都不用三角函数或除数，只需用整数加法、减法和乘法。Perspective-Correct Texture Mapping [3]：透视正确的光栅化纹理贴图算法是1980才出现的。第一代Quake引擎引入后，才开始支持不垂直的墙、不水平的地面天花。（图片来自维基百科）Polygon Rasterization with Edge Function [4]：Bresenham算法如果用来画多边形，两个多边形的共边会被重绘。后来发明了使用简单的edge function去解决这个问题，而且适合并行的硬件实现。现在的GPU都是使用这个算法。全局光照Precomputed Radiance Transfer (PRT) with Spherical Harmonics（SH）[5]：储存静态环境对于各个方向光源的漫反射数据，可以实现动态低频光源的全局光照效果。这种表示方式非常神奇。Halo 3也使用到这种技术[6]。Screen-space Ambient Occlusion （SSAO）[7]：Crytek提出的首个屏幕空间环境光遮蔽算法，之后引来大量的研究及改进算法。也有用类似的概念去做近距离的反射，如SSDO[8]。Light Propagation Volume （LPV）[9]：Crytek提出的首个动态全局光照算法，不需要预计算。但要在体积数据中计算传播，性能较慢，所以之后再优化成 Cascaded LPV [10]。Voxel Cone Tracing [11]：也是不需要预计算的动态全局光照算法。把场景动态生成层阶式的体素数据（像mipmap那样的pre-filtering），从光源视角计算直接光照，然后逐像素追踪这组数据获取非直接光照。结果比LPV精确，也可以做到光泽反射（glossy reflection）。阴影Shadow Volume [12]：阴影体积是1977年发表的阴影技术，在屏幕空间光栅化阴影体积，可准确判断每个屏幕像素是否在阴影之内。可以处理平行光源和点光源的阴影。1991年[13]讲述如何用stencil buffer来实现此算法，适合在图形加速硬件（当时还没有所谓GPU）上使用。但很多人发现，如果摄像机在阴影体积内，就会出错。在年有多人发现一种解决方法，需要把John Carmack在2000年的电邮[14]中提及这个想法，后来成为2004年《毁灭战士3（Doom 3）》引擎的重要特徵，因他把这项技术发扬光大，即使他非首个发明人，此项技术通常被称为Carmack's Reverse。Parallel Split Shadow Map (PSSM) [15][16] / Cascaded Shadow Map（CSM）[17]：虽然Shadow Volume很吸引，但它需要大量的内存频宽，而且通常不能实现软阴影。后来大部分游戏改为使用Shadow Map（阴影贴图），这更适合GPU，并且可以通过多次采样（Percentage Closer Filtering, PCF）来实现软阴影。然而，阴影贴图也有许多问题，例如远近景物都采用同一张纹理，就会令到近景的精度不足，出现锯齿。2006年香港中文大学的博士生Fan Zhang等人发表了一种 PSSM 算法 [15]，为不同距离的场景渲染多张阴影贴图，在采样的时候按距离决定使用那一张。这个方法的变种CSM，在切割上和PSSM有点差异，被广泛使用于现时大部分游戏引擎中。Variance Shadow Map（VSM）[18]：之前谈到用PCF做软阴影，它的坏处就是要做多次采样。那么可否把阴影贴图直接模糊化来实现软阴影？答案是否定的。但是在2006年有学者发表了VSM，它是一种用统计方式来逼近软阴影的效果。参考：场景管理、： - Milo Yip 的回答Potential Visibility Set（PVS）Occlusion Culling by Software Rasterization动画/物理Particle SystemSmoothed Particle Hydrodynamics（SPH）Curl NoiseDual Quaternion Skinning碰撞测试（或称separating axis theorem/SAT）：凸形状相交测试的基本原理。中，其实背后也是使用了SAT。 (GJK距离算法)：计算两个凸形状的距离（可用于相交测试）：用于broad phase碰撞检测，找出物体AABB是否相交。对于时空上连续的物体运动，算法最坏O(n^2)、最好O(n)。人工智能A* path findingBehavior Tree*欢迎分享好的算法。参考[1] Bresenham, Jack E. "." IBM Systems journal 4.1 (1965): 25-30.&[2] Bresenham, Jack. "." Communications of the ACM 20.2 (1977): 100-106.&[3] Catmull, Ed, and Alvy Ray Smith. "." ACM SIGGRAPH Computer Graphics. Vol. 14. No. 3. ACM, 1980.&[4] Pineda, Juan. "." ACM SIGGRAPH Computer Graphics. Vol. 22. No. 4. ACM, 1988.[5] Sloan, Peter-Pike, Jan Kautz, and John Snyder. "." ACM Transactions on Graphics (TOG). Vol. 21. No. 3. ACM, 2002.&[6] Chen, Hao, and Xinguo Liu. "." ACM SIGGRAPH 2008 Games. ACM, 2008.&[7] Mittring, Martin. "." ACM SIGGRAPH 2007 courses. ACM, 2007.&[8] Ritschel, Tobias, Thorsten Grosch, and Hans-Peter Seidel. "." Proceedings of the 2009 symposium on Interactive 3D graphics and games. ACM, 2009.&[9] Kaplanyan, Anton. "." ACM SIGGRAPH Courses 7 (2009): 2.&[10] Kaplanyan, Anton, and Carsten Dachsbacher. "." Proceedings of the 2010 ACM SIGGRAPH symposium on Interactive 3D Graphics and Games. ACM, 2010.&[11] Crassin, Cyril, et al. "."Computer Graphics Forum. Vol. 30. No. 7. Blackwell Publishing Ltd, 2011.&[12] Crow, Franklin C. "." ACM SIGGRAPH Computer Graphics. Vol. 11. No. 2. ACM, 1977.&[13] Heidmann, Tim. "Real shadows, real time." Iris Universe 18 (1991): 28-31.[14] Carmack, John, "", 23 May 2000.&[15] Zhang, Fan, et al. "Parallel-split shadow maps for large-scale virtual environments." Proceedings of the 2006 ACM international conference on Virtual reality continuum and its applications. ACM, 2006.[16] Zhang, Fan, Hanqiu Sun, and Oskari Nyman. "Parallel-split shadow maps on programmable gpus." GPU Gems 3 (2007): 203-237. GPU Gems 3 - Chapter 10. Parallel-Split Shadow Maps on Programmable GPUs[17] Dimitrov, Rouslan. "." Developer Documentation, NVIDIA Corp (2007).&[18] Donnelly, William, and Andrew Lauritzen. "."Proceedings of the 2006 symposium on Interactive 3D graphics and games. ACM, 2006.&
微信扫一扫
订阅每日移动开发及APP推广热点资讯公众号：CocoaChina
您还没有登录！请或
点击量4613点击量4418点击量4287点击量3892点击量3818点击量3800点击量3521点击量3507点击量3044
&2016 Chukong Technologies,Inc.
京公网安备89热门排序 |
Read The Fucking Document ！&br&&br&&br&刚好够五个人，这句话拥有着终极的劝世意义，部分词汇和符号也隐含着行为主义的乖张，老少皆宜，童叟无期，走在路上回头率爆棚！
Read The Fucking Document ！ 刚好够五个人，这句话拥有着终极的劝世意义，部分词汇和符号也隐含着行为主义的乖张，老少皆宜，童叟无期，走在路上回头率爆棚！
已有帐号？
无法登录？
社交帐号登录关于卡马克大神平方根算法并没有那么神秘，本质上这个超级Magic Number：0x5f3759df，是根据牛顿迭代，泰勒级数以及浮点数在计算机中的存储使用机器运算而来的。详情在&a href=&///?target=http%3A///vagerent/archive//794695.html& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&卡马克快速平方根---平方根倒数算法 [转]&i class=&icon-external&&&/i&&/a&以及表述的很清楚了，原文未知出处，侵删。&br&更多请看&a href=&///?target=http%3A//blog.csdn.net/yutianzuijin/article/details/& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&快速浮点开方运算&i class=&icon-external&&&/i&&/a&&br&&blockquote&&p& 快速平方根（平方根倒数）算法&/p&&p&日前在书上看到一段使用多项式逼近计算平方根的代码，至今都没搞明白作者是怎样推算出那个公式的。但在尝试解决问题的过程中，学到了不少东西，于是便有了这篇心得，写出来和大家共享。其中有错漏的地方，还请大家多多指教。&/p&&p&的确，正如许多人所说的那样，现在有有FPU，有3DNow，有SIMD，讨论软件算法好像不合时宜。关于sqrt的话题其实早在2003年便已在 &a href=&///?target=http%3A//GameDev.net& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://&/span&&span class=&visible&&GameDev.net&/span&&span class=&invisible&&&/span&&i class=&icon-external&&&/i&&/a&上得到了广泛的讨论（可见我实在非常火星了，当然不排除还有其他尚在冥王星的人，嘿嘿）。而尝试探究该话题则完全是出于本人的兴趣和好奇心（换句话说就是无知）。&/p&&p&我只是个beginner，所以这种大是大非的问题我也说不清楚（在&a href=&///?target=http%3A//GameDev.net& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://&/span&&span class=&visible&&GameDev.net&/span&&span class=&invisible&&&/span&&i class=&icon-external&&&/i&&/a&上也有很多类似的争论）。但无论如何，Carmack在DOOM3中还是使用了软件算法，而多知道一点数学知识对3D编程来说也只有好处没坏处。3D图形编程其实就是数学，数学，还是数学。&/p&&p&=========================================================&/p&&br&&p&约翰-卡马克（John Carmack）是Quake-III Arena (雷神之锤3)的3D引擎的开发者。QUAKE的开发商ID SOFTWARE 遵守GPL协议，公开了QUAKE-III的原代码，让世人有幸目睹Carmack传奇的3D引擎的原码。这是QUAKE-III原代码的下载地址： &a href=&///?target=http%3A///file.x%3Ffid%3D7547& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://www.&/span&&span class=&visible&&/file.x?&/span&&span class=&invisible&&fid=7547&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&。&/p&&br&&p&在3D图形编程中，经常要求平方根或平方根的倒数，例如：求向量的长度或将向量归一化。C数学函数库中的sqrt具有理想的精度，但对于3D游戏程式来说速度太慢。我们希望能够在保证足够的精度的同时，进一步提高速度。&/p&&p&Carmack在QUAKE3中使用了下面的算法，它第一次在公众场合出现的时候，几乎震住了所有的人。据说该算法其实并不是Carmack发明的，它真正的作者是Nvidia的Gary Tarolli（未经证实）。&br&－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－&br&//&br&// 计算参数x的平方根的倒数&br&//&br&float InvSqrt (float x)&br&{&br&float xhalf = 0.5f*x;&br&int i = *(int*)&x;&br&i = 0x5f3759df - (i && 1); // 计算第一个近似根&br&x = *(float*)&i;&br&x = x*(1.5f - xhalf*x*x); // 牛顿迭代法&br&&br&}&br&－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－&br&该算法的本质其实就是牛顿迭代法（Newton-Raphson Method，简称NR），而NR的基础则是泰勒级数（Taylor Series）。NR是一种求方程的近似根的方法。首先要估计一个与方程的根比较靠近的数值，然后根据公式推算下一个更加近似的数值，不断重复直到可以获得满意的精度。其公式如下：&br&－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－&br&函数：y=f(x)&br&其一阶导数为：y'=f'(x)&br&则方程：f(x)=0 的第n+1个近似根为&br&x[n+1] = x[n] - f(x[n]) / f'(x[n])&br&－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－&br& NR最关键的地方在于估计第一个近似根。如果该近似根与真根足够靠近的话，那么只需要少数几次迭代，就可以得到满意的解。&/p&&p&现在回过头来看看如何利用牛顿法来解决我们的问题。求平方根的倒数，实际就是求方程1/(x^2)-a=0的解。将该方程按牛顿迭代法的公式展开为：&br&x[n+1]=1/2*x[n]*(3-a*x[n]*x[n])&br& 将1/2放到括号里面，就得到了上面那个函数的倒数第二行。&/p&&p&接着，我们要设法估计第一个近似根。这也是上面的函数最神奇的地方。它通过某种方法算出了一个与真根非常接近的近似根，因此它只需要使用一次迭代过程就获得了较满意的解。它是怎样做到的呢？所有的奥妙就在于这一行：&br&i = 0x5f3759df - (i && 1); // 计算第一个近似根&/p&&p&超级莫名其妙的语句，不是吗？但仔细想一下的话，还是可以理解的。我们知道，IEEE标准下，float类型的数据在32位系统上是这样表示的（大体来说就是这样，但省略了很多细节，有兴趣可以GOOGLE）：&br&－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－&br&bits：31 30 ... 0&br&31：符号位&br&30-23：共8位，保存指数（E）&br&22-0：共23位，保存尾数（M）&br&－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－&br&所以，32位的浮点数用十进制实数表示就是：M*2^E。开根然后倒数就是：M^(-1/2)*2^(-E/2)。现在就十分清晰了。语句i& &1其工作就是将指数除以2，实现2^(E/2)的部分。而前面用一个常数减去它，目的就是得到M^(1/2)同时反转所有指数的符号。&/p&&p&至于那个0x5f3759df，呃，我只能说，的确是一个超级的Magic Number。&/p&&p&那个Magic Number是可以推导出来的，但我并不打算在这里讨论，因为实在太繁琐了。简单来说，其原理如下：因为IEEE的浮点数中，尾数M省略了最前面的1，所以实际的尾数是1+M。如果你在大学上数学课没有打瞌睡的话，那么当你看到(1+M)^(-1/2)这样的形式时，应该会马上联想的到它的泰勒级数展开，而该展开式的第一项就是常数。下面给出简单的推导过程：&br&－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－&br&对于实数R&0，假设其在IEEE的浮点表示中，&br&指数为E，尾数为M，则：&/p&&p&R^(-1/2)&br&= (1+M)^(-1/2) * 2^(-E/2)&/p&&p&将(1+M)^(-1/2)按泰勒级数展开，取第一项，得：&/p&&p&原式&br&= (1-M/2) * 2^(-E/2)&br&= 2^(-E/2) - (M/2) * 2^(-E/2)&/p&&p&如果不考虑指数的符号的话，&br&(M/2)*2^(E/2)正是(R&&1)，&br&而在IEEE表示中，指数的符号只需简单地加上一个偏移即可，&br&而式子的前半部分刚好是个常数，所以原式可以转化为：&/p&&p&原式 = C - (M/2)*2^(E/2) = C - (R&&1)，其中C为常数&/p&&p&所以只需要解方程：&br&R^(-1/2)&br&= (1+M)^(-1/2) * 2^(-E/2)&br&= C - (R&&1)&br&求出令到相对误差最小的C值就可以了&br&－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－&br&上面的推导过程只是我个人的理解，并未得到证实。而Chris Lomont则在他的论文中详细讨论了最后那个方程的解法，并尝试在实际的机器上寻找最佳的常数C。有兴趣的朋友可以在文末找到他的论文的链接。&/p&&p&所以，所谓的Magic Number，并不是从N元宇宙的某个星系由于时空扭曲而掉到地球上的，而是几百年前就有的数学理论。只要熟悉NR和泰勒级数，你我同样有能力作出类似的优化。&/p&&p&在&a href=&///?target=http%3A//GameDev.net& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://&/span&&span class=&visible&&GameDev.net&/span&&span class=&invisible&&&/span&&i class=&icon-external&&&/i&&/a&上有人做过测试，该函数的相对误差约为0.177585%，速度比C标准库的sqrt提高超过20%。如果增加一次迭代过程，相对误差可以降低到e-004 的级数，但速度也会降到和sqrt差不多。据说在DOOM3中，Carmack通过查找表进一步优化了该算法，精度近乎完美，而且速度也比原版提高了一截（正在努力弄源码，谁有发我一份）。&/p&&p&值得注意的是，在Chris Lomont的演算中，理论上最优秀的常数（精度最高）是0x5f37642f，并且在实际测试中，如果只使用一次迭代的话，其效果也是最好的。但奇怪的是，经过两次NR后，在该常数下解的精度将降低得非常厉害（天知道是怎么回事！）。经过实际的测试，Chris Lomont认为，最优秀的常数是0x5f375a86。如果换成64位的double版本的话，算法还是一样的，而最优常数则为0x5fe6ec85e7de30da（又一个令人冒汗的Magic Number - -b）。&/p&&p&这个算法依赖于浮点数的内部表示和字节顺序，所以是不具移植性的。如果放到Mac上跑就会挂掉。如果想具备可移植性，还是乖乖用sqrt好了。但算法思想是通用的。大家可以尝试推算一下相应的平方根算法。&/p&&p&下面给出Carmack在QUAKE3中使用的平方根算法。Carmack已经将QUAKE3的所有源代码捐给开源了，所以大家可以放心使用，不用担心会受到律师信。&br&－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－&br&//&br&// Carmack在QUAKE3中使用的计算平方根的函数&br&//&br&float CarmSqrt(float x){&br&union{&br&int intP&br&float floatP&br&}&br&union{&br&int intP&br&float floatP&br&} convertor2;&br&convertor.floatPart =&br&convertor2.floatPart =&br&convertor.intPart = 0x1FBCF800 + (convertor.intPart && 1);&br&convertor2.intPart = 0x5f3759df - (convertor2.intPart && 1);&br&return 0.5f*(convertor.floatPart + (x * convertor2.floatPart));&br&}&br&－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－&/p&&/blockquote&&br&&br&&p&故事还没完，普渡大学的数学家Chris Lomont看了以后也觉得很有趣，决定要研究一下卡马克弄出来的这个猜测值有什么奥秘。Lomont也是个牛人，在精心研究之后从理论上也推导出一个最佳猜测值，和卡马克的数字非常接近, 0x5f37642f。Lomont计算出结果以后非常满意，于是拿自己计算出的起始值和卡马克的神秘数字做比赛，看看谁的数字能够更快更精确的求得平方根。结果居然还是卡马克赢了... &/p&&p&最后Lomont怒了，采用暴力方法一个数字一个数字试过来，终于找到一个比卡马克数字要好上那么一丁点的数字，虽然实际上这两个数字所产生的结果非常近似，这个暴力得出的数字是0x5f375a86。&/p&&p&Lomont为此写下一篇论文，&Fast Inverse Square Root&。论文详见：&a href=&///?target=http%3A///data/InvSqrt.pdf& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://www.&/span&&span class=&visible&&/data/InvSq&/span&&span class=&invisible&&rt.pdf&/span&&span class=&ellipsis&&&/span&&i class=&icon-external&&&/i&&/a&。&/p&&br&&p&除此之外还有卡马克卷轴算法等，更多关于卡马克的事迹可以在google上找到很多。&/p&&br&你们还可看看他儿子的主页 :
&a href=&///?target=http%3A///& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://www.&/span&&span class=&visible&&/&/span&&span class=&invisible&&&/span&&i class=&icon-external&&&/i&&/a&，这稚嫩的笔触，极高的颜值，和这编程技术让人感慨大神就是不一样。
关于卡马克大神平方根算法并没有那么神秘，本质上这个超级Magic Number：0x5f3759df，是根据牛顿迭代，泰勒级数以及浮点数在计算机中的存储使用机器运算而来的。详情在以及表述的很清楚了，原文未知出处，侵删。 更…
已有帐号？
无法登录？
社交帐号登录
3648 人关注
1677 条内容
438 人关注
161 条内容
318 人关注
409 条内容
41651 人关注
974 条内容
1999 人关注
128 条内容2790被浏览117105分享邀请回答6添加评论分享收藏感谢收起