Разработка и исследование методов адаптивного синтеза изображений рельефов местности тема диссертации и автореферата по ВАК РФ 05.13.13, кандидат технических наук Перков, Антон Николаевич

• Перков, Антон Николаевич
• кандидат технических наук
• 1998

Оглавление диссертации кандидат технических наук Перков, Антон Николаевич

борки

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

2.5. Выводы

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

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

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

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

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

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

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

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

3.7. Выводы

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

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

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

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

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

4.4. Выводы

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

ЛИЗАЦИИ

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

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

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

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

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

5.5. Выводы

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

ЛИТЕРАТУРА

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

проекции на экран; 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 тыс. опорных вершин, только для проецирования всех вершин требуется

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

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

Таким образом, очевидно, решение задачи визуализации рельефа за счет одного повышения производительности аппаратуры все еще является слишком дорогостоящим. Для работы с трехмерными изображениями широко используются системы с распределенной обработкой [6-12]. Даже для персональных компьютеров и рабочих станций общего назначения все более типичным становится использование специализированных графических ускорителей, позволяющих разгрузить центральный процессор от множества характерных для трехмерной графики операций (проецирование, отсечение полигонов, вычисление освещенности, имитация тумана, удаление невидимых поверхностей, растеризация полигонов и т.п.) [3, 4]. Кроме того, с развитием аппаратных средств, к системам визуализации предъявляются новые требования по реалистичности (модели освещения, детализация трехмерных моделей объектов) и качеству изображения (разрешение экрана, количество используемых цветов). Эти требования в полной мере относятся и к системам визуализации рельефов. Следовательно, задача повышения эффективности использования аппаратуры при синтезе изображения рельефов имеет шанс оставаться актуальной в течение долгого времени.

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

При визуализации любой пространственной сцены, а, следовательно, и рельефа, вычислительная сложность фор-

мирования каждого кадра определяется следующими составляющими :

• Способ представления сцены:

- Граничное представление (описание поверхностей);

- Объемное представление (воксельное описание);

• Параметры наблюдения (рис. 1.1 ):

- Точка наблюдения;

- Передний отсекающий план;

- Задний отсекающий план;

- Горизонтальный сектор обзора;

- Вертикальный сектор обзора;

- Направление взгляда;

- Размеры окна вывода изображения;

Рис. 1.1 Пирамида видимости

• Динамические параметры:

- Перемещение за время смены кадров;

- Изменение направления взгляда за время смены кадров .

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

• Определение текущих параметров наблюдения;

• Выборка элементов сцены, попадающих в пирамиду видимости;

• Проецирование опорных точек сцены, выбранных на предыдущем этапе;

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

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

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

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

1

функцией Я, часто называется топографической или 2—£

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

На практике используются Дискретные Модели Рельефа (ДМР), которые производят дискретную аппроксимацию рельефа, построенного на базе конечного множества Р опорных точек, выбранных на поверхности. Дискретная Модель Рельефа (ДМР), построенная на Р, представляется парой й = {£, Ф) , где:

1. Е - участок связанной (не обязательно выпуклой) плоской области, имеющей в качестве своих вершин множество точек {(х, у) \ (х, у, г);

2. Ф - семейство непрерывных функций двух аргументов, таких что каждая функция ф±еФ определена на замкнутой области £¿6.27 и интерполирует высоту точек, чьи проекции являются вершинами (обычно используется линейная или билинейная интерполяция);

3. для каждой пары смежных областей £± и функции ф1

и ф^ принимают одинаковые значения на общем ребре областей ^ и

Как показал анализ существующих программных продуктов, использующих информацию о реальных рельефах [5, 14], нет смысла рассматривать вариант чисто аналитического задания функций окраски и высоты. Обычно бывают заданы значения функций для некоторого множества опорных точек, на основе которых и производится визуализация. Способы представления данных для описания рельефа разработаны, но непосредственная связь между представлением рельефа и выбором алгоритмов визуализации раскрыта слабо.

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

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

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

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

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

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

не связанная непосредственно с типом поверхности, как то: данные о концентрации полезных ископаемых или вредных веществ и т.п.

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

В программных системах, требующих хранения данных о рельефе (например, геоинформационных системах или ГИС) используются два основных способа представления информации о высотах [14, 17] :

• прямоугольные решетки (ПР);

• триангулированные нерегулярные сетки (ТНС).

Как следует из названия, в первом случае известна высота точек, являющимися узлами некоторой прямоугольной решетки. Рассмотрим формальное описание такого представления высот рельефа. Пусть задана правая декартова прямоугольная система координат ОХУг. Здесь и далее будем считать ось ОЪ направленной вверх, ось ОХ -вправо, ось ОУ - вглубь от наблюдателя, а рельеф - рас-

положенным в секторе ХОг. Заданы числа

11Х еК \1у е 1Х > 0 ' [1у > О

и Ьх е ТЯ, Ьу е И, множества X =

(л - 1)1}

п Е N л <

и

У

(л - 1)1

У

л е N л < 1„

Г

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

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

Числа 1Х и Ту назовем шагами прямоугольной сетки, заданными в некоторых условных единицах. В принципе, они могут и совпадать. По аналогии с представлением

Рис. 1.2 Задание рельефа в виде прямоугольной решетки: а) опорные точки; б) вариант триангуляции для прямоугольной решетки.

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

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

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

Во втором случае (ТНС) закон расположения опорных точек не может быть определен. Формально к данному описанию можно применить следующие требования: пусть задана правая декартова прямоугольная система координат

\ЬХ е I* е Р.

ОХУг, должны быть заданы числа « , < , п е Ы;

К >0 1а >0

множество точек на плоскости, заданных парами координат Ртнс = {Р1, р2, Рп} С ХхУ, где X = [О, Ьх) п Ы, У = [О, Ьу) п Ы, рк = (хк, ук) | к е [1, п] п N и функция высоты рельефа л = Нтнс(х, у), причем В(НТЯС) = Ртнс (рис. 1.3 а).

На множестве точек Ргнс производится триангуляция Делоне (Ре1аипау) [18, 19, 20] для получения множества треугольников Ттнс = {Ь1г Ьг, , где Ьк = {1к1, ±к2,

1к3) | к е [1, ш] п N/ а 1к1, 1к2, 1кз ~ номера точек из множества РТНСл являющихся вершинами данного треугольника, рис. 1.3 б.

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

ребро с данным треугольником, о точках, соединенных одним ребром с данной точкой, о ребрах, имеющих общую вершину с данным ребром и т.п. [17]. Эта информация мо-

а)

■■»»у -к

■с . - ■ ■-м: ■

г "

Заключение диссертации по теме «Телекоммуникационные системы и компьютерные сети», Перков, Антон Николаевич

5.6 Выводы

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

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

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

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

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

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

6 ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

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

Список литературы диссертационного исследования кандидат технических наук Перков, Антон Николаевич, 1998 год

ЛИТЕРАТУРА

1.Kilgour А.С. Techniques for modelling and displaying 3D scenes //Advances in Computer Graphics.-N.У.: Springer-Verlag.-198 9.

2.Башков E.A., Казак А.В. Генераторы изображений для тренажеров //Зарубежная радиоэлектроника.-198 4.-8.-С.64-79.

3.Bruce Buchanan 3D Technologies //Rexcellence, Computer Aided Engineering news.-1997.-7(8).-PP.57-61.

4.John Latta Major Performance Improvements in 3D, 2D and Video //THE WAVE REPORT ON DIGITAL MEDIA.-4th WAVE Inc.-1997.-PP.36-43.

5.Cignoni P., Puppo E., Scopigno R. Representation and Visualization of Terrain Surfaces at Variable Resolution //The Visual Computer.-1997.-13.-PP.89-134.

6.Мартинес Ф. Синтез изображений. Принципы, аппаратное и программное обеспечение.-М.: Радио и связь.-1990.

7.Баяковский Ю.М., Галактионов В.А., Ходулев А.Б. Архитектура высокопроизводительных графических систем

//Зарубежная радиоэлектроника.-1989.-2.-С.18-44.

8.Палташев Т.Т., Климина С.И., Ю В.К. Технология визуализации в компьютерном синтезе реалистичных изображений //Зарубежная радиоэлектроника.-198 9.-2.-

С.71,96-108.

9.Schmidt V., Shah V., Timofeev A., Perkov A., Burenev N. Research and development of parallel system for image synthesis of 3D-dynamic scenes //Projects in Massively Parallel Computing. Annual Report.-Center

for Parallel Computer Technologies, Electrotechnical University, St.-Petersburg.-1995.-P.14-24.

10. Schmidt V.K., Tatarinov Y.S., Shah V.V., Timofeiev A.V., Burenev N.A., Perkov A.N. Parallel processing in a problem of 3D scene visualization //The 10th Annual International Symposium on High Performance Computers. -IEEE Canada Electronic Services HPCS'96 Conference Proceedings on CD-ROM.-Ottawa, Canada.-July 5-7, 1996.

11. Шмидт В.К., Тимофеев А.В., Шах В.В., Перков А.Н. Система параллельного синтеза изображений динамических пространственных сцен //Материалы 6-ой Международной Конференции по Компьютерной Графике и Визуализации ГРАФИКОН'96.-Ст.-Петербург.-1996.-С.34-39.

12. Тимофеев А.В. разработка и повышение производительности параллельной системы визуализации трехмерных сцен //Автореферат диссертации на соискание ученой степени кандидата технических наук.-С.-Петербург.-1997 .

13. Арье Кауфман. Введение в объемную визуализацию //Программирование.-1992.-1.-С.8-20.

14. De Floriani L., Puppo E., Magillo P. Geometric structures and algorithms for geographic information systems //Technical Report DISI-TR-97-08.-Department of Computer and Information Sciences, University of Genova.-1997.

15. Magillo P., Puppo E. Algorithms for Parallel Terrain Modelling and Visualisation //Chapter 16 in Parallel Processing Algorithms for GIS.-R.G. Healey, S.

Dowers В.M. Gittings, M.J. Mineter (Editors).-Taylor and Francis.-1998.-PP.351-386.

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

17. Leila De Floriani Surface representation based on triangular greeds //The Visual Computer-1987.-1.-PP.27-50.

18. Майкл Ласло Вычислительная геометрия и компьютерная графика на С++: Пер. с англ.-М.: «Издательство БИНОМ».-1997.

19. Shubert L., Wang С.A. An optimal algorithm for constructing the Delanay triangulation of set of line segments //Proceedings 3rd ACM Symposium on Computational Geometry.-Waterloo.-June 1987.-PP.223-232.

20. Tsai V.J.D. Delanay triangulations in TIN creation: an overview and linear-time algorithm //International Journal of GIS.-1993.-7(6).-PP.501-524.

21. Chen Z.T., Guevara J.A. Systematic selection of very important points (VIP) from digital terrain model for constructing triangular irregular networks //Proceedings AUTO-CARTO 8.-Baltimore, MD, USA.-1987.-PP.50-56.

22. de Berg M., Dobrindt K.T.G. On the levels of detail in terrains //11th ACM Symposium on Computational Geometry .-Vancouver, ВС (Canada).-June 5-7.-1995.-

PP.147-154.

23. De Floriani L., Magillo P., Puppo E. Building and traversing a surface at variable resolution //Proceedings IEEE Visualization 97.-Phoenix, AZ (USA).-October 1997.-PP.236-253.

24. Fowler R., Little J. Automatic extraction of irregular network digital terrain models //ACM Computer Graphics.-13(3).-1979.-PP.199-207.

25. Franklin W.R. Triangulated irregular network to approximate digital terrain //Technical report.-ECSE Dept.-RPI, Troy (NY).-1994.

26. Kirpatrick D.G. Optimal search in planar subdivisions //SIAM Journal of Computing.-12(1).-1983.-PP.28-35.

27. Lee J. A drop heuristic conversion method for extracting irregular networks for digital elevation models //Proceedings GIS/LIS '89.-Orlando, FL, USA.-1989.-PP.30-39.

28. Rippa S. Adaptive approximations by piecewise linear polynomials on triangulations of subsets of scattered data //SIAM Journal on Scientific and Statistic Computing.-13(1).-1992.-PP.1123-1141.

29. Scarlatos L.L. An automatic critical line detector for digital elevation matrices //Proceedings 1990 ACSM-ASPRS Annual Convention.-2, Denver, CO.-1990.-PP.43-52.

30. Southard D.A. Piecewise linear surface models from sampled data //Proceedings Computer Graphics International 91.-Boston, MA.-22-28 June.-1991.-PP.27 4-295.

31. Schmidt V.K., Shah V.V., Timofeev A.V., Perkov

A.N., Burenev N.A. The distributed interactive system for synthesis of image space scene //Applications of Computer Systems.-Proceedings of the Second International Conference.-Szczecin-Poland.-December 8-9, 1995.-P.215-223.

32. Video Controllers.-Rose Computing Services Website.- Texas Networking Inc.-

http://www.texas.net/~res/reseat37.htm.-1998.

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

34. Кручинин С. Новое поколение графических подсистем для настольных рабочих станций HP, SGI и Sun //Computer Week.-1996.-4 4.-С.36-39,44,45.

35. Кларк Дж., Дэйвис Т.-Электроника.-1983.-т.56.-20.

36. Gelberg Lawrence М., MacMann Jeffrey F., Mathias Craig J. Graphics, image processing, and the Stellar graphics supercomputer //Proc. Soc. Photo-Opt. Instrum. Eng.-1989.-PP.89-96.

37. Advances in Computer Graphics.-Ed. by G. Enderle, M. Grave, F. Lillehagen.-Berlin: Springer-Verlag.-1986.

38. Фоли Дж., вэн Дэм А. Основы интерактивной машинной графики.-М.: Мир.-1985.-в 2-х кн.

39. Finke U., Hinrichs К.Н. The quad view data structure - A representation for planar subdivisions

//Advances in Spatiol Databases, Lecture notes in Computer Science.-Springer.-1995.-PP.29-46.

40. Flajolet p., Gonnet G.H., Puech C., Robson J.M. Analytic variations on quadtrees //Algorithmica.-

1993.-10(6).-PP.473-500.

41. van Oosterom P. A modified binary space partition for geographic information systems //International Journal of Geographical Information Systems.-1990.-4 (2) .-PP. 133-146.

42. Inventor Mentor: Openlnventor Reference Manual.-Openlnventor Architecture group.-Addison Wesley.-

1994.

43. Wernecke J. The Inventor mentor: programming Ob-jectOoriented 3D graphics with Openlnventor.-Addison Wesley.-1994.

44. The Virtual Reality Modeling Language Specification - Version 2.0.-August 1996.-http://vag.vrml.org/.

45. Puppo E. Variable resolution terrain surfaces //Proceedings Canadian Conference on Computational Geometry.-Ottawe (Canada) 12015 August.-1996.-PP.34-57 .

46. Samet H. Applications of spatial data structures.-Addison-Wesley.-1990 .

47. Dutton G. Improving locational specificity of map data - a multiresolutional, metedataOdriven approach and notation //International Journal of Geographic Information Systems.-199 6.-10(3).-PP.253-268.

48. Goodchild M.F., Shiren Y. A hierahical data structure for global geographic information systems

//Computer Vision, Graphics and Image Processing.-1992.-54.-PP.31-44.

49. Klein R., Strasser W. Generation of multireslution models from CAD data for real time rendering. Theory and Practice of Geometric Modelling.-Springer-Verlag .-1996.

50. Hoppe H. Progressive meshes //ACM Computer Graphics Proceedings.-Annual Conference Series (SIGGRAPH'96).-1996.-PP.99-108.

51. Hoppe H. View-dependent refinement of progressive meshes //ACM Computer Graphics Proceedings.-Annual Conference Series (SIGGRAPH '97).-1997.-PP.73-8 6.

52. Maheshwari A., Morin P., Sack J.R. Progressive TINs: algorithms and applications //Proceedindg 5th ACM Workshop on Advances in Geographic Information Systems.-Las Vegas (Nevada).-November 15-16, 1997.-PP.256-263.

53. Xia J.C., Varshney A. Dynamic view-depended simplification for polygonal models //Proceedings IEEE Visualization '96.-S. Francisco, CA.-R. Yagel and Nielson (Eds.).-1996.-PP.327-334.

54. De Floriani L., Magillo P., Puppo E. A formal approach to multiresolution modeling.-W. Strasser, R. Klein, R. Rau (Eds.).-Springer-Verlag.-1996.

55. De Floriani L., Magillo P., Puppo E. Efficient encoding and Retrieval of Triangle Meshes at Variable Resolution //Technical Report DISI-TR-97-01.-Department of Computer and Information Sciences, University of Genova.-Genova, Italy.-1997.

56. Brown P.J.С. A fast algorithm for selective refinement of terrain meshes //Proceedings COMPUGRAPHICS

96.-GRASP.-December 1996.-PP.7 0-82.

57. George Nasy Terrain visibility //Computers & Graphics . -1994 . -6 . -PP . 38-52 .

58. Вирт H. Алгоритмы + структуры данных = программы.-М.: Мир.-1985.

59. Кнут Д. Искусство программирования для ЭВМ.-М.: Мир.-1978.-в 3-х кн.

60. Холл П. Вычислительные структуры. Введение в нечисленное программирование.-М.: Мир.-1978.

61. Гилой В. Интерактивная машинная графика.-М.: Мир.-1981.

62. Rappoport A. An efficient algorithm for line and polygon clipping //The Visual Computer.-1991.-1 (7).-PP.19-25.

63. Barrera R., Vazques-Gomez J. A shortest path algorithm for hierarchical terrain models //Proceedings AUT_CARTO 9.-1989.-PP.156-163.

64. de Berg M., van Kreveld M., van Oostrum R., Overmars M. Simple traversal of a subdivision without extra storage //International Journal of Geographic Information Science.-1997.-11(4).-PP.359-373.

65. De Floriani L., Puppo E. Hierarchical triangulation for multiresolution surface description //ACM Transactions on Graphics.-1995.-14(4).-PP.363-411.

66. Dutton G. Polyhedral hierarchical tesselation: the shape of GIS to come //Geo Info Systems.-1991.-2(1).-PP.49-55.

67. De Floriani L., Marzano P., and Puppo E. Multiresolution models for topographic surface description //The Visual Computer.-1996.-12(7).-PP.317-345.

68. De Floriani L. A pyramidal data structure for triangle-based surface description //IEEE Comp.Graph. & Appl.-1995.-9(2).-PP.67-78.

69. De Floriani L., Puppo E. Hierarchical triangulation for multiresolution surface description //A.C.M. Trans, on Graphics.-1995.-14(4).-PP.363-411.

70. Dobkin D. and Laszlo M. Primitives for the manipulation of threedimensional subdivisions

//Algorithmica.-1989.-4.-PP.3-32.

71. Boissonnat J. and Teillaud M. On the randomized construction of the Delaunay tree //Theoretical Computer Science.-112.-1993.-PP.339-354.

72. Webb H. Creation of digital terrain models using analytical photogrammetry and their use in civil engineering //Terrain Modelling in Survey and Civil Engineering . -Petrie G. and Petrie T.J.M. (Editors).-London: Whittles Publishing - Thomas Telford.-1990.-PP.73-84.

73. Agarwal P.K., Suri S. Surface approximation and geometric partitions //Proceedings 5th ACM-SIAM Symposium on Discrete Algorithms.-1994.-PP.24-33.

74. Agarwal P.K., Desikan P.K. An efficient algorithm for terrain simplification //Proceedings 8th ACM_SIAM Symposium on Discrete Algorithms.-1997.-PP.162-184.

75. Silva C.T., Mitchell J.S.B., Kaufman A.E. Automatic generation of triangular irregular networks using

greedy cuts //Proceedings IEEE Visualization'95.-1995.-PP.201-208.

76. Джон Кармак. Direct3D или OpenGL? //Компьютерная графика.-1996.-6.-С.68-7 0.

77. Microsoft и Silicon Graphics совместно разработают набор графических драйверов для Windows //Компьютер-инфо.-1997.-39.-С.12.

78. Эллис М., Строуструп Б. Справочное руководство по языку программирования С++ с комментариями: Пер. с англ.-М.: Мир.-1992.

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

80. Мюррей У., Паппас К. Visual С++. Руководство для профессионалов: пер. с англ.-Спб.: BHV-Санкт-Петербург.-1996.