三维空间中的体素唯一ID
我正在寻找一种收集一组体素的方法。体素是一种3D单元，可以是满/空/未知的，并建立在点云上(用于数据约简)。体素集合一旦构建就不会被修改(每一轮都会被破坏和重建)，但是需要不同类型的访问(邻域，迭代，直接)。体素空间非常稀疏，在空间中使用1.000.000个可能的体素，最多只能使用1000个体素。
因此，我决定使用一个(自使用c++以来没有排序)的hashmap来收集它们(我认为八叉树是一种过激行为)，并以体素ID作为键。现在，我需要一个函数来将三维点转换为体素ID，将ID转换为体素点质心。
我发现困难的是一种非常快速的方法，我想让它们作为一个独立的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;
}但是对于双射函数，我不能很快想出任何东西(对于以前的转换等等，我不喜欢必须经常使用的函数(200 for x ~1000 x3 ) )。
所以：
- 这个hashmap是一个很好的数据结构(我担心的是邻居搜索)
- 什么是A-双函数的函数，还是整个函数的函数？
谢谢。
回答 3
Stack Overflow用户
发布于 2013-11-29 15:02:22
#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。如果您想要扩展世界限制，您将不得不使用更多/更大的整数。
希望这能帮上忙。
Stack Overflow用户
发布于 2013-11-29 14:01:47
你想要收集空间的方式连接每一个相邻的体素吗？如果这是您想要的，那么您可以在3D中使用霍森-科佩尔曼算法。为此编写代码大概需要一两天的时间，你就完成了。链接中的示例是2D，将其扩展到3D根本不是问题。
希望这能有所帮助。
Stack Overflow用户
发布于 2013-11-29 13:02:52
为什么不为您的hashmap使用更精细的密钥呢？可以使用x、y、z坐标构建元组，也可以实现自己的结构，而不是简单的int。后一个选项需要实现operator==()和一个哈希函数。有关一个好的哈希函数的一些信息可以找到这里。
https://stackoverflow.com/questions/20286179
复制相似问题
腾讯云开发者
