Разделение KDTree

В настоящее время я пишу KDTree для физического движка (проект Hobby).

KDTree не содержит точек. Вместо этого он содержит ограничивающие прямоугольники с выравниванием по оси, которые ограничивают различные объекты в среде.

Моя проблема заключается в том, чтобы решить, как разделить узлы KDTree, когда они заполнятся. Я пробую 2 метода:

Метод1: Всегда разделяйте узел точно пополам по самой большой оси.

• Это дает преимущество в виде довольно равномерно распределенного дерева.
• Большой недостаток: если объекты сосредоточены в небольших области узла будут созданы избыточные подразделения. Это потому, что все тома разделены точно пополам.

Метод 2: Найдите область узла, которая содержит объекты. Разделите узел на плоскости, которая разделяет эту область пополам по самой большой оси. Пример - Если все объекты сосредоточены в нижней части узла, то он разделяется по длине, тем самым разделяя нижнюю часть на две части.

• Это решает проблему с описанным выше методом
• При индексировании чего-то, что существует в той же плоскости ( terrain например), он создает длинные и узкие узлы. Если позже я добавлю другие объекты, которые не находятся в той же плоскости, Учитывая, что это будет физический движок, решение должно быть достаточно простым, чтобы его можно было принимать в реальном времени.