Факультет «Информатика и системы управления»

Кафедра «Программное обеспечение ЭВМ и информационные технологии»

Курсовой проект

по машинной графике

Расчётно-пояснительная записка

Тема:

«Построение изображений ландшафта в реальном времени»

Оглавление

1. Введение

2. Конструкторская часть

2.1 Выбор, обоснование и описание используемых алгоритмов и понятий машинной графики

2.1.1 Равномерная сетка высот

2.1.2 Сглаживание ландшафта

2.1.3 Трехмерные аффинные преобразования

2.1.4 Проецирование

2.1.5 Отображение в окне

2.1.6 Алгоритм Z-буфера

2.1.7 Освещение

2.1.7.1 Однотонная закраска (метод гранения)

2.1.7.2 Метод Гуро

2.1.7.3 Метод Фонга

2.1.7.4 Анализ методов Гуро и Фонга

2.1.8 Последовательность действий при визуализации сцены

2.2 Типы, структуры данных и функции, использованные при реализации программного комплекса

2.2.1 Представление исходных данных

2.2.2 Программа «Редактор карт»

2.2.2.1 Изообласти высоты

2.2.2.2 Равномерная сетка высот и ландшафт

2.2.2.3 Тип и структура файла для хранения карт изообластей

2.2.2.4 Распределение программы по модулям

2.2.2.5 Связи между модулями программы

2.2.3 Программа «Просмотр ландшафта»

2.2.3.1 Процедуры манипуляции изображением ландшафта

2.2.3.2 Z-буфер

2.2.3.3 Буфер кадра

2.2.3.4 Процедуры визуализации ландшафта

2.2.3.2 Тип и структура файла для хранения ландшафта

2.2.3.3 Распределение программы по модулям

2.2.3.4 Связи между модулями программы

3. Технологическая часть

3.1 Выбор языка программирования

3.2 Описание программного комплекса

3.2.1 Программа «Редактор карт»

3.2.1.1 Общие сведения

3.2.1.2 Интерфейс программы

3.2.1.3 Работа программы

3.2.2 Программа «Просмотр ландшафта»

3.2.2.1 Общие сведения

3.2.2.2 Интерфейс программы

3.2.2.3 Работа программы

3.2.3 Системные требования

4. Экспериментально-исследовательская часть

4.1 Исследование № 1

4.2 Исследование № 2

4.3 Исследование № 3

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

6. Список литературы

1. Введение

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

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

• преобразование данной карты в равномерную сетку высот;

• триангуляция полученной сетки высот;

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

Требование к скорости построения изображений ландшафта (для комфортной работы необходима производительность порядка 30 кадров в секунду [1]) определяет выбор алгоритма машинной графики, используемого для визуализации сцены – алгоритм Z-буфера в наибольшей степени отвечает этому требованию, так как он является наиболее простым в своей группе и требует наименьшего количества вычислительных ресурсов.

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

При работе с освещением реализованы следующие алгоритмы заполнения плоских граней (в данной работе - треугольников):

• метод гранения (однотонной закраски с учетом ориентации нормали к плоскости грани);

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

• метод Фонга – метод, основанный на билинейной интерполяции векторов нормалей в вершинах граней.

Цель данной работы – реализовать перечисленные алгоритмы в разрабатываемом программном комплексе.

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

2. Конструкторская часть

2.1 Выбор, обоснование и описание используемых
алгоритмов и понятий машинной графики

2.1.1 Равномерная сетка высот

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

• аналитическая модель – для описания поверхности используются математические формулы, например функции от двух аргументов z = f(x, y);

• векторная полигональная модель – для описания пространственных объектов используются такие элементы, как вершины, векторы, полилинии, полигоны, полигональные поверхности;

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

• неравномерная сетка – в этой модели поверхность описывается в виде множества отдельных точек, принадлежащих поверхности.

В данной работе в качестве модели описания поверхности (ландшафта) используется равномерная сетка высот. Эта модель описывает координаты отдельных точек поверхности способом, показанным на рисунке:

Рис. 2.1.1.1. Общий вид равномерной сетки высот

Каждому узлу сетки с индексами (i, j) приписывается значение высоты Z_ij. Индексам (i, j) отвечают определенные значения координат (x, y). Расстояние между узлами одинаковое – dX по оси X и dY по оси Y.

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

Следует отметить, что не каждая поверхность может быть представлена с помощью этой модели, так как если в каждом узле записывается только одно значение высоты, то это означает, что поверхность описывается однозначной функцией z = f(x, y). Кроме того, невозможно моделирование вертикальных граней.

В случае представления ландшафта в виде равномерной сетки высот эти ограничения являются незначительными и вполне допустимыми. Равномерная сетка часто используется для описания рельефа земной поверхности [2].

Следует выделить следующие положительные черты модели равномерной сетки:

• простота описания поверхностей;

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

Но эта модель также имеет и недостатки:

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

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

Но в данной работе равномерная сетка используется опосредованно – сразу же при получении она разбивается на треугольники (производится ее триангуляция), поскольку реализация необходимых в процессе работы алгоритмов машинной графики для этого примитива наиболее проста. Разбиение на треугольники производится путем проведения диагонали из точки (i, j) в точку (i – 1, j + 1).

2.1.2 Сглаживание ландшафта

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

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

Рис. 2.1.2.1. Циклы сглаживания ландшафта

Пиксели для усреднения высот выбираются следующим образом: на K-ой итерации цикла производится усреднение высот пикселей с индексами (i – 1, j - 1), (i – 1, j), (i, j - 1) и (i, j), на (K + 1)-ой же, в зависимости от номера цикла, усредняются высоты следующих пикселей:

• в I цикле – пиксели тех же двух строк с индексами столбцов, увеличенными на 1;

• во II цикле – пиксели тех же двух строк с индексами столбцов, уменьшенными на 1;

• в III цикле – пиксели тех же столбцов со строчными индексами, увеличенными на 1;

• в IV цикле – пиксели тех же столбцов со строчными индексами, уменьшенными на 1.

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

Рис. 2.1.2.2. Результаты сглаживания – без сглаживания, 1 цикл, 10 циклов.

2.1.3 Трехмерные аффинные преобразования

В процессе работы программы может возникать необходимость преобразования объектов сцены – их сдвига, масштабирования, поворота.

Для трехмерного пространства любое аффинное преобразование может быть представлено последовательностью простейших операций [3].

Ниже приводятся уравнения и матрицы преобразований:

• сдвиг точки вдоль координатных осей на dx, dy, dz:

;

• масштабирование относительно начала координат с коэффициентами k_x, k_y, k_z:

;

• поворот относительно осей x, y, z на угол :

  • ось x:

• ось y:

• ось z:

2.1.4 Проецирование

В настоящее время наиболее распространены устройства отображения, которые синтезируют изображение на плоскости, например – экране монитора. Устройства, которые создают по-настоящему объемные изображения, пока достаточно редки. Но все чаще появляются сведения о подобных разработках, например, об объемных мониторах [2].

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

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

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

В компьютерной графике распространены параллельная и центральная (перспективная) проекции.

Рис. 2.1.4.1. Параллельная и центральная проекции

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

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

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

Рис. 2.1.4.2. Аксонометрическая проекция

Для того, чтобы найти соотношения между координатами (x, y, z) и (X, Y, Z) для любой точки в трехмерном пространстве, рассмотрим преобразование системы координат (x, y, z) в систему (X, Y, Z). Такое преобразование может быть задано двумя шагами:

• поворот системы координат относительно оси z на угол . Такой поворот описывается матрицей

;

• поворот новой системы координат (x, y, z) относительно оси x на угол - получение координаты (X, Y, Z). Матрица поворота:

.

Преобразование координат выражается произведением матриц

Это же преобразование можно записать в формульном виде:

2.1.5 Отображение в окне

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

Пусть (Xэ, Yэ, Zэ) – это экранные координаты объектов в графическом устройстве отображения. Координаты проецирования обозначим как (X, Y, Z).

Преобразование координат проекции в экранные координаты можно представить как растяжение/сжатие и сдвиг:

.

Такое преобразование сохраняет пропорции объектов благодаря одинаковому коэффициенту растяжения/сжатия k для всех координат. Следует отметить, что для плоского отображения координату Z можно отбросить.

2.1.6 Алгоритм Z-буфера

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

Это один из простейших алгоритмов удаления невидимых поверхностей. Работает этот алгоритм в пространстве изображения. Идея Z-буфера является простым обобщением идеи о буфере кадра. Буфер кадра используется для запоминания атрибутов (интенсивности) каждого пикселя в пространстве изображения, Z-буфер - это отдельный буфер глубины, используемый для запоминания координаты Z (глубины) каждого видимого пикселя в пространстве изображения. В процессе работы глубина или значение Z каждого нового пикселя, который нужно занести в буфер кадра, сравнивается с глубиной того пикселя, который уже занесен в Z-буфер. Если это сравнение показывает, что новый пиксель расположен впереди пикселя, находящегося в буфере кадра, то новый пиксель заносится в этот буфер и, кроме того, производится корректировка Z-буфера новым значением Z. Если же сравнение дает противоположный результат, то никаких действий не производится. По сути, алгоритм является поиском по x и y наибольшего значения функции Z(x, у). Блок-схема алгоритма выглядит следующим образом:

Рис. 2.1.6.1. Блок-схема алгоритма Z-буфера

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

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

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

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

Для сканирующей строки, поэтому глубина пикселя на этой строке, у которого , равна

или

,

но , поэтому .

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

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

;

• затем для каждой стороны находится параметр t при пересечении с горизонталью :

;

• если , то рассчитывается абсцисса точки пересечения горизонтали со стороной треугольника:

.

Рис. 2.1.6.2. Поиск абсцисс точек пересечения горизонтали со сторонами треугольника

2.1.7 Освещение

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

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

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

Рис. 2.1.7.1. Матовая поверхность

,

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

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

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

_,

где R – расстояние от источника света до рассматриваемой точки поверхности, k – произвольная константа, предотвращающая деление на 0.

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

,

,

,

или

.

Следовательно

.

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

,

или, более развернуто,

.

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

2.1.7.1 Однотонная закраска (метод гранения)

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

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

• источник света находится на большом расстоянии от объекта;

• наблюдатель находится на большом расстоянии от объекта;

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

• поверхность аппроксимирована большим числом небольших плоских граней.

Рис. 2.1.7.1.1. Изображение, полученное методом гранения

2.1.7.2 Метод Гуро

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

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

• вычисляются нормали к каждой грани;

• определяются усредненные нормали в вершинах - производится усреднение нормалей примыкающих граней. На иллюстрации приведен пример – вектор нормали в вершине a равен ;

Рис. 2.1.7.2.1. Нормаль в вершине

• на основе усредненных нормалей в вершинах вычисляются значения интенсивностей в вершинах согласно принятой модели отражения;

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

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

Рис. 2.1.7.2.2. Интерполяция значений интенсивности

Интерполированная интенсивность I в точке (X, Y) определяется исходя из пропорции

.

Отсюда

.

Значения интенсивностей I₁ и I₂ на концах горизонтального отрезка представляет собой интерполяцию интенсивности в вершинах:

; или

, .

Рис. 2.1.7.2.3. Изображение, получено методом Гуро

2.1.7.3 Метод Фонга

Этот метод закраски аналогичен методу Гуро, но при использовании метода Фонга для определения цвета в каждой точке интерполируются не интенсивности отраженного света, а векторы нормалей.

Последовательность действий такова:

• определяются нормали к граням;

• по нормалям к граням определяются усредненные нормали в вершинах. В каждой точке закрашиваемой грани определяется интерполированный вектор нормали;

• по направлению векторов нормали определяется цвет точек грани в соответствии с принятой моделью отражения цвета.

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

Рис. 2.1.7.3.1. Интерполяция векторов нормалей

Нахождение и производится следующим образом:

,

.

где – координаты векторов . Теперь необходимо найти координаты вектора :

.

Вектор параллелен векторудля нормали в точке , поэтому его можно использовать для расчета отражения света так же, как и вектор нормали .

Рис. 2.1.7.3.2. Изображение, полученное методом Фонга

2.1.7.4 Анализ методов Гуро и Фонга

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

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

Рис. 2.1.7.4.1. Отличия закрашивания Фонга и Гуро

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

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

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

2.1.8 Последовательность действий при визуализации сцены

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

Рис. 2.1.8.1. Схема визуализации сцены

2.2 Типы, структуры данных и функции, использованные при реализации программного комплекса

2.2.1 Представление исходных данных

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

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

Разработанные типы данных и форматы файлов подробно описаны в последующих разделах.

2.2.2 Программа «Редактор карт»

2.2.2.1 Изообласти высоты

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

THeightColor = record

Color : TRGBColor;

Height : Single;

end;

Поля этой записи имеют следующее значение:

• Color – цвет изообласти;

• Height – представляемая высота.

Размер записи – 8 байт (компилятор Delphi производит выравнивание полей в записи, поэтому размер записи оказывается равным 8 байтам, а не 7, как должно быть).

Тип TRGBColor используется для хранения RGB-цвета. Представим его структуру:

TRGBColor = record

R, G, B : Byte;

end;

Размер записи – 3 байта (по неизвестным причинам в этом случае выравнивания не произошло).

В процессе создания каждой карты создается динамический массив, для хранения информации обо всех типах изообластей:

THeightColors = array of THeightColor;

2.2.2.2 Равномерная сетка высот и ландшафт

Для хранения узлов исходной равномерной сетки (с шагом 1) используется динамический массив элементов типа Single:

TZBitMap = array of array of Single;

Тип Single использован для экономии оперативной памяти и дискового пространства, точность этого типа – 8 знаков после запятой, что вполне достаточно в рамках этой работы, при этом переменная этого типа занимает в памяти 4 байта, вдвое меньше, чем переменная типа Real.

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

TTriangle = record

P : array [0..2] of TPoint3

N : TPoint3

pD : Single;

aN : array [0..2] of TPoint3;

Color : TRGBColor;

end;

Поля этой записи имеют следующие значения:

• P – массив точек треугольника;

• N – нормаль к плоскости треугольника;

• pD – свободный член уравнения плоскости, несущей треугольник;

• aN – массив усредненных нормалей в вершинах треугольника;

• Color – базовый цвет треугольника.

Поля N и pD в совокупности образуют уравнение плоскости, несущей треугольник.

Размер записи – 92 байта (реальный размер, без выравнивания – 91 байт).

Необходимо привести описания типов, использованных в записи TTriangle:

TPoint3 = record

X, Y, Z : Single;

end; - запись служит для хранения координат точки.

Размер записи – 12 байт.

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

• function CreateZBitMap(Width, Height : Integer) : TZBitMap – выделение памяти для первичной сетки высот, ее размеры - Width и Height, совпадают с размерами области вывода;

• procedure FreeZBitMap(var ZBMP : TZBitMap) – освобождение памяти, занимаемой первичной сеткой высот;

• function FillZBitMap(Image : TImage; Colors : THeightColors) : TZBitMap - заполнение первичной сетки высот на основе изображения, хранимого в Image и соответствий «Цвет-высота», содержащихся в массиве Colors;

• function DivideZBitMapIntoTriangles(BitMap : TZBitMap; StepX, StepY : Integer) : TTriangles – функция преобразования первичной равномерной сетки BitMap в более разреженную сетку с шагами StepX и StepY по горизонтали и вертикали соответственно. После этого преобразования полученная сетка разбивается на треугольники, на основе которых будет построен ландшафт;

• procedure SmoothMap(var BitMap : TZBitMap) – процедура для проведения одного цикла сглаживания первичной сетки высот;

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

• procedure FillTrianglesNormals(var Triangles : TTriangles) – расчет и заполнение всех полей записи TTriangle, кроме координат точек и цвета;

В процедуре FillTrianglesNormals используются следующие вспомогательные функции:

• function GetNormal(T : TTriangle) : TPoint3 – процедура для вычисления координат вектора нормали к плоскости треугольника;

• function CorrectNormal(N : TPoint3) : TPoint3 – процедура нормализации вектора нормали;

• procedure AddNormal(var N : TPoint3; NAdd : TPoint3; var Count : Integer), procedure DivideNormal(var N : TPoint3; Count : Integer) – эти процедуры в совокупности служат для вычисления усредненной нормали в вершине треугольника;

2.2.2.3 Тип и структура файла для хранения карт изообластей

Файл для хранения информации о разметке карты изообластей высот является текстовым. Он имеет расширение HCL и разбит на секции, разделенные строками–маркерами. Ниже приведена его структура:

• заголовок файла – строка 'Landscape heights map';

• заголовок секции высот – строка ‘[ColorHeights Start]’;

  • последовательность записей типа THeightColor;

• окончание секции высот – строка '[ColorHeights End]';

• заголовок секции пикселей – строка '[Pixels Start]';

• ширина и высота карты в пикселях;

• информация о пикселях карты, сжатая с помощью метода группового кодирования (последовательность пар «Индекс цвета – Длина участка»);

• окончание секции пикселей – строка '[Pixels End]';

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

Для работы c файлами карт изообластей высот предусмотрены следующие процедуры:

• procedure LoadFromHeightsMap(FileName : string; var Image : TImage; var Colors : THeightColors) - процедура для загрузки из файла HCL карты изообластей высот и соответствий цвет-высота. Информация загружается из файла FileName. Разметка карты выводится на Image, а соответствия «Цвет-высота» помещаются в динамический массив Colors;

• procedure SaveAsHeightsMap(Image : TImage; Colors : THeightColors; FileName : string) – процедура для сохранения разметки карты в файл HCL. Разметка считывается из Image, соответствия «Цвет-высота» из массива Colors, эта информация помещается в файл c именем FileName.

2.2.2.4 Распределение программы по модулям

Таблица 2.2.2.4.1. Распределение программы «Редактор карт» по модулям

Имя модуля

Описанные типы

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

AboutUnit.pas

-

Модуль формы «О программе»

ColorUnit.pas

-

Модуль формы определения соответствия «Цвет-высота»

HelpUnit.pas

-

Модуль формы «Помощь»

MainUnit.pas

-

Главный модуль программы

ME_ExtRegUnit.pas

-

Модуль регистрации расширения HCL

ME_FileUnit.pas

-

Модуль работы с файлами

ME_GraphicsUnit.pas

-

Модуль реализации процедур визуализации

ME_MathUnit.pas

TRGBColor, TPoint3, TTriangle, TTriangles, THeightColor, THeightColors, TZBitMap

Модуль реализации вычислений

MLEditorUnit.pas

-

Модуль инструментальной формы «Обработка карт»

NewPictureUnit.pas

-

Модуль формы определения размеров новой карты

SectionUnit.pas

-

Модуль формы «Разрез»

2.2.2.5 Связи между модулями программы

Рис. 2.2.2.5.1. Связи между модулями программы «Редактор карт»

2.2.3 Программа «Просмотр ландшафта»

В программе «Просмотр ландшафта» также используется тип TTriangle. Он полностью аналогичен типу TTriangle, используемому в программе «Редактор карт». Ландшафт, как уже говорилось, представляется как совокупность треугольников, поэтому для его хранения в программе предусмотрен тип, представляющий собой динамический массив:

TTriangles = array of TTriangle.

2.2.3.1 Процедуры манипуляции изображением ландшафта

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

• function GetScale(Triangles : TTriangles; Width, Height : Integer) : Single;

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

Triangles – треугольники ландшафта;

Width, Height – размеры области вывода.

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

• function MulTrianglesScale(Triangles : TTriangles; dX, dY : Integer; Scale : Real) : TTriangles;

Значения аргументов:

Triangles – исходные треугольники сцены;

dX, dY – экранные смещения по горизонтали и по вертикали;

Scale – коэффициент масштабирования.

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

• function RotatePointX(P, Center : TPoint3; Alpha : Real) : TPoint3;

• function RotatePointY(P, Center : TPoint3; Alpha : Real) : TPoint3;

• function RotatePointZ(P, Center : TPoint3; Alpha : Real) : TPoint3;

• function RotateTriangleX(T : TTriangle; Center : TPoint3; Alpha : Real) : TTriangle;

• function RotateTriangleY(T : TTriangle; Center : TPoint3; Alpha : Real) : TTriangle;

• function RotateTriangleZ(T : TTriangle; Center : TPoint3; Alpha : Real) : TTriangle;

• function RotateTrianglesX(Triangles : TTriangles; Center : TPoint3; Alpha : Real) : TTriangles;

• function RotateTrianglesY(Triangles : TTriangles; Center : TPoint3; Alpha : Real) : TTriangles;

• function RotateTrianglesZ(Triangles : TTriangles; Center : TPoint3; Alpha : Real) : TTriangles;

Аргументы всех функций однотипны: первый – объект, который должен быть повернут, второй – центр поворота; третий – угол поворота.

2.2.3.2 Z-буфер

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

TBuffer = array of array of Single.

Для работы с Z-буфером используются следующие процедуры:

• procedure CreateBuffer(out Buffer : TBuffer) – процедура для выделения памяти для Z-буфера;

• procedure ClearBuffer(var Buffer : TBuffer) – очистка буфера – его заполнение минимальным значением глубины;

• procedure FreeBuffer(var Buffer : TBuffer) – освобождение памяти, занимаемой буфером.

2.2.3.3 Буфер кадра

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

sWidth = 500;

sHeight = 650;

TScreen = array [0..sWidth - 1, 0..sHeight - 1] of Integer.

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

• procedure ClearScreenBuffer;

2.2.3.4 Процедуры визуализации ландшафта

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

• procedure FillTriangleNormal (T : TTriangle; var Buffer : TBuffer; dX, dY : Integer; Scale : Real; LightPos : TPoint3) – закрашивание треугольника T методом гранения. Используется Z-буфер Buffer, используются экранные смещения dX и dY, коэффициент масштабирования Scale, положение источника света задается точкой LightPos;

• procedure FillTriangleGouraud(T : TTriangle; var Buffer : TBuffer; dX, dY : Integer; Scale : Real; LightPos : TPoint3) – процедура, реализующая метод закраски Гуро. Аргументы аналогичны аргументам предыдущей процедуры;

• procedure FillTrianglePhong(T : TTriangle; var Buffer : TBuffer; dX, dY : Integer; Scale : Real; LightPos : TPoint3) – процедура, реализующая метод закраски Фонга. Аргументы аналогичны аргументам предыдущей процедуры;

• procedure DrawLightSource(P : TPoint3; dX, dY : Integer; Scale : Real; Buffer : TBuffer) – процедура для вывода окружности (по алгоритму Брезенхема), обозначающей положение источника света. Положение источника цвета задается точкой P. Остальные параметры аналогичны параметрам предыдущих функций;

• procedure DrawLine(S, E : TPoint; Color : TRGBColor) – процедура вывода линии по алгоритму ЦДА. Аргументы S и E – точки начала и конца отрезка, Color определяет цвет отрезка;

• procedure DrawTriangle(T : TTriangle) – вывод каркаса треугольника в буфер кадра;

• procedure DrawWireTriangles(Triangles : TTriangles; dX, dY : Integer; Scale : Real) – вывод треугольников ландшафта в каркасном режиме;

• procedure DrawSolidTriangles(Triangles : TTriangles; var Buffer : TBuffer; dX, dY : Integer; Scale : Real; Light : TLightType; LightPos : TPoint3; ShowLightSource : boolean) – вывод треугольников ландшафта в режиме сплошной закраски. Параметры процедуры:

  • Triangles – треугольники ландшафта;

  • Buffer – Z-буфер, используемый при визуализации;

  • dX, dY – экранные смещения по горизонтали и вертикали;

  • Scale – коэффициент масштабирования;

  • Light – определяет метод закраски треугольников. TLightType - перечисляемый тип, он определяется следующим образом:
    TLightType = (Normal, Gouraud, Phong);

  • LightPos – точка, задающая положение источника света;

  • ShowLightSource – логическая переменная, определяющая, отображается ли источник света;

• procedure DrawScene(Triangles : TTriangles; View : TViewType; Light : TLightType; LightPos : TPoint3; ShowLightSource : boolean; var Buffer : TBuffer; dX, dY : Integer; Scale : Real; DC : Integer; NHDC : HDC; HBMP : HBITMAP) – основная процедура, объединяющая в себе все методы м режимы вывода сцены.

Аргументы, которые не были описаны в процедуре DrawSolidTriangles:

• View – переменная определяющая режим отображения треугольников - каркасный или сплошной. TViewType – перечисляемый тип, его описание - TViewType = (Wire, Solid);

• DC, NHDC, HBMP – переменные, используемые при выводе изображения с помощью функции BitBlt.

2.2.3.2 Тип и структура файла для хранения ландшафта

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

В программе файлы ландшафтов описываются следующим образом: File of TTriangle;

Для работы с файлами ландшафта предусмотрена следующая функция:

function LoadTrianglesFromFile(FileName : string) : TTriangles;

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

2.2.3.3 Распределение программы по модулям

Таблица 2.2.3.3.1. Распределение программы «Просмотр ландшафта» по модулям

Имя модуля

Описанные типы

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

AboutUnit.pas

-

Модуль формы «О программе»

HelpUnit.pas

-

Модуль формы «Помощь»

L_ExtRegUnit.pas

-

Модуль регистрации расширения LND

L_FileUnit.pas

-

Модуль работы с файлами

L_GraphicsUnit.pas

TBuffer, TScreen, TViewType, TLightType

Модуль реализации процедур визуализации

L_MathUnit.pas

TRGBColor, TPoint3, TTriangle, TTriangles

Модуль реализации вычислений

LandscapePositionUnit.pas

-

Модуль формы «Положение ландшафта»

LightParamsUnit.pas

-

Модуль формы «Параметры источника света»

MainUnit.pas

-

Главный модуль программы

StatisticsUnit.pas

-

Модуль формы «Статистика»

ViewParamsUnit.pas

-

Модуль формы «Визуальные параметры»

2.2.3.4 Связи между модулями программы

Рис. 2.2.3.4.1. Связи между модулями программы «Просмотр ландшафта»

3. Технологическая часть

3.1 Выбор языка программирования

При разработке программного комплекса использовался язык программирования высокого уровня Object Pascal в составе среды визуального программирования Borland Delphi 7.

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

3.2 Описание программного комплекса

В состав программного комплекса входят два приложения: «Редактор карт» и «Просмотр ландшафта».

3.2.1 Программа «Редактор карт»

3.2.1.1 Общие сведения

Программа “Редактор карт” служит для создания ландшафтов на основе плоских карт изообластей. Данные карты могут быть созданы с помощью средств редактирования, предоставляемых “Редактором карт” или загружены в редактор из BMP-файлов (требуемая глубина цвета - 24 бита).

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

3.2.1.2 Интерфейс программы

При запуске программы на экране появляется главная и инструментальная формы.

Рис. 3.2.1.2.1. Формы, отображаемые при запуске «Редактора карт»

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

1. Файл:

• Создать - создать новую карту;

• Открыть - открыть уже существующую карту с помощью специального диалога;

• Сохранить - сохранить текущую карту в файл;

• Выход - прекратить работу с программой;

2. Инструменты и окна:

• Обработка карты - определяет видимость инструментальной формы "Обработка карты";

• Запустить "Просмотр ландшафта" - запускает приложение "Просмотр ландшафта", в которое загружается ландшафт, соответствующий текущей карте;

• Зарегистрировать собственное расширение - зарегистрировать в реестре расширение HCL, что даст возможность открывать файлы данного типа двойным щелчком мыши;

• Отменить регистрацию расширения - удалить из реестра информацию о расширении HCL;

3. О программе:

• О программе - вывод формы с некоторой информацией о данной программе;

• Помощь - вывод справочной информации о программе.

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

3.2.1.2.1 Инструментальная форма «Обработка карты»

Рис. 3.2.1.2.1.1. Инструментальная форма «Обработка карты»

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

Шаг разбиения на треугольники по горизонтали и вертикали задается с помощью полей ввода "Шаг по X" и "Шаг по Y". Единица измерения этих величин - пиксель.

Кнопка "Разбить на треугольники" служит для вывода плоских треугольников разбиения на карту.

Кнопка "Обновить карту" удаляет с карты выведенные треугольники.

Кнопка "Обновить ландшафт" предназначена для создания bitmap’а высот и, на его основе, с заданными шагами разбиения, - ландшафта.

Группа "Сглаживание ландшафта" позволяет сгладить ландшафт - придать его очертаниям большую плавность.

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

3.2.1.2.2 Инструменты главной формы

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

Если создается новая карта, то сначала необходимо задать соответствия "Цвет-высота", это делается с помощью кнопки "Добавить цвет" или нажатия клавиши Insert, когда фокус ввода находится на списке цветов. После выполнения этих действий появляется форма "Определение цвета", которая позволяет добавлять или редактировать существующие соответствия "Цвет-высота". Список цветов содержит информацию о существующих соответствиях. Его элементы можно удалять с помощью кнопки "Удалить цвет" или нажатия клавиши Delete, когда фокус ввода находится на списке. При удалении, области, занимаемые удаляемым цветом, заполняются цветом нулевой высоты.

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

• "Карандаш" - позволяет чертить произвольные кривые;

• "Кисть" - заполнение областей карты;

• "Отрезок";

• "Контурный прямоугольник";

• "Заполненный прямоугольник";

• "Контурный эллипс";

• "Заполненный эллипс".

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

Кроме описанных, существуют также следующие инструменты:

• "Ножницы" - для задания на карте прямой, определяющей вертикальную плоскость сечения. Просмотр сечений позволяет получать представление о ландшафте без его построения. Для получения разреза следует сначала задать секущую, а затем нажать на кнопку "Получить разрез" формы "Обработка карты";

• "Пипетка" - служит для определения цвета произвольного пикселя на карте.

3.2.1.3 Работа программы

3.2.1.3.1 Требования к расположению файлов программы

Исполняемый файл программы - MapEditorProj.exe. В папке, где размещен этот файл должна находиться пиктограмма HCL_Icon.ico. Эта пиктограмма потребуется при регистрации расширения HCL - она будет присвоена файлам с этим расширением. Кроме того, в основной папке MapEditorProj должна находиться программа LandscapeProj, т.к. в противном случае будет невозможна их интеграция. Желательно наличие в основной папке программы каталогов ScreenShots и Landscapes. В каталоге ScreenShots будут помещаться сохраненные изображения ландшафтов (в формате BMP, размер каждого файла ~ 1.23 МБ), создаваемые программой "Просмотр ландшафта". В каталоге Landscapes предполагается хранение файлов ландшафтов(*.lnd) и плоских карт(*.hcl), на основе которых строятся ландшафты.

3.2.1.3.2 Создание карт

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

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

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

3.2.1.3.3 Сохранение карт

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

• карта изообластей *.hcl;

• ландшафт *.lnd;

• *.bmp с изображением полученной карты.

3.2.1.3.4 Открытие карт

Возможна загрузка двух типов файлов - BMP и HCL. Загрузка может происходить тремя способами:

• через диалог открытия в самой программе;

• двойным щелчком по файлу (только для HCL-файлов после регистрации этого расширения);

• путем перетаскивания файла на форму приложения c помощью мыши.

3.2.2 Программа «Просмотр ландшафта»

3.2.2.1 Общие сведения

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

3.2.2.2 Интерфейс программы

При запуске программы на экране появляется главная и инструментальная формы.

Рис. 3.2.2.2.1. Формы, отображаемые при запуске «Просмотра ландшафта»

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

1. Файл:

   • Открыть - загрузить ландшафт с помощью диалога открытия файлов;

   • Выход - прекратить работу с программой;

2. Настройки и окна:

• Положение ландшафта - определяет видимость инструментальной формы "Положение ландшафта";

• Визуальные параметры - видимость формы "Визуальные параметры";

• Параметры источника света - видимость формы "Параметры источника света";

• Статистика - видимость формы "Статистика";

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

• Зарегистрировать собственное расширение - зарегистрировать в реестре расширение LND, что даст возможность открывать файлы данного типа двойным щелчком мыши;

• Отменить регистрацию расширения - удалить из реестра информацию о расширении LND;

3. О программе:

• О программе - вывод формы с некоторой информацией о данной программе;

• Помощь - вывод справочной информации о программе.

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

3.2.2.2.1 Инструментальная форма «Положение ландшафта»

Рис. 3.2.2.2.1.1. Инструментальная форма «Положение ландшафта»

Данная форма предназначена для управления положением ландшафта в пространстве. Она содержит следующие элементы управления:

• поле ввода "Приращение координат" - предназначено для задания величины шага перемещения ландшафта в экранной системе координат;

• поле ввода "Изменение масштаба" - задание величины процентного изменения коэффициента масштабирования;

• поле ввода "Приращение угла" - задание величины шага поворота ландшафта (задается в градусах);

• поле ввода "Центр вращение" - ввод трех координат центра вращения ландшафта в системе координат ландшафта;

• кнопки группы "Переместить" предназначены для перемещения и масштабирования ландшафта. Эти же действия можно выполнять с помощью мыши или клавиатуры. Мышь: перемещение осуществляется при удерживаемой клавише Shift, для масштабирования используется колесико мыши; Клавиатура: стрелочные клавиши для перемещения, клавиши '+', '-' для масштабирования;

• кнопки группы "Повернуть" используются для вращения ландшафта относительно соответствующих осей. Вращение ландшафта также может производиться с помощью мыши или клавиатуры. Мышь: горизонтальное смещение - поворот относительно оси Z, вертикальное - относительно X, горизонтальное с удерживаемой клавишей Alt - относительно Y; Клавиатура: относительно X - Insert и Delete, Y - Home и End, Z - PageUp и PageDown;

• кнопка "В исходное положение" предназначена для возвращения ландшафта и источника света в то положение, в котором они находились непосредственно после загрузки.

3.2.2.2.2 Инструментальная форма «Визуальные параметры»

Рис. 3.2.2.2.21. Инструментальная форма «Визуальные параметры»

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

• группа "Вид ландшафта" позволяет выбрать метод построения ландшафта;

• группа "Закраска" определяет метод визуализации треугольников ландшафта;

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

3.2.2.2.3 Инструментальная форма «Параметры источника света»

Рис. 3.2.2.2.3.1. Инструментальная форма «Параметры источника света»

Данная форма предназначена для управления источником света. Присутствуют следующие элементы интерфейса:

• поле ввода "Координаты" позволяет задавать координаты источника света в системе координат ландшафта;

• кнопки группы "Переместить" предназначены для переноса источника света вдоль соответствующих осей. Используется приращение координат, заданное на форме "Положение ландшафта". Перемещение источника возможно также и с помощью мыши и клавиатуры. Мышь (с удерживаемой клавишей Ctrl): горизонтальное перемещение - перемещение вдоль X, вертикальное - вдоль Y; Клавиатура (при удержании Ctrl): стрелочные клавиши - перемещение вдоль соответствующих осей, клавиши '+' и '-' - вдоль оси Z,

• кнопки группы "Повернуть" позволяют вращать источник света относительно соответствующих осей. Используется приращение угла с формы "Положение ландшафта". Вращение источника света предусмотрено также и с помощью клавиатуры (при удержании Ctrl): клавиши Insert и Delete, Home и End, Page Up и Page Down - вращение относительно осей X, Y и Z соответственно;

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

• группа "Вращение по таймеру" позволяет инициировать вращение источника света относительно выбранных осей по таймеру;

3.2.2.2.4 Инструментальная форма «Статистика»

Рис. 3.2.2.2.4.1. Инструментальная форма «Статистика»

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

Кнопка "Определить" позволяет определить число кадров вывода ландшафта, рассчитываемых и выводимых за 1 секунду.

3.2.2.3 Работа программы

3.2.2.3.1 Требования к расположению файлов программы

Исполняемый файл программы - LandscapeProj.exe. В папке, где размещен этот файл, должна находиться пиктограмма LND_Icon.ico. Эта пиктограмма потребуется при регистрации расширения LND - она будет присвоена файлам с этим расширением. Остальные требования аналогичны описанным в Разделе, касающемся программы “Редактор карт”.

3.2.2.3.2 Открытие файлов ландшафтов

Открытие файлов *.lnd возможно тремя способами:

• непосредственно через меню программы с помощью специального диалога;

• двойным щелчком по файлу ландшафта (после регистрации расширения);

• путем перетаскивания файла на форму приложения. После открытия файла просмотр ландшафта осуществляется с помощью уже описанных инструментальных форм.

3.2.3 Системные требования

Системные требования программного комплекса создаются главным образом приложением «Просмотр ландшафта», так как оно намного более требовательно к системным ресурсам, чем «Редактор карт». Они таковы:

• операционная система Windows 98/Me/2000/XP/2003 Server;

• процессор c тактовой частотой 400 МГц;

• объем оперативной памяти 64 МБ;

• видеокарта, обеспечивающая графическое разрешение 1024x768 и глубину цвета 24 бита;

• 35 МБ дискового пространства.

4. Экспериментально-исследовательская часть

Тестирование проводилось на компьютере Pentium IV - 2.67 GHz/768 Mb/GeForce4 MX-440, AGP 8x, DDR 128 Mb.

Были проведены следующие исследования:

1. исследование временных характеристик алгоритмов закраски – для 3 реализованных в работе алгоритмов были произведены исследования зависимости скорости работы от числа треугольников ландшафта;

2. исследование временных характеристик загрузки различных типов LND-файлов (текстового и типизированного);

3. исследование результатов использования метода группового кодирования при создании HCL-файлов.

В качестве тестовой карты в исследованиях № 1 и 2 была взята карта “Алтай.hcl”. Размеры карты “Алтай.hcl”: 430x409x39 пикселей (X x Y x Z).

4.1. Исследование № 1

Условия теста: в «Редактор карт» была загружена выбранная карта, далее, с изменяемым от 1 до 20 пикселей, шагом разбиения карты, строились ландшафты. Во время тестов никаких манипуляций с изображением ландшафта не производилось – оно оставалось в том положении, в котором находилось непосредственно после загрузки. Результаты теста приведены в таблице:

Таблица 4.1.1. Результаты исследования № 1

Метод закраски и
число кадров в секунду

Число
треугольников ландшафта

Шаг разбиения
(X x Y)

Однотонная

Гуро

Фонг

3

3

3

350064

1 x 1

8

7

6

87720

2 x 2

12

11

9

38896

3 x 3

17

15

10

22032

4 x 4

21

18

12

14104

5 x 5

24

21

12

9792

6 x 6

27

23

13

7316

7 x 7

30

25

14

5508

8 x 8

33

27

14

4416

9 x 9

35

28

14

3526

10 x 10

37

29

15

2964

11 x 11

39

30

15

2448

12 x 12

40

31

15

2112

13 x 13

41

32

15

1860

14 x 14

42

32

15

1624

15 x 15

43

33

16

1404

16 x 16

44

34

16

1248

17 x 17

46

35

16

1104

18 x 18

46

35

16

1012

19 x 19

49

36

16

924

20 x 20

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

Рис. 4.1.1. Результаты исследования № 1

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

• увеличение числа треугольников ландшафта вызывает уменьшение числа кадров, обрабатываемых за 1 секунду;

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

• при увеличении числа треугольников ландшафта разница в скорости работы рассмотренных алгоритмов уменьшается. Когда карта разбивается на треугольники с шагом 1 x 1, различие между алгоритмами становится минимальным – как по скорости работы, так и по качеству получаемого изображения (однотонная закраска выглядит менее качественно, чем закраска Фонга и Гуро).

4.2. Исследование № 2

При разработке программного комплекса формат файла LND (для хранения информации о треугольниках ландшафта) менялся. На начальной стадии разработки эти изменения касались только добавления новых полей в записи, хранимые в файле, тип файла был текстовым. Но постепенно карты ландшафтов, разрабатываемых в «Редакторе карт», становились все более сложными, они требовали все большей детализации. Поэтому возрастали объемы LND-файлов, При этом время загрузки значительно увеличивалось и становилось совершенно неудовлетворительным. В результате было принято решение изменить тип LND-файла, сделать его типизированным. После этого время загрузки LND-файлов в «Просмотр ландшафта» значительно сократилось. Следует заметить, что скорость записи информации в текстовый и типизированный файлы практически не отличается. Ниже приведены временные характеристики загрузки текстовых и типизированных LND-файлов.

Таблица 4.2.1. Результаты исследования № 2

Шаг разбиения (X x Y)

Тип LND-файла

Текстовый

Типизированный

Объем файла

(Мб)

Время загрузки (с)

Объем файла (Мб)

Время загрузки (с)

1 x 1

0,113

1,469

0,310

0,016

2 x 2

0,140

2,657

0,390

0,016

3 x 3

0,175

4,609

0,480

0,031

4 x 4

0,233

7,140

0,640

0,047

5 x 5

0,313

10,828

0,860

0,047

6 x 6

0,451

19,515

1,240

0,078

7 x 7

0,704

46,968

1,930

0,125

8 x 8

1,210

157,812

3,410

0,187

9 x 9

2,740

662,781

7,700

0,437

10 x 10

10,90

4102,093

30,71

1,922

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

Рис. 4.2.1. Результаты исследования № 2

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

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

• такое отличие времени загрузки, очевидно, объясняется постоянным преобразованием информации из символьного представления в числовое (работой функций Val или StrToFloat) при загрузке из текстового файла, в то время как при чтении из типизированного файла такого преобразования не требуется;

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

4.3 Исследование № 3

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

Демонстрация результатов использования метода была проведена на следующем наборе карт (размеры приведены в пикселях):

• Австралия.hcl (500 x 395);

• Алтай.hcl (430 x 409);

• Африка.hcl (700 x 730);

• Несжимаемый.hcl (200 x 200);

• Тест сглаживания.hcl (400 x 200);

• Южная Америка.hcl (735 x 1125).

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

Таблица 4.3.1. Результаты исследования № 3

Название карты

Размеры карты

(пиксели)

Размер BMP-файла

(Кб)

Размер HCL-файла

(Кб)

Отношение сжатия

Австралия.hcl

500 x 395

771

36

21:1

Алтай.hcl

430 x 409

687

78

9:1

Африка.hcl

700 x 730

1460

60

24:1

Несжимаемый.hcl

200 x 200

117

156

1:1,3

Тест сглаживания.hcl

400 x 200

312

10

31:1

Южная Америка.hcl

735 x 1125

3150

107

29:1

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

• применение метода группового кодирования в данной работе полностью оправдано, поскольку при использовании его в отношении карт изообластей высот, наблюдаются достаточно высокие показатели сжатия (от 9:1 до 29:1, карта «Тест сглаживания» не учитывается, так как она не является реальной картой). Единственным недостатком использования этого метода является незначительное увеличение времени загрузки кодированных файлов в программу «Редактор карт» (это не демонстрировалось в данном исследовании);

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

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

Разработанный программный комплекс отвечает всем предъявляемым к нему требованиям. Он обеспечивает возможность создания карт изообластей («Редактор карт») и построения в реальном времени на их основе трехмерных изображений ландшафтов («Просмотр ландшафта»). В нем реализованы все рассмотренные в данной работе алгоритмы машинной графики. Проведены исследования работы алгоритмов на различных наборах исходных данных. Тем не менее, существует множество путей усовершенствования описанного программного комплекса.

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

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

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

6. Список литературы

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

2. Порев В. Н. Компьютерная графика. – СПб.: БХВ-Петербург, 2002. – 432 с.: ил.

3. Никулин Е. А. Компьютерная геометрия и алгоритмы машинной графики. СПб.: БХВ-Петербург, 2003. – 560с.: ил.

4. Авдеева С.М., Куров А.В. Алгоритмы трехмерной машинной графики: Учебное пособие. – М.: Изд-во МГТУ им. Н.Э. Баумана, 1996. – 60 с.: ил.

5. Архангельский А.Я. Приемы программирования в Delphi. – М.: ООО «Бином-Пресс», 2003. – 784 с.: ил.

http://www.xdev.ru – «Генерация трехмерных ландшафтов».

Оглавление