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

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

□03449Э4Э

МИНАЕВ Евгений Владимирович

Методы и структуры данных эффективной визуализации открытых пространств

Специальность - 05 13.17 Теоретические основы информатики

АВТОРЕФЕРАТ

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

1 6 О КГ 2008

Москва 2008

003449949

Работа выполнена в Московском государственном университете приборостроения и информатики на кафедре «Персональные компьютеры и сета»

Научный руководитель

доктор технических наук, профессор Михаил Васильевич Ульянов

Официальные оппоненты

доктор технических наук, профессор Белов Владимир Викторович

кандидат технических наук Винокуров Станислав Владимирович

Ведущая организация

ОАО «Научно-исследовательский кинофотоинсппут»

Защита состоится 6 ноября 2008 г в 1400 часов на заседании диссертационного совета Д 212 147 03 при Московском государственном университете печати (127550 Москва, ул Прянишникова, 2А)

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

Автореферат разослан 4 октября 2008 г

Ученый секретарь диссертационного совета Д 212 147 03

д т н , профессор

Агеев В Н

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность темы диссертационной работы. Круг задач компьютерной графики постоянно расширяется в связи с непрерывным ростом аппаратных возможностей современных компьютеров По этой причине множество ранее не рассматриваемых проблем визуализации стали актуальными Вследствие возросших требований к современным системам визуализации, разрабатываются новейшие алгоритмы для решения возникающих задач, ориентированные на современное аппаратное обеспечение Большинство актуальных в настоящее время проблем визуализации связано с необходимостью хранения и отображения огромных объемов данных за минимальное время Обычно такие задачи решаются посредством специальных вычислительных комплексов, однако, разрабатывая новые алгоритмы хранения и отображения информации, представляется возможным перенести часть этих задач на персональные компьютеры

Интерактивные системы визуализации трехмерных сцен являются одной из самых широких областей применения компьютерной графики К ним относятся системы визуализации абстрактных данных, системы визуализации результатов научных экспериментов, геоинформационные системы, компьютерная томография, САПР, тренажёры имитирования реальной техники, системы виртуальной реальности (УК-системы), компьютерные игры, графические оболочки файловых систем и других программ В системах такого рода важнейшей характеристикой качества является временная эффективность процесса отображения информации в зависимости от объема визуализируемых данных Отображаемая информация обычно представляет собой трехмерную сцену, состоящую из множества различных объектов В целях повышения качества этого типа программного обеспечения, разработчики идут на нетривиальные способы улучшения временной эффективности алгоритмов визуализации применительно к конкретным отображаемым данным Эти алгоритмы базируются на методах компьютерной геометрии и машинной графики Их задачами является отсечение невидимых частей и отображение нужных объектов оптимальным образом Для выполнения этих операций используются специальные структуры

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

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

Для открытых пространств разработано множество подходов к трехмерной визуализации, в исследование и развитие которых внесли вклад множество людей и компаний по всему миру Среди них, фундаментальные научные труды в области интерактивной трехмерной визуализации принадлежат следующим уче'ным Д Колер, П Линдстром, Т Ульрих, М Дучейнеу, С Роджер, X Хоуп, В Д Бор, С М Нелли, Г Корпс, Р Паджарола, А Грин, Л Касл, Д Блоу, В Эванс, Г Тонсенд, Ю Зао, Д Джоу, Д Ши, В Пакуси, X Хакл, П Сигнони, Ф Гановели, Э Гобети, Ф Мартон, Ф Пончио, Р. Скопинго и др Кроме того, существует огромное количество научных центров, занимающихся компьютерной

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

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

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

ляется вопросам построения оптимальной последовательности видимых объектов для эффективного использования аппаратного ускорения Объект и предмет исследования

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

Здесь под интерактивностью подразумевается возможность визуализации сцены в режиме реального времени, причем частота выводимых кадров (FPS) итогового двумерного изображения сцены должна быть не менее частоты кадровой развертки монитора При сохранении такого уровня временной эффективности, должен обеспечиваться оптимальный уровень качества картинки Кроме того, структура данных сцены должна занимать объем памяти не больше определённого размера, чтобы сделать возможным визуализацию этой сцены на персональном компьютере

В работе рассматриваются только проекционные методы синтеза изображений, которые, единственные на сегодняшний день, обеспечивают достаточную скорость для интерактивного режима. Рассматриваются только явно заданные данные. В работе не рассматриваются различные параметрические и процедурные представления, так как их особенности (сложность вычислений, отсутствие аппаратной поддержки) делает затруднительным их использование для визуализации в реальном времени Также, не рассматриваются модели сцен на основе изображений (IBMR) и точечные представления (point sample)

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

Научная новизна. Научная новизна диссертационной работы состоит в разработке

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

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

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

Практическая ценность работы. Практическая ценность результатов работы заключается в

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

— задачи отсечения невидимых частей сцены,

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

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

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

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

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

— выбора наиболее эффективных способов рендеринга на уровне графического API в соответствии с типом отображаемых объектов

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

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

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

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

Апробация. Основные положения и результаты диссертационной работы докладывались на VIII международной научно-практической конференции «Фундаментальные и прикладные проблемы приборостроения, информатики и экономики», а также на научных семинарах кафедры "Персональные компьютеры и сети" МГУПИ Результаты работы внедрены и используется в программном продукте Electromap для отображения географических карт в реальном времени

Публикации. Основные материалы диссертации опубликованы в пяти печатных работах, в том числе 1 статья из перечня ВАК, получено свидетельство о регистрации разработанных программных средств в Федеральной службе по интеллектуальной собственности (свидетельство № 2008614506 от 19 09 2008)

Структура работы. Диссертационная работа состоит из введения, четырёх глав, заключения, приложения и библиографического списка Основной текст диссертации изложен на 140 страницах, содержит 29 рисунков, 3 таблицы и библиографический список из 128 наименований

СОДЕРЖАНИЕ РАБОТЫ. Во введении обоснована актуальность темы диссертации и ее практическая значимость Сформулированы основные направления исследований, цели и задачи работы

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

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

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

— отсечение всех возможных невидимых частей сцены,

— использование многомасштабности (LOD) для ландшафта,

— использование LOD для полигональных объектов,

— использование динамической подгрузки для очень больших сцен,

— рендеринг объектов в удобном для графического API порядке,

— эффективное использование декораций и систем частиц,

—ускорение средствами графического API

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

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

Во второй главе разработаны новая структура данных трехмерной сцены и алгоритм визуализации, ее использующий В отличие от других подобных алгоритмов в предлагаемом решении используется такая структура, которая объединяет и ландшафт, и объекты в едином квадродереве Это дерево используется для отсечения невидимых частей ландшафта и невидимых объектов, причём отсечение происходит за один проход, что позволяет увеличить временную эффективность Такое улучшение алгоритма С1шпкес1Ь(Ю позволяет подгружать в параллельном потоке данные не только о ландшафте, но и об объектах над ним Эта особенность дает возможность визуализировать сверхбольшие сцены с ландшафтом и объектами, общий объем данных которых, не умещается в оперативной памяти Если в сцене имеется множество объектов с одинаковой геометрией, те уникальных объектов не так много, то динамическая подгрузка происходит практически без потери производительности для системы визуализации.

Другой важной особенностью является использование «активных декораций» для отображения дальних полигональных объектов В отличие от распространённого использования предварительно заготовленных биллбоардов, в данном методе двумерные изображения объектов синтезируется в реальном времени, прямо в ходе визуализации Это позволяет осуществить точную автоматическую подстройку изображения объекта под текущее положение и взгляд наблюдателя Благодаря использованию ограниченного количества текстурных буферов, рендеринг объектов на текстуру происходит оптимально быстро для используемого аппаратного обеспечения (видеоадаптера)

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

и

— рендеринг больших (out of core) открытых пространств в реальном времени,

— поддержка очень дальнего взгляда наблюдателя вдоль линии горизонта,

— отображение большого количества сложных дальних объектов,

— неограниченные возможности масштабирования сцены с помощью перемещений камеры (достигается с помощью LOD),

— плавные переходы в различными уровнями детализации,

— устранение разрывов между разными частями ландшафта,

— текстурирование ландшафта совместно с использованием LOD технологии,

— использование аппаратного ускорения видеоадаптера средствами графического API в ключевых частях алгоритма

Следует отметить, что метод «активных декораций», предложенный в данной работе имеет возможности расширения Тк множество выводимых биллбоардов, привязанных к разным объектам, представляют собой фактически систему частиц, существует вероятность их эффективной группировки Более того, если такая группировка возможна, то её можно использовать для автоматического создания более грубых уровней детализации при перемещении камеры вверх от ландшафта Таким образом, может работать, например, псевдотрехмерная картографическая система реального времени или программа автоматизированного проектирования

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

1 Отсечение ландшафта Quadtree с равномерным разбиением

2 Отсечение объектов над ландшафтом Quadtree с разбиением пространства по количеству объектов

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

4 ЬСЮ для ландшафта: используется С1шпкес1ЬСЮ

5 ЬСЮ для объектов используется статический ЬСЮ (предварительно заготовленные полигональные сетки)

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

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

Теоретическая оценка в этой работе не использует понятие элементарной операции, по описанным причинам Вместо этого используется понятие времени выполнения операции алгоритма Если время операции является постоянной величиной, то эта операция получает символическое обозначение Таким образом, для функций трудоемкости и объема памяти можно получить аналитические выражения Полученные функции затем можно оценить табличным и графическим способом, зная примерное отношение используемых временных и ёмкостных констант Использование приблизительной временной оценки определённых фрагментов (вычисляемое экспериментально) является единственным возможным способом получения качественной функции трудоемкости Аналогичное замечание относится к функции объема памяти алгоритма

В ходе теоретического анализа были получены следующие основные результаты Функции трудоемкости базового (А1) и разработанного (А2) алгоритмов имеют вид

tAi(n, w, V, nj = d+c+0,51og2n(2c+3d) + спс + 0,6mv(c+0,9tpoi+0,ltps) + vfO.Wpoi + 0,lrpJ, tA2(n, w, v, nj = d+c+0,5Iog2n(2c+3d) + c(nc-l-log2n) + 0,6nw (c+0,216tu+0,181^1+ 0, ItpJ + v(0,18^+0,8гы+ 0,02rpJ, где n — количество листовых узлов ландшафта, w — среднее количество объектов в секторе, v — количество видимых объектов, вычисленное в алгоритме, пс — количество проверок на видимость узлов объектного дерева, произведенные в базовом алгоритме Другими символами обозначено фиксированное время выполнения различных блоков алгоритма Эффективность временных улучшений в предлагаемом алгоритме по сравнению с базовым равна

tAi-tA2=tAl.A2(n, Nobj, Npot) = 343(1+log2n) + Nobj(0J5Npor31), n=2k, k>l, Notj>0, Npop-0 Графическое представление функции tAi.A2(n, N0bj, Npd) при различных параметрах представлены в таблице 1. Таблица 1

Значения функции функции tA!.A2(n, N0bj, N^ù, при п=409б Графическое представление функции изображено на рис 1 Полученные результаты позволяют сделать следующие выводы. При среднем количестве полигонов на объект, превышающем 200 предлагаемый алгоритм работает быстрее базового при любом количестве объектов в сцене, причем чем больше объектов в сцене, тем больше эффективность улучшений. Если среднее количество полигонов в объектах меньше 200, то базовый алгоритм работает быстрее, если количество объектов в сцене не слишком велико При малом количестве объектов предлагаемый алгоритм работает быстрее при любой детализации

UïOOO 120000 100000 елооо 60000 40000 2<Ю<5а о

20000 40000

OOj

Рис 1 График функции tAl.Ai(n, N0bj, Л^, при п=409б

Функции объемов памяти для базового и разработанного алгоритма равны соответственно

VAi = NmodM1+NobJOj+Nh/ll+Nla^i+vR+nwR+Volh, VA 2 = NmodM,+Nob/Oi+Oi,,i)+NlanLl+nwR+Vlex(v)+vR+R(l+l,5log2n)+Volh, где Nia„, Si, N0bf Oi, Ом, V,№ R — постоянные величины, обозначающее количество или объём памяти различных программных объектов. Разность объемов памяти у алгоритмов можно записать следующем образом

уагуа2=уа1.а2(п, kbj) = 58Nlcm-25020Nohr61og2n+4 Все значения функции Vai-a2(h, NobJ отрицательны Это означает, что разработанный А2 алгоритм использует больше памяти, чем алгоритм Al. За счет использования этой памяти в разработанном алгоритме обеспечивается улучшение временной эффективности

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

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

Найдено решение ключевых проблем, возникших при реализации эффективного рендеринга посредством API OpenGL Рендеринг трехмерной модели в текстуру эффективно реализуется в основном посредством расширения GL_EXT_framebuffer_object Для оценки практической эффективности способов вывода геометрии была написана отдельная тестирующая система, давшая ответы на поставленные вопросы Все объекты над ландшафтом и сами блоки ландшафта в разработанной программной реализации выводятся через glDrawElements(...) в режиме GL TRIANGLE STRIP. Преобразование полигональных сеток в последовательности полос треугольников сделано с помощью библиотеки NvTnStnp Library на этапе предварительной обработки

Описана программная архитектура, реализующая предлагаемую структуру данных и алгоритм Архитектура программной системы представлена в виде UML диаграмм, на основе объектно-ориентированной методологии Общая модульная структура разработанной системы показана на рис 2

€

Рис 2. Общая модульная структура разработанной системы визуализации

Приведен ряд экспериментов, поставленных для практической оценки ресурсной эффективности алгоритма Для экспериментов была выбрана сцена со следующими параметрами Ландшафт, заданный картой высот размерностью 2048x2048 с текстурой размером 2048x2048 пикселей На поверхности равномерно расположено 600 объектов Положение задано случайным образом Каждый объект представляет собой LOD-мoдeль, представленную 10 уровнями детализации. Все модели одинаковы, но для каждого из 600 объектов существует собственная, загруженная в память модель со всеми LOD-ypoвнями. Это сдела-

но для имитации максимального количества уникальных моделей. Полнодета-лизированная полигональная сетка (LC)D=0) модели содержит 17362 полигона.

На рис. 3 показана зависимость частоты кадров (FPS) от количества видимых объектов (objects).

700 ■ — ..........

600 ♦ •

400 fe

о

0 100 200 300 400 500 600 700

objects

Рис. 3. График зависимости частоты кадров (FPS) от количества видимых объектов (objects). Синим цветом обозначен базовый алгоритм (std), а красным —

предлагаемый (new).

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

При малом количестве видимых объектов базовый алгоритм показывает лучшие результаты, поскольку аппаратное обеспечение прекрасно справляется с малым объёмом данных, а в предлагаемом алгоритме производятся дополнительные вычисления для поиска дальних объектов, которых не существует. С ростом количества объектов производительность обоих алгоритмов падает и разрыв сокращается. Приблизительно при 40 видимых объектах оба алгоритма обеспечивают одинаковый FPS. При дальнейшем увеличении числа объектов разработанный алгоритм показывает уже лучшие результаты и на уровне 140 объектов уже заметно обгоняет базовый. В пределах от 140 до 300 обозреваемых объектов дистанция становится уже достаточно большой и предлагаемый алгоритм использует «активные декорации» для всех дальних объектов, что позволяет ему сохранять стабильный FPS. Частота кадров базового алгоритма не-

прерывно падает в этом промежутке и далее, т.к. в его случае постоянно растёт общее количество выводимых полигонов. После достижения точки в 300 объектов камера выходит за пределы ландшафта и все видимые объекты начинают одинаково удаляться. В базовом алгоритме ничего особенного не происходит — идёт такое же увеличение выводимых полигонов и падение частоты кадров. В разработанном алгоритме всё больше и больше объектов начинают заменяться декорациями, поэтому общее количество выводимых полигонов начинает сокращаться и FPS начинает расти! В итоге все видимые объекты будут заменены «активными декорациями».

На следующем графике представлена зависимость количества видимых полигонов (polygons) от количества видимых объектов (objects). Этот график наиболее ярко показывает эффективность улучшений, а точнее насколько оптимальной получается итоговая полигональная сетка всей сцены.

2QOOOO ■ . . .

О 100 200 300 400 600 600 700

objects

Рис. 4. Зависимость количества видимых полигонов (polygons) от количества видимых объектов (objects).

При использовании метода «активных декораций» программа выводит в 1,6-8 раз меньше полигонов. При описанных условиях предлагаемый алгоритм требует всего на 5 Мб больше видеопамяти. Это отражено на графике на рис. 5.

10 s

о

О 100 200 300 400 500 600 700

billboards

Рис. 5. Зависимость занятой видеопамяти (VRAM) от количества декораций.

Для современных видеоадаптеров 5 Мб видеопамяти — достаточно небольшой объём, что делает требования к аппаратному обеспечению вполне приемлемыми.

Разработанная система визуализации используется в программном продукте Electromap для отображения географических карт в реальном времени. Electromap представляет собой интерактивную поисковую систему для ориентации по географическим картам определённых регионов. Программная система Electromap применяется для наблюдения за состоянием объектов в соответствии с их географическим положением. Другой областью применения этой программы является поиск определённых мест, маршрутов и просто ориентация на местности. Обзор карт происходит в трёхмерном интерактивном режиме, причём размеры используемой карты не оказывают влияния на производительность (FPS).

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

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

В диссертации получены следующие основные результаты

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

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

3 Проведен теоретический анализ ресурсной эффективности разработанных методов

4 Проведено экспериментальное исследование полученного алгоритма в сравнении с базовым

5 На основе проведенных исследований разработана графическая библиотека для визуализации сверхбольших открытых пространств, включающая в себя подходы, изложенные в диссертации Программные средства зарегистрированы в Федеральной службе по интеллектуальной собственности (свидетельство № 2008614506 от 19 09 2008)

6 Результаты проведенных исследований и разработок внедрены в производственный процесс ООО «Электроинторг-Ком» В частности, разработанные программные средства использованы в проекте Electromap для визуализация географических карт в реальном времени, что позволило использовать карты практически любого размера (ограничение только размером жесткого диска) и высокой детализации без потери производительности. Программная система Electromap применяется для наблюдения за состоянием объектов в соответствии с их географическим положением Другой областью применения этой программы является поиск определённых мест, маршрутов и просто ориентация на местности Обзор карт происходит в трехмерном интерактивном режиме, причем размеры используемой карты не оказывают влияния на производительность (FPS)

Публикации по теме диссертации

Публикации в ведущих рецензируемых научных изданиях, рекомендуемых ВАК

1 Минаев Е В Алгоритм визуализации открытых пространств в реальном времени // Автоматизация и современные технологии. 2006 №5 С 27-34

Другие публикации

2 Минаев ЕВ Структуры данных для представления открытых пространств и визуализации в реальном времени. // Научные труды VIII международной научно-практической конференции «Фундаментальные и прикладные проблемы приборостроения, информатики и экономики Сочи, 2005»-M МГАПИ, 2005 С 133-137

3 Минаев Е В. Сравнение способов реализации рендеринга полигональной модели в OpenGL на примере регулярной карты высот ландшафта // Вестник МГУП 2007 №3 С 79-83.

4 Минаев Е.В Параметризация систем трёхмерной визуализации // Вестник МГУПИ. Серия Естественные и технические науки 2007 №8 С 2024.

5 Минаев Е В Критерии выбора интерактивной системы трёхмерной визуализации //Вестник молодых учёных МГУПИ 2007 №2. С.32-36

6 Минаев Е В Электрокарта Свидетельство об официальной регистрации программы для ЭВМ № 2008614506 // Федеральная служба по интеллектуальной собственности, патентам и товарным знакам — 19 09 2008

Подписано в печать 02 10 08 г Формат 60x84/16 Уел печ л 1.05 Тираж 100 экз Заказ №286/263 Отпечатано в РИО Московского государственного университета печати 127550, Москва, ул Прянишникова,2а

ВВЕДЕНИЕ.

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

Состояние проблемы.

Объект исследования.

Цель работы.

Научная новизна.

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

Основные результаты,' выносимые на защиту.

Апробация работы.

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

Описание интерактивной системы визуализации.12

Основные виды систем визуализации.22

Критерии выбора системы визуализации.25

Проблемы визуализации открытых пространств.30

Классификация методов увеличения скорости визуализации.36

Заключение.50

Глава 2. Описание предлагаемого алгоритма визуализации и используемых структур данных

52

Введение.52

Используемые принципы повышения временной эффективности алгоритма визуализации

52

Общий алгоритм визуализации открытых пространств.77

Структуры данных, используемые в предлагаемом алгоритме.86

Заключение.91

Глава 3. Оценка ресурсной эффективности предлагаемого и базового алюритмов.94

Введение.94

Определение базового алгоритма.95

Оценка ресурсной эффективности базового алгоритма визуализации открытого пространства.102

Оценка ресурсной эффективности разработанного алгоритма визуализации открытого пространства.111

Ресурсная эффективность улучшений.116

Заключение.126

Глава 4. Программная реализация разработанного алгоритма визуализации открытых пространств, его применение и эксплуатация.129

Введение.129

Проблемы реализации высокоскоростного рендеринга для систем реального времени. 129

Программная реализация алгоритма в рамках системы визуализации.132

Экспериментальная оценка ресурсной эффективности предлагаемого алгоритма.137

Использование разработанной системы визуализации для интерактивной картографической системы Е1ес1гошар.143

Заключение.145

Заключение.148

Литература.150

ВВЕДЕНИЕ

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

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

Интерактивные системы визуализации трёхмерных сцен являются одной из самых широких областей применения компьютерной графики. К ним относятся системы визуализации абстрактных данных, системы визуализации результатов научных экспериментов [70,71,74,75,100], геоинформационные системы [71], компьютерная томография, САПР [28,34], тренажёры имитирования реальной техники, системы виртуальной реальности (УК-системы) [23,29], компьютерные игры, графические оболочки файловых систем [27] и других программ [22,38]. В системах такого рода важнейшей характеристикой качества является временная эффективность процесса отображения информации в зависимости от объёма визуализируемых данных. Отображаемая информация обычно представляет собой трёхмерную сцену, состоящую из множества различных объектов. В целях повышения качества этого типа программного обеспечения, разработчики идут на нетривиальные способы увеличения временной эффективности алгоритмов визуализации применительно к конкретным отображаемым данным. Эти алгоритмы базируются на методах компьютерной геометрии и машинной графики. Их задачами является отсечение невидимых частей и отображение нужных объектов оптимальным образом. Для выполнения этих операций используются специальные структуры данных для представления трёхмерных сцен в памяти компьютера. Многообразие практических ситуаций возникающих при визуализации различного рода сцен обуславливает необходимость разработки дополнительных алгоритмических решений и новых структур данных для обеспечения возможности использования этих сцен, а также улучшения временных показателей визуализации.

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

Состояние проблемы

Для открытых пространств в настоящее время разработано множество подходов к трёхмерной визуализации, в исследование и развитие которых внесли вклад множество людей и компаний по всему миру. Среди них фундаментальными научными трудами в области интерактивной трёхмерной визуализации отметились: Д. Колер, П. Линдстром, Т. Ульрих, М. Дучейнеу, С. Роджер, X. Хоуп, В.Д. Бор, С.М. Нелли, Г. Корпс, Р. Паджарола, А. Грин, Л. Касл, Д. Блоу, В. Эванс, Г. Тонсенд, Ю. Зао, Д. Джоу, Д. Ши, В. Пакуси, X. Хакл, П. Сигнони, Ф. Гановели, Э. Гобети, Ф. Мартон, Ф. Пончио, Р. Скопинго и др. Кроме того, существует огромное количество научных центров, занимающихся компьютерной графикой, которые уделяют внимание проблемам интерактивной визуализации открытых пространств.

В настоящее время существует множество представлений открытых пространств и эффективных методов визуализации многих классов сцен и объектов. Активно ведётся разработка структур данных и алгоритмов визуализации поддерживающих многомасштабность (ЬСЮ — уровни детализации). Большой интерес представляют алгоритмы многомасштабного видозависимого рендеринга. Наиболее существенными проблемами алгоритмов визуализации открытых пространств являются: отсечение невидимых частей сцены, представление больших объёмов визуализируемых данных в памяти компьютера, выбор или построение оптимального уровня детализации для отображаемых объектов, обеспечение непрерывности поверхностей для объектов с полигональной структурой, текстурирование получаемых поверхностей, построение оптимальной последовательности видимых объектов для эффективного использования аппаратного ускорения, оптимизация программных решений под современные аппаратные средства.

На сегодняшний день остаются актуальными многие проблемы трёхмерной визуализации открытых пространств в реальном времени [21,30].

Для представления больших сцен в памяти компьютера не разработано однозначно эффективных структур данных позволяющих визуализировать пространства различного рода в реальном времени. Это связано с трудностью достижения компромисса между способом сжатия данных сцены и их эффективной организацией для использования аппаратного ускорения визуализации. Прежде всего, это замечание относится к ландшафтам. Однако для определённых типов объектов разработаны частные решения [26,32,65,84,86,121], но они не позволяют работать с фиксированным уровнем детализации. Кроме того, существуют системы визуализации, реализующие подгрузку новых участков цены из файлов. Не опубликовано общих алгоритмов визуализации сцены в целом, с акцентом на взаимодействие различных этапов рендеринга с общей структурой данных. Например, мало внимания уделяется вопросам построения оптимальной последовательности видимых объектов для эффективного использования аппаратного ускорения.

Объект исследования

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

Здесь под интерактивностью подразумевается возможность визуализации сцены в режиме реального времени, причём частота выводимых кадров (FPS) итогового двумерного изображения сцены должна быть не менее частоты кадровой развёртки монитора. При сохранении такого уровня временной эффективности, должен обеспечиваться оптимальный уровень качества картинки. Кроме того, структура данных сцены должна занимать объём памяти не больше определённого размера, чтобы сделать возможным визуализацию этой сцены на персональном компьютере.

В работе рассматриваются только проекционные методы синтеза изображений, которые, единственные на сегодняшний день, обеспечивают достаточную скорость для интерактивного режима. Рассматриваются только явно заданные данные. В тексте не рассматриваются различные параметрические и процедурные представления [26,32], так как их особенности (сложность вычислений, отсутствие аппаратной поддержки) делает затруднительным их использование для визуализации в реальном времени. Также, не рассматриваются модели сцен на основе изображений (IBMR) [25,107] и точечные представления (point sample).

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

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

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

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

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

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

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

Апробация работы

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

Заключение

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

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

В диссертации получены следующие основные результаты:

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

2. Разработаны структура данных и алгоритм визуализации для сверхбольших пространств. Предлагаемая структура данных использует принципы, показанные в алгоритме СИипкеёЬОО и осуществляет поддержку визуализации множества объектов наряду с ландшафтом.

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

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

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

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

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

1. Эйнджел Э. Интерактивная компьютерная графика. Вводный курс на базе OpenGL™ . Пер. с англ. — М.: Издательский дом «Вильяме», 2001.

2. Херн Д., Бейкер М. Паулин. Компьютерная графика и стандарты OpenGL. Пер. с англ. — М.: Издательский дом «Вильяме», 2005.

3. Никулин Е.А. Компьютерная геометрия и алгоритмы машинной графики. — СПб.: «БХВ Петербург», 2005.

4. Гайдуков С. OpenGL профессиональное программирование трехмерной графики на С++. СПб.: «БХВ Петербург», 2004.

5. Снук Г. 3D ландшафты в реальном времени на С++ и DirectX9. Пер. с англ. М.: Кудиц - Образ, 2006.

6. Семенов B.JL, Крылов П.Б., Морозов C.B., Роминов М.Г., Тарлапан O.JI. Объектно-ориентированная методология разработки интегрированных приложений моделирования и визуализации. // ( http://www.ispras.ru/~3d/koi/problerns/math/frarnework.htrn).

7. Игнатенко А. Геометрической моделирование сплошных тел. // (http:// graphicscs.msu.su/ru/library/3d/solidmodelling/index.html).

8. Вирт Н. Алгоритмы и структуры данных: Пер. с англ. — М.: Мир, 1989.

9. Бачик М. Создание больших открытых пространств: Быстрое отсечение невидимых поверхностей для открытых уровней. // (http://dev.dtf.ru/articles/ read.php?id=126).

10. Серба А. Ландшафт шаг за шагом. // (http://www.gamedev.ru/coding/20208.shtml)

11. П.Кузнецов А. В. Программирование трёхмерной графики с использованием библиотеки OpenGL под ОС Windows. // fhttp://www.uran.donetsk.ua/~masters/2001/ vti/ kuznetsov/diss/lib/ogl/index.htm).

12. Баяковский Ю., Игнатенко А., Фролов А. Графическая библиотека OpenGL. Лаборатория компьютерной графики при ВМиК МГУ. // (http://rsdn.ru/article/ opengl/ ogltut2.xml).

13. BSP-дерево и его применение в трехмерной графике. // (http://u3d.agava.ru/doc/theory/bspbase.shtml).

14. Бачик М. Создание больших открытых пространств: Быстрое отсечение невидимых поверхностей для открытых уровней. // (http://dev.dtf.ru/articles/ read.php?id=126).

15. JM. Отсечение вне области просмотра. // (http://www.gamedev.chat.ru/ articles/a0028.html).

16. Game Engine своими руками #2: Quad-деревья. // (http://gamemaker. web servi s. ru/articles/engine/d2 .htm).

17. Попов П. Физическое моделирование воды. // (http://www.gamedev.ru/articles/? id=30119).

18. BoogMan. Частицы. // (http.7/www.gamedev.ru/articles/?id=30103).

19. Буч Г. Объектно-ориентированный анализ и проектирование с примерами приложений на С++. Пер. с англ. — Rational Санта-Клара, Калифорния.

20. Жирков А., Паршин А. Адаптивный рендеринг трехмерных сцен на основе иерархических ячеек. // М.: Лаборатория Компьютерной Графики факультета ВМиК МГУ.

21. Банковский Ю.М., Галактионов В.А. О некоторых фундаментальных проблемах компьютерной (машинной) графики. // Институт Прикладной Математики (ИПМ) им. М.В.Келдыша РАН.

22. Конушин A.C. Алгоритмы построения трехмерных компьютерных моделей реальных объектов для систем виртуальной реальности.

23. Чепурнова Е.В., Игнатенко A.B. Doc3D: Система трёхмерной визуализации архитектуры программных систем. М.: Московский государственный университет им. М.В. Ломоносова.

24. Игнатенко А. Введение в методы переменного уровня детализации полигональных сеток.

25. Кугушев Е.И., Зуева Е.Ю. Определение формы и движения объекта по последовательности изображений // М.: Труды конференции Графикон'92. 1992.

26. Галактионов В.А., Барладян Б.Х., Зуева Е.Ю., Кугушев Е.И. Параметрические модели трехмерных объектов и их использование для реконструкции сцен // "Открытые системы", № 5, 1995.

27. Васильев В.Р., Волобой А.Г., Вьюкова Н.И., Галактионов В.А. Контекстная визуализация пространственных данных // Препринт ИПМ им. М.В. Келдыша РАН, № 56, 2004.

28. Волобой А.Г., Галактионов В.А. Машинная графика в задачах автоматизированного проектирования // Препринт ИПМ им. М.В. Келдыша РАН, № 104, 2005.

29. Конушин A.C. Алгоритмы построения трехмерных компьютерных моделей реальных объектов для систем виртуальной реальности // М.: Автореферат диссертации на соискание ученой степени кандидата физико-математических наук, ИПМ им. М.В. Келдыша РАН, 2005.

30. Баяковский Ю.М., Галактионов В.А. Современные проблемы компьютерной (машинной) графики // Сб. "Будущее прикладной математики". Лекции для молодых исследователей. М.: Едиториал УРСС. 2005.

31. Конушин A.C. Система построения трехмерных моделей реальных объектов по последовательности изображений // Труды международной конференции студентов и аспирантов по фундаментальным наукам "Ломоносов 2005", 2005.

32. Лисицин Е., Конушин А. Подгонка параметрических моделей к облакам трехмерных точек. // Труды 16-ой международной конференции по компьютерной графике и ее приложениям ГрафиКон'2006, Новосибирск. 2006.

33. Волобой А.Г., Галактионов В.А., Копылов Э.А., Шапиро Л.З. Моделирование естественного дневного освещения, задаваемого изображением с большим динамическим диапазоном // "Программирование", № 5, 2006.

34. Волобой А.Г., Галактионов В.А. Машинная графика в задачах автоматизированного проектирования. // "Информационные технологии в проектировании и производстве", № 1, 2006.

35. Игнатенко А. Методы представления дискретных трехмерных данных. // Интернет-журнал. 2003.

36. Тисевич И. Рельефное текстурирование. // Интернет-журнал. 2005.

37. Сенюкова О., Анна Дегтярева А. Системы моделирования трехмерных объектов. // Интернет-журнал. 2006.

38. Борисов В., Игнатенко А. Системы трехмерной визуализации данных // Интернет-журнал. 2006.

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

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

41. Соловьёв С.А., Марков Н. Г. Сравнительный анализ алгоритмов разбиения трехмерных сцен на деревья графических примитивов. // Интернет-журнал. 2005.

42. Шикин Е.В., Боресков A.B. Компьютерная графика. Динамика, реалистические изображения. М.: «Диалог-Мифи», 1995.

43. Павлидис Т. Алгоритмы машинной графики и обработка изображений. М.: Радио и связь, 1988.

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

45. Роджере Дж., Адаме Дж. Математические основы машинной графики: пер. с англ. -М.: Машиностроение, 1980. 240 е., ил.

46. Томпсон Н. Секреты программирования трехмерной графики для Windows 95. Пер. с англ. — СПб.: Питер, 1997.

47. Тихомиров Ю. В. Программирование трехмерной графики. СПб.: «БХВ-Петербург», 2001.

48. Скворцов А. В., Костюк Ю. JI. Эффективные алгоритмы построения триангуляции Делоне // Гсоинформатика. Теория и практика. Выпуск 1. Томск: Издательство Томского Университета, 1998.

49. Фукс A. JI. Предварительная обработка набора точек при построении триангуляции Делоне // Геоинформатика. Теория и практика. Выпуск 1. Томск: Издательство Томского Университета, 1998.

50. Башков Е.А., Пауков Д.П. Триангуляция: Итеративные алгоритмы построения триангуляции. — Сборник трудов магистрантов Донецкого национального технического университета. Выпуск 2. — Донецк, ДонНТУ Министерства образования и науки Украины, 2003.

51. Аммерал Л. Принципы программирования в машинной графике. Пер. с англ. — М.: "Сол Систем", 1992.

52. Иванов В.П., Батраков A.C. Трехмерная компьютерная графика /Под ред. Г.М.Полищука. — М.: Радио и связь, 1995.

53. Хилл Ф. Open GL. Программирование компьютерной графики. Для профессионалов. Пер. с англ.— СПб.: Изд.дом «Питер», 2002.

54. Юань Фень. Программирование графики для Windows. Пер. с англ. — СПб.: Изд.дом «Питер», 2002.

55. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. Пер. с англ. — М.: МНЦМО, 1999.

56. Абламейко C.B., Лагуновский Д.М. Обработка изображений: технология, методы, применение. Мн.: Амалфея, 2000.

57. Форсайт, Дэвид А., Понс, Жан. Компьютерное зрение. Современный подход. : Пер. с англ. — М.: Изд. дом "Вильяме", 2004.

58. Рост Р. OpenGL. Трехмерная графика и язык программирования шейдеров.: Пер. с англ. — СПб: Изд.дом «Питер», 1-е издание, 2005.

59. Евченко А.И. OpenGL и DirectX: программирование графики. — СПб: Изд.дом «Питер», 1-е издание, 2006.

60. ИГрайнер Д., By M., Нейдер Дж., Девис T. OpenGL. Руководство по программированию. Библиотека программиста. 4-е изд.: Пер. с англ. — СПб: Изд.дом «Питер», 2006.

61. Боресков A.B. Расширения OpenGL. СПб.: «БХВ Петербург», 2005.

62. Боресков A.B. Графика трехмерной игры па основе OpenGL. M.: (Диалог Мифи», 2004.

63. Шрайнер Д. OpenGL. Официальный справочник: Пер. с апгл. — М: Торгово — издательский дом «DiaSoft», 2002.

64. Крафтов M.B. Использование мегатекстур (megatexture, clipmaps). // (http://www.gamedcv.ru/codc/articles/Mcgatexture').

65. Андерсон M. Фрактальные ландшафты. // (http://www.rlgclub.ru/pmwiki.php? n=Main.ArticlesDevFractalLandscapes)

66. Махоней Д. Большие изображения малые размеры пакетов. // (http://www.render.ru/books/showbook.php7book id—21

67. Харбунои П. Simplicity. Ландшафты без quadtree и octree. // (h ttp :// www, gamede v. ru/articles/? id 30130)

68. Милтри Д. Треугольная сетка с множественной детализацией. // (http://blender3d.org.ua/cgi-bin/def.pl7nt/192')

69. Байских Ю. Rendering: Теория. // (http://www.render.ru/books/show book.php? book id=52n

70. Мельман C.B.,Бобков В.А. Система визуализации пространственных полей синоптический объектов. Институт автоматики и процессов управления. Владивосток. //GraphiCon'2007.

71. Аниканов A.A., Потий O.A. Проблемы и подходы к решению задачи визуализации данных о течениях в природных объектах. //«Научная визуализация в прикладных задачах». Изд. МГУ. 2003. с. 20-22.

72. Шевцов М.Ю., Долговесов Б.С. Система объемной визуализации реального времени на базе стандартного графического акселератора. Институт Автоматики и Электрометрии Новосибирский Государственный Университет. //GraphiCon'2005, с. 401-405.

73. Ягель. Рендеринг объемов в реальном времени. //Открытые системы, #05, 1996.

74. Шевцов М.Ю. Объемная визуализация научных данных на базе VolumePro 1000. //Труды конференции-конкурса «Технологии Microsoft в информатике и программировании». 2004г. стр. 68-70. Диплом первой степени.

75. Мельман C.B., Гриняк Т.М. "Анимация трехмерных стационарных векторных полей" //Электронный журнал "Исследовано в России", 202, стр 2149-2155, 2004 г. (http://zhurnal.ape.relarn.ru/articles/2004/202.pdf)

76. Милов А.Н. Особенности построения архитектуры масштабируемой графической системы стандарта OpenGL на основе ЦПОС. Научно-производственный центр «Электронные Вычислительно-Информационные Системы», Москва. //GraphiCon'2007.

77. Дерябин Н.Б., Денисов Е.Ю. Объектно-ориентированная инфраструктура систем компьютерной графики. Институт прикладной математики им. М.В.Келдыша РАН, Москва. //GraphiCon'2007.

78. Волобой А.Г., Галактионов В.А. Машинная графика в задачах автоматизированного проектирования. "Информационные технологии в проектировании и производстве", № 1, 2006, с. 64-73.

79. Юсов Е., Турлапов В. Динамическая оптимизация ландшафта на базе преобразования Хаара и квадродерсва вершин. Нижегородский государственный университет им. Н.И.Лобачевского, Нижний Новгород. //GraphiCon'2006.

80. Елыков H.A., Белаго И.В., С.А. Кузиковский, Некрасов Ю.Ю. Методы непрерывной детализации террэйна. Материалы конф. по комп. граф. и визуализации -GraphiCon'2002, Н.Новгород, 16-21 сент. 2002.

81. Переберин A.B. Многомасштабньтс методы синтеза и анализа изображений. Диссертация на соискание ученой степени канд. физ.-мат. наук, Институт прикладной математики им. М.В. Келдыша, Москва-2002.

82. Жирков А., Паршин А. Адаптивный рендеринг трехмерных сцен на основе иерархических ячеек. Лаборатория Компьютерной Графики факультета ВМиК МГУ. //GraphiCon'2005.

83. Ким П.А. Один подход к визуализации масштабируемой модели рельефа. Институт Вычислительной Математики и Математической Геофизики, СО РАН, Новосибирск. //GraphiCon'2006.

84. Елыков Н. А., Белаго И. В., Кузиковский С.А. Метод непрерывной детализации трехмерных моделей растительности. Институт Автоматики и Электрометрии СО РАН Новосибирск. //GraphiCon'2006.

85. Заугольнова Е.В., Юрин Д.В. Алгоритм уточнения предварительной сегментации изображений с нечеткими, слабоконтрастными границами двумерных объектов. ВМиК, Московский государственный университет. //GraphiCon'2006.

86. Ульянов М.В. РЕСУРСНАЯ ЭФФЕКТИВНОСТЬ ВЫЧИСЛИТЕЛЬНЫХ АЛГОРИТМОВ: ТЕОРИЯ И ПРИМЕНЕНИЕ. Дис. док.техп.паук.-М.,2005.

87. Drebin,R.A., Carpenter,L., and Hanrahan,P., Volume Rendering //Computer Graphics, 22(4):65-74, August 1988.

88. Xia, J.C., El-Sana, J., Varshney, A., Adaptive Real-Time Level-of-Detail- Based Rendering for Polygonal Models. IEEE Trans, on Visualization and Computer Graphics, 1997.

89. Zhang H. and Ho K. Fast Backface Culling Using Normal Masks. Proc. Symposium on Interactive 3D Graphics, 1997.

90. Foley J. D., A. van Dam, Feiner S. К., Hughes J. H., Computer graphics: principles and practice. 2nd ed. in C. Addison-Wesley, 1996.

91. Policarpo F., Oliveira M, Comba J. Real-Time Relief Mapping on Arbitrary Polygonal Surfaces. // ACM SIGGRAPH 2005 Symposium on Interactive 3D Graphics and Games, 2005.

92. Lindstrom P., Koller D., Ribarsky, W., Hodges L., Faust N., Turner G., Real-Time Continuous Level of Detail Rendering of Height Fields. // (http://www.cc.gatech.edu/gvu/ people/ peter.lindstrom/papers/siggraph96).

93. Hoppe H. Smooth View-Dependent Level-of-Detail Control and its Application to Terrain Rendering. // (http://www.research.microsoft.com/~hoppe).

94. Snook G. Simplifed Terrain Using Interlocking Tiles. // Game Programming Gems 2. Charles River Media, Inc., 2001.

95. Farin G. Curves and surfaces for computer aided geometric design: a practical guide. 4th ed. ACADEMIC PRESS 1997.

96. Koller D., Lindstrom P. Real-Time, Continuous LOD Rendering of Height Fields. 1996.

97. Turner B. Real-Time Dynamic Level of Detail Terrain Rendering with ROAM. 2000.

98. Ruttger S., Heidrich W., Slusallek Ph., Seidel H-P. Real-Time Generation of Continuous Levels of Detail for Height. // University of Erlangen-Nuremberg. 1998.

99. Losasso F., Hoppe H. Geometry clipmaps: Terrain rendering using nested regular grids. // Siggraph. Stanford, Microsoft. 2004.

100. Nielson G., Hagen H., MullerH. Scientific visualization: overviews, methodologies and techniques. IEEE CS 1997.

101. Mark de Berg, Marc van Kreveld, Marc Overmars, Otfried Schwarzkopf Computational Geometry: algorithms and applications. 2nd edition. Springer-Verlag, 2000.

102. Dachsbacher C., Stamminger M. Rendering Procedural Terrain by Geometry Image Warping. // Eurographics. University of Erlangen-Nuremberg. 2004.

103. Humphrey B. Octree tutorial. // (http://gamemaker.webservis.ru/articles/Octree/ Octree.htm).

104. Larsen B.D., Christensen N.J. Real-time Terrain Rendering using Smooth Hardware Optimized Level of Detail. // Technical University of Denmark.

105. Pagarolo R. Overview of Quadtree-based Terrain Triangulation and Visualization. // (http:// www.ifi.unizh.ch/vmml/admin/upload/UCI-ICS-02-01.pdf).

106. Turner B., Real-Time Dynamic Level of Detail Terrain Rendering with ROAM. // ('http://www.research.microsoft.com/~hoppe).

107. Levkovich-Maslyuk L., Ignatenko A., Zhirkov A., Konushin A., In Kyu Park, Member, IEEE, Mahnjin Han, Member, IEEE, and Bayakovski Yu. Depth Image-Based Representation and Compression for Static and Animated 3-D Objects // Proc. IEEE

108. TRANSACTIONS ON CIRCUITS AND SYSTEMS FOR VIDEO TECHNOLOGY, Vol. 14, No. 7. 2004.

109. Kilgard M.J. An OpenGL Toolkit. The X Journal, SIGS Publications, November/December 1994.

110. Alekseev A.K., Bondarev A.E., Molotilin Y.A. On inverse problems for 3D time-dependent free convection heat transfer // Proc. National Heat Transfer Conference, Vol.10, 1995.

111. Yegor Yermack. BSP—дерево и его применение в трехмерной графике. // (http://www.xdev.ru/dxfip/rgd articlesr.asp?s=unsortedzone&art=uz 0054 bsptree 1).

112. Vladislav I. Suglobov Appearance-Preserving Terrain Simplification. Proc. of the Conf. on Сотр. Graph, and Visual. GraphiCon'2000, Moscow, August 28 - September 2, 2000.

113. Markus H. Gross, Roger Gatti, and Oliver G. Staadt. Fast multiresolution surface meshing. In Proc. of 14th International Conf. on Data Engineering, ICDE'98, pp. 550-557. IEEE, 1998.

114. Gross M.H., Staadt O.G., Gatti R. Efficient Triangular Surface Approximations Using Wavelets and Quadtree Data Structures. IEEE Trans, on Visualization and Computer Graphics. Vol. 2, No. 2, June 1996, pp. 130-143.

115. Duchaineau M., Wolinski M., Sigeti D., Miller M., Aldrich C. and Mineev-Weinstein M. ROAMing Terrain: Real-time Optimally Adapting Meshes. // (http://www.llnl.gov/graphics/ ROAM).

116. David Luebke. A developer's survey of polygonal simplification algorithms. IEEE Computer Graphics & Applications, 21(3):24-35, May/June 2001.

117. Hcckbert P., Garland M. Survey of polygonal surface simplification algorithms. SIGGRAPH 97 Course Notes 25, 1997.

118. Garland M., Heckbert Paul S. Fast polygonal approximation of terrains and height fields. Technical Report cmu-cs-95-181, School of Computer Science, Carnegie Mellon University, Pittsburgh, PA, 1995.

119. Kurt Pelzer, Piranha Bytes. "Rendering Countless Blades of Waving Grass","GPU Gems ", Addison Wesley, 2004, 107-121.47.67.

120. T. Optimized View Frustum Culling Algorithms. Chalmers University of Technology, 1999

121. Ulrich T. Chunked LOD: Rendering Massive Terrains using Chunked Level of Detail Control. // (http://tulrich.com/geekstuff/chunklod.htmn

122. Минаев E. Алгоритм визуализации открытых пространств в реальном времени. // Автоматизация и Современные Технологии: Ежемесячный межотраслевой научно-технический журнал / Под редакцией B.JI. Белоусова М., 2006, №5. С.27-34.

123. Минаев Е. Структуры данных для представления открытых пространств и визуализации в реальном времени. // Научные труды VIII международной научно-практической конференции М.: МГАПИ, 2005. С. 133-137.

124. Минаев Е. Сравнение способов реализации рендеринга полигональной модели в OpenGL на примере регулярной карты высот ландшафта. // Вестник МГУП: Научно-технический журнал М.: МГУП, 2007, №3. С.79-83.

125. Минаев Е. Параметризация систем трёхмерной визуализации. // Вестник МГУПИ -М.: МГУПИ, 2007, №8. С.20-24.

126. Минаев Е. Критерии выбора интерактивной системы трёхмерной визуализации. // Вестник молодых учёных М.: МГУПИ, 2007, №2.