游戏编程里面有哪些经典或者很酷的算法?

发表于2015-09-11
评论0 1.13w浏览

想免费获取内部独家PPT资料库?观看行业大牛直播?点击加入腾讯游戏学院游戏程序行业精英群

711501594

suanfa500.jpg

我挑一些有趣的算法,希望尽量提及相关算法在游戏中的应用。

光栅化

  • Bresenham's line algorithm [1]:经典的绘画直线算法,后来还可以稍作修改用于绘画圆弧[2],都不用三角函数或除数,只需用整数加法、减法和乘法。

QQ截图20150909142624.jpg

  • Perspective-Correct Texture Mapping [3]:透视正确的光栅化纹理贴图算法是1980才出现的。第一代Quake引擎引入后,才开始支持不垂直的墙、不水平的地面天花。

QQ截图20150909142720.jpg

(图片来自维基百科)

  • Polygon Rasterization with Edge Function [4]:Bresenham算法如果用来画多边形,两个多边形的共边会被重绘。后来发明了使用简单的edge function去解决这个问题,而且适合并行的硬件实现。现在的GPU都是使用这个算法。

QQ截图20150909142811.jpg

全局光照

  • Precomputed Radiance Transfer (PRT) with Spherical Harmonics(SH)[5]:储存静态环境对于各个方向光源的漫反射数据,可以实现动态低频光源的全局光照效果。这种表示方式非常神奇。Halo 3也使用到这种技术[6]。

QQ截图20150909142852.jpg

  • Screen-space Ambient Occlusion (SSAO)[7]:Crytek提出的首个屏幕空间环境光遮蔽算法,之后引来大量的研究及改进算法。也有用类似的概念去做近距离的反射,如SSDO[8]。

QQ截图20150909143009.jpg

  • Light Propagation Volume (LPV)[9]:Crytek提出的首个动态全局光照算法,不需要预计算。但要在体积数据中计算传播,性能较慢,所以之后再优化成 Cascaded LPV [10]。

QQ截图20150909143129.jpg

  • Voxel Cone Tracing [11]:也是不需要预计算的动态全局光照算法。把场景动态生成层阶式的体素数据(像mipmap那样的pre-filtering),从光源视角计算直接光照,然后逐像素追踪这组数据获取非直接光照。结果比LPV精确,也可以做到光泽反射(glossy reflection)。

QQ截图20150909143208.jpg

阴影

  • Shadow Volume [12]:阴影体积是1977年发表的阴影技术,在屏幕空间光栅化阴影体积,可准确判断每个屏幕像素是否在阴影之内。可以处理平行光源和点光源的阴影。1991年[13]讲述如何用stencil buffer来实现此算法,适合在图形加速硬件(当时还没有所谓GPU)上使用。但很多人发现,如果摄像机在阴影体积内,就会出错。在1998至2000年有多人发现一种解决方法,需要把John Carmack在2000年的电邮[14]中提及这个想法,后来成为2004年《毁灭战士3(Doom 3)》引擎的重要特徵,因他把这项技术发扬光大,即使他非首个发明人,此项技术通常被称为Carmack's Reverse。

QQ截图20150909143513.jpg

  • 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有点差异,被广泛使用于现时大部分游戏引擎中。

QQ截图20150909143600.jpg


QQ截图20150909143701.jpg

场景管理

动画/物理

  • Particle System

  • Smoothed Particle Hydrodynamics(SPH)

  • Curl Noise

  • Dual Quaternion Skinning

碰撞测试

人工智能

*欢迎分享好的算法。

参考

[1] Bresenham, Jack E. "Algorithm for computer control of a digital plotter." IBM Systems journal 4.1 (1965): 25-30. 

[2] Bresenham, Jack. "A linear algorithm for incremental digital display of circular arcs." Communications of the ACM 20.2 (1977): 100-106. 

[3] Catmull, Ed, and Alvy Ray Smith. "3-D transformations of images in scanline order." ACM SIGGRAPH Computer Graphics. Vol. 14. No. 3. ACM, 1980. 

[4] Pineda, Juan. "A parallel algorithm for polygon rasterization." ACM SIGGRAPH Computer Graphics. Vol. 22. No. 4. ACM, 1988.

[5] Sloan, Peter-Pike, Jan Kautz, and John Snyder. "Precomputed radiance transfer for real-time rendering in dynamic, low-frequency lighting environments." ACM Transactions on Graphics (TOG). Vol. 21. No. 3. ACM, 2002. 

[6] Chen, Hao, and Xinguo Liu. "Lighting and material of Halo 3." ACM SIGGRAPH 2008 Games. ACM, 2008. 

[7] Mittring, Martin. "Finding next gen: Cryengine 2." ACM SIGGRAPH 2007 courses. ACM, 2007. 

[8] Ritschel, Tobias, Thorsten Grosch, and Hans-Peter Seidel. "Approximating dynamic global illumination in image space." Proceedings of the 2009 symposium on Interactive 3D graphics and games. ACM, 2009. 

[9] Kaplanyan, Anton. "Light propagation volumes in cryengine 3." ACM SIGGRAPH Courses 7 (2009): 2. 

[10] Kaplanyan, Anton, and Carsten Dachsbacher. "Cascaded light propagation volumes for real-time indirect illumination." Proceedings of the 2010 ACM SIGGRAPH symposium on Interactive 3D Graphics and Games. ACM, 2010. 

[11] Crassin, Cyril, et al. "Interactive indirect illumination using voxel cone tracing."Computer Graphics Forum. Vol. 30. No. 7. Blackwell Publishing Ltd, 2011. 

[12] Crow, Franklin C. "Shadow algorithms for computer graphics." 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, "e-mail to Mark Kilgard on Shadow Volume", 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. "Cascaded shadow maps." De

如社区发表内容存在侵权行为,您可以点击这里查看侵权投诉指引

游戏学院公众号二维码
腾讯游戏学院
微信公众号

提供更专业的游戏知识学习平台