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

На правах рукописи

Надолинский Никита Александрович

РАЗРАБОТКА И ИССЛЕДОВАНИе МЕТОДОВ ОПРЕДЕЛЕНИЯ ВИДИМОСТИ ПОЛИГОНОВ В РЕАЛЬНОМ ВРЕМЕНИ ПРИ ОТРИСОВКЕ ТРЕХМЕРНЫХ ОБЪЕКТОВ

05.13.17 – Теоретические основы информатики

АВТОРЕФЕРАТ

диссертации на соискание ученой степени

кандидата технических наук

Таганрог - 2007

Работа выполнена на кафедре «Прикладной информатики» Технологического института Южного федерального университета, г. Таганрог

НАУЧНЫЙ РУКОВОДИТЕЛЬ:

заслуженный деятель науки и техники, доктор технических наук, профессор
Берштейн Леонид Самойлович

ОФИЦИАЛЬНЫЕ ОППОНЕНТЫ:

доктор технических наук, профессор

Ромм Яков Евсеевич (Таганрогский государственный педагогический институт, г. Таганрог)

доктор технических наук, профессор

Карелин Владимир Петрович (Таганрогский институт управления и экономики, г. Таганрог)

ВЕДУЩАЯ ОРГАНИЗАЦИЯ:

Ростовский государственный университет путей сообщений,

г. Ростов-на-Дону

Защита диссертации состоится «14» июня 2007 г. в 14.20 на заседании
диссертационного совета Д 212.208.21 в Южном федеральном университете, по адресу:
347928, Ростовская область, г. Таганрог, пер. Некрасовский, 44, Д-406

Отзывы на автореферат просьба направлять по адресу:
347928, Ростовская область, г. Таганрог, пер. Некрасовский, 44,
Южный федеральный университет,
Ученому секретарю диссертационного совета Д 212.208.21 Бабенко Л.К.

С диссертацией можно ознакомиться в Зональной научной библиотеке Южного федерального университета, по адресу:
344049, г. Ростов-на-Дону, ул. Пушкинская, 148.

Автореферат разослан «11» мая 2007 г.

Ученый секретарь

диссертационного совета,

доктор технических наук,

профессор Бабенко Л.К.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

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

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

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

1. Разработан целочисленный метод масштабной отбраковки геометрических данных, позволяющий определять видимость полигонов в объектном пространстве.
2. Впервые разработан двухпроходный метод определения видимости треугольников в отображаемом пространстве на основе иерархического тайлинга с применением бинарного маскирования участков изображения.
3. Разработан метод целочисленной растеризации и текстурирования треугольников, оптимизированный для архитектуры центрального процессора мобильных устройств.
4. Предложена организация системы определения видимости полигонов на основе бинарных деревьев в объектном пространстве для упорядоченной подачи геометрии на растеризацию и иерархического тайлинга в отображаемом пространстве с применением бинарного маскирования вакантных участков изображения.

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

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

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

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

Основные положения и результаты, выносимые на защиту:

1. Организация системы определения видимости полигонов на основе бинарных деревьев для масштабной отбраковки геометрических данных в объектном пространстве и двухпроходного иерархического тайлинга в отображаемом пространстве с использованием бинарного маскирования вакантных участков.
2. Метод масштабной отбраковки геометрических данных, позволяющий отсекать невидимые полигоны в объектном пространстве.
3. Метод определения видимости полигонов в отображаемом пространстве на основе иерархического тайлинга с использованием бинарного маскирования участков изображения.
4. Целочисленный метод растеризации и текстурирования треугольников с учетом особенностей архитектуры центрального процессора мобильных устройств.
5. Экспериментальные оценки основных характеристик программной модели системы отрисовки геометрических данных в сравнении с существующими аналогами.

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

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

1. Всероссийской конференции студентов, аспирантов и молодых ученых “Технологии Microsoft в теории и практике программирования”, (МГТУ им. Н.Э. Баумана, г. Москва) 2005 и 2006 года.
2. Ежегодной научной конференции студентов и аспирантов базовых кафедр южного научного центра РАН, (Южный Научный Центр РАН, г. Ростов-на-Дону) 2005, 2007 года.
3. Всероссийской научной конференции студентов и аспирантов “Техническая кибернетика, радиоэлектроника и системы управления” (ТРТУ, г. Таганрог) 2005 и 2006 года.
4. Всероссийской научной конференции с международным участием “Новые информационные технологии. Разработка и аспекты применения” (ТРТУ, г. Таганрог) 2004 года.

Публикации.

По теме диссертации опубликовано 16 научных статей и тезисов докладов, из них одна статья опубликована в журнале «Известия Таганрогского государственного радиотехнического университета (ТРТУ)» из перечня, рекомендованного ВАК РФ для публикации результатов диссертационных работ.

Объем и структура диссертации. Диссертация состоит из введения, четырех глав, заключения, списка литературы, включающего 65 наименований, приложения. Основной текст диссертации изложен на 139 страницах, включая 41 рисунок и 2 таблицы.

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

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

пусть отрезок задается начальной точкой и вектором . Плоскость определяется базовой точкой и вектором нормали . Уравнение плоскости в параметрическом виде имеет вид:

После подстановки координат нормали и начальной точки имеем:

Уравнение отрезка имеет вид:

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

откуда :

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

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

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

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

В большинстве случаев необходимо создать сбалансированное дерево, т.е. чтобы глубина любых двух листьев различалась максимум на единицу. Совершенно несбалансированное дерево неэффективно. Для балансировки дерева используется критерий наименьшего пересечения (least-crossing criteria). Для этого произвольно выбираются несколько полигонов. Для каждого их них определяется количество полигонов, пересекающих разделяющую плоскость. Выбирается тот, чья плоскость имеет наименьшее число пересечений. Статистически показано, что для получения сбалансированного дерева, необходимо протестировать только 0,5% треугольников, входящих в состав сцены. Тестирование более 0.5% треугольников не намного улучшает результат.

Алгоритм создания бинарного дерева выглядит следующим образом:

1. Выбрать треугольник из списка и использовать его в качестве разделительной плоскости. Если в списке больше нет треугольников — выход из алгоритма.

2. Создать два дочерних указателя, один из них указывает на left-узел, а на другой указывает на right узел дерева. По указателям содержатся списки треугольников, расположенных впереди и позади разделительной плоскости, как показано на рис. 1.

3. Рекурсивно обработать список left.

4. Рекурсивно обработать список right.

Рис. 1. Вид бинарного дерева, построенный для плоскости 3

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

Рис. 2. Пример обхода двоичного дерева

Начнем с корневой вершины дерева, как показано на рис. 2. Учитывая, что плоскость разделения принадлежит узлу дерева и определяется базовой точкой и вектором нормали , определим полупространство, в котором лежит точка обзора следующим образом:

где оператор обозначает знак выражения, стоящего в квадратных скобках.

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

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

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

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

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

Рис. 3. Масштабная отбраковка полигонов с точкой наблюдения в отрицательном полупространстве

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

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

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