2

我有一个非常大的点云（> 100000 个点），我想在其中检测平面排列。我决定使用八叉树将这些点分解为非常小的平面簇，然后合并共面的相邻簇。我已经用 C++ 编写了代码，可以将点云快速拆分成小的平面集群，但是如何有效地合并它们却让我望而却步……

我的Octree实现使用指针结构：有OctreeNodes 的数组OctreeNode* children[8]包含指向其子节点的指针，或者NULL如果它是叶节点，则为所有指针。

我的第一个想法是在每个OctreeNode对象中保留一个指向Plane对象的指针。在第一次分割点之后，八叉树中的每个叶子都会得到一个Plane代表叶子中包含的所有点的最小二乘拟合。然后我遍历树中的每个叶节点。对于每个叶节点，我检查它的每个相邻叶节点：如果邻居的平面应该与当前叶的平面合并，我调用Plane* newPlane = Plane::mergePlanes(this->plane, neighbor->plane);创建一个表示两个节点中的点的新平面。

这就是我遇到麻烦的地方......我首先认为我可以简单地用新平面替换两个平面，即plane = newPlane; neighbor->plane = newPlane;完成（除了内存泄漏；我在真实代码中处理它们）。不幸的是，这在实践中不起作用。合并几个平面后，可能会有几个不同OctreeNode的 s 指向一个 s Plane，并且只需替换其中的指针，this->plane而neighbor->plane不是替换指向其旧平面的每个指针。

甚至当我第一次想出这个解决方案时，它似乎也很老套，现在它的缺陷更加明显。任何人都可以想出一种方法来修复我提出的合并方法，或者想出更好的方法吗？

谢谢

4

2 回答 2

2

标准修复是延迟修复节点。有一个访问方法可以查看您指向的平面，然后查看它是否已指向其他地方。如果有，递归搜索直到找到它所在的位置，然后将所有对象修复回当前对象，然后将正确的平面交还。

这比跟随指针要昂贵得多，但实际上这并不像您想象的那么昂贵，因为大多数时候最终对象位于您看到的第一或第二位。

于 2011-04-27T22:27:24.303 回答
0

VTK 有一个类似的点句柄类vtkIncrementalOctreePointLocator。我认为合并插入点的理想点。

例如：

double xyz[3];    // location
id_type point_id; // we get back the point id

// bool InsertUniquePoint( double xyz[3], id_type &point_id );
// return value is true, if new point inserted
bool value = inserter->InsertUniquePoint( xyz, point_id );

所以我的观点是：如果类太大，重建它更容易。

于 2011-04-27T21:16:14.563 回答