c++ - 使用八叉树算法进行网格渲染

Question

我是 SceneMax 的创始人 - 自 2005 年以来是一种 3D 脚本语言。我想使用一个使用 3ds max 等 3d 包构建的网格对象添加场景渲染，并按八叉树算法分割以优化性能。

你知道我在哪里可以找到一种算法，它采用网格 .X 文件，将其拆分为节点（八叉树）并知道如何渲染它？我想将它添加到我的引擎中。该引擎是开源的（如果您有兴趣，请在谷歌上搜索 SceneMax）。

Answer 1

有几种变体，但是在构建八叉树时，一种方法是：

1. 从包含整个场景或被分割对象的一个​​节点（即一个立方体）开始。
2. 对于场景/对象中的每个元素（例如网格、多边形或您正在处理的任何粒度）：
   1. 检查该元素是否完全适合节点。
   2. 如果是，则将该节点细分为八个子节点，然后对每个子节点递归执行步骤 2。
   3. 如果否，则继续下一个节点，直到没有节点为止。
   4. 将元素添加到可以包含它的最小节点。

基于一些启发式停止递归也很常见，例如节点的大小或节点内的元素数量是否小于某个阈值。

有关构建八叉树的更多详细信息，请参阅此 Flipcode 教程。

一旦你有了八叉树，你可以采取几种方法来渲染它。基本思想是，如果你不能“看到”一个节点，那么你也看不到它的子节点，因此该节点（及其子节点）内的所有内容都不需要渲染。

截锥体剔除很容易实现，“你能看到吗？” 使用您的视图投影的平截头体进行测试。Gamedev.net 有一篇讨论截锥体剔除和其他一些方法的文章。

您还可以更进一步并在截锥体剔除之后实现遮挡剔除，这将让您跳过渲染被它们前面的节点覆盖的任何节点，使用 z 缓冲区来确定节点是否隐藏。这涉及能够从最近到最远遍历您的八叉树节点。此Gamasutra 文章中讨论了此技术。

Answer 2

首先考虑您必须支持的网格文件类型很重要。

实际上有 3 种不同类型的对象。1.开阔的自然地形。这非常适合四叉树，因为八叉树带来了不必要的复杂性。如果它不会给你带来太多的性能提升，那么没有理由引入第三维。2. 开阔的地形，有很多高大的物体。这非常适合八叉树，因为八叉树允许您从渲染中删除垂直轴上的东西，并且像这样的场景有很多这样的东西。老实说，我无法说出任何适合我的想法。3. 封闭空间或角色模型/静态网格。这非常适合 BSP 树。BSP 树允许完全在屏幕上的对象或封闭空间仅根据需要渲染尽可能多的多边形。

我建议添加 1 和 3，假设 1 甚至是您需要支持的模型类型。#3 对于第一人称射击游戏或角色模型来说是非常标准的，增加对它的支持可能会给你带来最大的收益。总体思路是从渲染中移除尽可能多的几何体，因此对于 95% 的户外地形玩家游戏世界拥有的四叉树是完美的。八叉树有用途，但比你想象的要少。

这些算法中的每一个都相对容易编写。例如，多年前我在 3 小时内写了一个八叉树。通常，这些是在加载时处理的，几何图形被添加到每个正方形（如果是四叉树/八叉树）或树（如果是 BSP），然后进行渲染。通过快速谷歌搜索有很多很棒的文章，我会留给你研究。快速说明的是，BSP 树还具有处理碰撞检测的能力，并且是角色模型和静态网格的理想候选者。因此，我建议您花时间研究这种算法，以确保它足够灵活，可用于多种用途。