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

Question

Я работаю над инструментом, который требует трехмерного "воксельного" движка. Под этим я подразумеваю добавление и удаление кубов из сетки. Для управления этими кубами мне нужна структура данных, которая позволяет быстро вставлять и удалять. Проблема, которую я видел с деревьями kd и октреями, заключается в том, что из-за этих операций кажется, что их часто нужно будет воссоздавать (или, по крайней мере, перебалансировать).

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

Еще несколько деталей:

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

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

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

Answer 1

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

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

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

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

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

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

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