Компьютерная Графика и Мультимедиа Сетевой журнал

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

В этой работе рассмотрены алгоритмы увеличения скорости вывода трёхмерных изображений на экран интерактивной системы ГИС - алгоритмы широко применяющегося октарного дерева [3], бинарного, и их модификаций. Описаны нюансы модификаций алгоритмов для работы с пространственными данными ГИС. Проведено сравнение алгоритмов по основным показателям работы, даны рекомендации по применению.

Эти алгоритмы не поддерживаются аппаратно, поэтому актуальность их эффективной реализации будет сохраняться постоянно.

Содержание

1. Введение.
2. Исследуемые алгоритмы.
3. Нюансы реализации.
1. Однозначное соответствие примитива узлу
2. Создание слоёв в древовидной структуре
3. Модификации бинарных деревьев.
4. Критерий определения листа
4. Результаты экспериментов.
1. Анализ структуры пространственных данных.
2. Скорость работы алгоритмов.
5. Заключение.
6. Литература.

Введение

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

Так как ГИС приложения работают с большим количеством визуализируемых данных, поэтому для любого приложения ГИС всегда актуальна задача минимизации времени перерисовки трёхмерной сцены. Обычно скорость перерисовки сцены измеряется количеством кадров в секунду (FPS - frames per second) . Существует несколько основных подходов, чтобы повысить FPS:

• оптимизация существующих и изобретение более быстрых алгоритмов;
• использование современной графической аппаратуры [5].

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

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

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

Рис. 1. Точки, на основании которых принимается решение о видимости узла

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

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

Рис. 2. Пирамида видимости

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

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

Рис. 3. Весовая точка

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

Кроме этих базовых алгоритмов, нами предлагаются и реализованы следующие алгоритмы: алгоритм бинарного весового, бинарного пропорционального весового, октарного весового деревьев.

Рис. 4. Пример разбиения сцены на бинарное весовое дерево

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

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

Суть бинарного весового пропорционального дерева опишем далее.

В табл. 1 представлены обобщённые достоинства и недостатки применения деревьев при выводе на экран трёхмерной сцены.

Таблица 1

Достоинства

Недостатки

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

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

Нюансы реализации

Однозначное соответствие примитива узлу

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

Например, вот ситуация (рис. 5), когда один примитив, при разбиении октарным деревом, относится сразу к 4м листам.

Рис. 5 Разбиение примитива плоскостями, при построении дерева

В этом случае нельзя относить этот примитив к какому-то одному листу, т. к. если примитив отнести к 3 листу, и этот лист не попадёт в область видимости, а листы 1, 2, 4 будут видны, то треугольник виден не будет. Что является ошибкой.

Если отнести примитив сразу к 4м листам, и они сразу все будут видны, то этот примитив будет выводиться четыре раза подряд. Несмотря на это, такие реализации применяются довольно часто [7]. Если таких примитивов много, и они покрыты текстурами, то все преимущества октарных деревьев очень мало проявляются.

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

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

Еще одна проблема традиционного алгоритма - примитивы нельзя относить к узлу только по координатам их вершин. На рис. 5 вершины треугольника расположены в узлах 1, 2, 3, а сам треугольник находится в узлах 1, 2, 3, 4. Возможен частный случай, когда видим будет только узел 4, а 1, 2, 3 будут не видны. Тогда треугольник отображаться не будет. Что тоже является ошибкой. Эта проблема не существует в модифицированном нами алгоритме, так как там примитивы однозначно присваиваются узлам.

Создание слоёв в древовидной структуре

Кроме того, в такой иерархической структуре ГИС данных необходимо предусмотреть наличие слоёв. Встаёт вопрос, как правильно организовать визуализацию слоёв, используя дерево.

Мы предлагаем следующие варианты:

1. Создать несколько деревьев, одно для каждого слоя.
2. Указывать атрибут слоя для каждого примитива, и потом проверять, видим ли слой, и если да, то выводить примитив на экран.
3. Указать атрибут слоя для группы примитивов, и потом проверять, видим ли слой, и если да, то выводить группу примитивов на экран.

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

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

Поэтому был реализован именно третий вариант.

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

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

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

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

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

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

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

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

Критерий определения листа

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

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

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

Результаты экспериментов

Реализуем программно описанные алгоритмы, протестируем их на FPS, и сравним между собой. Так как FPS сильно зависит от максимально допустимого количества примитивов в листе (глубины разбиения), выявим FPS при различной глубине разбиения, и при разном положении наблюдателя. При различном положении наблюдателя в область видимости попадают разные части сцены, при этом процент видимости примитивов и FPS меняются, что позволяет объективно сравнить алгоритмы. Проанализируем результаты полученных экспериментов. В качестве набора данных используем результаты гидрогеологических исследований, построенных на регулярной сетке. Для проведения экспериментов используется поверхностная модель (на экран выводятся только поверхности слоёв и различных объектов), которая выводится на экран гораздо быстрей воксельной (на экран выводится каждая точка регулярной кубической сетки). Как правило, данные гидрогеологических исследований хранятся в воксельной модели, поэтому лучше их конвертировать в поверхностную модель. До конвертации, воксельная модель содержала 630000 примитивов. После, поверхностная модель, на основе которой ставились эксперименты, стала содержать 100784 примитива.

Алгоритмы были реализованы на Delphi 5, тестировалась на компьютерах с процессором Celeron, Athlon. В качестве 3D библиотеки использовалась OpenGL. На разных компьютерах результаты сравнения алгоритмов принципиально не отличались. Как правило, отличия были заметны только в константном множителе.

Конечно, результаты экспериментов зависят от аппаратной платформы, компиляторов, 3D библиотеки, и других факторов. Но мы считаем, что полученные результаты экспериментов будут объективными. Так как компилятор Delphi создаёт код, мало уступающий по оптимальности и производительности другим современным компиляторам, кроме того, результаты экспериментов сравниваются между собой, только если были произведены на одном компьютере, и в одно время (с одинаковым количеством запущенных задач).

Каждое значение FPS получалось 20 раз. После этого искалось среднее арифметическое по формуле [1]:

(1),

где  Х_ср -среднее арифметическое;

 Х₁, Х₂ - Значения, получаемое в ходе эксперимента;

Среднее квадратическое отклонение σ( ) окончательного результата вычисляется по [1]:

(2),

В результатах (на графиках) указывается среднее арифметическое FPS, Среднее квадратическое отклонение окончательного результата указывается отдельно.

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

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

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

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

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

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

Рис. 6. Разбиение пространства бинарным весовым деревом при максимально допустимом количеством примитивов в узле 630

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

Рис. 7. Разбиение сцены пропорциональным весовым бинарным деревом при максимально допустимом количеством примитивов в узле 6300

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

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

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

Рис. 8. Разбиение сцены пропорциональным весовым бинарным деревом при максимально допустимом количеством примитивов в узле 630

Оценим визуально качество разбиения сцены алгоритмами.

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

Рис. 9. Разбиение пространства октарным деревом при максимально допустимом количеством примитивов в листе 200

Получающаяся неравномерность разбиения в весовом бинарном дереве получается при неравномерном распределении примитивов. Алгоритм должен более интеллектуально делить пространство, как это делает алгоритм бинарного весового пропорционального дерева.

На рис. 7, рис. 8, показано разбиение сцены алгоритмом бинарного весового пропорционального дерева. Видно, что сцена разбивается более равномерно, и параллелепипеды больше похожи на кубы. Безусловно, при таком разбиении, бинарное весовое пропорциональное дерево должно иметь более высокую FPS, чем бинарное весовое дерево.

Для сравнения приведём рис. 9, на котором показаны результаты разбиения сцены октарным деревом. Несмотря на то, что сцена разбивается на кубы, видно, что по сравнению с весовыми деревьями, многие кубы захватывают пространство, не содержащее примитивов. И только там, где сетка сгущается, находятся примитивы.

Рис. 10. Разбиение сцены октарным весовым деревом при максимально допустимом количеством примитивов в листе 4000

На рис. 10 показано разбиение сцены весовым октарным деревом. Даже при большом максимально допустимом количестве примитивов листе - 6300, линии разбиения проходят довольно близко друг к другу, деля сцену на большие и маленькие параллелепипеды. Если сравнить разбиение сцены весовым октарным деревом рис. 10, и пропорциональным весовым бинарным деревом рис. 7, то при одинаковом максимально допустимом количестве примитивов в листе, октарное весовое дерево разбивает сцену гораздо неравномерней, и на большее количество листов.

Скорость работы алгоритмов

Рис. 11. FPS алгоритмов в зависимости от глубины разбиения (при 20% видимости всех примитивов)

При видимости всех примитивов, все алгоритмы показывают примерно одинаковое значение FPS.

Рис. 12. FPS алгоритмов в зависимости от глубины разбиения (при 20% видимости всех примитивов)

Рассмотрим, какой алгоритм имеет лучшие показатели FPS. Для этого проведём эксперименты, меняя глубину разбиения, и точку зрения наблюдателя. На рис. 11, рис. 12, меняется максимально допустимое количество примитивов в листе от 200 до 101000, с шагом приращения в 500 примитивов. При этом у октарного дерева (OctreeD) максимальная равна 0,8, у весового бинарного пропорционального (BinVesPropD) (BVPD) 0,57, у бинарного весового (BinVesD) 0,68, у октарного весового (OctreeVesD) 0,59.

Тесты проводились на компьютере с конфигурацией Athlon 2000, 512мб, Video - Radeon 9600 Pro 128 Mb, OS Windows XP. Графики строились и интерполировались с помощью программы Mathcad.

Рис. 13. FPS алгоритмов в зависимости от глубины разбиения (при 20% видимости всех примитивов)

Октарное и бинарное весовое пропорциональное деревья занимают лидирующее положение по FPS (рис. 11, рис. 12). Поэтому рассмотрим дополнительно рис. 13, на котором максимально допустимое количество примитивов меняется от 200 до 3000, и шаг приращения равен 100. У первого дерева максимальная равна 2,70, у второго 1,19. Октарное дерево при уменьшении максимально допустимого количества примитивов в листе демонстрирует постоянный прирост FPS, а у бинарного весового пропорционального FPS меняется скачками. Хотя максимальные значения FPS у этих алгоритмов почти равны, но найти максимальное значение FPS у алгоритма октарного дерева значительно проще, так как значение FPS у этого алгоритма максимально при максимально допустимом количестве примитивов в листе около 300. Поэтому при использовании бинарных весовых деревьев нужно искать этот максимум FPS для более эффективного использования алгоритма. К тому же, экстремумов FPS бывает несколько, что усложняет поиск максимума.

Рис. 14. Время создания дерева, в зависимости от разбиения

На рис. 14 показана зависимость времени разбиения сцены различными алгоритмами, от глубины разбиения. Как видно, бинарному весовому пропорциональному дереву требуется меньше всего времени для разбиения сцены. Больше всего времени требует октарное дерево. После максимально допустимого количества примитивов в листе, от начиная от 9000, алгоритмы показывают примерно одинаковое время, поэтому на графике этого не изображено. Максимальная времени создания дерева для всех алгоритмов, изображённых на рис. 14, не превышает 1,7.

Проверим предположение, зависит ли скорость алгоритма от того, как удачно входят в пирамиду видимости узлы или листья. Отношение количества видимых узлов ко всем узлам, и видимых листов ко всем листьям примерно одинаково при 30% видимости сцены. Но у октарного дерева и бинарного весового пропорционального дерева этот показатель чуть ниже, это обуславливает его лучшие показатели FPS. Между отношением количества видимых узлов ко всем узлам, видимостью листов ко всем листьям и FPS есть хорошо заметная зависимость. Чем ниже эти показатели, тем выше FPS.

Заключение

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

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

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

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

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

Литература

1. Агапьев Б. Д. и др. "Обработка экспериментальных данных" Кафедры экспериментальной физики СПбГТУ, 2001. http://users.kpi.kharkov.ua/fmp/biblio/BOOK1/1-7.html
2. Игнатенко А. Геометрическое моделирование сплошных тел. On-line журнал <Графика и Мультимедиа> http://graphics.cs.msu.ru/ru/library/3d/solid_modelling/index.html
3. Роджерс Д. Математические основы машинной графики / Д. Роджерс, Дж. Адамс. - М: Мир, 2001.  - 604 с.
4. Роджерс, Дэвид. Алгоритмические основы машинной графики: Пер. с англ. / Д. Роджерс.-М.: Мир, 1989.-512 с.:
5. Рони Я. Рендеринг объемов в реальном времени Университет шт. Огайо, США Открытые Системы №5(19)/96 стр. 28-33. http://osp.aanet.ru/os/1996/05/source/28.htm
6. Ян Ф., и др. Удаленная визуализация 16.11.1999 Открытые системы, № 11-12/1999
7. HumphreyB. Octree tutorial. http://gamemaker.webservis.ru/articles/Octree/Octree.htm
8. Hudson T., Manocha D., Cohen J., Lin M., Hoff K, Zhang H. Accelerated occlusion culling using shadow frustra. In Proc. 13th Annu. ACM Sympos. Comput. Geom., pages 1-10, 1997

Дополнительная информация

Ссылка: 

Соловьёв С.А., Марков Н. Г.. Сравнительный анализ алгоритмов разбиения трехмерных сцен на деревья графических примитивов. Компьютерная графика и мультимедиа. Выпуск №3(1)/2005. http://cgm.computergraphics.ru/content/view/68

Выпуск: 

Выпуск №3(1)/2005