4

我正在寻找一种方法来收集一组体素。体素是一个 3D 单元，可以是完整的/空的/未知的，并且建立在点云之上（用于数据缩减）。一旦构建的体素集合永远不会被修改（每轮销毁和重建），但需要不同类型的访问（邻域，迭代所有，直接）。体素空间非常稀疏，在空间中可能有 1.000.000 个体素无序，最多仅使用 1000 个。

所以我决定使用（因为使用 c++ 后无序）hashmap 以体素 ID 作为键来收集它们（我认为八叉树是一种过度杀伤力）。现在我需要一个函数来以两种方式将 3D 点转换为体素 ID，并将 ID 转换为体素 3D 点质心。

我发现困难的是一种非常快速的方法，我希望将它们键为单个 int 值，例如：

unsigned int VoxelsMap::pointToVoxelId(const Vector3f & point){

    unsigned int id = 0;

    int x = (int)floor(roundpoint[0]);
    int y = (int)floor(roundpoint[1]);
    int z = (int)floor(roundpoint[2]);

    id = A-BIJECTIVE-FUNCTION(x, y, z);

    return id;
}

但是对于双射函数，我不能很快想出任何东西（至于以前的演员表等，我不喜欢必须经常使用的函数（200FPS x ~1000 x 3））。

所以：

  • hashmap 是一个好的数据结构吗（让我担心的是邻域搜索）
  • 什么可以是 A-BIJECTIVE-FUNCTION 或整个函数的函数

谢谢。

4

3 回答 3

4 
#include <iostream>

using namespace std;
int main()
{
    int x = 2.1474e+009;
    int y = -2097152;
    int z = -2048;

    int rx = x;
    int ry = y << 10;
    int rz = z << 20;

    int hashed = rx + ry + rz;

    x = rx;
    y = ry >> 10;
    z = rz >> 20;

    cout << hashed << endl;
    cout << x << " " << y << " " << z << endl;
    return 0;
}

这种散列/取消散列方法应该是最快的。请注意，我只使用 32 位整数中的 30 位。这允许最大世界大小为 4.2950e+009 x 4194304 x 4096。如果要扩展世界限制，则必须使用更多/更大的整数。

希望这能有所帮助。

于 2013-11-29T15:02:22.300 回答
1

你想以一种连接每个相邻体素的方式在空间上收集它们吗？如果这是您想要的，那么您可以在 3D 中使用Hoshen-Kopelman算法。为此编写代码大约需要一两天时间，然后就完成了。链接中的示例适用于 2D；将其扩展到 3D 根本不是问题。

希望这可以帮助。

于 2013-11-29T14:01:47.237 回答
0

为什么不为您的 hashmap 使用更精细的键？您可以使用 x,y,z 坐标构建元组，或者实现您自己的结构，而不是简单的 int。后一个选项需要实现 operator==() 和一个散列函数。可以在此处找到有关良好散列函数的一些信息。

于 2013-11-29T13:02:52.180 回答