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.

What is the highest possible size along one dimension of the voxel space? If it's not more than 1024, you could just concatenate the `x`, `y` and `z` indices as 10-bit numbers into a single 30 (or rather 32)-bit number. Would be a pretty fast and easy solution. — Christian Rau, Nov 29 '13 at 12:50
yes i can make it 1024 with a bit of work... elaborate as answer and i accept it if nothing better. thank you! — jalone, Nov 29 '13 at 12:54
With a 64bit integer you can remove the limit of 1024 max voxel per dimension. Obviously is not completely "free". Read this for more information http://stackoverflow.com/questions/16841382/what-is-the-performance-impact-of-using-int64-t-instead-of-int32-t-on-32-bit-sys — Davide Aversa, Nov 29 '13 at 13:32
I think the canonical way of getting linear ids is interleaving them. I believe there are simd instructions to do it on intel. — Tim Seguine, Nov 29 '13 at 19:35

score 4 · Accepted Answer · answered Nov 29 '13 at 15:02

#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.

This seems the best answer for the second point at this moment. If nothing more in a while i'll accept this. Thank you! — jalone, Nov 29 '13 at 15:07

score 1 · Answer 2 · answered Nov 29 '13 at 14:01

1

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.

answered Nov 29 '13 at 14:01

The Quantum Physicist

24,987
19
103
189

Thanks, maybe not exactly for this task, but can be very usefull in future. – jalone Nov 29 '13 at 15:08

score 0 · Answer 3 · edited May 23 '17 at 12:12

0

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.

edited May 23 '17 at 12:12

Community

1
1

answered Nov 29 '13 at 13:02

Julien B.

88
6

yes i know, but it's exactly what i wanted to avoid, since it requires complex comparisons (at least 3) and while building is performed partly offline the comparisons are not.Thank you anyway! – jalone Nov 29 '13 at 13:25

Voxel unique ID in 3D space

3 Answers3