问题标签 [octree]

我正在寻找将点云分离成未连接的对象，我尝试使用 k-means 算法，但它并没有完成整个工作。
我希望改进我添加的图片中显示的结果。有什么想法或方向吗？ 我的云，使用 k-means 分隔

我有一个 3d 网格（稀疏八叉树），其中每个叶子（最深节点）存储一个带颜色的 3d 点。我想将整个八叉树转换为 3d 点（顶点缓冲区）的线性数组，可以直接上传到 OpenGL。

以一种天真的方式，我可以遍历八叉树的所有节点并填充线性数组。

现在，我面临的问题是，当我向稀疏八叉树添加新的 3d 点并想要更新顶点缓冲区时，我必须遍历整个八叉树才能将数据导入 OpenGL。

当只更新/添加了几个点时，有谁知道如何避免完全迭代？

我能想到的唯一方法是记住八叉树中的哪些元素已添加，并将它们直接附加到顶点缓冲区数组。这会更好，但是当我从八叉树中删除一个元素时就不起作用了。

我使用 C++。

我正在将一个基于八叉树的容器从 10 点到 10 亿点之间的任何位置写入内存。由于要加载的数据量，我需要注意内存消耗。

一切似乎都正常工作并根据需要进行分段，但是插入时间非常慢。可能是因为父母之间的数据重新分配给孩子。我能做些什么来优化它吗？我是否正确实施了这一点？我可以在每个节点中保留向量以包含最大数量的点，但这会显着增加所需的内存。

使用一个简单的 R-tree 类型容器，我在大约 48 秒内加载了 4.68 亿个点。使用下面的八叉树，我在 245 秒内加载。

我正在尝试为空间分解算法实现我自己的八叉树类。我想做的是遍历树并将叶子节点的顶点保存在向量中。

到目前为止，我以这种方式实现了八叉树（为简单起见，它是二维的）：

要使用这个类，我主要是这样写的：

但是在访问了第一个叶子节点之后，我得到了一个分段错误：

dede@dede-P35V2:~/build/AdaptiveGrid/build$ ./adapative_grid

数据集有 185 个点

深度：0

中心：-0.75 -0.75

分段故障

拜托，你能解释一下我做错了什么吗？

谢谢。

我有一个应用程序，我在其中使用八叉树来存储轴对齐边界框（AABB）的体积网格。

给定一个防水三角形网格，我需要：

• 查找 AABB 是否与表面网格相交或完全在表面网格内部/外部，

• 用相交的 AABB 剪裁表面网格，以生成完全位于每个 AABB 内的三角形。

包含 AABB 的三角剖分和八叉树都是动态的。八叉树中的叶节点数量巨大。表面网格中的三角形数量要少得多（O(10^9 - 10^13) 个八叉树节点，与 O(10^6) 个三角形相比）。

哪些数据结构和算法适合我的问题？

现在我：

• 将三角形存储在与体积网格相同的八叉树中，
• 将每个三角形存储在包含它的最小八叉树节点中，
• 通过从该 AABB 遍历到根节点及其叶子，用单个 AABB 剪裁三角形网格，用 AABB 剪裁节点中包含的每个三角形。

直到叶子完全包含在 AABB 中的节点中的三角形不需要任何裁剪，而从 AABB 到根的节点中包含的三角形需要裁剪。然而：

• 由于我存储三角形的方式，我没有可以存储在每个单个八叉树节点中的最大三角形数量的上限，所以我没有必须的三角形数量的上限用单个 AABB 剪裁表面网格时被剪裁。

• 如果三角形存储在根节点中，则测试 AABB 是否与三角形网格相交可能需要裁剪。

• 无法快速确定节点是否在网格内部/外部/与网格相交。

我有一个八叉树，我必须删除一个通过它的分支搜索的节点。该程序可以找到该节点，但我很难删除它。当我创建八叉树的对象并创建一些节点但不删除它们时，析构函数将删除八叉树：

但是当我想用这种方法删除一个具体的节点时，

调用析构函数后出现异常。抛出异常：读取访问冲突。节点为 0x4。

我正在一步一步调试，我发现了一些奇怪的东西。当我创建一个节点时，我这样做：

没关系，我设置了值，节点的值为 xvalue，子节点为 NULL。但是在我使用 deletebranch() 方法删除该节点后，我的节点发生了这样的变化。

• n 0x00500788 {值=0 孩子=0x0050078c {0x00000004 {值=？？？child=0x00000008 {???, ???, ???, ???, ???, ...} }, ...} } Octree::node * value 0 int
• 孩子 0x0050078c {0x00000004 {值=？？？child=0x00000008 {???, ???, ???, ???, ???, ???, ???, ???} }, 0xfdfdfdfd {...}, ...} 八叉树::节点 *[8]
• [0] 0x00000004 {值=？？？child=0x00000008 {???, ???, ???, ???, ???, ???, ???, ???} } Octtree::node *
• [1] 0xfdfdfdfd {值=？？？child=0xfdfdfe01 {???, ???, ???, ???, ???, ???, ???, ???} } Octtree::node *
• [2] 0xdddddddd {值=？？？child=0xdddddde1 {???, ???, ???, ???, ???, ???, ???, ???} } Octtree::node *
• [3] 0x29122f71 {值=？？？child=0x29122f75 {???, ???, ???, ???, ???, ???, ???, ???} } Octtree::node *
• [4] 0x0000a9bd {值=？？？child=0x0000a9c1 {???, ???, ???, ???, ???, ???, ???, ???} } Octtree::node *
• [5] 0x004d5228 {value=5249384 child=0x004d522c {0x005007a0 {value=5067304 child=0x005007a4 {0x004fe218 {...}, ...} }, ...} } Octree::node *
• [6] 0x004fe218 {value=5244832 child=0x004fe21c {0x004d00c4 {value=5235224 child=0x004d00c8 {0x00501968 {...}, ...} }, ...} } Octree::node *
• [7] 0xdddddddd {值=？？？child=0xdddddde1 {???, ???, ???, ???, ???, ???, ???, ???} } Octtree::node *
• 这个 0x0043f818 {root=0x005006b0 {value=0 child=0x005006b4 {0x00000000 , 0x00000000 , 0x00000000 , ...} } } 八叉树 *

我真的不明白为什么会这样，因为我删除它后从未更改过节点。我认为这就是为什么我在析构函数中得到了那个异常。我应该如何删除一个节点？也许尝试抓住？

这是头文件：

我已经创建了一个八叉树数据结构，但它还不完美。我为复制构造函数和析构函数而苦苦挣扎。这是我的头文件：

构造函数、析构函数、复制构造函数

以下是我主要创建对象的方式：

在searchandset函数中，我在第一棵树上为节点号 8 赋值。之后，我调用复制构造函数并打印第二棵树的第 8 个节点。该值与我为第一棵树提供的值相同，但是当调用析构函数时，我总是遇到此异常：

抛出异常：读取访问冲突。节点为 0xDDDDDDDD。

据我所知，这意味着我试图删除已删除的节点。对象“tree2”是与“tree”不同的对象，具有相同的值和节点，不是吗？然后我不明白上面的那个例外。我是 C++ 的新手，我知道它是基本的东西，所以如果有人能引导我走向正确的方向，我将不胜感激。

我正在为八叉树库编写一个边界框模块。你可以在这里找到我的分店。在下面的函数中，我尝试明确Octree. 问题是，并非所有边界框都是有效的。

这是有问题的函数，然后是在ghci.

复制问题：

git clone https://github.com/mlitchard/octree.git

git checkout MBB

stack ghci

在ghci中，执行以下操作：

答案是 9，但应该是 0。

我觉得其中一个fooBox where条款是错误的，但我已经将每个条款都翻了好几遍，我没有看到它是哪一个。

如果你像我一样需要视觉辅助，我发现这张照片很有帮助。我的样本做了 2 个细分。

任何对出了什么问题的见解将不胜感激。

我正在尝试获取点云的最近邻居，但由于某种原因，我得到了一个矢量下标超出范围错误。当我尝试使用调试器找出它是如何超出范围时，所有的值似乎都很正常。

这是我正在使用的代码（我取自官方文档）

拥有一张图片，我想将其简化为x颜色并将其保存在 png 文件中。

我选择使用 k-means（OpenCV 中已经提供）来执行此操作。在全分辨率图像上，它需要超过一分钟，所以我将图像调整为更小的东西，然后我得到了调色板。

用调色板中的颜色替换原始图像中的颜色的最佳方法是什么？

我所做的一个简单实现是获取图像中的每个像素并计算该像素与调色板中的像素之间的欧几里德距离，然后在调色板中选择最接近的颜色。这在视觉方面是可以的，但是调色板大小超过 30 需要 30 多秒。

我知道要走的路是使用八叉树或某种形式的k-最近邻算法，但老实说，我不知道我是否应该花时间来实现我认为已经实现的东西。

我可以使用 OpenCV 中适合我的场景的东西吗？我可以期望它比使用欧几里得距离至少快 2 倍吗？

C++ 示例将不胜感激。