Исследуемые алгоритмы

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

Октарное дерево - это наиболее универсальное решение, которое позволяет увеличить скорость перерисовки почти всех типов и видов данных ГИС, начиная с рельефов, зданий, отдельных объектов, деревьев, данных для геологических исследований. Суть алгоритма построения октарного дерева заключается в том, при построении такого дерева вся сцена вписывается в куб, и этот куб делится трёмя плоскостями на 8 одинаковых кубов рис. 1. Каждый из получившихся кубов делится точно также, и так до тех пор, пока каждый не станет содержать менее определённого количества графических примитивов. Все примитивы, ограничиваемые этим кубом, присваиваются ему. Каждый куб считается узлом дерева. Такой узел, который содержит только примитивы, но не содержит других узлов, называется листом. Графические примитивы - это как правило треугольники, на которые можно разбить все фигуры в сцене. В итоге, получается иерархическая структура представления данных, где корневой узел - куб, в который вписана вся сцена, а листьям присваиваются все примитивы сцены.

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

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

Таким образом, рассматриваемые алгоритмы позволяют увеличить FPS путём отсечения групп примитивов, не входящих в поле зрения наблюдателя. Они могут работать со всеми наборами пространственных данных, встречающимися в ГИС, и это является большим преимуществом, по сравнению другими алгоритмами, увеличивающими скорость вывода на экран - например, алгоритмы плавающего горизонта[4], теневой [8], и др.