How to handle 3D voxels efficiently?

Question

I have a 3D point clouds with million of points. I want to store these points in 3D voxel space. The number of voxles along coordinate axis are more than 3000(x), 4000(y), 1500(z), for a total of 3000*4000*1500 voxels. I need to store in a voxel; maximum number of points, min height, max height and centorid. However, 90% of voxels are empty. So it takes lot of memory to store this. Actually, I want to search 26 neighbor voxels of each voxels in later. So What is the best way to store this data in voxel space and get access to this efficiently?

Creating a multidimensional array, is not the best solution, in term of performance...please any hint?

Answer 1

Classical data structures for this kind of data are kd-Trees and octrees..

Also, you should definitely take a look at the spatial searching and sorting data structures implemented in CGAL.

Answer 2

If it's really "just" millions of points, far more than 90% of the voxels will empty. I'd try a hashed multimap (std::unordered_multimap in C++11) from voxel coordinates to points. That gives you O(1) lookup, like an array. It comes with quite a lot overhead though, but it's probably the best compromise.

The only thing you need for this to work is an equality comparison in the voxel class, and a template specialisation std::hash<voxel>. You won't get "maximum number of points" implemented in any automatical way, but is that really useful anyway?