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

0

1

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

Перков Антон Николаевич

РАЗРАБОТКА И ИССЛЕДОВАНИЕ МЕТОДОВ АДАПТИВНОГО СИНТЕЗА ИЗОБРАЖЕНИЙ РЕЛЬЕФОВ МЕСТНОСТИ

Специальность: 05.13.13 - Вычислительные машины, системы, комплексы и сети

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Санкт-Петербург - 1998

Работа выполнена в Санкт-Петербургском государственном электротехническом университете имени В.И.Ульянова (Ленина) .

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

кандидат технических наук, профессор Шмидт В.К. Официальные оппоненты:

доктор технических наук, профессор Новиков Г.И. кандидат технических наук, доцент Горячев Г.А.

Ведущая организация - ГНИКИ СКУ «Система»

Защита диссертации состоится « » 1998 г.

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

К 063.36.12 Санкт-Петербургского государственного электротехнического университета имени В.И.Ульянова (Ленина) по адресу: 197376, Санкт-Петербург, ул. Проф. Попова, 5.

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

Автореферат разослан "_" _' 1998 г.

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

Маркин А.С.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность проблемы

-Машинная"графика является одной из наиболее активно развивающихся направлений информатики. На сегодняшний день разработано множество универсальных и специализированных вычислительных систем, предназначенных для решения задачи визуализации. Особенный интерес представляют системы визуализации, работающие в реальном времени. Уже на начальной стадии развития средств машинной графики визуализация изображений использовалась для построения тренажеров. В качестве примеров можно привести имитатор полета ASUPT и Electronic Scene Generator фирмы General Electric, имитатор полета фирмы Singer/Link и др.

Главные проблемы вытекают из необходимости десятки раз в секунду выполнять расчет и вывод сотен тысяч точек изображения визуализируемой сцены. Большой объем данных и вычислений требуют применения высокопроизводительной, а, следовательно, дорогой технической базы. В настоящее время производительность персональных компьютеров, оснащенных ускорителями трехмерной графики, достигла достаточно высокоvo уровня (до 250 млн. пике./с и порядка нескольких сотен тысяч текстурированных треугольников в секунду), что позволяет строить тренажеры на базе серийных персональных компьютеров. Тем не менее, при сложности сцены порядка нескольких сотен тысяч треугольников все еще возникаю'? проблемы нехватки быстродействия. Похожие проблемы возникают и в специализированных вычислительных системах, построенных на основе более производительных процессоров, при повышении требований к качеству получаемого изображения, точности представления объектов и общему объему сцены. Эти проблемы можно решать либо наращиванием производительности аппаратуры, либо снижением нагрузки на аппаратную составляющую системы визуализации посредством адаптации процессов визуализации к конкретным текущим условиям. Примером адаптации к условиям наблюдения может служить учет пирамиды видимости при выборке данных для визуализации или при динамической коррекции

сцены в зависимости от расстояния до наблюдателя.

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

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

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

- классификация рельефов по способу представления информации при их описании с целью выделения характерных случаев;

- анализ эффективности применения различных способов представления информации о рельефах для адаптации выборки данных к параметрам наблюдения;

- анализ известных методов визуализации и разработка новых, применимых к различным классам рельефов;

- отыскание путей адаптации методов визуализации рельефов к конкретным параметрам наблюдения.

Основные методы исследования

Для решения поставленных задач применялись методы вычислительной геометрии и интерактивной машинной графики, мето-

ды проектирования программного обеспечения.

Научная новизна исследования

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

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

Практические результаты

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

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

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

4. Произведена оценка эффективности применения разработанных методов в различных условиях применения.

Апробация работы Основные положения диссертационной работы представлялись и обсуждались на 5-ой и 6-ой Международных Конференциях по Компьютерной Графике и Визуализации ГРАФИКОН (С.-Петербург, 1995 и 1996), 2-ой Международной конференции по применению компьютерных систем Applications of Computer Systems (Щецин, Польша, 1995), 10-ом Международном симпозиуме по вопросам высокопроизводительных компьютерных систем HPCS (От-

тава, Канада, 1996), а также на семинарах Центра Транспьютерных Технологий (ЦТТ) СПбГЭТУ (С.-Петербург, 1995 и 1996).

Публикации.

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

Структура и объем работа!. Диссертация состоит из введения, пяти разделов, заключения, списка литературы, включающего 80 наименований. Основная часть работы изложена на 143 страницах машинописного текста. Работа содержит 41 рисунок и 7 таблиц.

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

В первом разделе диссертационной работы дается обзор особенностей задачи визуализации рельефов. Под рельефом понимается непрерывная поверхность в Е3, которая является графиком функции двух аргументов z = Я(х, у), определенной на связанном подмножестве D плана ХУ, т.е., топографическая или 2,5D поверхность. Рассматриваются основные способы представления дискретных моделей рельефов: 1. Пусть задана правая декартова прямоугольная система ко-

flx е R (I е R ординат OXYZ. Заданы числа < , ■< „ и Lx е N,

[1Х > О \1У > 0

N, множества X = •Нп — 1 )lx

п е N п < Lv

X = (n - l)x.

е N

>, такие, что для любых х е X и у л < L I

е У определена функция высоты рельефа г = Нщ,(х, у). Множество опорных точек на плоскости Рпр = ХхУ образует прямоугольную решетку (ПР) . 2. Пусть задана правая декартова прямоугольная система ко-

fLx e R (iy e R ординат OXYZ. Заданы числа { , < , n s N;

\h:, > Q > 0 ---------

множество точек на плоскости, заданных парами координат Ртнс = lPu Pzr Рл! С XxY, где X -= [О, Lx) n R, Y [О, Ly) n R, рк = {хк, ук) \ к е [1, л] n N и функция высоты рельефа z = Нтнс{х, у), причем D (Ятнс) - Ртнс- Если на множестве точек Ртнс производится триангуляция дающая множество треугольников Ттнс = {tj, t2, tffl}, то множества Ртнс и Т„вс задают триангулированную нерегулярную сетку (ТИС).

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

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

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

Второй раздел посвящен разработке адаптивного метода синтеза изображений рельефа местности, представленного в виде ТНС.

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

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

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

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

- для связных вершин V = 16п;

- для связных ребер V = 15л + 61 - 18;

- для связных треугольников V = Юл + 71-14.

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

При визуализации дискретной модели рельефа минимальным выбираемым для визуализации элементом является треугольник. Следовательно, весь процесс выборки элементов рельефа для визуализации разделяется на две стадии:

- поиск стартового треугольника;

- последовательная выборка всех треугольников, находящихся в заданной области.

К последовательной выборке треугольников предъявляются следующие требования:

- полное покрытие заданной области выбранными треугольниками;

- недопустимость многократной выборки одного и того же треугольника;

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

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

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

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

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

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

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

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

-9В третьем разделе рассматривается гипертриангуляция (ГиТ) как эффективный^ способ представления..рельефа, с муль--тиразрешением (Ми1Ь1гезо1иЬ1оп) . Представление рельефа с мультиразрешением предоставляет возможность адаптации отношения «точность представления» / «объем данных» к расстоянию от наблюдателя, что способствует разгрузке графического конвейера. ГиТ была предложена группой итальянских математиков в качестве представления рельефа, обеспечивающего в реальном времени выборку треугольников рельефа с переменной погрешностью. Однако при этом рассматривалась лишь полная выборка треугольников, покрывающих всю область определения дискретной модели неокрашенного рельефа, без учета параметров наблюдения.

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

- анализ влияния наличия окраски рельефа на процесс формирования ГиТ;

- анализ принципиальной возможности применения для ГиТ адаптивного волнового метода выборки треугольников, предложенного для ТНС со связными элементами;

- анализ корректности применения для Х'и'Г волнового метода с точки зрения непрерывности и однозначности покрытия заданной области выбираемыми треугольниками.

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

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

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

состоит в строгой упорядоченности извлечения треугольников из стека по степени удаления от точки наблюдения и, соответственно, по степени детализации, что позволяет точно сохранять направление распространения волны просмотра и избежать «завихрений», приводящих к неоднозначному покрытию просматриваемой области. Общая трудоемкость этого алгоритма оценивается как O(nlogn), - где п - количество треугольников на выходе.

При смене уровня детализации представления рельефа по мере удаления от точки наблюдения в качестве целевой функции выбирается, как правило, погрешность представления высоты рельефа е = I h„ - hyI, где ha - высота для представления рельефа с максимальной детализацией, а hy - высота для упрощенного представления рельефа. Автором диссертационной работы было предложено модифицировать целевую функцию таким образом, чтобы при смене уровня детализации учитывалась и погрешность представления границ окрашенных областей.

Четвертый раздел посвящен разработке эффективных методов работы с рельефами, представленными в виде прямоугольной решетки (ПР).

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

- отсутствие необходимости модификации исходного представления данных;

- простота преобразования исходных данных (матрица высот + матрица окраски) к виду, воспринимаемому графическим конвейером (список вершин, список полигонов);

- малый объем памяти, необходимой для хранения промежуточных данных (только две строки точек, попадающих в видимую область);

- возможность адаптации направления сканирования к направлению взгляда наблюдателя с целью обеспечения заданного

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

1 =

шах

/" \

/ I

+ 1, где

^1)5 у г

(р - неличина горизонтального сектора обзора;

~ максимальная допустимая глубина изображения; Хтах - ширина окна вывода изображения; ^ - фокусное расстояние; I - шаг ПР.

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

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

2

т + ^ Ьд<р < N , где

N - предельное количество визуализируемых треугольников; т - количество уровней детализации;

~~ максимальная допустимая глубина изображения; (р - величина горизонтального сектора обзора.

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

- количество пикселей к, необходимое для представления одной ячейки ПР на границе соседних уровней детализации: при к < кшх„ можно считать, что погрешность визуализации рельефа визуально не выявляется.

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

- отсутствие разрывов в представлении поверхности;

- отсутствие резких перепадов высот при переходе от одного уровня детализации к другому;

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

Рассмотрены два способа определения границ областей с различной детализацией (ОРД) при несовпадении направления взгляда с ориентацией ПР:

1. реальные границы ОРД соответствуют ориентации ПР;

2. реальные границы ОРД приближены к теоретическим;

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

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

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

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

ции рельефа, представленного ТНС:

- полный перебор, всех треугольников рельефа (ПП); ----

- выборка потенциально видимых элементов по связным треугольникам с определением видимости треугольника по проекции на плоскость изображения (СТПИ);

- выборка потенциально видимых элементов по связным треугольникам с определением видимости треугольника по проекции на план XY(CTXY);

- выборка потенциально видимых элементов по связным ребрам с определением видимости ребра по проекции на план XY(CPXY);

и два способа визуализации ПР:

- выборка ячеек ПР по прямоугольной области, описывающей проекцию пирамиды видимости на план XY(no);

- выборка ячеек ПР, попадающих в пирамиду видимости методом растровой развертки проекции пирамиды видимости на план XY по ячейкам ПР.

Для обеспечения относительной аппаратной независимости при построении универсальной системы были использованы библиотеки DirectDraw и Direct3D фирмы Microsoft. Измерения производились на PC с ЦП Pentium Pro 200, 32 Мбайт оперативной памяти с графическим ускорителем Matrox Mistique, 4Мб VRAM. В целях наиболее полной оценки изучаемых методов измерения производились как с применением аппаратного ускорения 3D графики, так и без него.

В качестве основной модели рельефа для проведения тестовых измерений была использована оцифрованная карта местности, представляющая территорию 12000x9000 м2, в виде ТНС представленная 1063 опорными точками и 1993 треугольниками. Представление в виде ПР выполнено с дискретностью 10 м по каждому направлению, что дает при описании рельефа 1082101 опорную точку. Также в качестве моделей рельефов, представленных ПР с различными разрешениями были использованы матрицы высот в формате DEM, свободно доступные через Internet по адресу и широко цитируемые в литературе по машинной графике .

Произведенные измерения показали, что применение адап-

тивных волновых методов визуализации рельефа, представленного ТНС сокращает время формирования кадра в среднем до 3 раз при использовании аппаратного ускорения графики и до 2 раз без аппаратного ускорения. Разброс значений относительной эффективности применения адаптивных методов по сравнению с ПП составил не более 5%. Получено экспериментальное подтверждение наличия незначительного преимущества метода СРХУ по сравнению с СТХУ за счет сокращения количества проверок ребра на видимость. Выявлена большая эффективность применения метода СТПИ по сравнению с СТХУ и СРХУ, при отсутствии аппаратного ускорения операции трансформации, что позволяет сделать вывод о предпочтительности применения данного метода для визуализации рельефов с использованием большинства современных графических ускорителей для РС.

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

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

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

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

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

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

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

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

3. Определены и проанализированы три основных варианта структур данных, задающих связность элементов рельефа, представленного ТНС. Из них, как перспективные, выделены две, основанные на связности ребер и связности треугольников .

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

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

6. Произведена оценка эффективности применения разработанных методов в различных условиях применения.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ 1. Research and development of parallel system for image synthesis of 3D-dynamic scenes /Schmidt V., Shah V., Ti-mofeev A., Perkov A., Burenev N. //Projects in Massively

Parallel Computing: Ann. Rep.-St.-Petersburg: Center for Parallel Computer Technologies: [Electrotechnical University] .-1995.-P.14-24.

2. Система визуализации при движении по рельефу /Шмидт В.К., Шах В.В., Перков А.Н., Буренев Н.А., Тимофеев А.В.: Материалы 5-ой Международной Конф. по Компьютерной Графике и Визуализации ГРАФИКОН'95, С.-Петербург., 3-5 июля 1995г.-СПб, 1995.-С.26-32.

3.The distributed interactive system for synthesis of image space scene /Schmidt V.K., Shah V.V., Timofeev A.V., Perkov A.N., Burenev Ы.А. //Applications of Computer Systems: Proceedings of the Second Intern. Conf., Szczecin (Poland), 8-9 December 1995.-Szczecin (Poland), 1995.-

P.215-223.

4. Parallel processing in a problem of 3D scene visualization /Schmidt V.K., Tatarinov Y.S., Shah V.V., Timofeev

A.V., Burenev N.A., Perkov A.N. //The 10th Ann. Intern. Symp. on High Performance Computers: IEEE Canada Electronic Services HPCS'96 Conference Proceedings (on CD-ROM) , Ottawa (Canada), 5-7 July 1996.-Ottawa (Canada), [1996].

5.Система параллельного синтеза изображений динамических пространственных сцен /Шмидт В.К., Тимофеев А.В., Шах

B.В., Перков А.Н.: Материалы 6-ой Международной Конф. по Компьютерной Графике и Визуализации ГРАФИКОН'96, С.Петербург., 10-12 июля 1996г.-СПб, 1996.-С.34-39.

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ ЭЛЕКТРОТЕХНИЧЕСКИЙ

УНИВЕРСИТЕТ

На правах рукописи ПЕРКОВ АНТОН НИКОЛАЕВИЧ

РАЗРАБОТКА И ИССЛЕДОВАНИЕ МЕТОДОВ АДАПТИВНОГО СИНТЕЗА ИЗОБРАЖЕНИЙ РЕЛЬЕФОВ МЕСТНОСТИ

Специальность: 05.13.13 - Вычислительные машины,

системы, комплексы и сети

ДИССЕРТАЦИЯ на соискание ученой степени кандидата технических наук

Научный руководитель к.т.н., профессор В.К.ШМИДТ

Санкт-Петербург - 1998

СПИСОК СОКРАЩЕНИЙ...............................................................................................4

ВВЕДЕНИЕ.....................................................................................................................5

1. ЗАДАЧА ВИЗУАЛИЗАЦИИ РЕЛЬЕФА...................................................................12

1.1. Общая характеристика задачи......................................................................13

1.2. Классификация рельефов по способу представления информации.........18

1.3. Организация параллельных структур для систем синтеза изображения рельефа.........................................................................................................26

1.4. Адаптация в задаче визуализации рельефов..............................................31

1.4.1. Определение параметров наблюдения...................................................31

1.4.2. Адаптация выборки элементов сцены к пирамиде видимости..............33

1.4.3. Адаптация представления рельефа к параметрам наблюдения..........36

1.4.4. Адаптация процесса визуализации рельефа к структуре вычислительной системы...................................................................................................44

1.4. Постановка задачи исследования.................................................................46

2. РАЗРАБОТКА АДАПТИВНОГО МЕТОДА СИНТЕЗА ИЗОБРАЖЕНИЙ РЕЛЬЕФА

МЕСТНОСТИ, ПРЕДСТАВЛЕННОГО В ВИДЕ ТНС............................................48

2.1. Способы представления рельефов со связными элементами...................49

2.2. Обход рельефа, представленного в виде связных треугольников.............57

2.3. Учет пирамиды видимости при обходе рельефа, представленного в виде

связных треугольников.................................................................................65

2.4. Поиск стартового треугольника при применении волнового метода вы-

борки ..............................................................................................................74

2.5. Обход рельефа, представленного в виде связных ребер...........................78

2.5. Выводы............................................................................................................83

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

ВОГО МЕТОДА К РЕЛЬЕФАМ С МУЛЬТИРАЗРЕШЕНИЕМ...............................85

3.1. Выбор наиболее эффективного представления рельефа с мультираз-решением для динамической выборки треугольников с требуемой точностью............................................................................................................86

3.2. Построение ГиТ..............................................................................................89

3.3. Способы обхода гипертриангуляции.............................................................97

3.4. Извлечение поверхности с постоянной погрешностью аппроксимации... 101

3.5. Извлечение поверхности с переменной погрешностью аппроксимации 105

3.6. Учет пирамиды видимости при обходе рельефа, представленного гипертриангуляцией .......................................................................................111

3.7. Выводы..........................................................................................................112

4. РАЗРАБОТКА ЭФФЕКТИВНЫХ МЕТОДОВ РАБОТЫ С РЕЛЬЕФАМИ, ПРЕД-

СТАВЛЕННЫМИ В ВИДЕ РЕГУЛЯРНОЙ ПРЯМОУГОЛЬНОЙ РЕШЕТКИ.......114

4.1. Адаптация выборки треугольников из ПР к параметрам наблюдения ... 117

4.2. Адаптация шагов ПР к производительности системы визуализации и к заданным параметрам наблюдения..........................................................122

4.3. Преобразование ПР в ТНС в целях сокращения объема описания рельефа...............................................................................................................131

4.4. Выводы..........................................................................................................133

5. ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ АДАПТИВНЫХ МЕТОДОВ ВИЗУА-

ЛИЗАЦИИ.............................................................................................................135

5.1. Разработка системы для оценки эффективности адаптивных методов визуализации...............................................................................................136

5.2. Экспериментальное исследование адаптивных волновых методов визуализации для рельефа, представленного ТНС.....................................139

5.3. Экспериментальное исследование адаптивного метода визуализации для рельефа, представленного ПР...........................................................145

5.4. Особенности структурной организации параллельной системы адаптивного синтеза изображений рельефов местности......................................149

5.4. Практическое применение полученных результатов в системе визуализации для тренажера операторов подвижных объектов..........................152

5.5. Выводы..........................................................................................................153

6. ЗАКЛЮЧЕНИЕ........................................................................................................155

ЛИТЕРАТУРА.............................................................................................................157

СПИСОК СОКРАЩЕНИЙ

ВС - вычислительная система;

ГИС - геоинформационная система;

ГиТ - гипертриангуляция;

ГК - графический конвейер;

ДМР - дискретная модель рельефа;

ММР -математическая модель рельефа;

МТ - мультитриангуляция;

ОМ - объект с мультиразрешением;

ПК - персональный компьютер;

ПР - прямоугольная решетка;

ТНС - триангулированная нерегулярная сетка;

УД - уровень детализации;

УМР - упрощенная модель рельефа;

ЦП - центральный процессор;

ОП - оперативная память;

ПП - полный перебор;

СТЭ - связные треугольники с определением видимости по

проекции на экран; CTXY- связные треугольники с определением видимости по

проекции на план XY; CPXY- связные ребра с определением видимости по проекции на план XY; БВТ - блок выборки треугольников; БИ - буфер изображения; MUX - мультиплексор.

ВВЕДЕНИЕ

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

Еще на начальной стадии развития средств машинной графики визуализация изображений использовалась для тренажеров. В качестве примеров можно привести имитатор полета ASUPT и Electronic Scene Generator фирмы General Electric, имитатор полета фирмы Singer/Link и др. [1, 2] . Однако вплоть до настоящего времени, эта задача всегда требовала дорогостоящего специализированного оборудования, которое не было широко доступно.

В настоящее время производительность персональных компьютеров, оснащенных ускорителями трехмерной графики, достигла достаточно высокого уровня (до 250 млн. пике./с и порядка нескольких сотен тысяч текстурирован-ных треугольников в секунду [3, 4]), чтобы говорить о визуализации на ПК и даже о построении тренажеров на базе серийных персональных компьютеров. Однако при сложности сцены порядка нескольких сотен тысяч треугольников все еще возникают проблемы нехватки быстродействия, которые можно решать либо простым наращивани-

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

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

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

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

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

- имитация полета ниже уровня облаков для пилотов летательных аппаратов;

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

совершенствование методов их построения представляется весьма актуальным.

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

Достижение указанной цели предполагает решение следующих задач:

1) классификация рельефов по способу представления информации при их описании; выделение характерных случаев;

2) анализ эффективности применения различных способов представления информации о рельефах для адаптации выборки данных к параметрам наблюдения;

3) анализ известных методов визуализации, применимых к различным классам рельефов;

4) нахождение путей адаптации известных методов визуализации рельефов к конкретным параметрам наблюдения;

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

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

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

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

3) Предложено распространение адаптивного волнового метода синтеза изображений на область гипертриангуляционного представления.

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

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

1) Определены три основных варианта структур данных, определяющих связность элементов рельефа, представленного ТНС. Из них, как перспективные, выделены две, основанные на связности ребер и связности треугольников .

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

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

4) Произведена оценка эффективности применения разработанных методов в различных условиях применения.

Апробация работы. Основные положения диссертационной работы представлялись и обсуждались на 5-ой и б-ой Международных Конференциях по Компьютерной Графике и Визуализации ГРАФИКОН (С.-Петербург, 1995 и 1996), 2-ой Международной конференции по применению компьютерных систем Applications of Computer Systems (Щецин, Польша, 1995), 10-ом Международном симпозиуме по вопросам высо-копроизодительных компьтерных систем HPCS (Оттава, Канада, 1996), а также на отчетных семинарах Центра Транспьютерных Технологий (ЦТТ) СПбГЭТУ (С.-Петербург, 1995 и 1996).

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

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

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

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

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

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

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

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

1 ЗАДАЧА ВИЗУАЛИЗАЦИИ РЕЛЬЕФА

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

Характерной особенностью представления реальных рельефов всегда были большие объемы данных (от тысяч до сотен тысяч опорных вершин). Например, для описания фрагмента рельефа площадью в один квадратный географический градус, представленного в формате DEM (Digital Elevation Models), обычно требуется 1201x1201 опорных точек, т.е., всего 1442401 точек. В таком виде представлены многие регионы США [5]. При необходимости формирования более десяти кадров в секунду даже для относительно простого рельефа, имеющего 10 тыс. опорных вершин, только для проецирования всех вершин требуется

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

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

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