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

Question

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

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

Некоторые подробности:

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

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

(Нет, я не делаю Minecraft)

Answer 1

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

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

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

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

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

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

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