Реферат: Генерация и построение изображений ландшафта в реальном времени

Московский Государственный Технический Университет им. Н.Э. Баумана

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

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

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

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

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

Тема:

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

Содержание:

Введение

Конструкторский раздел

Алгоритмы загрузки и генерации ландшафта

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

Генерация рельефа с помощью шума Перлина

Генерация рельефов с использованием холмового алгоритма

Алгоритмы визуализации ландшафта и окружающей среды

Использование карт освещенности

Наложение текстур

Смешивание текстур

Мипмапы

Билинейная фильтрация

Трилинейная фильтрация

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

Освещение

Модель освещения Фонга

Просчет теней

Перемещение и вращение камеры

Технологический раздел

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

Структура программы

Пользовательский интерфейс

Входные и выходные данные

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

Эксперементально-исследовательский раздел

Зависимость времени построение карты освещенности от количества источников света

Зависимость времени построения карты освещенности от ее размера размера

Эффективность использования карт освещения

Заключение

Список использованной литературы

Введение

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

И для каждой области необходимы свои собственные приложения, адаптированные для выполнения конкретных функций и задач. Благодаря этому в настоящее время постоянно появляются новые предметы изучения и исследования. Так, например, достаточно новым проявлением таких тенденций выступает машинная графика. Это целая наука, занимающаяся построением графических изображений посредством вычислительных систем. Появление машинной графики было вызвано многими важными задачами, среди которых присутствуют такие, как визуализация результатов, полученных при обработке данных, моделирование реальных процессов и др. Одной из важнейших областей, вызвавших формирование машинной графики как науки, послужила военная область. Для обучения пилотов самолетов, водителей танков и другой техники, подготовки к действиям в боевых условиях было необходимо создавать симуляторы реальных технических средств. Было гораздо безопасней посадить человека за симулятор для получения первоначальных навыков, чем на реальный объект. А для создания симуляторов потребовалось получать реалистичные изображения различных объектов, например местности, на которой ведутся учения, причем эти изображения должны быть получены в реальном времени, то есть так, чтобы в зависимости от действий обучаемого соответственно менялись и параметры системы, такие как положение на местности, высота и др. Через несколько лет стало понятно, что такие системы можно использовать не только для обучения новичков, но и для планирования реальных боевых операций на любой территории, о которой есть определенные данные. Об аналогичных системах мечтали и Географические Информационные Системы (ГИС).

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

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

Область 3D-моделирования можно разделить на 2 подобласти. Одна из них – это генерация трехмерных изображений в реальном времени, а другая – генерация высоко реалистичных трехмерных изображений. Высокореалистичные изображения требуют очень больших объемов вычислений, в то время как в первой подобласти применяется система условных допущений, позволяющая применять более простые алгоритмы, и тем самым значительно уменьшить объем вычислений, что, правда, сказывается на качестве изображения. Чтобы получить компромисс качества и скорости визуализации, я использовал комбинированный подход: вывод изображения в реальном времени, но просчет карты высот и карты освещенности заблаговременно. В скором будущем, вероятно, эти две области могут слиться, так как современные тенденции роста производительности вычислительных систем подают большие надежды. Даже сейчас уже изображения, построенные в реальном времени, становятся все более похожими на высокореалистичные изображения, появляются новые алгоритмы, совмещающие в себе обе области. Например, основная часть изображения строится алгоритмом, работающем в реальном времени, а некоторые участки, требующие специальной обработки – с помощью алгоритмов, строящих высокореалистичные изображения, что, однако не значительно сказывается на работе в реальном времени.

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

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

В данной записке речь пойдет о системе, производящей генерацию карты высот, карты освещенности и текстуры различными алгоритмами и построение изображения реалистичного трехмерного ландшафта в реальном времени. Для решения этой задачи, как уже было упомянуто, в машинной графике существует целая ветвь. Она занимается разработкой алгоритмов преобразования входных данных и построением на их основе ландшафтов. Мной было рассмотрено несколько подобных методик и алгоритмов. Для генерации карты высот: Шум Перлина, Холмовой алгоритм. Для создания карты освещенности: модель Фонга, просчет простых теней. Для вывода изображения в реальном времени: мипмапы, алгоритм z-буффера, текстурирование.

Конструкторский раздел

Алгоритмы загрузки и генерации ландшафта

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

Существует несколько основных принципов представления данных для хранения информации о ландшафтах:

·Первый - использование регулярной сетки высот (или еще другое название Карта Высот - HeightMap).

·Второе - использование иррегулярной сетки вершин и связей, их соединяющих (т.е. хранение простой триангулизированной карты).

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

В своем проект я выбрал первый способ представления ландшафтов.

Данные представлены в виде двухмерного массива. Уже заданы две координаты (x, y - по высоте и ширине массива), и третья координата задается значением в конкретной ячейке, это высота.

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

Плюсы данного подхода:

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

Также есть минусы:

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

Генерация рельефа с помощью шума Перлина

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

Изображение (или какой либо другой объем) – вне зависимости от диапазона значений его элементов – полностью накрывается сеткой, представляющей диапазон вещественных чисел. Таким образом, создается шум на сетке, представляющей по всему изображению значения между 0 и 4. Каждое число порождает линию сетки, а значит, все стороны каждого квадрата последней имеют длину, равную одной единице. Выбранный масштаб влияет на сложность шума. Большое число квадратов на сетке изображения создает более «плотно упакованный» шум, подобный белому шуму на экране плохо настроенного телевизора. Меньшее число квадратов на сетке порождает «клубящийся» шум, внешне похожий на облака.

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

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

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

Генерация рельефов с использованием Холмового алгоритма (Hill Algoritm)

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

· Создаем двухмерный массив и инициализируем его нулевым уровнем (заполняем все ячейки нолями);

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

· В выбранной точке "поднимаем" холм заданного радиуса;

· Возвращаемся ко второму шагу и так далее до выбранного количества шагов. От него потом будет зависеть внешний вид нашего ландшафта;

· Проводим нормализацию ландшафта;

· Проводим "долинизацию" ландшафта. Делаем его склоны более пологими.

Как сгенерировать один холм

Первый, второй и четвертый шаги тривиальны, пятый и шестой мы рассмотрим далее. Теперь же займемся третьим шагом. Что же означает "поднять" холм? Фактически холм - это в нашем случае половина шара, чем больше радиус - тем больше холм (и выше). Математически это похоже на перевернутую параболу. Что бы не быть голословным покажу как это выглядит:

здесь (x1, y1) - заданная точка, r - выбранный радиус, (x2, y2) - высота холма. Вот как выглядит одиночный холм:

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

Теперь у нас уже есть построенный ландшафт. Теперь пойдем далее - к нормализации полученного результата.

Нормализация Ландшафта

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

Чтобы нам это сделать мы производим следующие действия:

· сперва проходим по всему массиву и запоминаем наибольшее и наименьшее значения;

· после того, как мы узнали эти значения, мы заново проходим по всему ландшафту и производим нормализацию конкретных значений в пределы от 0 до 1. В виде формулы это выглядит так:

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

"Долинизация" ландшафта

Вообще говоря, данный ландшафт уже можно использовать. Что же мне еще не нравится? Конечно, ландшафт уже готов, но если присмотреться, то в нем достаточно мало долин. Склоны холмов излишне крутые, хочется сделать их более пологими. В этом нам поможет наш предыдущий шаг - нормализация. Все значения у нас сейчас находятся в пределах от 0 до 1. Идея "долинизации" состоит в следующем - взять от каждого значения квадратный корень. Это в большей степени влияет на средние значения, практически не затрагивая минимумов и максимумов. Графически это выглядит так:

А вот, как это повлияло на наш ландшафт:

Теперь с эти алгоритмом можно закончить.

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

· создаем простой, достаточно холмистый ландшафт;

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

Практически мы просто проходим весь массив высот и смещаем их на какое-то значение.

Теперь рассмотрим еще один тип ландшафтов - одиночные острова или горные плато, в зависимости от того, где мы затем "разместим" воду.

Модификация холмового алгоритма для островов

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

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

здесь size - размер карты высот, distance - расстояние, theta - угол. Помните - радиус должен быть меньше половины размера карты высот.

Поработав с этими величинами, мы можем получить довольно прилично выглядящий остров:

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

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

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

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

Полный алгоритм генерации карты высот

publicvoid GenerateHeightmap(int SizeX, int SizeY, GenMethod LandGenMethod, Convolution[] Convs, bool Smoothing, bool Valley, bool Island)

{

this.SizeX = SizeX;

this.SizeY = SizeY;

Heightmap = newdouble[SizeX, SizeY];

PerlinNoise Noise = newPerlinNoise(256);

double min = 99999;

double max = -99999;

double[,] ar = newdouble[SizeX, SizeY];

if (LandGenMethod == GenMethod.Perlin)

{

for (int i = 0; i < SizeX; i++)

for (int j = 0; j < SizeY; j++)

{

for (int l = 0; l < Convs.Length; l++)

{

if (Convs[l].Operation == Operation.Plus)

if (Convs[l].Coef != 0)

ar[i, j] += Noise.Generate(i, j, Convs[l].Coef);

else

if (Convs[l].Coef != 0)

ar[i, j] *= Noise.Generate(i, j, Convs[l].Coef);

}

if (max < ar[i, j]) max = ar[i, j];

if (min > ar[i, j]) min = ar[i, j];

}

}

else

{

Random rand = newRandom();

double theta;

double distanceX, distanceY;

double Radius;

double x, y;

double t;

min = 0;

for (int k = 0; k < Convs[0].Coef; k++)

{

Radius = rand.NextDouble() * (SizeX * Convs[1].Coef);

if (Island)

{

theta = rand.NextDouble() * Math.PI * 2;

t = rand.NextDouble();

distanceX = t * (SizeX * Convs[2].Coef - Radius);

distanceY = t * (SizeY * Convs[2].Coef - Radius);

x = SizeX / 2.0 + Math.Cos(theta) * distanceX;

y = SizeY / 2.0 + Math.Sin(theta) * distanceY;

}

else

{

x = SizeX * rand.NextDouble();

y = SizeY * rand.NextDouble();

}

for (int i = 0; i < SizeX; i++)

for (int j = 0; j < SizeY; j++)

{

t = Radius * Radius - ((i - x) * (i - x) + (j - y) * (j - y));

if (t > 0)

ar[i, j] += t;

if (max < ar[i, j]) max = ar[i, j];

//if (min > ar[i, j]) min = ar[i, j];

}

}

}

double coef = 1 / ((max - min));

for (int i = 1; i < SizeX-1; i++)

for (int j = 1; j < SizeY-1; j++)

{

if (Smoothing)

Heightmap[i, j] = (ar[i - 1, j - 1] + ar[i - 1, j] + ar[i - 1, j + 1] +

ar[i , j - 1] + ar[i , j] + ar[i , j + 1] +

ar[i + 1, j - 1] + ar[i + 1, j] + ar[i + 1, j + 1] - 9.0*min) / (9.0*(max-min));

else

Heightmap[i, j] = (ar[i, j] - min) * coef;

if (Valley)

Heightmap[i, j] = Math.Sqrt(Heightmap[i, j]);

}

Алгоритмы визуализации ландшафта и окружающей среды

Использование карт освещения

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

Сейчас под картами освещения чаще всего подразумевают одну из их разновидностей – текстурные карты освещения. Они представляют собой изображения, накладываемые при рисовании «поверх» основных текстур; при этом яркость точки на карте освещения используется для модуляции яркости точки основной текстуры. Этот процесс продемонстрирован на рисунке:

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

Часть набора карт освещения для небольшой сцены

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

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

R = R_текст R_осв

G = G_текст G_осв

B = B_текст B_осв

Где значение компонентов цвета лежат в диапазоне [0, 1].

Проверка: если карта освещенности будет полностью белой, то результирующая текстура будет такой же, как и основная текстура (компоненты везде домножаются на 1, т.к. белый цвет это R = 1, G = 1, B = 1)

если карта освещенности будет полностью черной, то результирующая текстура тоже черной (компоненты везде домножаются на 0, т.к. черный цвет это R = 0, G = 0, B = 0), что соответствует отсутствие источников освещения).

Создание карт освещения будет рассмотрено позже

Наложение текстур

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

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

В аффинном текстурировании (affine mapping ) используется линейная интерполяция:

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

,
где z 0 , z 1 – глубины концов отрезка, на котором проводится интерполяция.

Рис. Сравнение методов текстурирования

Все современные видеоадаптеры используют перспективно-корректное текстурирование.

Смешивание текстур

Смешивание с учетом цвета:

Смешивание без учета текстуры:

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

Расчет результирующего цвета каждого пикселя:

res=с_src *k₁ +c_dst *k₂

Параметр src определяет, как получить коэффициент k₁ исходного цвета пикселя, a dst задает способ получения коэффициента k₂ для цвета в буфере кадра. Для получения результирующего цвета используется следующая формула:, где с_src – цвет исходного пикселя, c_dst – цвет пикселя в буфере кадра (res, k₁ , k₁ , с_src, c_dst – четырехкомпонентные RGBA-векторы).

Приведем наиболее часто используемые значения аргументов src и dst.

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

Все прозрачные объекты выводятся после непрозрачных.

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

В нашем программном комплексе коэффициент ALPHA для воды = 0.45

А режим смешения SRC_ONE_MINUS_ALPHA

Мипмапы

Мипмапы (MipMaps) или Мип-карты — предрассчитанный, оптимизированный набор изображений связанных с одной текстурой и предназначенный для увеличения скорости рендеринга и улучшения качества изображения.

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

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

Предположим, что на модель натянута текстура размером 512х512. Модель стоит далеко от камеры и геометрические размеры на экране у нее малы (скажем 3 пикселя)

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

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

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

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

Генерацию мип-уровней можно сделать несколькими способами:

Самое простое, это указать видеокарте сгенерировать мип-уровни, но качество не будет очень хорошим, так как для генерации, скорее всего, будет использоваться простой Box фильтр (Используется в нашей программе).

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

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

Принцип действия

Создаётся так называемая MIP-пирамида — последовательность текстур с разрешением от максимального до 1×1. Например: 1×1, 2×2, 4×4, 8×8, 16×16, 32×32, 64×64, 128×128, 256×256 и 512×512. Каждая из этих текстур называется MIP-уровнем или уровнем детализации

На всех этих текстурах находится одно и то же изображение. Таким образом, MIP-текстурирование увеличивает расход видеопамяти на треть: .

При наложении текстур вычисляется расстояние до объекта, соответственно находится номер текстуры как ,

где resolution - разрешение виртуальной камеры (количество пикселей, которое будет в объекте размером в 1 ед., расположенном в 1 ед. от камеры),

texelsize — размер текселя в единицах трёхмерного мира,

dist — расстояние до объекта в тех же единицах,

mip bias — число, позволяющее выбирать более или менее детальную текстуру, чем даёт формула. Эта цифра округляется до целого, и текстура с соответствующим номером (нулевая — самая детальная, первая — вдвое меньшая и т. д.) накладывается на объект.

Недостатки, способы решения

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

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

Есть сразу несколько способов решения этого (начиная с наименее качественного):

1. Установить наиболее комфортное значение mip bias — числа, которое отвечает за выбор номера текстуры в пирамиде. Если оно отрицательное, видеоплата берёт более детальные текстуры, если положительное — менее детальные.

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

Наконец, видна чёткая граница между MIP-уровнями. Это решается трилинейной фильтрацией.

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

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

MIP-текстурирование, повышая чёткость изображения и процент попаданий в кэш на дальних расстояниях, имеет серьёзный недостаток: ясно видны границы раздела между MIP-уровнями. Трилинейная фильтрация позволяет исправить этот недостаток ценой некоторого снижения резкости текстур.С недостаточной резкостью борются, устанавливая отрицательный mip bias — то есть, текстуры берутся более детальные, чем нужно было бы без трилинейной фильтрации.

Алгоритм, использующий Z-буфер

Это один из простейших алгоритмов удаления невидимых поверхностей. Работает этот алгоритм в пространстве изображения. Идея z-буфера является простым обобщением идеи о буфере кадра. Буфер кадра используется для запоминания атрибутов (интенсивности) каждого пикселя в пространстве изображения, z-буфер – это отдельный буфер глубины, используемый для запоминания координаты z, или глубины каждого видимого пикселя в пространстве изображения.

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

Основной недостаток алгоритма – большой объем требуемой памяти. Если сцена подвергается видовому преобразованию и отсекается до фиксированного диапазона координат г значений, то можно использовать z-буфер с фиксированной точностью. Для обработки информации о глубине достаточно 32 бит. z-буфер размером 1280*1024*32 бит требует 40 Mb памяти. Но в настоящее время этот недостаток перестал быть актуальным из-за удешевления и миниатюризации элементов памяти.

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

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

При визуализации изображения, как пиксельная информация, так и глубина усредняются. В этом методе требуются очень большие объемы памяти. Например, изображение размером 512х512х24 бита, использующее z-буфер размером 20 бит на пиксель, разрешение которого повышено в 2 раза по осям х и у, и на котором устранена ступенчатость методом равномерного усреднения, требует почти 6 Mb памяти.

Описание алгоритма z-буфера таково:

Заполнить буфер кадра фоновым значением интенсивности или цвета.

Заполнить z-буфер минимальным значением z.

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

Для каждого Пиксель(x, y) в многоугольнике вычислить его глубину z(х, у).

Сравнить глубину z(x, у) со значением Z буфер(x, у), хранящимся в z-буфере в этой же позиции.

Если z(х, у) > Z буфер(x, у), то записать атрибут этого многоугольника (интенсивность, цвет и т. п.) в буфер кадра и заменить Z буфер( х, у) на z(х, у).

В противном случае никаких действий не производить.

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

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

ах + by + cz + d = 0

z = -(ах + by + d)/с

Для сканирующей строки y = const. Поэтому глубина пикселя на этой строке, у которого х1 = x + Dх, равна

z1 – z = -(ах1 + d)/c + (ах + d)/с = а(х – х1)/с

или

z1 = z-(a/c)Dx

Но Dx = 1, поэтому z1 = z – (а/с).

Освещение

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

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

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

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

,

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

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

Для точечного источника света можно еще усовершенствовать модель отражения, если учесть, что энергия уменьшается пропорционально квадрату расстояния и пропорционально расстоянию.

Кроме того, в данной программе вместо интенсивности света используется расширенная величина цвет света, которая состоит из трех компонент (R, G, B)

Итак, цвет в данной точке для одного источника направленного освещения рассчитывается по следующей формуле:

Для точечного источника света:

Где I – это интенсивности источников света (R, G, B)

K_d - способность материала отражать диффузный свет (тоже имеет R, G, B)

d – Расстояние от источника света до рассматриваемой точки поверхности,

c₁ , c₃ , c₃ – произвольные коэффициенты угасания, которые находятся эмпирическим путем

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

,

,

,

или

.

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

.

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

,

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

.

Модель освещения Фонга и просчет теней

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

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

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

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

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

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

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

,

.

где – координаты векторов .

В данном случае необходимости в вычислении некоторых величин на каждом шаге нет. Так что их можно вычислить заранее

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

.

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

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

Просчет теней

Для построения сплошных теней на этапе вычисления «локальной» интенсивности цвета в точке объекта проверяется «видимость» каждого источника света из этой точки.

Принцип работы алгоритма.

1. Из проверяемой точки строится луч, направленный на источник света.

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

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

4. Если пересечений не найдено, точка не в тени. При расчете ее цвета учитываем

проверяемый источник.

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

Вычисление точки пересечения луча с Треугольником для построения тени.

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

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

Q(x, y, z) = Ax + By + Cz +D = 0. (2.2.5.3)

Здесь коэффициенты A, B, C совпадают с координатами нормали к этой плоскости. Координаты нормали плоскости совпадают с координатами нормали треугольника, которые мы посчитали на этапе загрузки сцены.

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

D = –Ax –By – Cz. (2.2.5.4)

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

Теперь для нахождения точки пересечения подставим уравнения луча в

уравнение плоскости.

A (x₁ + at) + B (y₁ + bt) + C (z₁ + ct) + D = 0

Откуда получим

t = – (Ax₁ + By₁ + Cz₁ + D) / (Aa + Bb + Cc) (2.2.5.5)

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

Для нахождения координат точки пересечения надо подставить найденное значение параметра t в уравнения луча (2). Назовем точку пересечения D. Мы получим координаты x_D , y_D , z_D .

Теперь необходимо определить, попала ли точка D внутрь треугольника. Найдем координаты векторов AB, BC, CA (A, B, C – вершины треугольника) и координаты векторов AD, BD, CD. Затем найдем три векторных произведения:

nA = ABxAD,

nB = BCxBD, (2.2.5.6)

nC = CAxCD.

Эти вектора будут коллинеарные. Если все три вектора сонаправлены, то точка D лежит внутри треугольника. Сонаправленность определяется равенству знаков соответствующих координат всех трех векторов.

Операцию проверки принадлежности точки D треугольнику ABC можно ускорить. Если ортогонально спроецировать треугольник ABC и точку D на одну из плоскостей xOy, yOz или xOz, то попадание проекции точки в проекцию треугольника будет означить попадание самой точки в треугольник (конечно же, если уже известно, что точка D лежит в плоскости, содержащей треугольник ABC). При этом число операций заметно сокращается. Так для поиска координат всех векторов нужно искать по две координаты на каждый вектор, а при поиске векторных произведений нужно искать только одну координату (остальные равны нулю).

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

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

Остается добавить, что для проецирования лучше выбирать ту из плоскостей, площадь проекции треугольника на которую больше. При таком условии исключается случай проецирования треугольника в отрезок (при условии, что проверяемый треугольник не вырожден в отрезок). Кроме того, при увеличении площади проекции уменьшается вероятность ошибки. Для определения такой плоскости проецирования достаточно проверить три координаты нормали треугольника. Если z-координата нормали больше (по абсолютному значению) x и y, то проецировать надо на плоскость xOy. Если y больше чем x и z, то проецируем на xOz. В оставшемся случае – на yOz.

bool RayTriangleIntersect(Vector RayPos, Vector RayDir, Vector P1, Vector P2, Vector P3,

outVector ResultPoint, outVector ResultNormal)

{

constdouble EPSILON2 = 0.00001;

Vector v1 = P2 - P1;

Vector v2 = P3 - P1;

Vector pvec = RayDir ^ v2;

double det = v1 * pvec;

ResultPoint = newVector();

ResultNormal = newVector();

if ((det < EPSILON2) && (det > -EPSILON2))

{

returnfalse;

}

double invDet = 1 / det;

Vector tvec = RayPos - P1;

double u = (tvec * pvec) * invDet;

if ((u < 0) || (u > 1))

returnfalse;

else

{

Vector qvec = tvec ^ v1;

double v = (RayDir * qvec) * invDet;

if ((v < 0) || (u+v > 1))

returnfalse;

double t = (v2 * qvec) * invDet;

if (t > 0)

{

ResultPoint = RayPos + RayDir * t;

ResultNormal = v1 ^ v2;

returntrue;

}

else

returnfalse;

}

}

Перемещение и вращение камеры

Представление камеры с помощью векторов:

Матрица вращения вокруг единичного вектора vна угол омега:

Вычисление матрицы камеры:

// вектор бинормали

Vector sideVec(viewMat.p[0], viewMat.p[1], viewMat.p[2]);

//вектор нормали (указывает "верх" камеры)

Vector upVec(viewMat.p[3], viewMat.p[4], viewMat.p[5]);

// векторнаправления

Vector dirVec(viewMat.p[6], viewMat.p[7], viewMat.p[8]);

// построение матрицы поворота (по формуле выше на рисунке)

Matrix Rot(camAng.y, (dirVec ^ upVec).Normalize());

// добавление вращения по оси Y (он указывает верх камеры), которое зависит от смещение мыши по х

Rot.AddRotationY(-camAng.x);

// обновление векторов камеры (домножение на матрицу поворота)

upVec = Rot * upVec;

dirVec = Rot * dirVec;

sideVec = Rot * sideVec;

// обновление матрицы камеры

viewMat.p[0] = sideVec.x; viewMat.p[1] = sideVec.y; viewMat.p[2] = sideVec.z;

viewMat.p[3] = upVec.x; viewMat.p[4] = upVec.y; viewMat.p[5] = upVec.z;

viewMat.p[6] = dirVec.x; viewMat.p[7] = dirVec.y; viewMat.p[8] = dirVec.z;

// обновление матрицы камеры с учетом ее позиции

float m[16] = {

viewMat.p[0], viewMat.p[3], -viewMat.p[6], 0,

viewMat.p[1], viewMat.p[4], -viewMat.p[7], 0,

viewMat.p[2], viewMat.p[5], -viewMat.p[8], 0,

-(viewMat.p[0]*camSrc.x + viewMat.p[1]*camSrc.y + viewMat.p[2]*camSrc.z),

-(viewMat.p[3]*camSrc.x + viewMat.p[4]*camSrc.y + viewMat.p[5]*camSrc.z),

(viewMat.p[6]*camSrc.x + viewMat.p[7]*camSrc.y + viewMat.p[8]*camSrc.z),

1

};

Технологический раздел

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

После подготовки и изучения алгоритмов встал еще ряд вопросов:

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

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

-какую технологию программирования положить в основу проекта.

В качестве операционной системы была выбрана система WidowsXP и более новые Vista и 7. Это обусловлено тем, что WindowsXP — самая распространенная на сегодняшний день ОС. И для нее написано больше всего IDE и программного обеспечения для разработки.

Программный комплекс состоит из двух модулей: редактора и просмотра ландшафта.

Языком программирования для написания программы «Редактор» был выбран язык C#. С помощью C# можно быстро писать программы под Windows или интернет-приложения, благодаря удобному синтаксису, интеллектуальным подсказкам и управляемому коду. Используя управляемый код, не нужно заботится о сборке мусора, об указателях и о некоторых базовых структурах и алгоритмах – все это уже реализовано. Минусом разработки на C# .Net является низкая производительность программ. Но это уже компенсируется современным аппаратным обеспечением. Кроме того, в редакторе нам и не требуется высокая производительность, потому что там рассчитываются только карты (изображение) и нет интерактивных элементов, в отличие от программы просмотра.

Языком программирования для написания программы просмотра ландшафтов был выбран язык С++. Язык С++ сочетает в себе удобство с точки зрения структуры кода (объекты, перегрузка функций, операторов, обработка исключений и др.) и программирование на низком уровне (арифметика указателей, ассемблерные вставки, выравнивание памяти, директивы компилятора). Кроме того, среда разработки VisualStudio 2008 может сильно оптимизировать код, используя раскрытие циклов, встраивание функций, использование суперскалярных команд процессора SSE и др., тем самым увеличив производительность.

Минусы языка С++ тоже имеются: ручная сборка мусора (возможные утечки памяти из-за этого).

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

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

Выбор библиотек, поддерживающих аппаратные возможности современных компьютеров, был не велик: Direct3D или OpenGL. Я выбрал OpenGL, как более распространенную и простую для понимания. OpenGL является открытым графическим стандартом, разработанным и утвержденным несколькими ведущими фирмами, такими как Nvidiacorporation, AMD, Intel, и др. В число ее достоинств входят стабильность, надежность, переносимость, простота использования. Хотя следует отметить, что Direct3D немного выигрывает в скорости и в возможностях.

Структура программы

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

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

// загрузка настроек, таких как путь к карте высот, карте освещенности и текстуре ландшафта и неба, из файла

voidLoadSettings(char *FileName)

// В этом событии указываются действии, совершаемые в момент старта программы

boolappPreInit()

// В этом событии указывается последовательность действий при визуализации каждого кадра (несколько раз в секунду)

boolappRender()

// В этом событии указываются действия, совершаемые при закрытии программы (освобождение ресурсов)

voidappShutdown()

// Обработчик нажатий клавиш

boolProcessKey(HWNDhWnd,WPARAMwParam)

Terrain – Описывает непосредственно геометрию ландшафта (вершины, индексы, нормали), текстуры ландшафта, неба, воды.

Также этот класс отвечает за визуализацию всех этих объектов.

DynamicCamera – Реализация камеры, ее передвижения, вращения, а также связь с ландшафтом (передвижение по нему).

Font – модуль для инициализации и вывода текста на экран

Render – модуль для реализации визуализации в 3-мерном и 2-мерном режимах

Image – модуль для загрузки и обработки изображений

Texture – модуль для загрузки изображений и инициализаций структур

Vector – модуль для работы с векторами (сложение, вычитание, скалярное произведение, векторное произведение)

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

Base – модуль для включения основных стандартных библиотек

Win32 – модуль, связанный с включением библиотек среды Windows

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

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

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

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

Программа «Редактор ландшафта»

// в данной структуре вместо целого значения цвета используется вектор с реальными координатами

classLight

{

publicVector Ambient;

publicVector Diffuse;

publicVector Mirror;

public Light() { }

public Light(Vector Ambient, Vector Diffuse, Vector Mirror)

{

this.Ambient = Ambient;

this.Diffuse = Diffuse;

this.Mirror = Mirror;

}

}

classDirLight : Light

{

publicVector Dir;

public DirLight() { }

public DirLight(Vector Ambient, Vector Diffuse, Vector Mirror, Vector Dir)

: base(Ambient, Diffuse, Mirror)

{

this.Dir = Dir;

}

}

classPointLight : Light

{

publicVector Point;

publicdouble c1, c2, c3;

public PointLight(Vector Ambient, Vector Diffuse, Vector Mirror, double c1, double c2, double c3, Vector Point)

: base(Ambient, Diffuse, Mirror)

{

this.Point = Point;

this.c1 = c1;

this.c2 = c2;

this.c3 = c3;

}

}

classMaterial

{

publicVector Ambient;

publicVector Diffuse;

publicVector Mirror;

public Material(Vector Ambient, Vector Diffuse, Vector Mirror)

{

this.Ambient = Ambient;

this.Diffuse = Diffuse;

this.Mirror = Mirror;

}

}

classPerlinNoise

{

int TableSize;

int TableMask;

structvec2

{

publicdouble x, y;

public vec2(double x, double y) { this.x = x; this.y = y; }

};

vec2[] VectorTable;

byte[] lut;

public PerlinNoise(int TableSize)

void setup()

// вычисляется значение шумовой функции (в данной программе высота) с коэффициентом scale (чем больше scale, тем более изломанная карта) в координате xy

publicdouble Generate(double x, double y, double scale)

publicdouble Generate(int x, int y, double scale)

}

classLandscape

{

GenMethod LandGenMethod;

Convolution[] Convs;

bool Smoothing;

bool Valley;

bool Island;

publicdouble[,] Heightmap;

int[,] Lightmap;

int[,] Colormap;

publicint SizeX, SizeY;

int LSizeX, LSizeY;

int CSizeX, CSizeY;

Vector[,] Points;

int[] Indexes;

Vector[] FaceNormals;

Vector[,] VertexNormals;

Vector Pos;

Vector Dimen;

publicMaterial Ground;

public Landscape() { }

// генерирует карту высот с размером SizeX, SizeY, по методу LandGenMethod c коэффициентами Convs, со сглаживанием или нет (Smoothing) с долинизацией (Valley)

publicvoid GenerateHeightmap(int SizeX, int SizeY, GenMethod LandGenMethod, Convolution[] Convs, bool Smoothing, bool Valley, bool Island)

// строить трехмерную модель ландшафта с размерами Dimen.X Dimen.Y Dimen.Z

// Также просчитываются нормали к граням FaceNormals и к вершинам VertexNormals

publicvoid BuildMesh(Vector Dimen)

// Цвет данной точки ландшафта с координатами Pos нормальную Normal добавляетсякрезультирующему Color

publicvoid AddColor(Vector Pos, Vector Normal, Light Source, refint Color)

// построение карты освещенности с учетом Sources источников света. Размеркарты SizeX*Size SizeY*Size

publicvoid BuildLightmap(Light[] Sources, int Size)

// построение карты теней и смешение ее с картой освещенности

publicvoid BuildShadowmap(Light[] Lights, int Size)

// построение "цветовой" карты (или текстуры) на основе массива Colors

publicvoid GenerateColormap(Color[] Colors, int Size)

// сохранение карты высот в файл BMP

publicvoid SaveHeightmap(string FileName, outBitmap Result)

// сохранение карты освещенности в файл BMP

publicvoid SaveLightmap(string FileName, outBitmap Result)

// сохранениетекстурывфайл BMP

publicvoid SaveColormap(string FileName, outBitmap Result)

}

Пользовательский интерфейс

Редактор ландшафта

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

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

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

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

Шкала цветов используется при построении текстуры ландшафта (каждому значению высоты соответствует цвет из этой шкалы цветов)

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

Флажок «Остров» используется для генерации таких типов ландшафтов, на границе которых высота равна нулю (для плавного спуска в воду)

Флажок «Долина» используется для долинизации ландшафта

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

Для каждого источника света также можно настривать цвет фонового освещения, диффузного освещения, вектор направления (или позицию с коэффициентами угасания c1 c2 c3 для точечных источников)

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

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

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

· загрузить уже имеющееся изображение в формате BMP (поддерживается работа только с 24-битным цветом).

· сгенерировать новую карту

При создании карты высот, автоматически создаются карта освещенности и текстура.

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

Сохранение производится автоматически при нажатии на кнопку «Генерировать». При сохранении создаются 3 файла:

· карта высот *.bmp

· карта освещенности *.bmp

· текстура *.bmp

Программа LandViewer

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

W, A, S, D – навигация по пространству

[ ] – увеличение/уменьшение уровня моря.

z, x, c – включение/отключение соответственно текстуры, карты освещенности и карты деталей.

v – привязка камеры к поверхности ландшафта (нельзя будет опуститься под поверхность) .

Входные и выходные данные

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

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

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

Рекомендуемые требования к аппаратному обеспечению:

· x86-совместимый процессор Intel или AMD с тактовой частотой 1 ГГц и выше;

· Оперативная память объемом от 512 Гб и выше;

· Видеоадаптер, совместимый с OpenGL 1.2.

· Операционная система: WindowsXPили выше

Исследовательский раздел

Тестирование проводилось на компьютере IntelCore 2 Duo 3 Hz, 1 GbRAM, GeForce 8800 Gts 320 Mb.

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

Зависимость времени построение карты освещенности от количества источников света

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

Зависимость времени построения карты освещенности от ее размера

Из данной зависимости становится понятным, что затрачиваемое время на просчет карты освещенности ~ 2^N, где N – размер карты.

Эффективность использования карт освещения

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

Двухпроходное рисование	Мультитекстурирование

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

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

Сравнение временных затрат на наложение карт освещения и использование простой модели освещения

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

Заключение

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

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

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

Тем не менее, существует множество путей усовершенствования описанного программного комплекса.

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

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

Внесение данных нововведений, несомненно, добавило бы реалистичности в генерируемый мир и расширило бы его возможности.

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

1.Г.Снук — 3D ландшафты в реальном времени на С++ и DirectX9

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

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

4.Свободная энциклопедия Wikipedia. http://ru.wikipedia.org/

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