Анализ структуры пространственных данных

Скорость работы алгоритма зависит от того, как распределены примитивы по узлам. Алгоритмы по разному разбивают пространство, по разному распределяют примитивы по узлам. Оценим распределение примитивов по узлам, по равномерности разбиения, по количеству листьев, по количеству примитивов, присвоенным узлам, которые не являются листьями (родительские узлы).

Равномерность разбиения пространства алгоритмами сравнивалась по двум основным признакам: минимальное и максимальное количество примитивов в листе. В идеале эти значения должны совпадать, и равняться максимально допустимому количеству примитивов в листе (глубине разбиения). Эти критерии годятся для оценки качества разбиения, хотя идеальные значения этих параметров можно получить только при очень простой пространственной сцене.

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

У октарного и октарного весового дерева количество листьев примерно одинаково, у бинарного весового в несколько раз меньше, а у бинарного весового пропорционального ещё меньше. Это тоже говорит о лучшем распределении примитивов по узлам у бинарного весового пропорционального дерева.

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

Больше всего примитивов, присвоенных родительским узлам, имеет алгоритм бинарного весового дерева, примерно раза в полтора больше, чем у октарных деревьев, меньше всего - алгоритм октарного дерева, чуть больше алгоритм октарного весового дерева. Алгоритм бинарного пропорционального весового дерева имеет как правило меньше таких примитивов, чем бинарное весовое дерево, но больше чем октарное весовое. Вообще, чем меньше примитивов присваивается родительским узлам, тем лучше. Но эта величина не влияет сильно на FPS.

Рассмотрим, стоит ли присваивать примитивы, попадающие на граничные зоны листов родительским узлам, как мы предлагаем это в модифицированных алгоритмах.

Например, для октарных деревьев количество примитивов, присвоенных родительским узлам примерно равно 45000, при максимально допустимом количестве примитивов в узле до 200. Это значит, что 45000 примитивов отрисовывалось бы как минимум два раза вместо одного. Всего примитивов 100784, положим, что при этом FPS равно 100%. Тогда, при использовании алгоритма, который не присваивает эти примитивы родительским узлам, мы бы отрисовывали 145784 примитива. FPS при этом был бы: 100784/145784= 0, 69. То есть, потери FPS составляли бы примерно 30%. Это достаточно большая величина, которая говорит о необходимости такого присвоения. Тем более, что для бинарного дерева разница FPS ещё большая.