CODEWITHSUNDEEP
c++3dcomputational-geometry
user1286780
user1286780

Reputation: 53

How to handle 3D voxels efficiently?

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?

Upvotes: 5

Views: 6356

Answers (4)

cmannett85
cmannett85

Reputation: 22346

You're going to become unstuck whatever you do, even if you find a perfect memory layout for your sparse grid - that's still too much memory required. The real issue is being able to efficiently store it on disk and intelligently cache the regions of interest.

Thankfully Field3D was developed for just that.

Upvotes: 1

justin
justin

Reputation: 104698

One approach would be to back your actual data with data from a collection.

To illustrate:

struct t_voxel {
  size_t nPoints, minHeight, maxHeight, centorid;
};

struct t_voxel_id {
  uint16_t index;
};

// one dimension
class t_voxel_collection {
  // the actual voxel data needed for the indices represented by the collection of voxelId
  std::vector<t_voxel> d_voxel;
  // here, empty voxel is designated by t_voxel.index = 0
  // this collection is your primary array representation
  // these elements just refer to a unique or shared index in this->d_voxel
  std::vector<t_voxel_id> d_voxelId;
public:
  // >> the interface to access and set, which abstracts the backing collection.
  // and prohibits the client from accessing the actual data.

  t_voxel get(const size_t& idx) const {
    return this->d_voxel[this->d_voxelId[idx].index];
  }
  // ...
};

You can achieve a big drop in memory consumption this way (assuming you see the direction this is going).

That's not a complete answer, but could help in this scenario.

There are several ways to further optimize and share the voxel data in this collection, depending on your use.

Upvotes: 1

hc_
hc_

Reputation: 2628

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.

Upvotes: 3

leftaroundabout
leftaroundabout

Reputation: 120711

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?

Upvotes: 2

Related Questions