今天读一下这篇：How Much of a Genius-Level Move Was Using Binary Space Partitioning in Doom?

The BSP tree is a solution to one of the thorniest problems in computer graphics. In order to render a three-dimensional scene, a renderer has to figure out, given a particular viewpoint, what can be seen and what cannot be seen. This is not especially challenging if you have lots of time, but a respectable real-time game engine needs to figure out what can be seen and what cannot be seen at least 30 times a second.

在计算机图形学里，实时渲染的主要挑战就是在 1/30 秒内计算出当前能看到的所有多边形，并把它们急匆匆地搬上搬下场。至于在视野外是什么样子，就完全不需要关心了。正因为如此，这个领域内发展出了各种奇技淫巧，用来解决这个被称作 VSD (visible surface determination, 有时候包括了 culling) 的问题。

而 John Carmack 在 1993 年的 Doom 里实现了 BSP (binary space partitioning) 算法，被很多人认为是天才的创举。这篇文章追溯了 BSP 的来龙去脉，指出 BSP 最早被空军用于开发飞行模拟器，Carmack 也是站在前人的肩膀上写的代码，虽然他读论文和实现数据结构的能力值得嘉许，但也别吹得太过——大概是这么个意思。

Ray Casting, Ray Tracing, Ray Marching, etc.

这篇文章解释说，最初只有 ray casting，后两种都是它的变种。一般而言的 ray casting 指的是从屏幕的每一个像素发射出一道射线，击中某个物体时，就标记出对应的点。击中与否是靠解析式判断的。

So the ray casting algorithm has to calculate the intersection points of all the rays with all the objects, pick the closest intersection point and calculate the distance to the camera.

Ray marching 和它的区别则是，只需要沿着那个方向走几步，如果某两步之间和物体表面的位置关系改变了，说明穿过了该表面。这种方法不需要解析式，所以可以应用于完全不规则的物体，例如人体器官。

The ray marching algorithm has the advantage over traditional ray casting that you need not compute intersection points analytically. Instead, you walk along the ray and simply check after each step whether you’ve hit an object.

最后是 Ray Tracing，简单来说就是同时考虑到物体受不受光照。

The main idea behind that is that you do not only compute the ray from the camera to the object, but also from the object to the light source, whereever it is. By checking whether an object actually gets light and taking this into consideration in the formula computing the colour of the pixel, you can get more realistic pictures.

BSP

Ray casting 是 image-first，从图像的每个像素出发看它们击中了哪个物体；而 doom 的渲染是 object-first，把每个物体投射到屏幕上。一般来说，后者会用到 z-buffer 来检验当前物体是不是被遮挡，没被遮挡就画上去，但 z-buffer 超占内存，而且这个方法会导致大量 overdraw，也就是在已经画好的像素上重新画一遍。

BSP 算法会把 3D 空间分成好几部分。其大致步骤如下：

  1. 随便挑一个多边形，把它当做初始分割面 (partitioning plane)，也是 BSP 树的根节点。
  2. 在根节点“前面”的多边形都进入左子树，在“后面”的进入右子树。
  3. 重复以上步骤直到多边形耗尽（注意 partitioning plane 可能会切出更多多边形，也正因此 BSP 解决了优先级循环问题）。

img

和 1980 那篇提出 BSP 的论文相比，Carmack 进一步使用了 front-to-back 渲染，来避免 back-to-front (painter’s algorithm) 造成的大量 overdraw。

最后一个要解决的问题是怎么处理移动的敌人等物件，因为这些面不能被放进 BSP 里。

So the Doom renderer draws the static level geometry first, keeping track of the segments of the screen that were drawn to (with yet another memory-efficient data structure). It then draws the enemies in back-to-front order, clipping them against the segments of the screen that occlude them. This process is not as optimal as rendering using the BSP tree, but because there are usually fewer enemies visible than there is level geometry in a level, speed isn’t as much of an issue here.