问题标签 [octree]

线程化八叉树的有效方法，使得八进制中每个八进制单元所包含的指针可以轻松地遍历同一级别的树。

我们必须在这里使用全线程树，以便我可以使用 openmp 在同一级别并行化代码。

我想运行 Barnes Hut N 体模拟（维基百科文章）。我知道八叉树的单个节点将占用多少内存，但我无法弄清楚对于给定数量的粒子，最坏的内存使用情况是什么。简而言之，我想知道对于给定数量的粒子，八叉树中可能存在多少个节点。我需要知道这一点才能知道为八叉树分配多少内存。

编辑：

哦，如果有人想给我代码而不是仅仅和解释，我正在用 C 语言编写。

我有这个，这比最坏的情况还要糟糕。但它保证至少分配足够的内存。我希望有人能给我一些内存效率更高的东西。

我在网上搜索了有关八叉树容器如何工作的解释。我找不到任何关于如何工作的明确解释。（至少，这对我来说很有意义......）有谁知道如何实现一个八叉树容器？一个有 8 个孩子（左右）。如果是这样，你介意分享/解释逻辑......或者我可以去哪里学习如何实现一个。

我很难掌握如何迭代八叉树或四边形。这可能是因为我没有经历过不同的迭代神话。但是让我们假设我生成了一个四叉树，它包含 float x,y,z; 双字颜色。现在，我们还假设这个节点一次只能产生 4 个孩子（这些孩子都可以产生 4 个孩子，等等），直到： 达到 7 个级别（这样孩子就不能再创建孩子了，但是它兄弟/姐妹可以），创建的所有 4 个孩子都是相同的 dword 颜色（同样，如果发生这种情况，其兄弟/姐妹仍然可以生产），或者创建的节点总数等于 87380。发生上述情况时，将其放入容器。这个过程还在继续。

现在这个包含节点的容器（例如）有 7 层深，所有子节点的子节点的所有子节点都有不同的 x、y、zs 和颜色。我遇到的问题是我如何迭代这个容器，我怎样才能遍历所有的孩子，姐妹们？由于根导致 4 个孩子，而这 4 个孩子有 4 个孩子，依此类推，依此类推：4^1+4^2....+4^7。如何在不编写复杂的 if 语句和遍历整个节点（从根开始）的情况下找到我想要的节点？容器（产生节点的容器）是否需要额外的代码来简化这个过程？

对不起，如果问题是一般性的。

在过去的几天里，我一直在搞乱八叉树和四叉树。我可以构建它们、迭代它们并吐出我需要的信息。我也知道它们在碰撞检测中非常有用，您可以将屏幕细分为更小的部分，以便能够检测屏幕上特定部分的移动，而不是一直遍历整个屏幕。但是，我无法理解如何使用八叉树或四叉树来生成立方体类型的世界。

以下是我一直在思考的一些想法：

1）您使用四边形/八角树细分一个集合立方体（10x10x10），并细分它直到至少有一个叶子是均匀的；然后，您删除所有其他不统一的叶子，从而为您提供不同大小的立方体。

2）你在空间（x，y，z）中细分一个点，直到你得到一个立方体，它至少有一个大小相同的叶子，或者达到节点的深度，并使用所有这些位置（x， y,z) 作为不同类型块的位置。

谁能解释在构建这样一个 3D 环境中使用八叉树或四叉树背后的逻辑？它是基于 x、y、z 还是基于恒定的立方体测量？我非常不确定如何进行。

我正在通过八叉树量化为图像生成调色板。它为任何图像提供了最多 256 种颜色。现在我只想显示这 256 种颜色中图像的前 10 种颜色（根据图像中颜色的数量）。我怎么能在 C# 中做到这一点？

我在directx11 中创建了一个简单的场景，它有一个平面作为地板，有几个球体、立方体和矩形墙。只加载了 3 个对象：平面、立方体和球体；但是立方体和球体被多次实例化，具有不同的缩放、位置和旋转。其中两个对象是动态的。

考虑到具有不同比例和旋转的对象实例，我想将整个场景（100x100x20 单位）体素化为 0.2 单位体素。

我已经阅读了几篇关于体素化的文章，并获得了来自 GPU Pro 3 的“Practical Binary Surface and Solid Voxelization with Direct3D 11”的源代码；但是所有这些文章都展示了单个对象的体素化——将它们的三角形分割成一个网格。

我将如何扩展这些方法以解决具有多个对象实例的整个场景？

我唯一能想到的就是我必须对整个场景进行自上而下的八叉树划分。但对于动态场景，这会不会太贵？

对于我的场景，我为每个加载的模型使用一个缓冲区，所以如果我要在计算着色器中进行体素化，我是否需要将所有三个缓冲区复制到一个缓冲区中？我如何考虑模型实例？

谢谢你。

我从 Scenegraph 2009 课程笔记的Advanced IlluminationTechniques for GPU-Based Volume Raycasting中学习了一些体积渲染技术。我对对象顺序空白空间跳过感兴趣，它将边界框光栅化为许多小块，如下图所示：

我想知道如何实现这个？通过八叉树？或任何其他技术？我已经实现了一个简单的光线投射体积渲染程序，没有对象顺序空白空间跳过。代码片段或伪代码会有很大帮助。

是否有内存和速度有效的方法来在哈希图中动态存储唯一键：值对？密钥保证是唯一的，但它们的数量经常变化。插入和删除必须快速。

我所做的是包含有符号距离场的八叉树（不是线性/完整）。八叉树经常更新。我想做的是尝试使其无指针以节省一些空间。

第一次在这里发帖，但我已经阅读该网站几年了。我正在尝试在 C# 中实现一个简单的泛型八叉树（使用一些 XNA 包括）。我已经进行了彻底的研究并且我理解了这个概念，但我似乎无法让它发挥作用。四处搜索会产生一些其他语言的实现，但它们似乎都是针对特定应用程序定制的；我还没有真正理解这些。

下面是到目前为止我的八叉树类，Vector3、BoundingBox 和 ContainmentType 来自 XNA。我输入最大和最小点，以及边界内的点列表。然而，实际上没有一个点被添加到树中。任何帮助将非常感激！