Введение к работе
Актуальность темы диссертационной работы. Круг задач компьютерной графики постоянно расширяется в связи с непрерывным ростом аппаратных возможностей современных компьютеров По этой причине множество ранее не рассматриваемых проблем визуализации стали актуальными Вследствие возросших требований к современным системам визуализации, разрабатываются новейшие алгоритмы для решения возникающих задач, ориентированные на современное аппаратное обеспечение Большинство актуальных в настоящее время проблем визуализации связано с необходимостью хранения и отображения огромных объемов данных за минимальное время Обычно такие задачи решаются посредством специальных вычислительных комплексов, однако, разрабатывая новые алгоритмы хранения и отображения информации, представляется возможным перенести часть этих задач на персональные компьютеры
Интерактивные системы визуализации трехмерных сцен являются одной из самых широких областей применения компьютерной графики К ним относятся системы визуализации абстрактных данных, системы визуализации результатов научных экспериментов, геоинформационные системы, компьютерная томография, САПР, тренажёры имитирования реальной техники, системы виртуальной реальности (VR-системы), компьютерные игры, графические оболочки файловых систем и других программ В системах такого рода важнейшей характеристикой качества является временная эффективность процесса отображения информации в зависимости от объема визуализируемых данных Отображаемая информация обычно представляет собой трехмерную сцену, состоящую из множества различных объектов В целях повышения качества этого типа программного обеспечения, разработчики идут на нетривиальные способы улучшения временной эффективности алгоритмов визуализации применительно к конкретным отображаемым данным Эти алгоритмы базируются на методах компьютерной геометрии и машинной графики Их задачами является отсечение невидимых частей и отображение нужных объектов оптимальным образом Для выполнения этих операций используются специальные структуры
4 данных для представления трехмерных сцен в памяти компьютера Многообразие практических ситуаций возникающих при визуализации различного рода сцен обуславливает необходимость разработки дополнительных алгоритмических решений и новых структур данных для обеспечения возможности использования этих сцен, а также улучшения временных показателей визуализации
Открытые пространства являются одним из наиболее часто встречающихся типов трехмерных сцен в интерактивных программных системах В связи с этим, структуры данных и алгоритмы для этого типа сцен требуют к себе особого внимания Для отображения ландшафтов в открытых пространствах в основном используется технология уровней детализации, позволяющая обеспечить различные вариации между временной эффективностью и качеством получаемого изображения, и возможность отсечения невидимых частей Однако для представления всего многообразия типов объектов трехмерной сцены не существует абсолютно-универсальных структур данных и алгоритмов, обеспечивающих максимальную эффективность Общая производительность системы визуализации, как правило, складывается из совокупности алгоритмов отсечения невидимых частей и оптимизации конечной модели выводимых объектов для окончательной визуализации Таким образом, разработка дополнительных методов увеличения временной эффективности процесса визуализации открытых пространств, базирующихся на специальных структурах данных, является актуальной проблемой
Для открытых пространств разработано множество подходов к трехмерной визуализации, в исследование и развитие которых внесли вклад множество людей и компаний по всему миру Среди них, фундаментальные научные труды в области интерактивной трехмерной визуализации принадлежат следующим уче'ным Д Колер, П Линдстром, Т Ульрих, М Дучейнеу, С Роджер, X Хоуп, В Д Бор, С М Нелли, Г Корпс, Р Паджарола, А Грин, Л Касл, Д Блоу, В Эванс, Г Тонсенд, Ю Зао, Д Джоу, Д Ши, В Пакуси, X Хакл, П Сигнони, Ф Гановели, Э Гобети, Ф Мартон, Ф Пончио, Р. Скопинго и др Кроме того, существует огромное количество научных центров, занимающихся компьютерной
5 графикой, которые уделяют внимание проблемам интерактивной визуализации открытых пространств
В настоящее время существует множество представлений открытых пространств и эффективных методов визуализации многих классов сцен и объектов Активно ведется разработка структур данных и алгоритмов визуализации поддерживающих многомасштабность (LOD — уровни детализации) Большой интерес представляют алгоритмы многомасштабного видозависимого рендеринга Наиболее существенными проблемами алгоритмов визуализации открытых пространств являются отсечение невидимых частей сцены, представление больших объемов визуализируемых данных в памяти компьютера, выбор или построение оптимального уровня детализации для отображаемых объектов, обеспечение непрерывности поверхностей для объектов с полигональной структурой, текстурирование получаемых поверхностей, построение оптимальной последовательности видимых объектов для эффективного использования аппаратного ускорения, оптимизация программных решений под современные аппаратные средства
На сегодняшний день остаются актуальными многие проблемы трехмерной визуализации открытых пространств в реальном времени Для представления больших сцен в памяти компьютера не разработано однозначно эффективных структур данных, позволяющих визуализировать пространства различного рода в реальном времени Это связано с трудностью достижения компромисса между способом сжатия данных сцены и их эффективной организацией для использования аппаратного ускорения визуализации Прежде всего, это замечание относится к ландшафтам Однако для определённых типов объектов разработаны частные решения, но они не позволяют работать с фиксированным уровнем детализации Кроме того, существуют системы визуализации, реализующие подгрузку новых участков цены из файлов Не опубликовано общих алгоритмов визуализации сцены в целом, с акцентом на взаимодействие различных этапов рендеринга с общей структурой данных Например, мало внимания уде-
6 ляется вопросам построения оптимальной последовательности видимых объектов для эффективного использования аппаратного ускорения
Объект и предмет исследования
Объектами исследования диссертационной работы являются структуры данных и алгоритмы трехмерной интерактивной визуализации открытых пространств, основой которых являются объекты полигонального типа
Здесь под интерактивностью подразумевается возможность визуализации сцены в режиме реального времени, причем частота выводимых кадров (FPS) итогового двумерного изображения сцены должна быть не менее частоты кадровой развертки монитора При сохранении такого уровня временной эффективности, должен обеспечиваться оптимальный уровень качества картинки Кроме того, структура данных сцены должна занимать объем памяти не больше определённого размера, чтобы сделать возможным визуализацию этой сцены на персональном компьютере
В работе рассматриваются только проекционные методы синтеза изображений, которые, единственные на сегодняшний день, обеспечивают достаточную скорость для интерактивного режима. Рассматриваются только явно заданные данные. В работе не рассматриваются различные параметрические и процедурные представления, так как их особенности (сложность вычислений, отсутствие аппаратной поддержки) делает затруднительным их использование для визуализации в реальном времени Также, не рассматриваются модели сцен на основе изображений (IBMR) и точечные представления (point sample)
Цель и задачи работы. Целью работы является разработка структуры данных трёхмерной сцены и алгоритма визуализации, в совокупности повышающих ресурсную эффективность систем визуализации открытых пространств в режиме реального времени при оптимальном уровне качества отображаемой картинки на основе сравнительного анализа существующих методов визуализации открытых пространств Причем приоритетным критерием является временная эффективность
7 Научная новизна. Научная новизна диссертационной работы состоит в разработке
новой структуры данных трехмерной сцены, являющейся открытым пространством, ориентированной на визуализацию в реальном времени с использованием современных возможностей аппаратного ускорения,
алгоритма визуализации, использующего специальные структуры данных для увеличения ресурсной эффективности рендеринга всей сцены в целом,
методов представления различных типов объектов сцены для эффективной группировки и реалистичной визуализации в реальном времени
Практическая ценность работы. Практическая ценность результатов работы заключается в
1 Возможности решения, на основе полученных результатов, круга практических проблем и задач, связанных с повышением производительности интерактивных систем визуализации открытых пространств, в том числе
задачи отсечения невидимых частей сцены,
задачи выбора или построения оптимального уровня детализации для отображаемых объектов,
проблемы обеспечения связанности поверхностей полигонального типа на различных уровнях детализации,
задачи представления больших сцен в памяти компьютера ориентированных на эффективную визуализацию в реальном времени с использованием преимуществ аппаратного ускорения,
разработки структур данных и алгоритмов законченной визуализации всей сцены в целом, с оптимальным взаимодействием различных этапов рендеринга,
задачи построения оптимальной последовательности видимых объектов для эффективного использования аппаратного ускорения,
выбора наиболее эффективных способов рендеринга на уровне графического АРІ в соответствии с типом отображаемых объектов
8 2 Возможности построения программных продуктов на основе разработанных библиотек, поддерживающих предлагаемые в работе структуры данных и алгоритмы интерактивной визуализации открытых пространств. Основные результаты, выносимые на защиту
-
Структура данных трехмерной сцены, обеспечивающая достаточную ресурсную эффективность для системы реального времени, ориентированной на персональные компьютеры
-
Алгоритм интерактивной визуализации открытого пространства, базирующийся на специальной структуре данных трехмерной сцены и использующий аппаратное ускорение для повышения скорости рендеринга
Апробация. Основные положения и результаты диссертационной работы докладывались на VIII международной научно-практической конференции «Фундаментальные и прикладные проблемы приборостроения, информатики и экономики», а также на научных семинарах кафедры "Персональные компьютеры и сети" МГУПИ Результаты работы внедрены и используется в программном продукте Electromap для отображения географических карт в реальном времени
Публикации. Основные материалы диссертации опубликованы в пяти печатных работах, в том числе 1 статья из перечня ВАК, получено свидетельство о регистрации разработанных программных средств в Федеральной службе по интеллектуальной собственности (свидетельство № 2008614506 от 19 09 2008)
Структура работы. Диссертационная работа состоит из введения, четырёх глав, заключения, приложения и библиографического списка Основной текст диссертации изложен на 140 страницах, содержит 29 рисунков, 3 таблицы и библиографический список из 128 наименований
