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

□ОЗОВЗЭбВ

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

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

05 13 17-Теоретические основы информатики

АВТОРЕФЕРАТ

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

1 4 ИЮН 2007

Таганрог-2007

003063966

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

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

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

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

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

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

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

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

Защита диссертации состоится «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 GeForce3Tt, с vertex shaders и pixel shaders версии 1 0 вряд ли появится в мобильных устройствах, из-за проблем с энергопотреблением и выделением тепла Следовательно, сейчас трехмерная графика реального времени на КПК практически не развита, по сравнению с настольными системами

Развитие трехмерной графики реального времени, за счет средств цетрального процессора (CPU - centra] 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 таблицы

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

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

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

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

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

пусть отрезок задается начальной точкой А = (Ах,Ау,А2) ивектором V = (Ух,Уу,Уг) Плоскость определяется базовой точкой Рр "^О'-^О^Ср и ве(п0Р0М нормали п = (пх,пу,пг) Уравнение плоскости в параметрическом виде имеет вид

й(Р-Р0) = О,

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

пх(х-х0)+пу{у-,у0)+ и2(г-г0) = 0,

пхх+пуу+п2г+(~пхх0 - пуу0 - п220) = О

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

Px = Ax + Vxt, Py = Ay + Vyt,

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

пхАх + пхУх1+ПуАу + ПуУу! + п2Л2 + п2У21 = пхх0 + пуу^ + пгх0 ,

откуда I

{nxxQ +nyyQ+nz20)-(,nxAx + nyAy+nzAz)

nxVx + nyVy+nzVz

При /е [О, ^У^ + + У^ ] отрезок пересекает заданную плоскость, иначе точки пересечения нет Координаты точки пересечения I = {1х,/у,1г) находятся следующим образом

/ =А ("**0 + пуУр + "г*о)~(»хАх + пуАу + Мг)

* * г,хУх + пуУу + п2У2

Av + V.

(»хХц+ПуУц +nzz0)-(nxAx + nyAy + nzAz) nxVx+nyVy+nzVz

(пххо +nyyQ +nzz0)-(nxAx + пуАу +nzAz)

lz- Az + rz ——■ — |-—-

nxVx + nyVy+nzVz

Если вектор направления отрезка V вырождается в точку, те V = (0,0,0) то необходимо проверить истинность данного выражения

nxAx + nyAy + nzAz = nxx0 + nyyQ + nzz0

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

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

В большинстве случаев необходимо создать сбалансированное дерево, т е чтобы глубина любых двух листьев различалась максимум на единицу Совершенно несбалансированное дерево неэффективно Для балансировки дерева используется критерий наименьшего пересечения (least-crossmg entena) Для этого произвольно выбираются несколько полигонов Для каждого их них

определяется количество полигонов, пересекающих разделяющую плоскость Выбирается тот, чья плоскость имеет наименьшее число пересечений Статистически показано, что для получения сбалансированного дерева, необходимо протестировать только 0,5% треугольников, входящих в состав сцены Тестирование более 0 5% треугольников не намного улучшает результат Алгоритм создания бинарного дерева выглядит следующим образом

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

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

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

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

Двоичное дерево

При обходе дерева составляется список визуализации

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

Начнем с корневой вершины дерева, как показано на рис 2 Учитывая, что плоскость разделения принадлежит узлу дерева и определяется базовой точкой /q =(Xq,)1q,Zq) и вектором нормаяи

п = {пх,пу,п2), определим полупространство, в котором лежит точка обзора

Pview = (Pvte wx, Pview у, Pviewz) следующим образом

R = sign[nx(Pviewx ~x0) + ny (Pvtewy - уQ) + nz (Pviewz - zQ)],

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

При R > 0 точка обзора лежит в положительном полупространстве, при R < 0 в отрицательном, при Л = 0на разделяющей плоскости

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

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

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

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

Р Р

о 1 Плоскость треугольника

1п

''о в / Плоскость треугольника

View

view

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

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

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

К)

>90 ,

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

нн

Найдем значение угла в, учитывая, что View — вектор направления взгляда, Pvtew —

положение точки наблюдения, п — нормаль к поверхности, а — угол обзора наблюдателя, V — вектор от поверхности к точке наблюдения, в — угол между нормалью к поверхности п и вектором направления взгляда View

Если точка наблюдения Pvlew находится с лицевой стороны исследуемого треугольника, те (n'V) > 0, тогда условие видимости следующее j>90° Учитывая, что п'У = |и|-|Р|соз# и считая

векторы нормализованными (|и[=\V\ = 1), получим

rt'V = case, в = arccos(n-F).

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

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

M = VxPxTxSxR,

где V - матрица экранной области, Р * матрица проекций, Т - матрица смещений, S - матрица масштаба, R - матрица поворота Представленные матрицы имеют следующий вид

0 0 Sx^+Sxj

2 2

0 0

2 2

0 0 1 1

0 0 0 1

Р=

1 0 0

0 1 0

0 0 1

0 0 ~~Т7Г~ 1

'far

*пеаг>

0 0 о, 1

1 0 0 Тх 0 0 0

т= 0 1 0 ТУ s= 0 *У 0 0

0 0 1 Tz 0 0 0

0 0 0 1 0 0 0 1

cos(ar )cos(/?)

sin(a )cos(/3)

- sin(/J) O

-sin(a)cosO)+ cos(or)cos(y) + eos (a )sin(6)sin(^) sin(ar )sin(;3 )sm(x)

cos(/?)sin (/) 0

R =

sin(a )sin(y) + - cos(ar) sin(/)+

cos(a ) sin(yff ) cos(^) sin (a )sin(/!? )cos(f)

cos(/0 )cos(/) 0

0

0

0

1

где - координаты левого верхнего угла экрана, (й^,^) - координаты правого

нижнего угла экрана, 2пеаг - передняя отсекающая плоскость по глубине, задняя отсекающая

плоскость, (а,р,у) обозначают углы поворота относительно осей (Х,У,2Г) соответственно, - масштабные коэффициенты, (Тх,Ту,Т2) - смещения Для перехода из объектного пространства в отображаемое пространство, необходимо умножить векторы, описывающие вершины треугольников, на матрицу результирующих трансформаций М

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

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

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

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

Для эффективного тайлинга полигонов, метод использует предпросчитанные бинарные маски на всех уровнях иерархии изображения Такое решение позволит реализовать процесс рекурсивного деления изображения, которое будет управляться результатом операций бинарного маскирования Бинарная маска классифицирует каждый растровый блок на краю примитива как наружный и внутренний по отношению к краю примитива (Рис 15а) Подобная операция классифицирует субъячейки как внешние, внутренние и пересекающие край, как показано на Рис 1 5Ь, где край полигона проходит через сетку (4x4) субъячеек Таким образом, в результате применения бинарной маски для текущей субячейки будет получено три возможных результата "принять", "отклонить" или "работать дальше" Совокупная бинарная маска, состоит из двух бинарных масок первая указывает на внутренние субъячейки, вторая на внешние (Рис 1 5с и 1 5(1) Будем обозначать маску для внутренних ячеек - буквой "I", а маску для внешних ячеек - буквой "О"

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

Эта часть маски будет обозначена букаой "А", как показано на Рис. 4. "А" представляет собо З: 1

А=-ЩО\ |

где А - активная площади маски, / - маска для внутренних ячеек, О - маска для внешних я^еек. Знак " означает операции логического отрицания, знак")" - операцию дизъюнкции

На практике алгоритм использует сетку размерностью 8x8, однако на рисунках в целях наглядности изображена сетка 4x4.

Внешня СТирОИР

Маска О

Маска А=~{1\0)

Пересекаю щне ячейки

Внешняя

сторона

сторона а

Маска /

Внутренние ячейки

Внешние ячейки

Рис 4, Типы бинарных масок

Механизм бинарных масок реализуют две базовые функции тайлинга и определения видимости:

1. поиск маски, соответствующей обрабатываемому полигону из таблицы масок, описывающих края полигона;

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

Получаемая иерархия изображения составляет уровни пирамиды, которая схематично воспроизведена на Рис, 5. (Если представить данный рисунок » трехмерной проекции, с соблюдением масштаба размеров уровней, изображение будет иметь вид пирамиды), э*рам

Й 1

1

увеличение

1 Ш --* п

Блок пикселей Блок пикселей Ъдо, пюгйглей Отдельный

размерностью р,-ушсрност»-ю размерностью пикселей

Л'£-'.ЛГ1-< Я2.]?* ШV

Ваутреязляя сторона б.

Рис 5. Пирамида иерархического тайлинга

На рис $ представлена схематическая диаграмма пирамиды масок размерностью и

количеством уровней Ь Данная пирамида полностью состоит из бинарных масок В приведенном примере иерархической дискретизации всего экрана, биты I и О масок будут указывать, какие именно квадратные участки экрана (тайлы) будут считаться закрытыми, вакантными или активными На самом нижнем уровне, бинарные маски соответствует экрану, на самом верхнем - пикселю Четырехуровневая пирамида с масками 8x8 соответствует изображению в 512x512 пикселей

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

1 Находим точки пересечения краев полигона с границей ячейки и находим соответствующие

этим краям маски из таблицы ((71,,Го,),{Тг2,Тог)......,(7\,7о„)), где кортеж (Тгк,Ток)

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

= Г(, &Ъг & &Т1„, Р0=То,\То2\....\То„,

где " &" - операция конъюнкции

2 Находим маску Р полностью видимых ячеек, принадлежащих полигону внутри тайла, характеризующимся масками (К,,К0)

Р=К„&Р„

где Ка - текущее состояние маски внешних ячеек, Р1 - маска внутренних ячеек полигона

3 Находим маску А активных ячеек полигона внутри тайла

где К, - текущее состояние маски внутренних ячеек, Рв - маска внешних ячеек полигона

4 Обновляем значения масок для текущего тайла {К,, Кв )

Ко = Ка&~ Р,

где (К.', ,К'0) характеризуют новые значения масок для текущего тайла Напомним, что знак

" ~ " означает операцию логического отрицания

Отметим, что обновление (К.,Ко) осуществлятся вызовами с любых уровней пирамиды

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

пространстве на основе бинарных деревьев, метод двух проходного расчета видимости частей изображения на основе иерархического тайлинга, метод определения видимости треугольнико» на основе бинарного маскирования, целочисленный метод растеризации и текстурирования треугольников Программная модель реализована в виде С++ библиотеки для платформ Microsoft Windows CE 3 О, 4х, 5 0 (включающей в себя PocketPC, Smartphone и Windows СЕ устройства) Кодовое название библиотеки—SGL (Smart Graphie Library) SGL работает за счет средств цемрального процессора.

Библиотека поддерживает 2 конвейера отрисовки фиксированный (FFP - fixed-function pipeline) и программируемый

FFP включает в себя следующие функции освещенность на уровне вершин, интерполяцию цветов, текстурирование, мультитекстурирование (реализуется аналогично nVidia Register Combiners)

Программируемый конвейер позволяет использовать технологию вершинных и пиксельных шейдеров Входные и выходные параметры шеЩюра аналогичны спецификации ARB версии 3 0 Нет ограничений на текстурную выборку, количество инструкций, динамические ветвления, циклы и прочее, тк код шейдера представляет собой inline функцию на С++, выполняемую центральным процессором Шейдеры позволяют создавать попиксельную освещенность, рельефное текстурирование, отражения и преломления на различных поверхностях и т д.

SGL поддерживает stencil-buffer для маскирования на уровне пикселей Код растеризации, геометрических трансформаций, вершинных и пиксельных шейдеров использует вычисления в пространстве целых чисел, что позволяет отрисовывать достаточно сложные сцены в реальном времени на процессорах со средней частотой в 266MHz и ниже

Код библиотеки содержит программные оптимизации, позволяющие увеличить скорость выполнения в среднем на 200% Дня увеличения скорости работы использовались следующие критерии оптимизации

• Целочисленные вычисления в критических участках программного кода (геометрические трансформации, растеризация, z-buffer, интерполяция и пр )

• Использование чисел близких к нулю Работа с низкими порядками (3-6 битов на вещественную часть)

• Отсутствие условных переходов в критических участках программного кода

• Снижение числа выборок из памяти за счет изменения формата представления текстурных данных

• Процедурно-ориентированный подход в цикле рендеринга, широкое использование встраиваемых функций

• Отсутствие операций приведения типов в критических участках программного кода

• Отсутствие обращений к массивам по индексу Инкрементирование и декрементирование указателей при трассировке по элементам массива

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

SGL позволяет отрисовывать до 1 ООО ООО видимых треугольников в секунду, что является очень высоким показателем для мобильных устройств (цифры для PocketPC, процессора Intel XScale РХА270 520 MHz, экрана QVGA)

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

При решении поставленных в диссертационной работе задач получены следующие научные результаты

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

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

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

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

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

По теме диссертационной работы опубликованы следующие работы

1 Надолинский H А, Мобильные геоинформационные системы на платформе Microsoft Windows CE // Материалы Всероссийской конференции студентов, аспирантов и молодых ученых "Технологии Microsoft в теории и практике программирования" Москва Изд-во МГТУ им H Э Баумана, 2006

2 Надолинский H А, Трехмерная графика реального времени для мобильных устройств на платформе Microsoft Windows Mobile // Материалы Всероссийской конференции студентов, аспирантов и молодых ученых "Технологии Microsoft в теории и практике программирования" Москва Изд-во МГТУ им H Э Баумана, 2006

3 Надолинский H А, Библиотека быстрой отрисовки двумерной графики QuickDraw // Материалы III Всеросийской научной конференции молодых ученых, аспирантов и студентов "Информационные технологии, системный анализ и управление" Таганрог Изд-во ТРТУ, 2005

4 Надолинский НА, Программирование трехмерной графики реального времени Создание реалистичных отражений и преломлений // Материалы первой ежегодной научной конференции студентов и аспирантов базовых кафедр южного научного центра РАН Ростов-на-Дону Изд-во ЮНЦ РАН, 2005

5 Надолинский H А, Трехмерные геоинформационные системы // Материалы Всероссийской конференции студентов, аспирантов и молодых ученых "Технологии Microsoft в теории и практике программирования" Москва Изд-во МГТУ им H Э Баумана, 2005

6 Надолинский H А, Программирование трехмерной графики на платформе Microsoft Windows CE II Материалы Всероссийской конференции студентов, аспирантов и молодых ученых "Технологии Microsoft в теории и практике программирования" Москва Изд-во МГТУ им H Э Баумана, 2005

7 Надолинский H А, Программирование библиотеки Smart OpenGL для платформы Microsoft Windows CE // Материалы VII Всеросийской научной конференции с международным участием "Новые информационные технологии Разработка и аспекты применения" Таганрог Изд-во "ПБОЮЛ В А Кравцов", 2004

8 Надолинский НА, Динамические тени реального времени Sample-based метод поточечного построения тени в пиксельном шейдере // Материалы VII Всеросийской научной конференции с международным участием "Новые информационные технологии Разработка и аспекты применения" Таганрог Изд-во "ПБОЮЛ В А Кравцов", 2004

9 Надолинский Н А, Программирование трехмерной графики для КПК на платформе Microsoft Windows СЕ // Материалы VII Всеросийской научной конференции студентов и аспирантов "Техническая кибернетика, радиоэлектроника и системы управления" Таганрог Изд-во ТРТУ, 2004

10 Надолинский Н А, Удаление невидимых граней для групп треугольников на основе графового представления данных // Материалы VII Всеросийской научной конференции студентов и аспирантов "Техническая кибернетика, радиоэлектроника и системы управления" Таганрог Изд-во ТРТУ, 2004

11 Надолинский Н А, Программирование геометрических процессоров с помощью технологии вершинных и пиксельных шейдеров Языки CG и HLSL // Материалы Всероссийской научной конференции молодых ученых и аспирантов "Информационные технологии, системный анализ и управление" Таганрог Изд-во ТРТУ, 2003

12 Надолинский Н А, Трехмерное математическое моделирование опасных ситуаций на железной дороге // Материалы VI Всеросийской научной конференции с международным участием "Новые информационные технологии Разработка и аспекты применения" Таганрог Изд-во "Антон", 2003

13 Надолинский Н А, Виртуальная реальность Программное ядро трехмерной визуализации // Материалы VI Всеросийской научной конференции студентов и аспирантов "Техническая кибернетика, радиоэлектроника и системы управления" Таганрог Изд-во ТРТУ, 2002

14 Надолинский Н А, Трехмерные геоинформационные системы // Материалы VI Всеросийской научной конференции студентов и аспирантов "Техническая кибернетика, радиоэлектроника и системы управления" Таганрог Изд-во ТРТУ, 2002

15 Вишнякова Д Ю, Надолинский Н А, Программная реализация трехмерных сцен // Известия ТРТУ Тематический выпуск "Интеллектуальные САПР" Материалы международной научно-технической конференции "Интеллектуальные САПР" Таганрог Изд-во ТРТУ, 2001, №4

16 Надолинский Н А, Метод удаления невидимых поверхностей с динамически изменяемым уровнем детализации сцены // Известия ТРТУ Специальный выпуск "Естественные и гуманитарные науки" Таганрог Изд-во ТРТУ, 2006, №9

Личный вклад автора в работах, написанных в соавторстве, состоит в следующем [8,10,16] -разработка базовых методов и алгоритмов определения видимости полигонов в реальном времени, [2,4,6,7,8,11,12,13,15] - программная реализация разработанного метода, [1,3,5,14] - основные направления применения методов определении видимости полигонов в реальном времени

ЛР N2 020565 от 23 06 97 г Подписано в печать Ю 0$ О^. формат 60x84 1/16 Бумага офсетная Печать офсетная Уел п л - 1 Тираж 100 экз Заказ №

"С"

Издательство Таганрогского технологического института южного федерального университета

ГСП 17 А, Таганрог - 28, Некрасовский, 44 Типография Таганрогского технологического института южного федерального университета ГСП 17 А, Таганрог-28, Энгельса, 1

ВВЕДЕНИЕ.

1. ОБЗОР СУЩЕСТВУЮЩИХ МЕТОДОВ ОПРЕДЕЛЕНИЯ ВИДИМОСТИ ПОЛИГОНОВ В РЕАЛЬНОМ ВРЕМЕНИ ПРИ ОТРИСОВКЕ ТРЕХМЕРНЫХ ОБЪЕКТОВ.И

1.1. Анализ характеристик методов удаления невидимых поверхностей.

1.1.1. Использование когерентных связей.

1.1.2. Соотношение визуализируемой части геометрии к общей.

1.1.3. Количество перекрытий.

1.2. Методы оптимизации.

1.2.1. Отсечение нелицевых граней.

1.2.2. Ограничивающие тела.

1.2.3. Разбиение пространства.!.

1.2.4. Иерархические структуры.

1.3. Удаление невидимых поверхностей.

1.3.1. Метод трассировки лучей.

1.3.2. Метод z-буфера.

1.3.3. Сортировка по глубине. Метод художника.

1.3.4. Метод построчного сканирования.

1.3.5. Метод Варнока.

1.5. Выводы.

2. ОРГАНИЗАЦИЯ ПОЛИГОНОВ В ОБЪЕКТНОМ ПРОСТРАНСТВЕ.

2.1. Описание метода двоичного разбиения пространства.

2.2. Построение дерева на основе пространственного разбиения граней.

2.3. Механизм обхода двоичного дерева полигонов.

2.4. Пространственное отсечение задних поверхностей и групп поверхностей.

2.6. Механизм отображения двоичного дерева полигонов.

2.7. Выводы.

3. ОРГАНИЗАЦИЯ ПОЛИГОНОВ В ОТОБРАЖАЕМОМ ПРОСТРАНСТВЕ.

3.1. Описание метода двухпроходной растеризации на основе иерархического тайлинга полигонов.

3.2. Механизм бинарных масок.

3.3. Механизм отсечений по границам экрана.

3.4. Механизм растеризации.

3.5. Механизм текстурирования.

3.6. Выводы.

4. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ МОДЕЛИ СИСТЕМЫ ОПРЕДЕЛЕНИЯ ВИДИМОСТИ ПОЛИГОНОВ, ЕЕ ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ И СРАВНЕНИЕ С АНАЛОГАМИ.

4.1. Программные оптимизации.

4.2. Экспериментальное исследование программной модели, сравнение с аналогами.

4.3. Выводы.

Современное программное обеспечение в таких областях как 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. Проведены экспериментальные оценки основных характеристик модели системы отрисовки геометрических данных в сравнении с существующими аналогами. На основе полученных экспериментальных оценок сделаны выводы о работоспособности предложенных методов удаления невидимых поверхностей и применимости их в реальных, системах отображения графических данных.

1. Надолинский Н.А. "Трехмерные геоинформационные системы". Материалы VI Всеросийской научной конференции студентов и аспирантов "Техническая кибернетика, радиоэлектроника и системы управления". Сборник тезисов. Таганрог: Изд-во ТРТУ, 2002. с.119

2. Надолинский Н.А. "Программная реализация трехмерных сцен". Известия ТРТУ. Тематический выпуск "Интеллектуальные САПР".

3. Материалы международной научно-технической конференции "Интеллектуальные САПР". Сборник статей. Таганрог: Изд-во ТРТУ, 2001, №4, с.342

4. Надолинский Н.А. "Метод удаления невидимых поверхностей с динамически изменяемым уровнем детализации сцены". Известия ТРТУ. Специальный выпуск "Естественные и гуманитарные науки". Таганрог: Изд-во ТРТУ, 2006, №9, с.25.

5. Агапьев Б. Д. и др. "Обработка экспериментальных данных" Кафедры экспериментальной физики СПбГТУ, 2001.

6. Игнатенко А. Геометрическое моделирование сплошных тел. On-line журнал "Графика и Мультимедиа".

7. Роджерс Д. Математические основы машинной графики / Д. Роджерс, Дж. Адаме. М: Мир, 2001.

8. Роджерс, Дэвид. Алгоритмические основы машинной графики: Пер. с англ. / Д. Роджерс.-М.: Мир, 1989.

9. Рони Я. Рендеринг объемов в реальном времени Университет шт. Огайо, США Открытые Системы №5(19)/96.

10. Ян Ф., и др. Удаленная визуализация 16.11.1999 Открытые системы, № 11-12/1999

11. Hudson Т., Manocha D., Cohen J., Lin M., Hoff К, Zhang H. Accelerated occlusion culling using shadow frustra. In Proc. 13th Annu. ACM Sympos. Comput. Geom., 1997

12. Borshukov, G.D., New Algorithms for Modeling and Rendering Architecture from Photographs., M.S Thesis, EECS department, UC Berkeley, 1997.

13. Cipolla, R., D. Robertson, and E. Boyer. Photobuilder 3D Models of Architectural Scenes from Uncalibrated Images. Procedings of Conference on Multimedia Computing and Systems. 1999.

14. Horry, Y., K.I. Anjyo, and K. Arai. Tour into the picture: Using a spidery mesh interface to make animation from a single image. Procedings of SIGGRAPH 1997.

15. K.Turkowski., Y.X.a., Creating image-basedVRusing a self-calibrating fish-eye lens. In IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'97), San Juan, Puerto Rico, June 1997.

16. Kang, S.B. and R. Szeliski. 3-D scene data recovery using omnidirectional multibaseline stereo. Procedings of EEE Computer Society Conference on Computer Vision and Pattern Recognition. 1996. San Francisco, California.

17. Kutulakos, K. and S. Seitz, A Theory of Shape by Space Carving. International Journal of Computer Vision, 2000. 38(3).

18. Pollefeys, M., R. Koch, M. Vergauwen, B. Deknuydt, and L.V. Gool. Three-dimensional scene reconstruction from images. Procedings of SPIE Electronic Imaging, Three-Dimensional Image Capture and Applications III, SPIE Proceedings series. 2000.

19. Scharstein, D., Stereo vision for view synthesis. In IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'96), San Francisco, California, June 1996.

20. Seitz, S.a.C.D. Photorealistic Scene Reconstruction by Voxel Coloring. Procedings of Computer Vision and Pattern Recognition Conference, p. 1997.

21. Taylor, C., P. Debevec, and J. Malik. Reconstructing Polyhedral Models of Architectural Scenes from Photographs. Procedings of ECCV '96: Fourth European Conference on Computer Vision, 1996.

22. Trucco, E. and A. Verri, Introductory Techniques for 3-D Computer Vision. 1998, New Jersey: Prentice Hall.

23. PhotoModeler. http://www.PhotoModeler.com

24. Canoma. http://www.canoma.com.

25. Liebowitz, D., A. Criminisi, and A. Zisserman. Creating Architectural Models from Images. Procedings of Eurographics 1999, Computer Graphics Forum. 1999.

26. Lengyel., J., The convergence of graphics and vision. Technical report, IEEE Computer, July 1998.

27. Cyberware, Inc. Available from: www.cyberware.com

28. Kang, S.B., A survey of image-based rendering techniques. VideoMetrics , SPIE, 1999.3641: p. 2-16.

29. Kurt Akeley and T. Jermoluk. High-Performance Polygon Rendering. Computer Graphics (SIGGRAPH 88 Conference Proceedings), volume 22, number 4, pages 239-246. August 1988.

30. Kurt Akeley. RealityEngine Graphics. SIGGRAPH 93 Conference Proceedings, pages 109-116. August 1993. ISBN 0-89791-601-8.

31. Loren Carpenter. The A-buffer, an Antialiased Hidden Surface Method. Computer Graphics, (SIGGRAPH 84 Conference Proceedings), volume 18, number 3, pages 103-108. July 1984. ISBN 0-89791-138-5.

32. Michael Deering and S. Nelson, Leo: A System for Cost Effective 3D Shaded Graphics. SIGGRAPH 93 Conference Proceedings, pages 101-108. August 1993.

33. Henry Fuchs. Distributing a Visible Surface Algorithm over Multiple Processors. Proceeding of the 6th ACM-IEEE Symposium on Computer Architecture, pages 58- 67. April, 1979.

34. Henry Fuchs et al. Fast Spheres, Shadows, Textures, Transparencies, and Image Enhancements in Pixel-Planes. Computer Graphics, (SIGGRAPH 85 Conference Proceedings), volume 19, number 3, pages 111-120. July 1985.

35. Paul Haeberli and Kurt Akeley. The Accumulation Buffer: Hardware Support for High-Quality Rendering. Computer Graphics, (SIGGRAPH 90 Conference Proceedings), volume 24, number 4, pages 309-318. August 1990. ISBN 0-89791-344-2.

36. Chandlee Harrell and F. Fouladi. Graphics Rendering Architecture for a High Performance Desktop Workstation. SIGGRAPH 93 Conference Proceedings, pages 93-100. August 1993.

37. Michael Kelley, K. Gould, B. Pease, S. Winner, and A. Yen. Hardware Accelerated Rendering of CSG and Transparency. SIGGRAPH 94 Conference Proceedings, pages 177-184.1994.

38. Abraham Mammen. Transparency and Antialiasing Algorithms Implemented with the Virtual Pixel Maps Technique. IEEE Computer Graphics and Applications, 9(4), pages 43-55. July 1989. ISBN 0272-1716.

39. Steven Molnar, John Eyles, and John Poulton. PixelFlow: High-Speed Rendering Using Image Composition. Computer Graphics, (SIGGRAPH 92Conference Proceedings), volume 26, number 2, pages 231-240. July 1992.

40. F. Park. Simulation and Expected Performance Analysis of Multiple Processor Z-Buffer Systems. Computer Graphics, (SIGGRAPH 80 Conference Proceedings), pages 48-56.1980.

41. Thomas Porter and Tom Duff. Compositing Digital Images. Computer Graphics, (SIGGRAPH 84 Conference Proceedings), volume 18, number 3, pages 253-259. July 1984. ISBN 0-89791-138-5.

42. Andreas Schilling. A New Simple and Efficient Antialiasing with Subpixel Masks. Computer Graphics, (SIGGRAPH 91 Conference Proceedings), volume 25, number 4, pages 133-141. July 1991.

43. Jay Torborg and James Kajiya. Talisman: Commodity Realtime 3D Graphics for the PC. SIGGRAPH 96 Conference Proceedings, pages 353363.1996.

44. G. Watkins. A Real-Time Visible Surface Algorithm. Computer Science Department, University of Utah, UTECH-CSC-70-101. June 1970.

45. Lance Williams. Pyramidal Parametrics. SIGGRAPH 83 Conference Proceedings, pages 1-11. July 1983.

46. G. Abram, L. Westover, and T. Whitted, "EcientAlias-Free Rendering using Bit-Masks and Look-Up Tables" Proceedings of SIGGRAPH *85, July 1985, 53-59.

47. L. Carpenter, "The A-buffer, an Antialiased HiddenSurface Method" Proceedings of SIGGRAPH '84 , July 1984.

48. E. Catmull, "A Subdivision Algorithm for ComputerDisplay of Curved Surfaces" PhD Thesis, Report UTEC-CSc-74-133, Computer Science Dept., University of Utah, Salt LakeCity, Utah, Dec. 1974.

49. E. Catmull, "A Hidden-Surface Algorithm with Anti-Aliasing" Proceedings of SIGGRAPH 1% , Aug. 1978, 6-11.

50. R. Cook, "Stochastic Sampling in Computer Graphics" ACM Transactions on Graphics, Jan. 1986,51-72.

51. M. A. Z. Dippe and E. H. Wold, "Antialiasingthrough Stochastic Sampling" Proceedings of SIGGRAPH 85, July 1985,69-78.

52. E. Fiume, A. Fournier, and L. Rudolph, "A ParallelScan Conversion Algorithm with Anti-Aliasing for a General-Purpose Ultracomputer" Proceedings of SIGGRAPH '83 , Julyl983,141-150.

53. E. Fiume, "Coverage Masks and Convolution Tables forFast Area Sampling" Graphical Models and Image Processing, 53(1), Jan. 1991, 2530.

54. J. Foley, A. van Dam, S. Feiner, and J. Hughes, Computer Graphics, Principles and Practice, 2nd edition, Addison-Wesley, Reading, MA, 1990.

55. H. Fuchs, J. Kedem, and B. Naylor, "OnVisible Surface Generation by a Priori Tree Structures", June 1980,124-133.

56. N. Greene, M. Kass, and G. Miller, "Hier-archical Z-Buffer Visibility" July 1993,231-238.

57. N. Greene and M. Kass, "Error-Bounded An-tialiased Rendering of Complex Environments", July 1994, 59-66.

58. N. Greene, "Hierarchical Rendering of Complex Environments" PhD Thesis, Univ. of California at Santa Cruz, ReportNo. UCSC-CRL-95-27, June 1995.

59. N. Greene, "Naked Empire" ACM Siggraph Video Re-view Issue 115: The Siggraph '96 Electronic Theater, August 1996.

60. P. Haeberli and K. Akeley, "The AccumulationBuffer: Hardware Support for High-Quality Rendering", Aug. 1990,309-318.

61. A. Kaufman, "3D Scan Conversion Algorithms forVoxel-Based Graphics", Oct. 1986, 45-75.

62. D. Meagher, "The Octree Encoding Method for Efficient Solid Modeling" PhD Thesis, Electrical Engineering Dept., Rensselaer Polytechnic Institute, Troy, New York, Aug. 1982.

63. B. Naylor, "Interactive Solid Geometry Via PartitioningTrees", May 1992, 11-18.

64. B. Naylor, "Partitioning Tree Image Representation andGeneration from 3D Geometric Models", May 1992,201-212.

65. D. Rogers, Procedural Elements for Computer Graphics, McGraw-Hill, New York, 1985.

66. P. Sabella and M. Wozny, "Toward Fast Color-Shaded Images of CAD/CAM Geometry", 3(8), Nov. 1983,60-71.

67. S. Teller, "Visibility Computations in Densely OccludedPolyhedral Environments" PhD Thesis, Univ. of California atBerkeley, Report No. UCB/CSD 92/708, Oct. 1992.

68. J. Warnock, "A Hidden Surface Algorithm for Com-puter Generated Halftone Pictures" PhD Thesis, ■ ComputerScience Dept., University of Utah, TR 4-15, June 1969.