八叉树

前言

在创建三维图形显示子系统的过程中，剔除场景中不可见几何体是最重要的问题之一。这种处理方法允许只绘制场景中当前可见的部分（位于摄像机视锥体内的部分）。有许多数据结构和算法可以在一定程度上解决上述问题。

为什么需要这样的处理？

答案显而易见：效率。尽管现代图形处理器每秒能够处理数百万个多边形，但实际的每帧性能却差很多。场景当然必须由大量的多边形组成才能看起来逼真。如果我们忽略这个问题，并在动画的每一帧中处理所有的三角形，最终每秒帧数将急剧下降，因为会处理大量不会出现在屏幕上的不必要的多边形。此外，还有几何体数据通过总线传输的开销问题（如果出于某种原因这些数据无法分配在服务器端内存中），以及光栅化（包括填充率）和各种图形效果（如凹凸贴图、光照、着色等）所需的 GPU 功率。为了解决这个问题，应用了不同的场景分割算法，将多边形分成更小的集合，以便显卡能够以可接受的速度处理。到目前为止，BSP 是游戏中应用最广泛的算法（BSP 树可以看作是某种画家算法的修改）。它将场景分割成扇区，并按前后关系对多边形集合进行排序。通过这种排序，可以禁用深度缓冲区进行渲染，但这并不是最佳方案，因为启用深度缓冲区并按从前到后的顺序绘制多边形后，性能得到了改善。然而，BSP 树在场景分割过程中可能会分割场景中的多边形，导致创建新的几何体数据（需要处理更多的三角形）。它们还对几何体施加了限制，并阻止对关卡进行任何修改（这需要重新构建树）。BSP 树在包含少量三角形的关卡游戏中一直表现良好。BSP（或其修改版）已用于《Quake》、《Unreal》、《Unreal Tournament》等热门游戏。在作者自己的引擎中，他采用了另一种隐藏表面移除方法，即八叉树。

Octree

八叉树将整个场景的几何体（玩家所处的世界）包含在一个立方体中。该立方体（称为父节点或根节点）可以被分成八个更小的立方体（以下称为子节点、子节点或八分枝），如图（图 1）所示。反过来，每个子节点都可以被分成八个连续的立方体，以此类推，直到达到某个阈值（通常是立方体能包含的最少多边形数量，或者舞台分割的最大级别，或者立方体边的最小长度）。每个子节点都分配了一个包含其中的三角形列表。根节点包含世界的所有多边形。每个父节点包含随后被分配给具体子节点的多边形。

渲染

绘制场景取决于是否检查包围根节点的立方体是否在视域范围内。如果不在，则场景中的任何多边形都不会被绘制。如果整个立方体可见，则绘制场景中的所有多边形，即整个世界。如果根节点仅部分可见，我们开始遍历树。我们像检查根节点一样检查子节点。如果遇到一个完全可见的立方体，我们渲染其中包含的几何体。如果立方体仅部分可见且没有子节点（子节点），我们绘制分配给它的多边形（玩家小于最小八分枝的情况）。正如可以看出，使用此算法，我们只绘制玩家当前看到的内容。

创建树

首先，必须创建一个包围整个场景根节点的立方体。为此，我们查找场景几何体列表中每个节点的 x、y、z 坐标的最大绝对值（称之为 V）。该值将用于生成立方体（相对顶点为 [V, V, V] 和 [-V,-V,-V]）。我们将即将被分割的场景的所有多边形列表附加到描述根节点的结构中。然后，立方体沿主轴被分成八个部分，并检查哪些多边形位于不同的八分枝（子节点）中。递归地执行此操作，直到达到我们自己设定的完成树的条件阈值，如上所述。由于一个多边形可能包含在几个节点中（通过几个立方体），因此强烈建议不要在几个叶子节点中存储副本。在某些情况下，这会迫使显卡多次处理同一个多边形，从而降低效率。沿着立方体边缘分割多边形是一种解决方案，但我们对此不感兴趣，因为它会导致出现新的几何体数据，从而消除实现中的抽象级别（当关卡数据分开保存，树数据分开保存时）。每个多边形中的帧计数器将是一个解决方案。渲染子系统将检查计数器的值，并防止在当前帧中重复绘制已渲染到屏幕上的三角形。

动态对象呢？

为了允许正确渲染树中的动态对象，每个节点应包含一个动态对象列表，并且每个此类对象应包含一个指向其所附着节点的列表。当对象改变位置时，将其从当前节点分离并附加到新节点。在绘制场景的过程中，只使用可见的节点及其连接的对象，不要忘记重新绘制对象的可能性，同时也要使用帧计数器。

结论

正如您所见，八叉树结构是记录和可视化场景（包括，当然，其主要用途——从渲染过程中剔除不可见几何体）的一种非常有效的方法。它可以处理任意大小的场景，并且不像二叉空间分割（BSP 树）那样对几何体施加任何限制。这里介绍的方法描述了作者在他自己的引擎中使用的具体实现。显而易见，实现的一些方面也可以有其他解决方案。

历史

• 2010 年 9 月 10 日：初始发布