Информационная система "Конференции"

Тезисы докладов

информационные технологии

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

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

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

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

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

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

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

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

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

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

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

Сравним рассматриваемые алгоритмы, используя пространственные данные с регулярной сеткой, по FPS, времени разбиения сцены на дерево.

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

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

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

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

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

Примечание. Тезисы докладов публикуются в авторской редакции

Ваши комментарии Обратная связь

[Головная страница] [Конференции]

© 1996-2005, Институт вычислительных технологий СО РАН, Новосибирск
© 1996-2005, Сибирское отделение Российской академии наук, Новосибирск