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

Содержание:
Введение
Конструкторский раздел
Алгоритмы загрузки и генерации ландшафта
Представление данных о ландшафте
Генерация рельефа с помощью шума Перлина
Генерация рельефов с использованием холмового алгоритма
Алгоритмы визуализации ландшафта и окружающей среды
Использование карт освещенности
Наложение текстур
Смешивание текстур
Мипмапы
Билинейная фильтрация
Трилинейная фильтрация
Алгоритм z-буффера
Освещение
Модель освещения Фонга
Просчет теней
Перемещение и вращение камеры
Технологический раздел
Выбор среды разработки и технологий программирования
Структура программы
Пользовательский интерфейс
Входные и выходные данные
Системные требования
Эксперементально-исследовательский раздел
Зависимость времени построение карты освещенности от количества источников света
Зависимость времени построения карты освещенности от ее размера размера
Эффективность использования карт освещения
Заключение
Список использованной литературы
Введение
Все большую роль в современной жизни играют компьютеры. После того как они вышли за пределы военных и научно-исследовательских организаций, они приобрели статус неотъемлемой части практически любого современного вида деятельности, будь то производство машин или операции с ценными бумагами, проектирование зданий или транспортировка грузов, обучение или индустрия развлечений. Компьютеры используются везде.
И для каждой области необходимы свои собственные приложения, адаптированные для выполнения конкретных функций и задач. Благодаря этому в настоящее время постоянно появляются новые предметы изучения и исследования. Так, например, достаточно новым проявлением таких тенденций выступает машинная графика. Это целая наука, занимающаяся построением графических изображений посредством вычислительных систем. Появление машинной графики было вызвано многими важными задачами, среди которых присутствуют такие, как визуализация результатов, полученных при обработке данных, моделирование реальных процессов и др. Одной из важнейших областей, вызвавших формирование машинной графики как науки, послужила военная область. Для обучения пилотов самолетов, водителей танков и другой техники, подготовки к действиям в боевых условиях было необходимо создавать симуляторы реальных технических средств. Было гораздо безопасней посадить человека за симулятор для получения первоначальных навыков, чем на реальный объект. А для создания симуляторов потребовалось получать реалистичные изображения различных объектов, например местности, на которой ведутся учения, причем эти изображения должны быть получены в реальном времени, то есть так, чтобы в зависимости от действий обучаемого соответственно менялись и параметры системы, такие как положение на местности, высота и др. Через несколько лет стало понятно, что такие системы можно использовать не только для обучения новичков, но и для планирования реальных боевых операций на любой территории, о которой есть определенные данные. Об аналогичных системах мечтали и Географические Информационные Системы (ГИС).
В ответ на эти запросы сначала появилась такая область машинной графики, как «трехмерное моделирование»(3D-моделирование), а затем, некоторое время спустя, ветвь 3D-моделирования, которая занималась проектированием и созданием трехмерных реалистичных изображений ландшафтов.
В настоящее время 3D-моделирование является важнейшей областью машинной графики, так как построение трехмерного изображения, близкого к реальному, является достаточно сложной задачей. Но, благодаря обширному кругу потребителей и невообразимо быстрому росту производительности вычислительных систем, эта область активно развивается.
Область 3D-моделирования можно разделить на 2 подобласти. Одна из них – это генерация трехмерных изображений в реальном времени, а другая – генерация высоко реалистичных трехмерных изображений. Высокореалистичные изображения требуют очень больших объемов вычислений, в то время как в первой подобласти применяется система условных допущений, позволяющая применять более простые алгоритмы, и тем самым значительно уменьшить объем вычислений, что, правда, сказывается на качестве изображения. Чтобы получить компромисс качества и скорости визуализации, я использовал комбинированный подход: вывод изображения в реальном времени, но просчет карты высот и карты освещенности заблаговременно. В скором будущем, вероятно, эти две области могут слиться, так как современные тенденции роста производительности вычислительных систем подают большие надежды. Даже сейчас уже изображения, построенные в реальном времени, становятся все более похожими на высокореалистичные изображения, появляются новые алгоритмы, совмещающие в себе обе области. Например, основная часть изображения строится алгоритмом, работающем в реальном времени, а некоторые участки, требующие специальной обработки – с помощью алгоритмов, строящих высокореалистичные изображения, что, однако не значительно сказывается на работе в реальном времени.
Как уже было сказано, алгоритмы 3D-моделирования делятся на две группы. В первую входят такие алгоритмы, как алгоритм Робертса, алгоритм Варнока, алгоритм, использующий z-буфер, которые в свою очередь используют простейшие алгоритмы построения линий, треугольников, закрашивание замкнутых областей. Также к этой группе можно отнести алгоритмы, выполняющие текстурирование и отсечение. Последние так же используются и для второй группы алгоритмов, обеспечивающих построение высокореалистичных изображений. В эту группу входят такие алгоритмы как трассировка лучей.
Для ускорения построения изображений в реальном времени осуществляется аппаратная реализация части алгоритмов, например в современных системах аппаратно реализованы алгоритмы построения и текстурирования треугольников, удаления ступенчатости и другие. Это находит отражение в таких библиотеках, как OpenGL и Direct3D. Эти библиотеки, использующие аппаратно реализованные алгоритмы, во-первых значительно увеличивают эффективность программы (действия аппаратно выполняются гораздо быстрее), во-вторых позволяют значительно разгрузить центральный процессор, который может взять на себя в этом случае некоторые дополнительные функции, и в-третьих, позволяют программисту абстрагироваться от простейших алгоритмов, давно изученных и оптимизированных, и направить свою умственную деятельность на более сложные алгоритмы с целью их улучшения и, возможно, создания новых. Эффективность такого рода библиотек подтверждает массовость их применения (практически не осталось систем, не использующих какие-либо из этих библиотек) и огромный прорыв в индустрии машинной графики (в частности в индустрии компьютерных развлечений) после перехода к аппаратной реализации алгоритмов машинной графики. Даже такие системы-гиганты как 3DStudioMax, LightWave, AutoCAD, которые, казалось бы, должны были давно обзавестись собственными библиотеками, используют стандартные OpenGL и Direct3D.
В данной записке речь пойдет о системе, производящей генерацию карты высот, карты освещенности и текстуры различными алгоритмами и построение изображения реалистичного трехмерного ландшафта в реальном времени. Для решения этой задачи, как уже было упомянуто, в машинной графике существует целая ветвь. Она занимается разработкой алгоритмов преобразования входных данных и построением на их основе ландшафтов. Мной было рассмотрено несколько подобных методик и алгоритмов. Для генерации карты высот: Шум Перлина, Холмовой алгоритм. Для создания карты освещенности: модель Фонга, просчет простых теней. Для вывода изображения в реальном времени: мипмапы, алгоритм z-буффера, текстурирование.
Конструкторский раздел
Алгоритмы загрузки и генерации ландшафта
Представление данных о ландшафте
Существует несколько основных принципов представления данных для хранения информации о ландшафтах:
·Первый - использование регулярной сетки высот (или еще другое название Карта Высот - HeightMap).
·Второе - использование иррегулярной сетки вершин и связей, их соединяющих (т.е. хранение простой триангулизированной карты).
·Третий - хранение карты ландшафта, но в данном случае хранятся не конкретные высоты, а информация об использованном блоке. В этом случае создается некоторое количество заранее построенных сегментов, а на карте указываются только индексы этих сегментов.
В своем проект я выбрал первый способ представления ландшафтов.
Данные представлены в виде двухмерного массива. Уже заданы две координаты (x, y - по высоте и ширине массива), и третья координата задается значением в конкретной ячейке, это высота.
Обычно карту высот хранят в файлах изображений. Это позволяет легко вносить изменения и более-менее наглядно просматривать данные. Тогда двумя координатами будет положение конкретного пикселя на картинке, а третья координата будет представлена цветом (чем выше значение, прямая зависимость от яркости пикселя - тем больше значение высоты для этой точки). Обычно такие картинки содержатся в монохромном варианте. С помощью этого способа можно представить достаточно обширные пространства.
Плюсы данного подхода:
Простота реализации: легкость нахождения координат (и высоты) на карте, простая генерация ландшафта по карте высот или методом шума Перлина.
Наглядность: в любой программе просмотра графических файлов можно сразу увидеть или изменить всю информацию.
Скорость: благодаря конвейерной архитектуре процессора, просчет и вывод таких карт высот производится очень быстро (динамическое освещение, т.к освещенность вершины напрямую зависит от расстояния от этой вершины до источника освещения).
Также есть минусы:
Большое количество избыточных данных (особенно для поверхностей, близких к плоским).

Генерация рельефа с помощью шума Перлина
При разработки данной программы возник вопрос: откуда брать информацию для генерации карты высот? Конечно же можно просто загружать монохромное изображение и на его основе генерировать ландшафт(об этом говорилось выше).Но если нужно каждый раз генерировать разные карты высот (например, для компьютерных игр или демонстрационных программ, таких как эта), то на помощь приходит следующий метод на основе шума Перлина.
Изображение (или какой либо другой объем) – вне зависимости от диапазона значений его элементов – полностью накрывается сеткой, представляющей диапазон вещественных чисел. Таким образом, создается шум на сетке, представляющей по всему изображению значения между 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 - угол. Помните - радиус должен быть меньше половины размера карты высот.
Поработав с этими величинами, мы можем получить довольно прилично выглядящий остров:
Вот мы и рассмотрели некоторые алгоритмы построения карт высот для ландшафтов. Рассмотрим еще некоторые сопутствующие операции:
· Сглаживание (или по-другому - размытие). Низкочастотный фильтр для уменьшения эффектов угловатости. При многократном применении позволяет добиться очень гладких очертаний ландшафта.
· Превращение гористой местности в холмистую. Я их различаю по очертанию вертикальных разрезов у вторых более пологие края.
· Создание пляжей и отмелей в случае с островами и берегами. Для этого места соприкосновения с водой сглаживают. Хотя могут существовать и скалистые пляжи и просто скалы.

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать полную версию