Переупаковка воксельных данных для эффективного хранения

У меня есть 3D-воксельные данные, и я хочу переупаковать их для эффективного использования памяти и быстрого доступа. Данные генерируются в обычном октодереве, по одному целочисленному значению на ячейку. К сожалению, данные не разрежены, но ячейки с одинаковым значением должны быть связаны.

Example for one slice:
[11122]
[11223]
[12222]
[44444]

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


kdtree voxel octree
person user1387    schedule 04.03.2016    source источник

Ответы (2)


arrow_upward
1
arrow_downward

Как насчет OctoMap? Я так понимаю, это как Octree, но объединяет соседние занятые области в регионы для экономии памяти. Но я мало что знаю об этом.

ИЗМЕНИТЬ

Вы также можете попробовать мое PH-Tree. Он работает как октодерево, но достаточно эффективно использует память, потому что каждый узел хранит только биты, отличные от родительского узла. Фактически вы можете сохранить свое целочисленное значение как 4-е измерение. Вопреки интуиции, для 4D-дерева может потребоваться меньше места, чем для 3D-дерева, и оно может быть быстрее (объяснение находится в PDF-файле, который можно найти по ссылке выше). Если ваше целое число является 4-м измерением, то любое поддерево в дереве будет иметь записи только с «похожими» целыми числами, может быть, этого достаточно для вашего случая? Кроме того, любой узел содержит только близких соседей, но близкие соседи не обязательно находятся в тех же (или смежных) узлах.

person TilmannZ    schedule 05.03.2016

arrow_upward
0
arrow_downward

Еще одна ссылка: http://www.openvdb.org/ . Почему я нашел это только после того, как задал вопрос? Это как просить что-то в супермаркете только для того, чтобы узнать, что ты стоишь рядом с этим.

В итоге я сделал что-то более простое, потому что мне нужно было решение: я преобразовываю воксельный объем в стек 2D-плоскостей, и каждая плоскость сохраняет, в какой момент значение изменяется на следующую более высокую плоскость. Таким образом, воксельные данные уплотняются только по вертикали, но на данный момент они кажутся «достаточно хорошими». Если у меня будет свободное время, я подсчитаю цифры (требования к пространству и производительность) для других структур данных.

person user1387    schedule 07.03.2016