用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 树的主要缺点是整个地图必须是静态的（不可移动）——如果其中一部分移动，则必须重建整个树。 克服这个问题的一种方法是将静态和移动部分分开，并分别渲染它们。
3、BSP 树的其他用途
除了可见性排序之外，BSP 树还有许多其他用途。 其中之一是，以分层方式划分地图（例如这样）允许将地图的大部分排除在渲染过程之外 - 如果所有特定节点都在视点的视野之外，则该节点可以从渲染中丢弃。 这是加速渲染引擎的快速有效的方法。
这棵树还可以用于许多其他效果，例如阴影。