Voxel unique ID in 3D space

Question

i am looking for a way to collect a set of voxels. A voxel is a 3D cell that can be full/empty/unknown and is built upon a point cloud (for data reduction). The voxels collection once built is never modified (destroyed and rebuilt each round), but different kind of access are required (neighborood, iterative on all, direct). The voxel space is very very sparse, out of order of 1.000.000 possible voxels in space only at most 1000 are used.

So i decided to use a (unordered since using c++)hashmap to collect them (an octree is an overkill i think) with the voxel ID as a key. Now i need a function to convert in both way a 3D point to voxel ID and the ID to the voxel 3D point centroid.

What i find hard is a very fast way to do it, i'd like to have they key as a single int value like:

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;
}

but for the bijective function i cant come up with anything very fast (as for the previous casts etc that i dont like for a function that must be used so often (200FPS x ~1000 x 3) ).

So:

• is the hashmap a good datastructure (what worries me is the neighborood search)
• what can be a function for A-BIJECTIVE-FUNCTION or for the whole function

Thanks.

Answer 1

#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;
}

This hash/unhash method should be the fastest. Note that I only use 30 bits out of 32 bits of the integer. This allows a maxmimum world size of 4.2950e+009 x 4194304 x 4096. If you want to extend the world limits, you will have to use more/bigger integers.

Hope this can help.

Answer 2

Do you want to collect them space-wise in a way that links every adjacent voxel? If this is what you want, then you could use the Hoshen-Kopelman algorithm in 3D. Writing the code for that should take like a day or two, and you're done. The exmaple in the link is for 2D; expanding that to 3D isn't an issue at all.

Hope this helps.

Answer 3

Why not using a more elaborate key for your hashmap? Instead of a simple int, you could build a tuple with your x,y,z coordinates or implement you own struct. The later option would require implementing operator==() and a hash function. Some information about a good hash function can be found here.