光柵化

• Bresenham's line algorithm?[1]：經典的繪畫直線算法，后來還可以稍作修改用于繪畫圓弧[2]，都不用三角函數或除數，只需用整數加法、減法和乘法。

• Perspective-Correct Texture Mapping [3]：透視正確的光柵化紋理貼圖算法是1980才出現的。第一代Quake引擎引入后，才開始支持不垂直的墻、不水平的地面天花。

（圖片來自維基百科）

• Polygon Rasterization with Edge Function [4]：Bresenham算法如果用來畫多邊形，兩個多邊形的共邊會被重繪。后來發明了使用簡單的edge function去解決這個問題，而且適合并行的硬件實現?，F在的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年發表的陰影技術，在屏幕空間光柵化陰影體積，可準確判斷每個屏幕像素是否在陰影之內?？梢蕴幚砥叫泄庠春忘c光源的陰影。1991年[13]講述如何用stencil buffer來實現此算法，適合在圖形加速硬件（當時還沒有所謂GPU）上使用。但很多人發現，如果攝像機在陰影體積內，就會出錯。在1998至2000年有多人發現一種解決方法，需要把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，它是一種用統計方式來逼近軟陰影的效果。 如何推導方差陰影貼圖（variance shadow map, VSM) ? - Milo Yip 的回答

場景管理

• Binary Space Partitioning?（BSP）
  

• Portal rendering
  

• Quadtree、Octree：游戲場景管理的八叉樹算法是怎樣的？ - Milo Yip 的回答

• Potential Visibility Set （PVS）

• Occlusion Culling by Software Rasterization

動畫／物理

• Particle System

• Smoothed Particle Hydrodynamics（SPH）

• Curl Noise

• Dual Quaternion Skinning

碰撞測試

• Hyperplane separation theorem?（或稱separating axis theorem/SAT）：凸形狀相交測試的基本原理。在怎樣判斷平面上一個矩形和一個圓形是否有重疊？ - Milo Yip 的回答中，其實背后也是使用了SAT。
  

• Gilbert-Johnson-Keerthi distance algorithm?(GJK距離算法)：計算兩個凸形狀的距離（可用于相交測試）
  

• Sweep and prune：用于broad phase碰撞檢測，找出物體AABB是否相交。對于時空上連續的物體運動，算法最壞O(n^2)、最好O(n).

參考
[1] Bresenham, Jack E. "Algorithm for computer control of a digital plotter."?IBM Systems journal?4.1 (1965): 25-30.?http://www.cse.iitb.ac.in/~paragc/teaching/2011/cs475/papers/bresenham_line.pdf
[2] Bresenham, Jack. "A linear algorithm for incremental digital display of circular arcs."Communications of the ACM?20.2 (1977): 100-106.?http://www.cse.iitb.ac.in/~paragc/teaching/2014/cs475/papers/bresenham_circle.pdf
[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.?http://alvyray.com/Papers/CG/2pass80.pdf
[4] Pineda, Juan. "A parallel algorithm for polygon rasterization."?ACM SIGGRAPH Computer Graphics. Vol. 22. No. 4. ACM, 1988.?http://people.csail.mit.edu/ericchan/bib/pdf/p17-pineda.pdf
[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.?http://www1.cs.columbia.edu/~ravir/6998/papers/p527-sloan.pdf
[6] Chen, Hao, and Xinguo Liu. "Lighting and material of Halo 3."?ACM SIGGRAPH 2008 Games. ACM, 2008.?http://developer.amd.com/wordpress/media/2012/10/S2008-Chen-Lighting_and_Material_of_Halo3.pdf
[7] Mittring, Martin. "Finding next gen: Cryengine 2."?ACM SIGGRAPH 2007 courses. ACM, 2007.?http://developer.amd.com/wordpress/media/2012/10/Chapter8-Mittring-Finding_NextGen_CryEngine2.pdf
[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.?https://people.mpi-inf.mpg.de/~ritschel/Papers/SSDO.pdf
[9] Kaplanyan, Anton. "Light propagation volumes in cryengine 3."?ACM SIGGRAPH Courses?7 (2009): 2.?http://www.crytek.com/download/Light_Propagation_Volumes.pdf
[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.?http://www.vis.uni-stuttgart.de/~dachsbcn/download/lpv.pdf
[11] Crassin, Cyril, et al. "Interactive indirect illumination using voxel cone tracing."Computer Graphics Forum. Vol. 30. No. 7. Blackwell Publishing Ltd, 2011.?https://research.nvidia.com/sites/default/files/publications/GIVoxels-pg2011-authors.pdf
[12] Crow, Franklin C. "Shadow algorithms for computer graphics."?ACM SIGGRAPH Computer Graphics. Vol. 11. No. 2. ACM, 1977.?http://excelsior.biosci.ohio-state.edu/~carlson/history/PDFs/crow-shadows.pdf
[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.?http://web.archive.org/web/20090127020935/http://developer.nvidia.com/attach/6832
[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."?Developer Documentation, NVIDIA Corp?(2007).?http://www.cse.chalmers.se/edu/year/2011/course/TDA361/Advanced%20Computer%20Graphics/cascaded_shadow_maps.pdf
[18] Donnelly, William, and Andrew Lauritzen. "Variance shadow maps."Proceedings of the 2006 symposium on Interactive 3D graphics and games. ACM, 2006.?http://www.punkuser.net/vsm/vsm_pa

∑編輯?|?Gemini

來源 | 知乎 李小浩的回答

算法數學之美微信公眾號歡迎賜稿

稿件涉及數學、物理、算法、計算機、編程等相關領域，經采用我們將奉上稿酬。

投稿郵箱：math_alg@163.com

總結

以上是生活随笔為你收集整理的游戏编程里面有哪些经典或者很酷的算法？的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。