这篇文章是聊关于BSP技术的历史的文章，很有趣，内容很详实。
翻译补充内容：
Homer Simpson，动画片辛普森一家的老爸，智商不在线
DOOM，毁灭战士，这里不翻译了
id Software，公司名，不翻译了
原文链接
正文开始
1993年，id software发布了第一人称射击游戏DOOM，很快成为了现象级游戏。如今这款游戏自始至终被认为是最具有影响力的游戏之一。
DOOM发售的10年后，在2003年，传记作家David Kushner出版了一本关于id software的书籍，《Doom启示录》，这本书成为了DOOM创作历程的权威解说。我在几年前读过本书，但如今已经不太记得详细内容了，但书中有个关于主程序约翰卡马克的一则故事一直困扰着我。
下面是这个故事的大意（后面会有更具体的细节），但本质上，Doom开发的早期，卡马克意识到他为游戏实现的3d渲染逻辑，在渲染某些关卡时，慢如龟爬。因此，卡马克意识到，他的渲染代码基本够用，但他需要找到更好的渲染算法。他开始阅读学术论文，最终他实现了叫做“二叉空间划分”的技术，这项技术显著的提升了Doom 引擎的效率，而这个技术此前从未在游戏领域应用过。
这则关于卡马克将学术论文的尖端技术应用到游戏中的故事一直令我影响深刻。为何卡马克成为如此传奇的人物，我有着自己的解释。有以各种理由他值得被称作是典型的天才游戏程序员，但我首先想到的是这个关于学术论文和二叉空间划分的故事是一个实证。
显然，这个故事令人影响深刻，因为“二叉空间划分”听上去是件让你自己阅读和实现，显得复杂困难的事情。我在很长一段时间猜想卡马克做到这点是天赋异禀，但因为我从未理解什么是二叉空间划分或者为何当初卡马克决定使用它，我不确定我了解。卡马克把二叉空间划分加入到DOOM中，从 Homer Simpson到爱因斯坦这个智商范围内，到底费了多少脑力？
我也好奇二叉空间划分法一开始是如何诞生的，卡马克是如何想到这个方法的。这篇文章是关于卡马克和DOOM的，但也是一个关于数据结构的历史：二叉空间划分树（BSP tree）。有意思的是，事实表明，BSP tree就像很多计算机科学的技术一样，他的起源来自军方的研究。
没错就是这样：E1M1,DOOM的第一关，把你带到了美国空军基地。
VSD问题
BSP树是解决计算机图形学中棘手问题的解决方法只一。为了渲染一个3d空间场景，一个渲染器必须计算给定一个特定的观察点，哪些元素可以被看到，哪些看不到。如果你有很多处理时间，那么这并没有挑战性，但对于一个让人肃然起敬的实时游戏引擎，至少需要在1秒内计算30次，找出哪些元素看得见哪些看不见。
这个问题有时被称为，可见表面决定问题。Michael Abrash，曾今和卡马克一起为雷神之锤（id公司继Doom的后续作品）工作的程序员，在他那本非常著名的图形学开发黑皮书中记叙了关于VSD的问题：
我想要聊聊这件事，在我看来，3D里所有问题最难的是：确定表面可见性，和他相关的，cull裁剪（尽可能快的丢弃不可见的多边形，一种加速的确定表面可见性方法）。
未完待续...