算法与计算机科学twobithistory.org
Doom 中二叉空间分割（BSP）的天才之处
The genius of binary space partitioning in Doom (2019)
2022 — 2024，它一次次回到首页
黑点是上首页（≥ 50 分）的那次投稿，空心点是没冲上去的投稿，点越大分数越高。
导读
这篇文章讲解 Doom 引擎中二叉空间分割树（BSP）的原理与作用：它让 Carmack 在没有 Z 缓冲的硬件上高效地按前后顺序渲染多边形，解决了当时 3D 游戏的核心难题。文章追溯了该算法的学术渊源及其在游戏史上的意义。
为什么经久不衰：它把一段经典游戏引擎技术讲得深入浅出，即使硬件早已内置 Z 缓冲，这种把学术研究转化为工程实践的故事对今天的开发者仍有启发。
HN 评论精选
从亲历者角度解释为何多边形排序是当时的核心难题，以及 Doom 的方案为何出色
极其出色的作品，尤其考虑到当时的 CPU 性能。Carmack 对 BSP 树的运用启发了我后来在《古惑狼》渲染器上的工作。如今所有硬件都有 Z 缓冲，这些技术已不再需要，但在 90 年代中期，多边形排序可以说是 3D 游戏开发者必须解决的关键问题。一个关键洞察是：正确排序多边形本质上是 O(N²) 而非多数人以为的 O(N lg N)，因为多边形的前后关系不满足传递性（存在循环遮挡），这意味着无法用高效排序，1000 个多边形需要百万次比较——当时的硬件根本做不到。这就是为什么那个年代很多游戏（3DO、PS1 等）的多边形会前后闪烁：大多数游戏用的是只求近似的桶排序。而 Doom、《古惑狼》等少数做了更聪明处理的游戏，画面因此好得多。
dmbaggett查看英文原文
Amazingly brilliant work, especially given the CPU capabilities at the time. Carmack's use of BSP trees inspired my own work on the Crash Bandicoot renderer. I was also really intrigued by Seth Teller's Ph.D. thesis on Precomputed Visibility Sets though I knew that would never run on home console hardware. None of these techniques is relevant anymore given that all the hardware has Z buffers, obviating the need to explicitly order the polygons during the rendering process. But at the time (mid 90s) it was arguably the key problem 3D game developers needed to solve. (The other was camera control; for Crash Andy Gavin did that.) A key insight is that sorting polygons correctly is inherently O(N^2), not O(N lg N) as most would initially assume. This is because polygon overlap is not a transitive property (A in front of B and B in front of C does NOT imply A in front of C, due to cyclic overlap.) This means you can't use O(N lg N) sorting, which in turn means sorting 1000 polygons requires a million comparisons -- infeasible for hardware at the time. This is why many games from that era (3DO, PS1, etc) suffer from polygons that flicker back and forth, in front of and behind each other: most games used bucket sorting, which is O(N) but only approximate, and not stable frame to frame. The handful of games that did something more clever to enable correct polygon sorting (Doom, Crash and I'm sure a few others) looked much better as a result. Finally, just to screw with other developers, I generated a giant file of random data to fill up the Crash 1 CD and labeled it "bsptree.dat". I feel a bit guilty about that given that everyone has to download it when installing the game from the internet, even though it is completely useless to the game.
纠正神话：BSP 是教科书级算法，Carmack 的贡献在于应用而非发明
BSP 是一个早已广为人知的算法，并非 Carmack 从默默无闻中发掘的。Foley 和 van Dam 的经典教材《计算机图形学》每一版都有详尽介绍，Atari 1983 年的街机游戏《I, Robot》就用 BSP 从后往前渲染多边形。这不是否认 Carmack 的才华，但使用 BSP 本身算不上什么天才之举。
tasty_freeze查看英文原文
BSP (binary space partitioning) was a well known algorithm, not something Carmack picked out of obscurity. It is well covered in every edition of Foley and van Dam's bible "Computer Graphics". The arcade game "I, Robot" from Atari (1983) used BSP to render the polygons back to front -- there was no z-buffer. That isn't to deny that Carmack was brilliant. But him using BSP isn't some masterstroke of genius in itself.
Carmack 真正的天才是把论文变成能跑的代码，这种能力很稀缺
我当年正在学计算机图形学，用的教材里就有 BSP 树，文章也提到它早在十多年前就被发表过。Carmack 的过人之处在于能把研究论文读透并转化为可运行的代码。我也能做到这一点，但这种能力在软件行业似乎并不常见。
phkahler查看英文原文
I was studying computer graphics at the time. The book we used was "Computer Graphics Principles and Practice" I don't recall which edition. BSP trees are covered in the book, and like the article says, had been written about more than a decade prior. What Carmack had was the ability to read research papers and translate them into working code. I can do that too, but it does seem to be a less common skill in the software world.
同时代开发者印证：BSP 是当时被广泛研究和采用的方案
我大约在 1995 年的 CDROM 游戏《Dark Fiber》里实现过 BSP 渲染器。我也记得在 Foley 和 van Dam 的书里见过这个算法，但直到在某个展会上和 John 聊过之后，我才决定用 BSP 做引擎。优化这个算法的过程很有趣，我还花了不少时间用 Mathematica 推导公式。
diskzero查看英文原文
I implimented a BSP renderer in my somewhat unremarkable CDROM game Dark Fiber [1] in 1995 or so. I also remember seeing the algorithm in Foley and Van Dam, but it wasn't until a conversation with John at some conference/tradeshow that I went for doing the engine using BSP. It was a lot of fun figuring out how to optimize the algorithm and I also spent a lot of time using Mathematica figuring out the equations. Well, that was at least my excuse for buying a fairly expensive piece of software as a small gaming startup. https://archive.org/details/DarkFiberWindowsMac
历次讨论
同类还值得读
位运算技巧集
Bit Twiddling Hacks
斯坦福页面上的经典位运算技巧合集，收录了 popcount、前导/尾随零、位反转、交换、舍入等大量技巧，并附有解释和性能讨论。
算法与计算机科学上首页 8 次 · 2011–2024graphics.stanford.edu编辑精选如何不按平均评分排序
How Not To Sort By Average Rating
经典文章解释了为什么按平均评分排序不可靠：只有少量评价的条目（比如仅一条五星）会轻易排到最前，而评价数量的差异被忽略。
算法与计算机科学上首页 7 次 · 2009–2024evanmiller.org编辑精选数据结构可视化
Data Structure Visualizations
旧金山大学 David Galles 教授制作的数据结构与算法交互式可视化网站，涵盖 B 树、红黑树、排序、图算法等，可逐步操作观察其运行过程。
算法与计算机科学上首页 6 次 · 2011–2021cs.usfca.edu编辑精选1996 年以来的计算机科学最佳论文奖
Best Paper Awards in Computer Science since 1996
Jeff Huang 维护的一个汇总页面，收录了自 1996 年以来计算机科学各主要会议的“最佳论文奖”获奖名单，并按年份和会议整理，方便读者一站式浏览历届获奖论文。
算法与计算机科学上首页 6 次 · 2010–2018jeffhuang.com编辑精选算法（Jeff Erickson）
Algorithms, by Jeff Erickson
伊利诺伊大学 Jeff Erickson 教授的算法课教材，免费在线开放。
算法与计算机科学上首页 5 次 · 2018–2022jeffe.cs.illinois.edu编辑精选