问题标签 [octree]

我正在创建一个类似于 Minecraft 的地形引擎，我想知道八叉树到底是什么。使用我的引擎，我将它的每个部分分成块或区域 - 从我所读到的内容中，这与它有关。另外，我想知道指数是否确实会提高游戏中的性能，如果可以，会提高多少？任何其他提高性能的想法/方法将不胜感激。请注意，我已经包含了背面剔除，如果盒子或一侧被隐藏，则不要显示该侧。

正如我在之前的几篇文章中提到的，我正在创建一个类似于引擎的东西。

我已将地形划分为多个区域，并且仅渲染位于相机视锥体中的区域。当每个区域的顶点缓冲区被构建时，它们会检查每个块是否可以看到，如果不是，则不会将其添加到缓冲区中，如果是，它会检查哪些边没有被其他块包围并构建这些面. 我也启用了逆时针剔除。

任何人都可以提出任何其他提高性能的方法（注意：我还没有添加索引缓冲区，但只使用顶点缓冲区进行渲染）？前面提到的原因可能是我帧率低的原因......而且我也想知道向这个引擎添加索引是否会提高性能。

我也不认为这与内存分配有任何关系。

编辑：好的，我已经暗示了索引缓冲区，性能已经大大提高，但我仍然认为它可以增加更多......

请推荐一本关于空间数据结构的书。我有兴趣Quadtrees and Octrees。

我为封闭曲面创建了一个边界八叉树。所有包含曲面的八叉树立方体都被划分为同一级别。所以所有叶子节点的大小都是一样的。我需要帮助找出每个终端立方体的邻居。我尝试参考不同的论文，但无法弄清楚如何在 Matlab 中实际实现它。现在，我将所有终端立方体视为体素立方体（不使用八叉树数据结构），并使用蛮力找出 26 个可能的邻居中的哪些在构成表面的立方体列表中。获得输出需要很长时间。我是编程新手，所以如果有人能提出更有效地找到叶节点邻居的方法以及如何通过在 matlab 中编码来实现该方法，我将不胜感激。谢谢！！

这是我过去几个小时一直在考虑的事情。这是一个头脑练习。

所以我今天知道了八叉树是什么！很有意思！我一直在考虑如何实现一个解析为体素的八叉树。

我现在无法解决的最大问题是引用八叉树中的位置。

免责声明：首先，我将在二维平面中使用四叉树来可视化我的问题。其次，我在这里不理解正确的术语，我将假设八叉树中作为父级的任何细分都是“分支”，而任何只有子级的细分（在这种情况下它解析为体素）是一片树叶”。第三，我要对四叉树的一个分支中的每个空间进行编号，从左到右从上到下 {1,2,3,4}

假设我有一个定义 16x16 单位空间的四叉树。在位置 [16,16] 我存储了一个体素。

现在假设我们将一个体素添加到位置 [4,4]。（注意，我们从零开始）

现在假设我想检查 [16,8] 以查看是否存储了体素。使用前面的方法，我们将在技术上遍历这些分支：

但是 4->1 没有分配任何数据，所以它是空的。（它没有细分，因为它没有在使用中）。

我的问题变成了这个，我怎样才能快速遍历四叉树找到体素？

我的第一个也是最简单的方法是以我上面使用的格式沿着分支向下移动。

这里的问题是 voxelArray[16][16]、voxelArray[4][4] 或 voxelArray[16][8] 要快得多。使用更大的四叉树 (256x256) 会增加深度（从 4 到 8）。嵌套数组仍然是 2 个内存操作。（注意，对于四叉树，实际上我们将使用访问器的东西并检查以确保孩子存在条件逻辑）

我的第二个想法是将四叉树本身存储为体素。例如，假设我们有一个 2x2 数组，空它看起来像

在位置 [1,1] 我们将添加一个体素，它会变成

如果我们要存储四叉树，它看起来像这样

把它带到一个 4x4 和

尽管现在您可以直接访问数据，但您已经失去了四叉树的内存紧凑性，您仍然可以执行许多逻辑操作。IMO 仅当您有大面积的 0 和小范围的 1 时，这才会有效。

通过将体素存储在四叉树/八叉树中，您可以在循环遍历所有体素时获得性能，但在直接访问它们时会损失性能。

我正在寻找一种好的光线八叉树交集算法，它可以让我以迭代的方式获得光线穿过的叶子。我计划在 CPU 上实现它，因为我还不想深入研究 CUDA :)

目前，我的 Voxel raycaster 只是在 XxYxZ 体素的非分层阵列上执行 3D DDA（Amanatides/Woo 版本）。您可以想象，当有很多空白空间时，这会非常昂贵，如下图所示（更亮的红色 = 更多工作 :)）：

我已经发现这个任务有两种算法：bottom-up，从叶子向上工作，top-down，基本上是深度优先搜索。

我已经找到了 Revelles 从 2000 年开始的算法，称为An Effective parametric algorithm for octree traversal，看起来很有趣，但已经很老了。这是一种自上而下的算法。

最流行的自下而上方法似乎是K. Sung，A DDA Octtree Traversal Algorithm for Ray Tracing，Eurographics'91，North Holland-Elsevier，ISBN 0444 89096 3，p。73-85。问题是大多数 DDA 八叉树遍历算法都期望八叉树具有相同的深度，这是我不想要的 - 空子树应该只是一个空指针或类似的东西。

在最近关于稀疏体素八叉树的文献中，我设法通读了（最值得注意的是莱恩关于 SVO 的工作，它们似乎都基于某种 GPU 实现的 DDA 版本（Amanatides/Woo 风格）。

现在，这是我的问题：有没有人有实现基本的、简洁的光线八叉树相交算法的经验？你会推荐什么？

我目前正在为我的学士论文项目实施八叉树。我的八叉树将 std::vector 作为参数：

我在渲染顶点并对它们进行任何剔除测试等之前询问通常用于存储顶点的内容。

我现在保持这个非常简单，我所拥有的只是一个渲染网格的函数。一些片段：

现在，当渲染它时，我使用我的自定义结构 GridVertex，即为 pos 保存一个 D3DXVECTOR9，为颜色值保存一个 DWORD，并通过将灵活的顶点格式设置为 GRIDFVF 来告诉 GPU。但是在我的八叉树中，如果某些顶点在我的八叉树内的节点内，我只想存储位置以执行测试，依此类推。因此，我想创建另一个名为 SceneManager 的类并将所有值存储在 std::vector 中，最后将其传递给我的 Octree 类，该类进行测试，然后将检查的顶点传递给 GPU。这会是一个可靠的解决方案还是实现这样的事情的常见方法？提前致谢

我将编写一个 KDTree 的模板化实现，它现在只能用作 BarnesHut 实现的 Quadtree 或 Octree。

这里的关键是设计，我想指定树定义为模板参数的维数，然后简单地声明一些常用方法，它们会自动以正确的方式运行（我认为那时需要一些模板专业化）。

我想专门化模板以获得 2^2（四叉树）或 2^3（八叉树）节点。

有人有一些设计理念吗？我想避免继承，因为它限制我进行动态内存分配而不是静态分配。

这里 N 可以是 2 或 3

另一个问题是四叉树有 4 个节点但 2 维，八叉树有 8 个节点但 3 维，即节点数为2^dimension。我可以通过模板元编程指定这个吗？我想保留数字 4 和 8，以便循环展开器可以更快。

谢谢！

我正在使用这篇维基百科文章中描述的技术构建一个四叉树。我将坐标存储在 2 维或 3 维数组中。

我需要一种方法来计算 z 顺序中下一个框的坐标。它可以通过交错位来工作，增加一而不是去交错，但这会变得非常复杂。我希望有一个类似于文章中 cmp_zorder(...) 方法的实现，它可以在不交错位的情况下工作。

我正在与 opencl 合作开发体素光线投射引擎。我正在尝试做类似于Crassin的 Gigavoxels 的事情。在本文中，他们使用八叉树来存储体素数据。目前我只是试图在八叉树内下降，直到到达包含渲染数据的叶子。

我做了两个实现：一个在 GPU 上的 OpenCl 中，另一个在 CPU 上的 C++ 中。我遇到的问题是，在 GPU 上，算法正在经历错误数量的级别，直到到达八叉树内的叶子。CPU 版本给出了正确的结果。两个版本的算法相同，代码几乎相似。

你们知道可能是什么问题吗？可能是硬件问题、OpenCl 问题还是我做错了什么？我在三个不同的 nVidia GPU 上遇到了相同的结果。

这是 C++ 代码：

这是 OpenCL 代码：

这是extractOctreeNodeAddress，根据要求：

这两个函数都只是做一些位操作：

OpenCL 版本：

C++ 版本：

嗨，我发现了一些有趣的东西。我尝试手动测试不同的变量，比较它们在单个精确像素和相机位置和方向上的 CPU 和 GPU 版本。在下面的代码中，如果我像现在这样运行程序，像素被打印为白色，并且值（> 5.5 与 CPU 实现相比完全错误），但是如果我注释最后一个 if 结构，并取消注释第一个，我得到的结果是红色的......这对我来说有点无法解释。有任何想法吗？