Заключение

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

Не стоит применять алгоритм весового октарного дерева, так как он имеет более низкие показатели FPS чем у октарного дерева (рис. 11), его структура в пространстве сложней, чем у октарного дерева. Кроме того, время разбиения сцены на весовое октарное дерево кое-где больше, чем время разбиения на традиционное октарное дерево.

Алгоритм бинарного весового дерева наиболее универсальный. Его можно применить ко всем наборам данных. Если для увеличения FPS при визуализации сложных помещений, лабиринтов, используют октарное дерево, то для увеличения FPS, при визуализации рельефа используют квадродеревья. В ГИС могут встречаться данные обоих типов. Очень сложно совмещать два таких алгоритма в одном программном пакете. Гораздо проще создать универсальный алгоритм, который будет эффективно работать со всеми данными ГИС.

Алгоритм бинарного весового дерева является именно таким универсальным алгоритмом. Более того, скорость разбиения сцены на дерево этим алгоритмом выше, чем у октарного и октарного весового. И, если правильно подобрать максимально допустимое количество примитивов в листе, алгоритм весового бинарного дерева отстаёт от алгоритма октарного дерева на исследуемом наборе данных на 5-30%. Недостатками этого алгоритма являются: сложность программирования, и подбор максимально допустимого количества примитивов в листе. А достоинства - универсальность применения к различным наборам данных. Используя этот алгоритм, можно получить высокую FPS, при минимальном времени разбиения. Например, при максимально допустимом количестве примитивов в листе равном 2000, время разбиения будет минимальным примерно 0, 6с, а FPS равняться примерно 250 (рис. 12, рис. 14). Этот алгоритм хороший компромисс между не очень большим FPS, и маленьким временем разбиения. Так как другие рассмотренные алгоритмы не обеспечивают такого маленького времени разбиения, и такого высокого FPS. Возможно, на других наборах данных (более сложно расположенных) алгоритм бинарного весового дерева будет опережать октарное дерево по количеству FPS.

Если же ставится цель получить максимально возможное FPS, то необходимо использовать октарное, или бинарное весовое пропорциональное дерево. Они имеют примерно одинаковые показатели FPS, при этом, бинарное весовое пропорциональное дерево гораздо быстрей разбивает сцену, но у него достаточно сложно найти максимально допустимое количество примитивов в листе, при котором FPS максимальна. То есть, если не критично время разбиения сцены, то лучше использовать октарное дерево. Если важно время разбиения сцены на дерево, (и если данные сложно расположены в пространстве - есть большие скопления и пустоты) то нужно использовать бинарное весовое пропорциональное дерево.