问题标签 [bsp-tree]

我有一个三角形的多边形汤，我想为其构建一个 BSP 树。我当前的程序只是通过从模型中一次插入一个随机三角形来构造一个 BSP 树，直到所有三角形都被消耗完，然后它检查树的深度和宽度并记住它获得的最佳分数（最低深度，最低宽度）。

根据定义，最佳深度为 log2(n)（如果共面三角形被分组，则更小？）其中 n 是我的模型中三角形的数量，最佳宽度为 n（意味着没有发生分裂）。但是，有些三角形的配置永远无法达到这个顶峰。

是否有有效的测试来检查我的 BSP 树的质量？具体来说，我试图找到一种方法让我的程序知道它应该停止寻找更优化的结构。

互联网上充斥着二维 BSP 树的信息（即光线投射，所有墙壁都是平行的）。有没有人有任何链接或知道一本讨论 3 维 BSP 树的书？

大家好。我正在将预建的 BSP 树加载到内存中，我很困惑。它被用于第一人称探索程序。你如何建议我使用已经制作的 BSP 树。我知道我遍历了这棵树，但我要寻找什么？

对不起我的英语。

我正在构建一个二叉树。二叉树是预先构建在一个文件中的，我需要构建它。由于它的结构方式，我将树读入一个数组。每个树节点看起来像这样。

我尝试了多种方法来编写一些构建树的代码。让我给你一些伪代码，以便你了解我想要做什么。

• 读入头节点。节点在数组中排名第一。
• 如果节点具有左右数组索引，则创建新节点并将数组索引中的信息插入该树节点。
• 如果节点没有左右索引，则为叶子节点。

这是我的建筑功能：

我的调试显示该函数会尝试插入节点 2，直到程序崩溃。

有人可以帮我弄这个吗？

我知道如何利用像 Quake 等旧 3d 关卡的预构建 BSP 树，甚至编写了一个关卡渲染器。现在，我正在进入下一步，实际上是自己构建 BSP 树。我知道它背后的过程，但我想知道是否有人有任何建议或教程链接。

嗨，我正在编写 Quake 级别的渲染器。我已经到了需要考虑透明度的地步。我知道二进制空间分区器（BSP）树的格式化方式是数据按距离排序，或者至少我听到的是这样，但我不知道如何实现这一点。我已经构建了我的 BSP 树并解码了我的 PVS。

我是否： 1. 弄清楚我在哪一片叶子上。例如 6。2. 从最大值渲染到叶子 6，假定这些叶子在我的截锥体和 PVS 中。3. 从 min 渲染到叶 6，再次考虑 PVS 和截锥体。

这不是 BSP 树的工作原理吗？

这就是问题#1。第二个问题涉及 PVS。我知道在过去，当空间是一个问题时，PVS 很棒，因为它被压缩了。我现在拥有它的方式，我不会在每次渲染帧时解压缩 PVS，我只执行一次并将叶子的可见性存储在我在渲染过程中遍历的向量中。这有意义还是适得其反？

所以再次回顾一下，我可以假设一个 BSP 树的结构使得叶子已经按距离排序，在叶子 6（总共 9 个叶子），我应该渲染 9、8、7、6、1、2、3， 4、5（假设所有 9 在叶子 6 的 PVS 中都可见）同样考虑到 PVS 和截锥体。

谢谢你。

我有一个 BSP 树加载到内存中。我首先找出我所在的叶子。接下来，我对 PVS 进行解码。然后，我遍历那个 PVS 中的每个区域，看看它是否在我的视锥体中。

有人告诉我这是不正确的渲染方式，我实际上应该通过遍历 BSP 树来进行从后到前的渲染。我该怎么做？我已经看到了许多不同的方法来做到这一点，这就是我问的原因。

例如，Quake 3 BSP 渲染显示：遍历 BSP 以确定相机位于哪个叶子中。检索并解压缩此叶子的 PVS，遍历 PVS 并在 BSP 中标记叶子。从近到远遍历 BSP 如果没有标记节点，则跳过它。针对相机视锥体测试节点边界框​​。将当前叶子添加到再现列表

这仍然是今天的标准方式吗，或者至少对于更简单的游戏来说是这样吗？

Anyone can point to a resource with code example on generating triangles out of polygonal shape using BSP trees approach ? Thanks.

这更像是一个概念问题，而不是编码问题。我已经弄清楚了 BSP 树的基本概念，但是在定位定位方面遇到了麻烦。我已经想出要在 BSP 树中找到我当前的位置，如果我在拆分平面前面，我会不断递归地遍历树，如果我在拆分平面前面，则向右移动，如果我在它后面，则向左移动。当我最终击中一个叶节点时，这就是我所处的世界。

现在，在渲染方面，如果我必须从前到后渲染，我会从树的右侧开始，一直递归地渲染，直到碰到左侧的最后一个节点。后面跟前面呢？会不会适得其反？

谢谢！

我一直在尝试实现一个三维 BSP 树来渲染透明的单个对象（一个立方体、一个带有圆柱体的盒子等）。据我了解，这应该有效，但事实并非如此，我不知道为什么。我读过的所有内容都是指在二维或多个对象上使用 BSP 树，所以我想知道我是否只是普遍误解了 BSP 树可以应用于什么而不是在我的代码中出现错误。我在网上看了很多东西，我的代码似乎和布雷顿韦德的（ftp://ftp.sgi.com/other/bspfaq/faq/bspfaq.html）一样，所以如果有人有任何样本特别是单个对象/透明度的 BSP 代码，那将是美妙的。

谢谢你。