Преобразование неуравновешенного в сбалансированное дерево bsp?

Question

Мне нужен пример, который покажет, как я могу изменить несбалансированное БСП к сбалансированBSp дерево.

, пожалуйста, помогите мне.

Answer 1

В Quake это действительно оставлено до картографа. Компилятор Quake BSP начинает делить пополам тома с начала (0, 0, 0). Итак, чтобы создать более сбалансированную и совместимую с BSP карту, картограф должен центрировать свою геометрию на всех трех осях вокруг начала координат.

Я думаю, что подобная стратегия может быть применима к вашей проблеме. Найдите абсолютные границы (mins и maxs) ваших узлов BSP и вычислите точку в центре. Вот где вы должны начать разбивать дерево. Теперь, если ваша карта не является абсолютно симметричной, вы никогда не достигнете идеально сбалансированного дерева. Но для практических целей это дает вам относительно близкое отношение.