Сделай Сам Свою Работу на 5

Шум Перлина, подробная характеристика и реализация ландшафтов на его основе

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

 

 

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

 

Научныйруководитель: Шарифов Ариф Ялчин оглы

 

 

Ізмаил – 2013

Содержание

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

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

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

1.2 Карта высот

1.3 Сравнение

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

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

2.2 Шум Перлина

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

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

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

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

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

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

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

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

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

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

ВВЕДЕНИЕ

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

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

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



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

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

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

 

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

 

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

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

Плюсы:

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

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

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

Минусы:

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

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

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

Плюсы:

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

· Легко реализуется реалистичное освещение raytrace с globalillumination

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

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

Минусы:

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

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

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

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

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

 

 

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

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

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

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

 

Шум Перлина, подробная характеристика и реализация ландшафтов на его основе

Шум Перлина(Perlin noise) – математический алгоритм для генерирования градиентного шума. Шум был создан Кеном Перлином в 1983 году, назван в честь своего создателя.

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

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

Наличие множества входных параметров для функции Перлина делает ее шум гибко регулированным. Основные параметры функции: амплитуда(amplitude) - максимальное значение шума; частота(frequency) – величина, численно равная 1/wavelength(длинна волны – длинна между концом возрастающего участка функции и началом спадающего(и наоборот)), стойкость(persistence) – величина связывающая амплитуду и частоту в один параметр.

Для создания более качественного ландшафта и увеличения влияния параметров функции на конечный результат, в функцию реализующюю шум Перлина добавляют октавы. Октавы – каждая выполненная функция шума, выполненная с удвоенным значением частоты прошлой октавы.
Одной из важных частей функции шума является интерполяция между значениями соседних с данным узлом узлов. Для этого могут быть использованы такие виды интерполяции: линейная, косинусная и кубическая. Линейная функция – наиболее быстрая, но при этом выдает результаты намного хуже остальных. Косинусная и кубическая функции интерполяции – выдают очень гладкий результат, но за это мы платим в скорости. Что быстрее/красивее – косинусная или кубическая – предмет для спора, так как и скорость и плавность у них примерно одинаковая, но в теории кубическая должна быть эффективней, за счет более высокого качества интерполяции и отсутствия ресурсоемких функций, таких как cos.

Реализации разных типов интерполяции на C++:

Float linear_mix(float a, float b, float k){

Return a + (b - a)* k;

}

floatcos_mix( float a, float b, float x){

float f = (float)(( 1.0 - cosf( x * Pi)) / 2.0);

return (float)(a * (1.0 - f) + b * f);

}

Сама реализация шума Перлина на C++ выглядит так:

floatPerlinNoise(float x, float y, float seed_x = 660, float seed_y = 660){

float total = 0.0;

floatpres = (float)0.01; //любоечисло

floatampl = (float)100.2; //любоечисло

floatfreq = (float)0.06; //любоечисло

inti;

for (i = 0; i<num_octaves; i++)

{

total += final_noise( x * freq + seed_x, y * freq + seed_y) * ampl;

ampl *= pres;

freq *= 2;

}

return total;

}

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

1) Инициализация двухмерного массива

2) Для каждого узла в массиве вычислить значение шумом Перлина, посылая параметрами функции xи yиндексы текущего узла * v(2Dвектор; x, y != 0)

HeightmapGenerate(int max_x, int max_y, int seed = 0){

inti = 0;

int j = 0;

vector<vector<float>> _data(max_x);

for ( i = 0; i< (max_x); i++)

{

_data[i].resize(max_y);

for ( j = 0; j < (max_y); j++)

{

_data[i][j] = (float)(PerlinNoise( (float)i * offset_coef_x, (float)j * offset_coef_y, (float)seed, (float)seed) - 10.0);

}

}

returnHeightmap(_data);

}

3) Триангулировать карту высот путем деления каждых 4 близ лежащих узлов на треугольникb и вычислить вспомогательные данные для рендеринга

staticTriangleData Generate(Heightmapheightmap){

int size = heightmap.XBounds * heightmap.YBounds * VERTEX_NUMBERS_PER_TRIANGLE;

float *vertexes = new float[size];

size = heightmap.XBounds * heightmap.YBounds * TEX_COORDS_NUMBERS_PER_TRIANGLE;

float *texcoords = new float[size];

inti = 0;

int j = 0;

int g = 0;

int c = 0;

floatmaxf = (float)heightmap.XBounds;

for ( i = 0; i<heightmap.XBounds - 1; i++)

for ( j = 0; j <heightmap.YBounds - 1; j++)

{

vertexes[c] = (float)i + (float)heightmap.XOffset;

vertexes[c + 1] = heightmap.Data[i][j];

vertexes[c + 2] = (float)j + (float)heightmap.YOffset;

texcoords[g] = (float)i / maxf;

texcoords[g + 1] = (float)j / maxf;

vertexes[c + 3] = (float)(i + 1) + (float)heightmap.XOffset;

vertexes[c + 4] = heightmap.Data[i + 1][j + 1];

vertexes[c + 5] = (float)(j + 1) + (float)heightmap.YOffset;

texcoords[g + 2] = (float)(i + 1) / maxf;

texcoords[g + 3] = (float)(j + 1) / maxf;

vertexes[c + 6] = (float)(i + 1) + (float)heightmap.XOffset;

vertexes[c + 7] = heightmap.Data[i + 1][j];

vertexes[c + 8] = (float)j + (float)heightmap.YOffset;

texcoords[g + 4] = (float)(i + 1) / maxf;

texcoords[g + 5] = (float)j / maxf;

vertexes[c + 9] = (float)i + (float)heightmap.XOffset;

vertexes[c + 10] = heightmap.Data[i][j];

vertexes[c + 11] = (float)j + (float)heightmap.YOffset;

texcoords[g + 6] = (float)i / maxf;

texcoords[g + 7] = (float)j / maxf;

vertexes[c + 12] = (float)(i + 1) + (float)heightmap.XOffset;

vertexes[c + 13] = heightmap.Data[i + 1][j + 1];

vertexes[c + 14] = (float)(j + 1) + (float)heightmap.YOffset;

texcoords[g + 8] = (float)(i + 1) / maxf;

texcoords[g + 9] = (float)(j + 1) / maxf;

vertexes[c + 15] = (float)i + (float)heightmap.XOffset;

vertexes[c + 16] = heightmap.Data[i][j + 1];

vertexes[c + 17] = (float)(j + 1) + (float)heightmap.YOffset;

texcoords[g + 10] = (float)i / maxf;

texcoords[g + 11] = (float)(j + 1) / maxf;

c += 18;

g += 12;

}

returnTriangleData(vertexes, texcoords, NULL, heightmap.XBounds * heightmap.YBounds * 2, heightmap.XBounds, heightmap.YBounds);

}

4) Отрендерить ландшафт, используя полученные вершины.

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

f(h, x, y) = h - h * (waterside - min(x, y)) / waterside

Реализация алгоритма на C++:

Static HeightmapIslandFilter(Heightmap _heightmap, int _underwater_size = 100)

{

vector<vector<float>>island_height_map(_heightmap.XBounds);

inti = 0;

int j = 0;

intmax_x = _heightmap.XBounds;

floatmax_xf = (float)max_x;

intmax_y = _heightmap.YBounds;

floatmax_yf = (float)max_y;

int max = max_x;

floatmaxf = (float)max;

intunderwater_size = _underwater_size;

floatunderwater_sizef = (float)underwater_size;

intfar_uw_side = max - underwater_size;

floatfar_uw_sidef = (float)far_uw_side;

for ( i = 0; i<max_x; i++)

{

island_height_map[i].resize(max_y);

for ( j = 0; j <max_y; j++)

{

bool done = false;

island_height_map[i][j] = _heightmap.Data[i][j];

if (i<underwater_size&& j <underwater_size)

{

if (i<= j)

{

island_height_map[i][j] -= _heightmap.Data[i][j] * ((underwater_sizef - i) / underwater_sizef);

done = true;

}

if (j <i)

{

island_height_map[i][j] -= _heightmap.Data[i][j] * ((underwater_sizef - j) / underwater_sizef);

done = true;

}

}

if (i<underwater_size&& j >far_uw_sidef)

if (i> -(j - max_yf))

{

island_height_map[i][j] -= _heightmap.Data[i][j] * (-(far_uw_sidef - j) / underwater_sizef);

done = true;

}

else

{

island_height_map[i][j] -= _heightmap.Data[i][j] * ((underwater_sizef - i) / underwater_sizef);

done = true;

}

if (j <underwater_size&&i>far_uw_side)

if (j > -(i - max_xf))

{

island_height_map[i][j] -= _heightmap.Data[i][j] * (-(far_uw_sidef - i) / underwater_sizef);

done = true;

}

else

{

island_height_map[i][j] -= _heightmap.Data[i][j] * ((underwater_sizef - j) / underwater_sizef);

done = true;

}

if (i<underwater_size&& (j >= underwater_size&& j <= far_uw_side))

{

island_height_map[i][j] -= _heightmap.Data[i][j] * ((underwater_sizef - i) / underwater_sizef);

done = true;

}

if (j <underwater_size&& (i>= underwater_size&&i<= far_uw_side))

{

island_height_map[i][j] -= _heightmap.Data[i][j] * ((underwater_sizef - j) / underwater_sizef);

done = true;

}

if (i>far_uw_side&& (j >= underwater_size&& j <= far_uw_side))

{

island_height_map[i][j] -= _heightmap.Data[i][j] * (-(far_uw_sidef - i) / underwater_sizef);

done = true;

}

if (j >far_uw_side&& (i>= underwater_size&&i<= far_uw_side))

{

island_height_map[i][j] -= _heightmap.Data[i][j] * (-(far_uw_sidef - j) / underwater_sizef);

done = true;

}

if (!done)

{

if (i>far_uw_side&& j >far_uw_side)

{

if (i>= j)

{

island_height_map[i][j] -= _heightmap.Data[i][j] * (-(far_uw_sidef - i) / underwater_sizef);

done = true;

}

if (j >i)

{

island_height_map[i][j] -= _heightmap.Data[i][j] * (-(far_uw_sidef - j) / underwater_sizef);

done = true;

}

}

}

}

}

returnHeightmap(island_height_map);

}

 

 

Программа

Программа “LandscapeAdvancedGen” написана на C++ и является графическим редакторов ландшафтов. Для ее написания было использовано всего одна сторонняя библиотека: OpenIL(DevIL) –библиотека для работы с текстурами. В качестве графического APIпрограмма использует OpenGL2.0 и расширения 3.3+. Для рендеринга ландшафта использовалась технология VBO. На протяжении разработки программы мною была написана небольшая графическая оболочка над OpenGL.

Визуальные эффекты реализованные в программе на данный момент:

  • Multisampling 4x(сглаживание)
  • Вода
  • Динамическое небо
  • Сплатинг ландшафта(зависимость текстуры от какого либо параметра вершины ландшафта – я реализовал зависимость от высоты)

Все(кроме мильтисемплинга) эффекты были реализованы с помощью шейдеров.

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

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

При нажатии на клавишу “shift” выскакивает панель-меню, в котором есть кнопки “save” и “load”. Кнопка “save”сохраняет текущий ландшафт в файл “landscape.bhef”. Кнопка “load” загружает последний сохраненный ландшафт.

Формат “BHEF” – бинарный созданный мной специально для ландшафтов. В нем хранится только карта высот. Функция записи:

 

staticvoidexportBin(Heightmap _heightmap){

std::ofstream file("landscape.bhef");

FILE *f = new FILE();

f = fopen("landscape.bhef", "wb");

int *HM_global_header = new int[2];

HM_global_header[0] = _heightmap.XBounds;

HM_global_header[1] = _heightmap.YBounds;

fwrite(HM_global_header, sizeof(int), 2, f);

int *nodeID = new int[2];

float *nodeHeight = new float(0);

for (inti = 0; i< _heightmap.XBounds; i++)

for (int j = 0; j < _heightmap.YBounds; j++)

{

nodeID[0] = i;

nodeID[1] = j;

nodeHeight[0] = _heightmap.Data[i][j];

fwrite(nodeID, sizeof(int), 2, f);

fwrite(nodeHeight, sizeof(float), 1, f);

}

deleteHM_global_header;

delete [] nodeID;

deletenodeHeight;

fclose(f); }

Заголовок файла состоит лишь из 8 байт(2 целочисленных значения – размеры карты высот). Затем записывается информация о каждом узле – индексы и высота.

Заключение

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

· функциональный графический движок

· множество новых различный визуальных эффектов

· библиотека, содержащая классы и функции для работы с картой высот, включая генератор

· новый эррозизйный алгоритм пост обработки ландшафта(развертывание в остров)

· гибкую систему редактирования ландшафта и регулирования его генерации

 



©2015- 2017 stydopedia.ru Все материалы защищены законодательством РФ.