Разработка и исследование методов определения видимости полигонов в реальном времени при отрисовке трехмерных объектов

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

Задача удаления невидимых поверхностей является классической задачей компьютерной графики, и еще в 70-х годах было предложено значительное количество алгоритмов для ее решения. Удаление невидимых поверхностей основывается на том факте, что если пользователь не видит некоторый объект, то нет необходимости этот объект визуализировать, т. е. визуализировать нужно только полностью или частично видимые объекты. Методы удаления невидимых поверхностей определяют невидимые для пользователя части сцены и не визуализируют их (удаляет из множества визуализируемых частей). На сегодняшний день можно считать базовую задачу решенной, а самым распространенным алгоритмом ее решения — алгоритм z-буфера, реализованный аппаратно.

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

Актуальность темы

.

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

Около 5 лет назад появился рынок мобильных компьютеров (КПК), которые также нуждаются в отрисовке больших объемов данных. Здесь дела обстоят гораздо хуже, чем на настольных системах, потому как в КПК нет геометрических процессоров. Опыт показывает, что в ближайшее время полноценные геометрические процессоры (GPU — geometry processing unit) с архитектурой и возможностями, аналогичными nVidia GeForce3Ti, с vs 1.0 и ps 1.0 вряд ли появится в мобильных устройствах, из-за проблем с энергопотреблением и выделением тепла. Следовательно, сейчас трехмерная графика реального времени на КПК практически не развита, по сравнению с настольными системами.

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

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

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

Исходя из основной дели данной работы, определяется перечень основных задач:

1. Разработка целочисленного метода организации геометрических данных в объектном пространстве на основе двоичных деревьев.

2. Разработка метода двухпроходного расчета видимости частей изображения на основе иерархического тайлинга.

3. Разработка нового метода расчета видимости треугольников на основе бинарного маскирования.

4. Разработка целочисленного метода растеризации и текстурирования треугольников с учетом особенностей архитектуры центрального процессора мобильных устройств.

5. Экспериментальные оценки основных характеристик программной модели системы отрисовки геометрических данных в сравнении с существующими аналогами.

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

Научная новизна диссертационной работы заключается в следующем:

1. Разработан метод определения видимости и масштабной отбраковки полигонов в объектном пространстве на основе двоичных деревьев.

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

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

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

Практическая ценность работы.

Практическая значимость результатов диссертации заключается в следующем:

1. Разработанный метод удаления невидимых поверхностей может быть использован для отображения сложных трехмерных геометрических данных в реальном времени.

2. Разработанные методы двухпроходной отрисовки на основе иерархического тайлинга, с применением бинарных масок, могут быть использованы в системах моделирования для формирования участков изображения.

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

Основные положения и результаты, выносимые на защиту: 1. Организация системы определения видимости полигонов на основе двоичных деревьев в объектном пространстве для упорядоченной подачи геометрии на растеризацию и двухпроходного иерархического тайлинга в пространстве отображения с использованием бинарного маскирования вакантных участков.

2. Метод организации геометрических данных в объектном пространстве на основе бинарных деревьев. Масштабная отбраковка полигонов.

3. Метод определение видимости полигонов в отображаемом пространстве на основе иерархического тайлинга с использованием бинарного маскирования участков изображения.

4. Целочисленный метод растеризации и текстурирования треугольников с учетом особенностей архитектуры центрального процессора мобильных устройств.

5. Экспериментальные оценки основных характеристик программной модели системы отрисовки геометрических данных в сравнении с существующими аналогами.

Использование результатов. Результаты, полученные в ходе работы над диссертацией, были использованы при проведении научно-исследовательской работы «Построение трехмерных схем железнодорожных станций» по договору с НТЦ «ИНТЕХ» по заказу ОАО РЖД в 2005 году.

Апробация работы. По теме диссертации опубликовано 20 научных статей и тезисов докладов. Основные результаты, полученные в ходе работы над диссертацией, были представлены на:

1. Всероссийской конференции студентов, аспирантов и молодых ученых «Технологии Microsoft в теории и практике программирования», (МГТУ им. Н. Э. Баумана, г. Москва) 2005 и 2006 года.

2. Первой ежегодной научной конференции студентов и аспирантов базовых кафедр южного научного центра РАН, (Южный Научный Центр РАН, г. Ростов-на-Дону) 2005 года.

3. Всероссийской научной конференции студентов и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления» (ТРТУ, г. Таганрог) 2005 и 2006 года.

4. Всероссийской научной конференции с международным участием «Новые информационные технологии. Разработка и аспекты применения» (ТРТУ, г. Таганрог) 2004 года.

Аннотация работы. Диссертационная работа представлена четырмя значимыми главами.

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

В первой главе рассмотрены основные цели применения и возможные варианты использования методов определения видимости полигонов, основанных на особенностях аппаратного обеспечения современных графических процессоров. Определяются основные понятия, относящиеся к методам определения видимости полигонов в реальном времени. Предложен способ совокупной оценки эффективности методов определения видимости полигонов, который позволяет всесторонне и объективно оценить скорость их работы. Проведен анализ существующих математических методов применяемых для построения проекций трехмерных объектов в реальном времени. Выявлены недостатки существующих методов, основной из которых — медленная скорость работы на современном оборудовании. Предложена организация метода определения видимости полигонов на основе бинарных древовидных структур для отсечений в объектном пространстве и иерархического тайлинга с применением операций бинарного маскирования для определения видимости в пространстве изображения.

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

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

Первый проход позволит определить все видимые треугольники, которые попали на растеризацию после проведенных оптимизаций в объектном пространстве. Этот проход использует иерархический тайлинг. Видимость треугольника определяется на основе охватывающих масок. Треугольники закрашиваются постоянным цветом. Все видимые треугольники заносятся в список' треугольников, необходимых для использования в следующем проходе. Заметим, что иерархический тайлинг отобразит только те треугольники, хотя бы один пиксел которых видим на экране. Все невидимые треугольники будут отброшены на раннем этапе. Таким образом, сущность первого прохода состоит в быстрой подготовке списка треугольников, видимых на экране в текущем кадре.

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

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

• Построение двоичного дерева в объектном пространстве и обход дерева в порядке, необходимом для подачи геометрии на блок растеризации в порядке строго от ближних полигонов к дальним.

• Двухпроходный рендеринг в отображаемом пространстве на основе иерархического тайлинга изображения и механизма двоичных масок для быстрой растеризации.

• Текстурирование и попиксельная освещенность треугольников с учетом корректировки при проецировании, вычисляемые в пространстве целых чисел.

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

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

4.3. Выводы.

SGL позволяет отрисовывать до 1 ООО ООО видимых треугольников в секунду, что является очень высоким показателем для мобильных устройств. SGL превосходит по качеству изображения и по скорости работы все коммерческие реализации OpenGL ES, EDGE и др. Прирост в скорости отрисовки составляет от 300% до 1500% с использованием FFP. Программируемая архитектура, поддерживаемая SGL, реализована в мобильных устройствах впервые, и не поддерживается конкурирующими библиотеками.

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

ЗАКЛЮЧЕНИЕ

.

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

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

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

2. Разработан более эффективный метод двухпроходного расчета видимости частей изображения на основе иерархического тайлинга. Иерархический тайлинг необходим для быстрой отбраковки рассчитанных частей изображения.

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

4. Разработан более эффективный целочисленный метод растеризации треугольников с учетом особенностей архитектуры центрального процессора КПК. Этот метод позволяет растеризовать треугольники в 5−6 раз быстрее метода инкрементального сканирования.

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