用BSP优化3D渲染

3D渲染引擎设计者面临的最大问题之一是可见性计算：只必须绘制可见的墙壁和物体，并且必须以正确的顺序绘制它们（应该在远处的墙壁前面绘制近墙）。更重要的是，对于游戏等应用程序来说，开发能够快速渲染场景的算法非常重要。因此，现在存在多种解决可见性计算问题的方法。

二进制空间分区 (BSP) 是一种可用于大大加快 3D 渲染中可见性计算速度的技术。它已被多款著名游戏使用，例如《Doom》和《Quake》。

Map — 这是指正在渲染的区域：在游戏中，这是游戏地图或关卡。
Viewpoint——我们渲染的视角
Field of View — 视野，从视点的位置和角度可见的地图区域

使用 Doom 使用的二维地图示例来解释该系统。然而，BSP 可以轻松扩展到 3 维（或更多？）——代替 2 维线，可以使用 3 维平面等。

1、预先计算

在渲染地图之前，我们必须对其执行大量计算。然而，一旦执行这些计算，其结果就可以多次使用。这是 BSP 的优点之一——一旦执行了计算，就不需要再次执行，除非地图发生更改。 BSP 只允许“静态”地图，或者不移动的地图。如果地图有任何移动部分，那么它们必须单独渲染。

必须做的是将地图划分为凸多边形。凸多边形是所有内角都小于或等于180度的多边形。例如，以下形状是凸多边形：

然而，以下形状不是凸形的：

如果地图被认为是一个非凸多边形，我们可以通过在其上画一条分界线将其分成两个子多边形。例如，考虑以下地图：

将这个多边形一分为二时，我们创建了两个“子多边形”。这种划分可以用一个简单的树来表示：

现在可以递归地划分两个子多边形中的每一个。每个分支都会为树产生一个新的“分支”。递归一直持续到地图被划分为凸多边形，即树的“叶子”。

出于显而易见的原因，如果可能的话，希望保持树“平衡”：也就是说，保持树两侧的高度大致相等。

2、渲染

使用 BSP 树的渲染也是使用递归算法完成的。最常见的方法是从根节点（树的顶部）开始并递归地向下工作。这就是为什么需要保持树平衡：这减少了递归的数量。递归到大深度可能会显着减慢渲染速度。

可见性排序系统的核心在于渲染函数递归的顺序。也就是说，给定节点的左子树还是右子树是否先渲染。对于任何特定节点，都有一条分界线，将其分为两个子节点。如果这条线延伸到无穷远，我们渲染的视点可以被认为是在“左”或“右”侧。视点所在的一侧决定首先渲染哪个子节点。

请注意，实际上有两种执行渲染的方式：

从后到前

在从后到前的渲染器中，首先渲染远处的墙壁，并被较近的墙壁遮挡。这是上图中使用的系统。从后到前渲染的缺点之一是过度绘制 - 绘制的部分墙壁被较近的墙壁遮挡而看不到。这是不必要的开销。

从前到后

从前到后渲染器以相反的方式工作：首先渲染较近的墙壁，然后将较远的墙壁剪裁到已绘制的墙壁上。因为它没有过度绘制，所以几乎所有实用的 BSP 渲染器都使用从前到后的方法。

因此，简单的从后到前渲染器的一些示例伪代码将是：

function render(node)
{
  if this node is a leaf
    {
      draw this node to the screen
    }
  else
    {
      determine which side of the dividing line the viewpoint is
      
      if it is on the left side
        {
          render(right subnode)
          render(left subnode)
        }
      else
        {
          render(left subnode)
          render(right subnode)
        }
    }
}

bsp 树的主要缺点是整个地图必须是静态的（不可移动）——如果其中一部分移动，则必须重建整个树。克服这个问题的一种方法是将静态和移动部分分开，并分别渲染它们。