Способы описания ландшафтных структур

ГЕНЕРАЦИЯ И ВИЗУАЛИЗАЦИЯ ПРОЦЕДУРНЫХ ЛАНДШАФТОВ ПОСТРОЕННЫХ НА ОСНОВЕ ШУМОВ ПЕРЛИНА

Автор: Агафонцев Семен Алексеевич, ученик 10-Б класса общеобразовательного политехнического лицея ІІ – ІІІ степеней г. Измаила

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

Ізмаїл – 2013

Содержание

ВВЕДЕНИЕ………………………………………………2

Способы описания ландшафтных структур………3

1.1 Воксельная структура

1.2 Карта высот

1.3 Сравнение

Алгоритмы, используемые для генерирования ландшафтов……………………………………………5

2.1 Диаграммы Вороного

2.2 Шум Перлина

2.3 Симплекс шум

Шум Перлина, подробная характеристика……….6

3.1 Определение

3.2 Сферы использования

3.3 Параметры функции

3.4 Виды интерполяции

3.5 Пример реализации на C++
4. Программа “Landscape Advanced Gen”…………17

4.1 Технические характеристики

4.2 Средства редактирования

4.3 Сохранение, загрузка и формат файла

ВВЕДЕНИЕ

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

Главной особенностью такого вида контента является отсутствие какой либо нужды хранить какие то ресурсы на физическом носителе(тем самым освобождая память для других ресурсов), но взамен требует больших мощностей главного процессора. Возросшая популярность так же обусловлена выросшей мощностью процессора и увеличением количества ядер в нем. Так как практически любой процедурный алгоритм легко распараллеливается, n-ое количество ядер позволяет увеличить производительность в n раз(!). Из-за этого в последнее время множество процедурных алгоритмов было перенесено на графический процессор который имеет от 500 пиксельных ядер, благодаря чему процедурный контент может генерироваться каждый кадр без особого вреда для FPS и не занимать ОЗУ.

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

Предметом исследования является процедурное генерирование и визуализация ландшафтов в современной графической среде.

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

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

Способы описания ландшафтных структур

Существуют два основных способа описывания ландшафта: карта высот(height map) и воксельная структура(voxel map). Каждая из них обладает своими плюсами и минусами, которые будут описаны далее.

Карта высот – дискретная двухмерная сетка, каждый узел которой имеет определенное значение – высоту. Интервал между узлами одинаков на всех участках сетки. Это делает возможным описания карты высот в програмном обеспечении простым двухмерным массивом. Пример на C++:
float height_map[width][height];

Плюсы:

· Визуализация карты высот довольно легка благодаря тому, что ее очень легком триангулировать(из каждых четырех соседних узлов – два треугольника).

· Занимает малый объем оперативной памяти: mem = sizeof(float) * width * height.

· Имеет множество алгоритмов для генерации.

Минусы:

· Невозможность сделать “нависающую гору” из-за фиксированного интервала между узлами(то есть фксированные координаты x, z).

Воксельная структура ландшафта – дискретная трехмерная сетка фиксированного интервала между узлами, в которой каждый узел является вокселем. Пример описания в C++:
bool voxel_field[width][height][depth];

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

Плюсы:

· Легко реализовать LOD модель.

· Легко реализуется реалистичное освещение ray trace с global illumination

· Возможность реализации реалистичного разрушения ландшафта

· Возможность “нависающих гор”, “пещер”.

Минусы:

· Невероятно ресурсоемкая триангуляция(особенно marching cubes)

· Огромное потребление оперативной памяти

· Огромное потребление видео памяти

· Очень требовательный к видеокарте рендеринг

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

1) Алгоритмы, используемые для генерации ландшафтов

Midpoint displacement – рекурсивный, не поддающийся распараллеливанию алгоритм. Его суть заключается в том, что в четверых крайних узах карты высот находятся совершенно случайные значения, затем карта разбивается на четыре равных квадрата и в центральном узле(общем для всех квадратов) находится высота по формуле h = (h1 + h2 + h3 + h4)/4 + rand(-R*l, R*l), где h1, h2, h3, h4 – высоты в 4 крайних узлах, R – шероховатость, l – длинна разбиения.

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

Одной из самых значительных модификаций является Simplex Noise, созданная Кеном Перлином специально для шумов с большим количеством измерений. Его главное отличие является то, что вместо интерполяции между 2 ^ n значениями, производится интерполяция между (n + 1) значениями(то есть вместо n dimension square, используется n-dimension triangle).
Сравнивая все эти алгоритмы, их плюсы и минусы, я пришел к выводу, что наиболее эффективным для pre-run генерации ландшафта средних размеров с использованием двух мерной карты алгоритмом является классический Perlin Noise за счет его регулироемости, качества и простоты редактирования.

Дата добавления: 2015-11-04