问题标签 [octree]

我编写了一个完整的八叉树实现，没有对 3D 重建进行太多优化，但是，树结构包含太多指针，不能支持超过 256^3 个体素。

从理论上讲，对于非树结构，如果我使用vector<bool>每个体素使用约 1 位的 a，这将更容易接受，因为非树结构可以支持 2k^3 和 8GB 内存。

然而，优化的八叉树结构应该能够做到等于或比这更好，因为：

1. 它不应该存储每个体素，因为冷凝可以允许压缩附近的相同值体素。

2. 它不应该使用太多的指针，因为指针本身已经使用了大量的字节。

3. 八叉树必须具有相当低的节点/体素比率。

对于完整的八叉树，节点数可以计算为(s^3 -1) / 7。是s体积分辨率，它是 2 的幂。例如，如果s = 4，我需要1 + 8 = 9八叉树中的节点来表示 4x4x4 体素网格。

有谁知道符合这些规范的 C++ 八叉树实现？

我正在编写一个复杂的树数据结构，它存储了很多指针。指针本身占用了大量空间，这就是我期望保存的。

所以我在这里问是否有这方面的例子。例如：对于 64 位数据类型，如果它指向的数据肯定是连续的，我可以使用 32 位或更少的指针吗？

我找到了一篇名为Transparent Pointer Compression for Linked Data Structures的论文，但我认为可能有一个更简单的解决方案。

更新：

它是一个八叉树。一篇关于 GPU 的论文是GigaVoxels: A Voxel-Based Rendering Pipeline For Efficient Exploration Of Large and detailed Scenes，他们在 GPU 上使用 15 位指针

我正在研究一个八叉树实现，其中树节点使用它们的维度长度（作为 2 的幂）进行模板化：

并专门用于 N = 0（叶子）指向数据。

（除此之外：我想我可能还需要一个不包括父指针的 N​​_MAX 特化，否则 C++ 会生成不断增加的 N 的类型？但这与我的问题并不真正相关。）

我想创建一个函数，它沿着我的八叉树占据的 3D 空间中的一条射线前进，所以表面上我可以只保留一个指向根节点（具有已知类型）的指针，并在每次从根节点遍历八叉树步。但是，我更喜欢“本地”选项，我可以在其中跟踪当前节点，以便尽可能从树的较低位置开始，从而避免不必要地遍历八叉树的上层节点。

但我不知道该类型指针可能是什么（或任何其他实现方式），因此我不会体验切片。

我不受模板的束缚，因为维度可以简单地实现为long const. 但是我不知道如何使叶子具有与 inode 不同的子类型。

谢谢你的帮助！

更新

我想这样做而不是类似的原因是因为count每个节点中的变量：如果计数为 0，我想跳过整个立方体，而不是浪费时间通过叶子我知道是空的。（这是针对光线追踪体素引擎的。）

于是我写了一个八叉树结构体，如下：

我担心的是析构函数......
它会调用孩子的析构函数还是我必须自己做？

我正在使用轴对齐边界框的八叉树来分割场景中我进行物理模拟的空间。问题是，场景非常大（空间），我需要检测远距离大物体的碰撞以及近距离的小物体。问题是，场景中只有少数几个，但相距几公里，所以这意味着很多空白空间。所以基本上我浪费了 2 GB 的 RAM 来存储边界框对于空扇区。我只想为实际包含某些东西的扇区分配内存（让它们成为指向 AABB 的指针），但这意味着每帧有数千个分配来重新创建八叉树。如果我使用一个池为了应对分配的放缓，这仍然意味着我为我的应用程序分配了 2 gigs 的 RAM。还有其他方法可以实现这一点吗？

尽管我尝试以二叉树遍历的方式接近它，但我无法弄清楚迭代八叉树遍历的过程。对于我的问题，我有具有子指针和父指针的八叉树节点，我想迭代并且只将叶节点存储在堆栈中。另外，迭代遍历比递归遍历更快吗？

我正在 OpenGL 4.3.0 中实现体素光线投射器。我有一个基本版本，我将浮点值的 256x256x256 体素数据集存储在相同尺寸的 3D 纹理中。

但是，我想使用八叉树制作一个 LOD 方案。我将数据存储在主机端的一维数组中。根的索引为 0，根的子节点的索引为 1-8，下一级的索引为 9-72，依此类推。八叉树总共有 9 个级别（最后一个级别具有完整的 256x256x256 分辨率）。因为八叉树总是满的，所以结构是隐式的，不需要存储指针，每个体素只有一个浮点值。我已经设置好了一维索引和遍历算法。

我的问题是我不知道如何将它存储在纹理中。GL_TEXTURE_MAX_SIZE 太小（16384），无法使用我已经找到索引的一维数组方法。我需要将它存储在 3D 纹理中，我不知道当我尝试将我的 1D 数组塞入其中时会发生什么，也不知道如何选择尺寸和 1D->3D 转换方案以免浪费空间或时间。

我的问题是，是否有人有一个很好的策略来将整个八叉树结构存储在一个 3D 纹理中，在这种情况下如何为它选择维度和索引。

I am developing a small minecraft style game on XNA. I generates a voxel mode, so I'm looking to be optimized to the maximum my matrix "World"! This is the one I'm looking for example "How to Use Octree with Xna ?." Unfortunately, I have not found a tutorial on this on google or other ... I find this strange, because this technology is much used!

I wish I could turn my 100x100x100 matrix containing for each box a bit (1 or 0) indicating whether or not there is a block. Is this a tutorial "Octree" I need to do this? Or can someone show me an example of a transformation matrix3D to a Octree matrice ?

Thousand thank you.

我正在实现一个体素八叉树光线投射器，唯一剩下的就是重新排列数据以填充八叉树的叶级别，以便可以对数据进行平均以构建树的较低级别。

为了方便起见，我最初考虑的是 2D（四叉树）。我在图中的左侧排列了数据，我目前可以将其重新排列到右侧。例子是8x8.

但是，我意识到我需要按节点顺序对数据进行排序，如下图所示：

换句话说，我想从一个数据对应于这样的索引的数组中去：

到将按此顺序包含数据的数组：

以8x8四叉树为例。

我不知道该怎么做。我的主要问题是处理任意树大小。如果我事先知道大小，我可能可以硬编码一组嵌套循环，但这显然不是一个很好或优雅的解决方案。我在想可能有一种递归的方式来实现它。

这就是我以图一中描述的方式对数据进行排序的快速而肮脏的草图。它基本上是通过跟踪原始数据中的四个位置来工作的，然后随着新数组的填充而将这些位置向前推进。据我所知，这很好用，但不能满足我的需要：

八叉树是行进立方体的特例吗？我的意思是八叉树是否使用与行进立方体相同的三角立方体。我知道八叉树是四叉树的 3d 形式。我只想知道我的方向是否正确。树形成后，八叉树形成三角形的步骤（用于创建表面）如何与行进立方体的步骤相同？