Главная
страница 1


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

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



РАЗРАБОТКА И ИССЛЕДОВАНИе МЕТОДОВ ОПРЕДЕЛЕНИЯ ВИДИМОСТИ ПОЛИГОНОВ В РЕАЛЬНОМ ВРЕМЕНИ ПРИ ОТРИСОВКЕ ТРЕХМЕРНЫХ ОБЪЕКТОВ
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. Выбрать треугольник из списка и использовать его в качестве разделительной плоскости. Если в списке больше нет треугольников — выход из алгоритма.




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




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




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



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


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

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



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

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


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

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





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

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



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

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


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

где - матрица экранной области, - матрица проекций, - матрица смещений, - матрица масштаба, - матрица поворота. Представленные матрицы имеют следующий вид:


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


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

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

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

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

Для эффективного тайлинга полигонов, метод использует предпросчитанные бинарные маски на всех уровнях иерархии изображения. Такое решение позволит реализовать процесс рекурсивного деления изображения, которое будет управляться результатом операций бинарного маскирования. Бинарная маска классифицирует каждый растровый блок на краю примитива как наружный и внутренний по отношению к краю примитива (Рис 1.5а). Подобная операция классифицирует субъячейки как внешние, внутренние и пересекающие край, как показано на Рис. 1.5b, где край полигона проходит через сетку (4х4) субъячеек. Таким образом, в результате применения бинарной маски для текущей субячейки будет получено три возможных результата: "принять", "отклонить" или "работать дальше". Совокупная бинарная маска, состоит из двух бинарных масок: первая указывает на внутренние субъячейки, вторая на внешние (Рис 1.5с и 1.5d). Будем обозначать маску для внутренних ячеек - буквой "I", а маску для внешних ячеек - буквой "O".

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

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

где - активная площадь маски, - маска для внутренних ячеек, - маска для внешних ячеек. Знак “” означает операцию логического отрицания, знак“” – операцию дизъюнкции.

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



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


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

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

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



Рис 5. Пирамида иерархического тайлинга
На рис. 5 представлена схематическая диаграмма пирамиды масок размерностью и количеством уровней L. Данная пирамида полностью состоит из бинарных масок. В приведенном примере иерархической дискретизации всего экрана, биты I и O масок будут указывать, какие именно квадратные участки экрана (тайлы) будут считаться закрытыми, вакантными или активными. На самом нижнем уровне, бинарные маски соответствует экрану, на самом верхнем - пикселю. Четырехуровневая пирамида с масками 8х8 соответствует изображению в 512х512 пикселей.

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

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

где “” – операция конъюнкции.
2. Находим маску полностью видимых ячеек, принадлежащих полигону внутри тайла, характеризующимся масками :

где - текущее состояние маски внешних ячеек, - маска внутренних ячеек полигона.
3. Находим маску активных ячеек полигона внутри тайла:

где - текущее состояние маски внутренних ячеек, - маска внешних ячеек полигона.
4. Обновляем значения масок для текущего тайла :

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

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


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

Программная модель реализована в виде С++ библиотеки для платформ Microsoft Windows CE 3.0, 4.x, 5.0 (включающей в себя PocketPC, Smartphone и Windows CE устройства). Кодовое название библиотеки – SGL (Smart Graphic Library). SGL работает за счет средств центрального процессора.

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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




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

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

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

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

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


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

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

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

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

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

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

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

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

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

  9. Надолинский Н.А., Программирование трехмерной графики для КПК на платформе Microsoft Windows CE // Материалы 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] – основные направления применения методов определении видимости полигонов в реальном времени.

ЛР № 020565 от 23.06.97 г.

Подписано в печать формат 60х84 1/16

Бумага офсетная. Печать офсетная. Усл. п.л. – 1

Тираж 100 экз. Заказ №

“С”



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


ГСП 17 А, Таганрог – 28, Некрасовский, 44.

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



ГСП 17 А, Таганрог – 28, Энгельса, 1.




Смотрите также:
Разработка и исследование методов определения видимости полигонов в реальном времени при отрисовке трехмерных объектов 05. 13. 17 Теоретические основы информатики
241.76kb.
1 стр.
Общение в реальном времени
310.41kb.
1 стр.
Теоретические основы информатики Содержание тестовых материалов Информатика и математика 2 курс агпа
209.72kb.
1 стр.
Наземные наблюдения космических лучей и представление информации в интернет в реальном времени
104.27kb.
1 стр.
В настоящее время курс «Основы искусственного интеллекта» является базовым при подготовке учителей информатики по специальности 030100. 00 информатика
788.06kb.
6 стр.
Исследование и разработка методов построения и кэширования веб-приложений
25.77kb.
1 стр.
Основы правовой информатики (юридические и математические вопросы информатики)
3027.48kb.
33 стр.
Разработка и исследование методов геометрической коррекции и фотограмметрической обработки материалов воздушной нестабилизированной гиперспектральной съемки
227.61kb.
1 стр.
«Анализ угроз, использующих уязвимости защиты, и разработка методов повышения уровня защищенности объектов информационных процессов»
55.23kb.
1 стр.
Скороходов Алексей Дмитриевич исследование и разработка методов взаимодействия в интернете вещей направление 23. 01. 00. 68 Информатика и вычислительная техника Магистерская программа
698.42kb.
5 стр.
Тема: «Разработка теории обоснования параметров, методов моделирования и исследования элементов, объектов и систем возобновляемой энергетики с использованием инновационных технологий»
133.94kb.
1 стр.
Разработка и исследование
806.11kb.
6 стр.