问题标签 [octree]

如何将递归数据结构（如八叉树）发送到 OpenGL GLSL 着色器？我想，我可以将它作为节点数组发送并使用索引而不是指针，这是个好主意吗？还有其他选择吗？

我正在尝试确定测试两个细胞\体素是否连接的最有效方法。为简单起见，我将在二维中讨论这个问题，并考虑图中的单元格......

现在我将问题限制在垂直轴上，称之为 y 轴。

每个单元格的左下角是它的坐标，它总是一个正整数（如果有帮助的话）。

A 和 B 的 y 轴边界可以写成，

A.y1 = 4
A.y2 = 8
B.y1 = 7
B.y2 = 8

现在测试 A 和 B 是否在 y 轴上连接/重叠的最有效方法是什么？请注意，如果您在图表中切换 A 和 B 标签，它也应该起作用。

这是我毫无疑问的天真尝试......

当我遇到这个问题时，我很想创建一个稀疏八叉树实现，就像 nVidia 的人（“高效稀疏体素八叉树”）正在为他们的体素事情做的那样：

我有一个字节类型的位域（所以只有 8 位），它告诉我八叉树的叶子在哪里（1 表示叶子，0 表示没有叶子，附加了 8 个节点 --> 8 位）。我现在要做的是返回一个叶子位置的数组。我当前的实现是使用一个while循环来确定是否设置了LSB。之后输入移位 1。所以我是这样做的：

这看起来并不优雅，并且有两件事令人不安：

• 这个 while 循环模仿了一个 for 循环
• 结果数组很可能小于 8 个值，但调整大小的成本很高

我希望结果类似于[2,4,6]42 (0010 1010)。

任何人都可以提供一个更优雅的仍然可读的解决方案吗？

结果

我正在使用我之前实现的八叉树叶计数函数将数组设置为适当的大小。

我读到了八叉树，但我并不完全理解它们是如何在体素世界中工作/实现的，在体素世界中，八叉树的目的是通过将重复体素连接到一个大的“体素”来降低要渲染的体素数量。

以下是我想澄清的问题：

• 你会使用什么类型的数据结构？如何将体素的 3-D 数组转换为具有不同大小体素的数组，这些体素在数组中占据多个位置？
• 什么是节点，它们的用途是什么？
• 八叉树是否连接体素，所以只有正方形，或者它可以是矩形或 L 形或整个 Y 体素列还是什么？
• 八叉树真的能提高体素游戏的性能吗？如果有的话，一般是多少？

我创建了这个方法来修剪 3D 数组以在八叉树中使用。由于一些奇怪的原因，我在返回修剪后的数组后无法弄清楚它只是充满了零。什么时候应该装满。

这是更好地解释的代码：

打印矩阵方法（它用于仅打印零以检查是否有）（不应该有）：

trim 方法（x,z,y 用于说明从哪里开始修剪，以便您可以将 3D 数组修剪为八叉树的 8 个部分）（注意：自杀永远不会发生，这意味着体素数组永远不会有零）：

现在我不是任何想像力的Java新手，但我不知道为什么会这样。

我试图弄清楚哪种结构更适合对点进行多个半径搜索，kd-tree 还是 octree？在这个问题中已经提到过，但没有答案。在我看来，由于八叉树的叶子大小固定，它已经可以计算出我需要访问的分支，而对于 kd-tree，您必须迭代地访问分支，直到覆盖半径。

我正在尝试实现八叉树搜索以将我的数据从粗网格（例如 20 点）映射到精细网格（例如超过 50 点）。我设法构造了八叉树（使用 C++ 中的类），但现在面临查询它的问题。

我想要的是从粗网格到细网格上每个点的最接近的 3 个点，并使用这 3 个点的数据值来查找细网格点的数据值。所以现在在查询时我遍历八叉树直到到达叶节点。假设我的每个叶节点至少有三个点（粗网格），我将找到我的细网格点所在的叶节点并计算相应的数据值。

现在的问题是，在某些情况下，与我为精细网格点获得的叶节点相邻的叶节点可能包含比当前叶节点中更接近它的点（或多个点）。确定这是我无法理解的。

我希望我的描述很清楚，并且一些好的灵魂能够帮助我。此外，如果有人可以指出我在八叉树中查询某个半径内的点，那也会有很大帮助。

我正在添加一张图片以更好地解释我的担忧。红点是八叉树中的点，蓝点是查询后细网格点的位置。现在我将使用叶节点 1 中的点来评估这个精细网格点的数据值，而叶节点 2 的点更接近精细网格点。

是否有比单独测试 8 个角是否在球体内更快的方法来检查轴对齐的立方体是否在球体内？

我正在穿过一个八叉树，检查它的立方体叶子是否相交或包含在一个球体中。我在这里找到了一种交叉点的方法：立方体球体交叉点测试？

我希望找到一种更有效的方法来测试封闭性。我最终需要的是一个返回三种状态之一的测试：

1. 外球体
2. 相交球体
3. 球内

立方体由两个点定义，球体由其中心点和半径定义。

我正在寻找表示体积对象的算法和数据结构的想法。我正在开发一个雕刻系统，比如 sculptrix 或 mudbox，并希望找到一个好的实施策略。

我目前有一个非常好的动态半边网格系统来折叠/细分面。它工作得非常好并且速度非常快，但是由于它是一种表面算法，因此很难鲁棒地改变拓扑结构。

所以我想回到绘图板并实施一个适当的体积系统。我的第一个想法是对体积和行进立方体进行某种八叉树表示以使其多边形化。

但是，我对此有一些问题。首先，行进立方体通常会产生小的或薄的三角形，这是非常不受欢迎的（原因稍后再说）。其次，我只想在编辑区域和不同的细节层次上对体积进行多边形化。例如，我可能想要一个低分辨率的球体，但有一些微小的高分辨率凸起。我可以使用当前基于表面的系统轻松获得这种细分行为，但我无法想象如何使用行进立方体稳健地做到这一点。

另一个问题是实际的三角形网格在 gpu 上被进一步细分以获得光滑的表面，所以我也需要邻域信息。同样，我已经在当前的半边系统中拥有了这个，但是对于体积多边形化系统，我想它需要大量的额外处理才能找到额外的连接信息。这就是细三角形不好的原因。

所以我有很多限制，我要求这个社区提供想法或相关论文来阅读。我正在考虑使用表面网来避免小/薄三角形问题。另外，我觉得 kd-trees 可能更适合存储多分辨率卷，因为它们看起来比八叉树更灵活。

无论如何，非常欢迎任何想法/建议。

我有以下。该结构是原型的，因此可以正常编译。

我正在尝试写一个八叉树的东西。我想要做的是使用递归函数继续向每个节点添加一个节点，直到我到达一个特定点，此时该函数而不是添加另一个节点，而是添加一个叶子。如果可能的话，我想在没有添加更多节点或叶子时不使用内存。

也许模板在这种情况下会有所帮助，但我不知道如何使用它们......

我认为我没有很好地解释自己。这是一个图表：

我不知道我所要求的内容是不可能的，还是太混乱而无法理解，或者只是愚蠢的，但我自己无法弄清楚。对不起，我无法更好地解释它。

我正在使用 C++98/03 (VC++2008) 并且不能使用 C++11

任何帮助都将不胜感激。

附加信息：

更好的解释：我想要一个数组数组的数组数组。内存使用在这方面非常重要（我存储了数百万个元素，因此单个字节会产生巨大的差异）。每个数组可以包含 8 个以上的数组，但在我需要使用它之前，我希望每个数组都不使用内存。这是一个八叉树。

更多附加信息：

这是另一个图表。它有点大，因此您可能需要右键单击它并选择Open image in new tab使其可读。

我不想要的是“棕色”（红色+绿色）框，其中每个框都为更多节点和叶数据保留内存。这将使用太多的内存来满足我的需求。

这基本上是我想要实现的目标，为简单起见，如图 2D 所示：