Автоматическая балансировка (или дешевая балансировка) 3D-структуры данных

Я работаю над инструментом, для которого требуется 3D-движок на основе вокселей. Под этим я подразумеваю, что это будет включать добавление и удаление кубов из сетки. Чтобы управлять этими кубами, мне нужна структура данных, позволяющая быстро вставлять и удалять данные. Проблема, которую я видел с k-d деревьями и октодеревьями, заключается в том, что кажется, что их часто нужно воссоздавать (или, по крайней мере, перебалансировать) из-за этих операций.

Прежде чем я вскочил, я хотел узнать мнение о том, как лучше всего это сделать.

Еще немного деталей:

  • x,y,z позиция находится в целочисленном пространстве
  • должен быть достаточно эффективным для приложения в реальном времени
  • нет жесткого ограничения на количество используемых кубов. По всей вероятности, число чаще всего будет несущественно низким (‹100), однако я хотел бы, чтобы инструмент обрабатывал как можно больше кубов.

Я думаю, что главный вопрос заключается в том, как лучше всего управлять тем, что по сути является трехмерными точечными данными, таким образом, чтобы они могли обрабатывать частые вставки и удаления?

(Нет, я не делаю Майнкрафт)


3d data-structures voxel
person Kyle    schedule 01.08.2013    source источник
comment
Если вам нужно только вставить и удалить, используйте простую хеш-таблицу с (x, y, z) в качестве ключа. Но я предполагаю, что в какой-то момент вам также понадобятся пространственные запросы, верно?   -  person fortran    schedule 01.08.2013
comment
Я не уверен в данный момент. Мои текущие требования на самом деле не требуют пространственных запросов, но я вижу, что в какой-то момент они могут понадобиться. Я, вероятно, начну с хеш-таблицы для простоты, а затем перейду к октодеревьям по мере необходимости. Спасибо!   -  person Kyle    schedule 01.08.2013

Ответы (1)


arrow_upward
1
arrow_downward

Octrees являются простыми в использовании. обновлять динамически. Обычно дерево уточняется на основе подсчета верхней/нижней популяции для каждого листа:

  1. Когда вставляется новый элемент, он помещается в список элементов для окружающего конечного узла. Если верхний предел численности населения превышен, лист уточняется.

  2. Когда существующий элемент стирается, он удаляется из списка элементов для окружающего конечного узла. Если достигается меньшее количество популяции, сканируются одноуровневые листы. Если все братья и сестры являются конечными узлами и их совокупное количество элементов меньше, чем верхнее число элементов, набор братьев и сестер удаляется, а элементы помещаются в родительский узел.

Обе операции являются локальными, обходя только высоту дерева, которая равна O(log(n)) для хорошо распределенных наборов точек.

KD-деревья, с другой стороны, сложно динамически обновлять, поскольку их структура основана на распределении полного набора точек.

Существует также ряд других пространственных структур данных, поддерживающих динамические обновления: R-деревья, триангуляции Делоне и это лишь некоторые из них, но неясно, обеспечивают ли они лучшую производительность, чем Octree. . Я не знаю ни одной пространственной структуры, которая поддерживает динамические запросы лучше, чем O(log(n)).

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

person Darren Engwirda    schedule 01.08.2013
comment
Как упоминалось в Fortran, мне лучше всего начать с хеш-таблицы. У меня, очевидно, было некоторое недопонимание октодеревьев, поэтому спасибо за разъяснение. Эта ссылка (в частности, растущий и уменьшающийся раздел) — именно то, что я искал изначально. - person Kyle; 01.08.2013