Как эффективно обрабатывать 3D вокселы?

Question

У меня 3D облака точек с миллионами точек.Я хочу хранить эти точки в трехмерном пространстве вокселей.Число вокселей вдоль координатной оси составляет более 3000 (x), 4000 (y), 1500 (z), в общей сложности 3000 *4000* 1500 вокселей.Мне нужно хранить в вокселе;максимальное количество точек, минимальная высота, максимальная высота и центорид.Однако 90% вокселей пусты.Так что требуется много памяти, чтобы сохранить это.На самом деле, я хочу найти 26 соседних вокселей каждого вокселя позже.Итак, каков наилучший способ хранения этих данных в пространстве вокселей и эффективного доступа к ним?

Создание многомерного массива - это не лучшее решение с точки зрения производительности ... пожалуйста, любой намек?

Answer 1

Классическими структурами данных для этого вида данных являются kd-Trees и октр. .

Кроме того, вы обязательно должны взглянуть на пространственный поиск и сортировку структур данных, реализованных в CGAL. ​​

Answer 2

Если это действительно «просто» миллионы точек, гораздо больше, чем 90% вокселей будут пустыми. Я бы попробовал хэшированную мультикарту (std::unordered_multimap в C ++ 11) от воксельных координат до точек. Это дает вам O (1) поиск, как массив. Это идет с довольно большими накладными расходами, но это, вероятно, лучший компромисс.

Единственное, что вам нужно для этого, - это сравнение на равенство в классе вокселей и специализация шаблона std::hash<voxel>. Вы не сможете реализовать «максимальное количество баллов» каким-либо автоматическим способом, но действительно ли это так полезно?

Answer 3

Вы станете отклеены от всего, что делаете, даже если вы найдете идеальный план памяти для своей разреженной сетки - это все еще слишком много памяти. Реальная проблема заключается в возможности эффективно хранить его на диске и разумно кэшировать области интереса.

К счастью Field3D был разработан именно для этого.

Answer 4

Один из подходов состоит в том, чтобы подкрепить ваши фактические данные данными из коллекции.

Для иллюстрации:

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];
  }
  // ...
};

Таким образом можно добиться значительного снижения потребления памяти (еслипосмотрите, в каком направлении это происходит).

Это не полный ответ, но может помочь в этом сценарии.

Существует несколько способов дальнейшей оптимизации и совместного использования данных вокселей в этой коллекции, в зависимости отна ваше использование.