Модификации бинарных деревьев

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

Но если эти плоскости будут располагаться под любым углом, то в результате разбиения сцены будет разбита не на прямоугольники, а на сложные многоугольные структуры. Получившиеся таким образом многоугольники будет сложно тестировать на попадание в пирамиду видимости, так как вместо анализа четырёх вершин, придётся производить анализ множества вершин на вхождение в пирамиду видимости. Кроме этого, увеличится объём памяти, для хранения вершин узлов. И усложнится алгоритм получения новых узлов. Поэтому нами предлагается разбивать сцену на параллелепипеды.

В бинарном дереве мы делим параллелепипед одной плоскостью, и получаем параллелепипеды, секущая плоскость может быть проведена перпендикулярно любой из осей X, Y, Z. Например на рис. 4 показаны два варианта проведения такой плоскости - перпендикулярно Y и перпендикулярно Х.

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

Весовое разбиение пространство должно быть эффективно для сложно расположенных примитивов. Но если предполагается, что данные ГИС, это большие массивы рельефа, с зданиями, сооружениями, подземными и надземными, то примитивы будут распределены по горизонтали больше, чем по вертикали, и FPS весового бинарного и весового октарного дерева может оказаться выше, чем у октарного. Бинарное дерево более эффективно распределяет примитивы по узлам, а проверка на видимость узла - и все остальные процедуры при визуализации одинаковы. Но преимущество октарного дерева - оно разбивает пространство на кубы. Такое разбиение должно показывать максимальную скорость тестирования нахождения узла в пирамиде видимости. Так как кубы лучше других параллелепипедов отсекают невидимые группы примитивов, не входящих в пирамиду видимости, при любом положении наблюдателя. Действительно, если будет много узких длинных параллелепипедов, то при попадании хотя бы части одного из них в пирамиду видимости, будет выводиться на экран (или тестироваться на видимость) и вся его другая часть, что будет уменьшать FPS. А задача исследуемых нами алгоритмов быстро и эффективно отсечь невидимые группы примитивов.

Для того, чтобы тест на попадание в пирамиду видимости проходил как можно эффективней, нами предлагается делить узлы по такому принципу - параллелепипед должен стремиться кубу. Поэтому, если длинная сторона параллелепипеда расположена горизонтально - то делим её вертикальной секущей плоскостью. Если вертикально - то горизонтальной. То есть - делим секущей плоскостью ту сторону параллелепипеда, которая самая большая. Такое дерево мы назвали бинарным весовым.

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