Voxel уникальный идентификатор в 3D пространстве

Question

Voxel уникальный идентификатор в 3D пространстве

Я ищу способ собрать набор вокселей. Воксель — это трехмерная ячейка, которая может быть полной / пустой / неизвестной и построена на облаке точек (для сокращения данных). Однажды созданная коллекция вокселей никогда не изменяется (уничтожается и перестраивается каждый раунд), но требуется различный доступ (соседний, итеративный для всех, прямой).
Пространство вокселей очень очень редкое, из порядка 1.000.000 возможных вокселей в пространстве используется не более 1000.

Поэтому я решил использовать (неупорядоченный, поскольку использовал c ++) хэш-карту для их сбора (я думаю, что октре — это перебор) с идентификатором вокселя в качестве ключа. Теперь мне нужна функция для преобразования как 3D-точки в ID вокселя, так и ID в центроид 3D-точки вокселя.

То, что я нахожу сложным, — это очень быстрый способ сделать это, я бы хотел, чтобы они имели ключевое значение типа int, например:

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

но для биективной функции я не могу придумать что-то очень быстрое (как и для предыдущих приведений и т. д., которые мне не нравятся для функции, которую нужно использовать так часто (200FPS x ~ 1000 x 3)).

Так:

является ли хэш-карта хорошей структурой данных (меня беспокоит поиск соседей)
что может быть функцией для A-BIJECTIVE-FUNCTION или для всей функции

Благодарю.

4

3d c++voxels

Решение

Другие решения

Вы хотите собрать их в пространстве так, чтобы связать каждый соседний воксель? Если это то, что вы хотите, то вы можете использовать Хошен-Копельман Алгоритм в 3D. Написание кода для этого должно занять день или два, и все готово. Пример в ссылке для 2D; расширение этого до 3D не проблема вообще.

Надеюсь это поможет.

1

Почему бы не использовать более сложный ключ для вашей хэш-карты? Вместо простого int, вы можете построить кортеж с вашими координатами x, y, z или реализуйте собственную структуру. Последняя опция потребует реализации оператора == () и хэш-функции. Некоторая информация о хорошей хэш-функции может быть найдена Вот.

0

Источник

Accepted Answer

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

Этот метод хеширования / хеширования должен быть самым быстрым.
Обратите внимание, что я использую только 30 бит из 32 бит целого числа. Это позволяет максимальный размер мира 4,2950e + 009 x 4194304 x 4096. Если вы хотите расширить границы мира, вам придется использовать больше / больше целых чисел.

Надеюсь, это поможет.

3