基于八叉树算法的网格绘制

Question

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

你知道我在哪里可以找到一种算法，它可以将网格.X文件分割成节点(八叉树)，并知道如何渲染它？我想把它添加到我的引擎中。该引擎是开源的(如果您有兴趣，可以使用谷歌的SceneMax )。

Answer 1

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

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

​

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

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

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

Frustum剔除很容易实现，并且会问“你能看到吗？”使用视图投影的平截体进行测试。Gamedev.net has an article讨论了截顶剔除和其他一些方法。

您还可以更进一步，在截体剔除之后实现遮挡剔除，这将允许您跳过渲染任何被节点前面的节点覆盖的节点，使用z缓冲区来确定节点是否隐藏。这包括能够从最近到最远遍历你的八叉树节点。在this Gamasutra article中讨论了这项技术。

Answer 2

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

实际上有3种不同的对象。1.开放的自然地形。这非常适合四叉树，因为八叉树带来了不必要的复杂性。如果它不会给你带来很大的性能提升，那么就没有理由引入3D。2.开放的地形，有许多高大的物体。这非常适合八叉树，因为八叉树允许你从渲染中移除垂直轴上的东西，像这样的场景有很多这样的东西。老实说，我不能说出任何适合我头顶的东西。3.封闭空间或角色模型/静态网格。这非常适合BSP树。BSP树允许完全显示在屏幕上的对象，或仅渲染所需数量的多边形的封闭空间。

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

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