使用八叉树算法进行网格渲染
我是 SceneMax（自 2005 年以来的一种 3D 脚本语言）的创始人。我想使用使用 3ds max 等 3d 软件包构建的一个网格对象来添加场景渲染，并按八叉树算法分割以优化性能。
您知道在哪里可以找到一种算法，该算法采用网格 .X 文件，将其拆分为节点（八叉树）并知道如何渲染它？ 我想将它添加到我的引擎中。 该引擎是开源的（如果您有兴趣，请谷歌搜索 SceneMax）。
I'm the founder of SceneMax - a 3D scripting language since 2005. I want to add a scene rendering using one mesh object built with 3d package like 3ds max and split by octree algorithm for optimized performance.
Do you know where can I find an algorithm which takes a mesh .X file, splits it to nodes (octree) and knows how to render it? I want to add it to my engine. The engine is open source (google for SceneMax if you're interested).
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
有多种变体，但在构建八叉树时，一种方法是：
基于某些启发式停止递归也很常见，例如节点的大小或节点内元素的数量是否小于某个阈值。
有关构建八叉树的更多详细信息，请参阅此 Flipcode 教程。
获得八叉树后，您可以采用多种方法来渲染它。 基本思想是，如果您看不到一个节点，那么您也看不到它的子节点，因此不需要渲染该节点（及其子节点）内的所有内容。
视锥体剔除很容易实现，并且“你能看到它吗？” 使用视图投影的视锥体进行测试。 Gamedev.net 有一篇文章讨论视锥体剔除和其他一些方法。
您还可以更进一步，在视锥体剔除之后实现遮挡剔除，这将让您跳过渲染被前面的节点覆盖的任何节点，使用 z 缓冲区来确定节点是否被隐藏。 这涉及能够从最近到最远遍历八叉树节点。 这篇 Gamasutra 文章中讨论了此技术。
There are several variations, but when building an octree, one approach is this:
It's also common to stop recursion based on some heuristic, like if the size of the nodes or the number of elements within the node is smaller than a certain threshold.
See this Flipcode tutorial for some more details about building the octree.
Once you have the octree, there are several approaches you can take to render it. The basic idea is that if you can't "see" a node, then you can't see its children either, so everything inside that node (and its children) don't need to be rendered.
Frustum culling is easy to implement, and does the "can you see it?" test using your view projection's frustum. Gamedev.net has an article discussing frustum culling and some other approaches.
You can also go further and implement occlusion culling after frustum culling, which will let you skip rendering any nodes which are covered up by nodes in front of them, using the z-buffer to determine if a node is hidden. This involves being able to traverse your octree nodes from closest to furthest. This technique is discussed in this Gamasutra article.
首先考虑您必须支持的网格文件类型非常重要。
实际上有 3 种不同类型的对象。
1、自然地形开阔。 这非常适合四叉树，因为八叉树带来了不必要的复杂性。 如果第三维度不能给你带来太多的性能提升，那么就没有理由引入它。
2. 地形开阔，高大物体较多。 这非常适合八叉树，因为八叉树允许您从渲染中删除垂直轴上的东西，而像这样的场景有很多这样的东西。 老实说，我一时想不出任何符合这个要求的名字。
3. 封闭空间或角色模型/静态网格物体。 这非常适合 BSP 树。 BSP 树允许完全在屏幕上的对象或封闭空间仅根据需要渲染尽可能多的多边形。
我建议添加 1 和 3，假设 1 甚至是您需要支持的模型类型。 #3 对于第一人称射击游戏或角色模型来说是非常标准的，添加对此的支持可能会给您带来最大的收益。 总体想法是从渲染中删除尽可能多的几何体，因此四叉树对于玩家游戏世界中 95% 的户外地形来说是完美的。 八叉树有用途，但比您想象的要少。
这些算法中的每一个都相对容易编写。 例如，很多年前我花了3个小时写了一个八叉树。 一般来说，这些是在加载时处理的，几何图形块被添加到每个正方形（如果是四叉树/八叉树）或树（如果是 BSP），然后渲染也会随之而来。 通过快速谷歌搜索，可以找到很多很棒的文章，我将留给您研究。 需要注意的是，BSP 树还具有处理碰撞检测的能力，并且是角色模型和静态网格物体的理想候选者。 因此，我建议您花点时间研究这个算法，以确保它足够灵活，适合多种用途。
It's important to first consider the types of mesh files that you will be having to support.
There are effectively 3 different kinds of objects.
1. Open natural terrain. This fits with a quadtree very well as an octree brings complexity that is unnecessary. There's little reason to introduce a 3rd dimension if it won't give you much performance gain.
2. Open terrain with many tall objects. This fits into an octree very well as an octree allows you to remove things on the vertical axis from rendering and a scene such as this has a lot of those. I honestly can't name any that fit into this off the top of my head.
3. Enclosed spaces or character models/static meshes. This fits very well into BSP trees. A BSP tree allows for objects that are fully onscreen, or enclosed spaces to only render as many polygons as needed.
I would recommend adding 1 and 3, assuming 1 is even a model type you need to support. #3 is very standard for first person shooters or character models and adding support for that may give you the best bang for your buck. The overall idea is to remove as much geometry from a render as possible, thus a quad tree for 95% of the outdoor terrain players game worlds have is perfect. An octree has uses, but less than you may think.
Each of these algroithms are relatively easy to write. For example I wrote an octree in 3 hours many years ago. Generally these are processed at load time, pieces of geometry being added to each square (if quad/octree) or to the tree (if BSP) and then rendering follows suit. There are a lot of great articles out there via a quick Google search that I will leave for your research. A quick note is that BSP tree's also have the ability to handle collision detection and are ideal candidates for character models and static meshes. Thus this is an algorithm that I would recommend taking your time on in order to ensure it is flexible enough for multiple uses.