Исторические карты Кавказа

Размещено на http://www.allbest.ru

Федеральное государственное автономное образовательное учреждение

высшего профессионального образования

«ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ»

Факультет математики, механики и компьютерных наук

Кафедра информатики и вычислительного эксперимента

Исторические карты Кавказа

(направление подготовки 010400 - Информационные технологии)

Курсовая работа студента 3 курса

Гаджиева К.С.

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

доцент, кандидат физ.-мат. наук

В.А. Нестеренко

Ростов-на-Дону

2013



Содержание

Введение

Постановка задачи

Суть алгоритма Diamond-Square

Реализация алгоритма на базе OpenGL

Скриншоты

Заключение

Литература



Введение

Почему я решил выполнить именно эту работу? Во-первых, с исторической точки зрения, Кавказ - очень интересный регион. На протяжении веков на его территории образовывались новые государства и погибали старые. И ту небольшую часть из них я отметил в своей работе. Во-вторых (и это будет главной причиной), это возможность поработать с алгоритмами генерации ландшафта, воочию убедиться, как они работают. Среди всех алгоритмов (например, диаграмма Вороного или Midpoint Displacement) я выбрал алгоритм Diamond-Square как наиболее эффективный. Я выбрал OpenGL как наиболее подходящий программный интерфейс и язык C++



Постановка задачи

Сгенерировать на основе имеющихся карт Кавказа ландшафт на базе алгоритма Diamond-Square.

Визуализировать получившуюся карту высот с помощью библиотек glut и glaux OpenGL.

Суть алгоритма Diamond-Square

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

Начнем с более простого алгоритма midpoint displacement. Как уже сказано, он работает не на двумерной плоскости, а на одномерном отрезке (поэтому с его помощью можно, например, создать линию горизонта).

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

h = (hL + hR) / 2 + random(- R * l, R * l)

(hL и hR -- высоты на левом и правом конце отрезка, а константа R определяет «шероховатость» (roughness) получающейся ломаной и является главным параметром в данном алгоритме).

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

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

Это ещё не diamond-square -- данный алгоритм, как правило, тоже называют алгоритмом midpoint displacement и несмотря на то, что он дает уже относительно приемлемые результаты, в получившейся картинке без особого труда можно заметить её «прямолинейную» натуру.

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

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

Кроме необходимости использовать, скажем так, обход в ширину вместо обхода в глубину, есть ещё одна тонкость -- ситуация на краях ландшафта. Дело в том, что на этапе «diamond» алгоритм использует высоту точек, которых находятся за пределами текущего квадрата и, возможно, всей карты. Как быть? Варианта два (хотя вы можете придумать и свой собственный, конечно): либо считать эти высоты равными 0 (или 1, или любой другой константе; это, кстати, удобно для погружения краев нашего ландшафта под воду), либо представить что наша плоскость свернута в тор и пытаясь узнать высоту точки, лежащей на 64 пикселя левее левой границы карты, мы узнаем высоту точки, отстоящей на 64 точки от правой границы. Реализуется очень просто (как, впрочем, и первый вариант) -- нам поможет взятие координат по модулю, равному размеру карты.

Реализация алгоритма на базе OpenGL

Заведем структуру:

struct Node

{

int x;

int y;

float h;

bool flag;

Color color;

float normal[3];

};

где x, y - координаты, h - высота или глубина, flag - это флаг того, просматривали ли мы вершину или нет, color нам нужен не будет, это как вы догадались, цвет, normal - вектор нормали, нужен для освещения.

Далее инициализируем двумерный массив:

Node bitmap[size][size];

где size - размер

const int size = 513;

Размер должен быть равен 2^n + 1.

Затем мы инициализируем начальные значения двумерного массива. У нас двумерный массив свернут в тор, поэтому инициализируем начальные значения по краям. Цвет присутствует на всякий случай, мы его использовать не будем:

void InitBitmap(float beginh)

{

srand(time(0));

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

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

{

bitmap[i][j].x = i;

bitmap[i][j].y = j;

bitmap[i][j].flag = false;

bitmap[i][j].h = 0;

bitmap[i][j].color.blue = 0.2;

bitmap[i][j].color.green = 0.8;

bitmap[i][j].color.red = 0.2;

}

bitmap[0][0].h = beginh;

bitmap[0][0].flag = true;

bitmap[0][size-1].h = beginh;

bitmap[0][size-1].flag = true;

bitmap[size-1][0].h = beginh;

bitmap[size-1][0].flag = true;

bitmap[size-1][size-1].h = beginh;

bitmap[size-1][size-1].flag = true;

}

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

Далее идет непосредственно сам алгоритм. Мы будем использовать «классическую» версию, то есть от углов(которые мы уже инициализировали), мы идем вглубь. Сам алгоритм рассказан выше.

void diamond_square(Node node1, int shift, int n, bool square = true)

{

if (n == 0)

return;

srand(time(0));

if (square)

{

if (!bitmap[node1.x + shift][node1.y + shift].flag)

bitmap[node1.x + shift][node1.y + shift].h = 0.25*(bitmap[node1.x][node1.y].h + bitmap[node1.x + 2*shift][node1.y].h +

bitmap[node1.x][node1.y + 2*shift].h + bitmap[node1.x + 2*shift][node1.y + 2*shift].h) +(float)rand()/RAND_MAX*shift;

diamond_square(node1, shift, n, false);

}

else

{

float b1, b2, b3, b4;

if (node1.x == 0)

b1 = bitmap[size - shift][node1.y + shift].h;

else

b1 = bitmap[node1.x - shift][node1.y + shift].h;

if (node1.y == 0)

b2 = bitmap[node1.x + shift][size - shift].h;

else

b2 = bitmap[node1.x + shift][node1.y - shift].h;

if (node1.x + 2*shift == size)

b3 = bitmap[shift][node1.y + shift].h;

else

b3 = bitmap[node1.x + 3*shift][node1.y + shift].h;

if (node1.y + 2*shift == 0)

b4 = bitmap[node1.x + shift][shift].h;

else

b4 = bitmap[node1.x + shift][node1.y + 3*shift].h;

if (!bitmap[node1.x][node1.y + shift].flag)

bitmap[node1.x][node1.y + shift].h = 0.25*(bitmap[node1.x][node1.y].h + bitmap[node1.x + shift][node1.y + shift].h +

bitmap[node1.x][node1.y + 2*shift].h + b1) +(float)rand()/RAND_MAX*shift;

if (!bitmap[node1.x + shift][node1.y].flag)

bitmap[node1.x + shift][node1.y].h = 0.25*(bitmap[node1.x][node1.y].h + bitmap[node1.x + shift][node1.y + shift].h +

bitmap[node1.x + 2*shift][node1.y].h + b2)

+(float)rand()/RAND_MAX*shift;

if (!bitmap[node1.x + 2*shift][node1.y + shift].flag)

bitmap[node1.x + 2*shift][node1.y + shift].h = 0.25*(bitmap[node1.x + shift][node1.y + shift].h + bitmap[node1.x + 2*shift][node1.y].h +

b3 + bitmap[node1.x + 2*shift][node1.y + 2*shift].h) +(float)rand()/RAND_MAX*shift;

if (!bitmap[node1.x + shift][node1.y +2*shift].flag)

bitmap[node1.x + shift][node1.y + 2*shift].h = 0.25*(bitmap[node1.x + shift][node1.y + shift].h + bitmap[node1.x + 2*shift][node1.y +2*shift].h +

b4 + bitmap[node1.x][node1.y + 2*shift].h) +(float)rand()/RAND_MAX*shift;

int auxshift = shift;

shift /= 2;

diamond_square(node1, shift, n - 1);

diamond_square(bitmap[node1.x + auxshift][node1.y], shift, n - 1);

diamond_square(bitmap[node1.x][node1.y + auxshift], shift, n - 1);

diamond_square(bitmap[node1.x + auxshift][node1.y + auxshift], shift, n - 1);

}

}

Как видно, это рекурсивный алгоритм. Расскажу подробнее, что здесь да как.

Первое, входные параметры. Первый параметр - это узел, который мы описывали выше. shift - это сдвиг, n - глубина рекурсии, square - флаг-переключатель между режимами «квадрата» и «ромба».

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

Далее рассмотрим визуализацию прямоугольниками :

if (bRender)

glBegin( GL_QUADS );

else

glBegin( GL_LINES );

int x, y, z;

int moving = 0;

float fColor;

for (int i = 0; i < size; i += step_size)

for (int j = 0 ; j < size; j += step_size)

{

int avg = 0;

x = i;

y = bitmap[i][j].h + moving;

z = j;

avg += y;

if (y > waterlevel)

{

fColor = 0.1f + bitmap[x][z].h / (max - min);

glColor3f(0.0f, fColor, 0.0f);

glVertex3i(x, y, z);

}

else

{

glColor3f(0.1f, 0.1f, 0.95f);

glVertex3i(x, waterlevel, z);

}

x = i;

y = bitmap[i][j + step_size].h + moving;

z = j + step_size;

avg += y;

if (y > waterlevel)

{

fColor = 0.1f + bitmap[x][z].h / (max - min);

glColor3f(0.0f, fColor, 0.0f);

glVertex3i(x, y, z);

}

else

{

glColor3f(0.1f, 0.1f, 0.95f);

glVertex3i(x, waterlevel, z);

}

x = i + step_size;

y = bitmap[i+step_size][j + step_size].h + moving;

z = j + step_size;

avg += y;

if (y > waterlevel)

{

fColor = 0.1f + bitmap[x][z].h / (max - min);

glColor3f(0.0f, fColor, 0.0f);

glVertex3i(x, y, z);

}

else

{

glColor3f(0.1f, 0.1f, 0.95f);

glVertex3i(x, waterlevel, z);

}

x = i + step_size;

y = bitmap[i+step_size][j].h + moving;

z = j;

avg += y;

if (y > waterlevel)

{

fColor = 0.1f + bitmap[x][z].h / (max - min);

glColor3f(0.0f, fColor, 0.0f);

glVertex3i(x, y, z);

}

else

{

glColor3f(0.1f, 0.1f, 0.95f);

glVertex3i(x, waterlevel, z);

}

avg /= 4;

if (avg > waterlevel)

set_normals(i, i + step_size, j, j + step_size);

else

set_water_normals(i, i + step_size, j, j + step_size);

}

glEnd();

glPopMatrix();

Тут фигурируют неизвестные min, max и установка нормалей. min, max - минимальная и максимальная высоты соответственно. Они вычисляются функцией:

void get_max_min(int & min, int & max)

{

min = 10000;

max = 0;

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

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

{

if (bitmap[i][j].h < min)

min = bitmap[i][j].h;

if (bitmap[i][j].h > max)

max = bitmap[i][j].h;

}

}

Потом шла речь о нормалях. Есть обычные нормали, есть «водные» нормали. Они реализуются следующими функциями :

void set_normals(int x1, int x2, int y1, int y2)

{

float z1 = bitmap[x1][y2].h;

float z2 = bitmap[x1][y1].h;

float z3 = bitmap[x2][y1].h;

for (int i = x1; i < x2; ++i)

for (int j = y1; j < y2; ++j)

{

bitmap[i][j].normal[0] = y2*(z2 - z3) + y1*(z3-z1) + y1*(z1 - z2);

bitmap[i][j].normal[1] = z1*(x1 - x2) + z2*(x2 - x1) + z3*0;

bitmap[i][j].normal[2] = x1*0 + x1*(y1 - y2) + x2*(y2 - y1);

glNormal3fv(bitmap[i][j].normal);

glVertex3i(i, bitmap[i][j].h, j);

}

}

void set_water_normals(int x1, int x2, int y1, int y2)

{

for (int i = x1; i < x2; ++i)

for (int j = y1; j < y2; ++j)

{

Node & n = bitmap[i][j];

n.normal[0] = 0;

n.normal[1] = 1;

n.normal[2] = 0;

glNormal3fv(n.normal);

glVertex3i(i, n.h, j);

}

}

На вход, как видим, подаются двумерные координаты

В моей программе реализовано освещение, оно реализовано следующими функциями библиотеки glut:

GLfloat ambientLight[]= {0.5, 0.5, 0.5, 1.0}; //фоновый све

GLfloat diffuseLight[]= {1.0, 1.0, 1.0, 0.9}; //свет источника

GLfloat positionLight[]= {-100.0, 200.0, 0.1, 1.0}; //положение источника света

glLightfv (GL_LIGHT1, GL_DIFFUSE, diffuseLight); //освещение источником

glLightfv (GL_LIGHT1, GL_POSITION, positionLight); //положение источника света

glLightModelfv (GL_LIGHT_MODEL_AMBIENT, ambientLight); //фоновое освещение сцены

glEnable (GL_LIGHT1);//источник света включен

glEnable (GL_LIGHTING);//включен механизм рассчета освещенности

glColorMaterial (GL_FRONT, GL_AMBIENT_AND_DIFFUSE); //свойства материала

glEnable (GL_COLOR_MATERIAL);

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

void keyboard(unsigned char c, int x, int y)

{

switch(c)

{

case (unsigned char)'у' : {index = 0; firstpict = true; mouseclick = false; display(); break;};

case (unsigned char)'т' : {index = 0; firstpict = false; mouseclick = false; display(); break;};

case (unsigned char)'а' : {index = 1; mouseclick = false; display(); break;};

case (unsigned char)'л' : {index = 2; mouseclick = false; display(); break;};

case (unsigned char)'р' : {index = 3; mouseclick = false; display(); break;};

case (unsigned char)'в' : {index = 4; mouseclick = false; display(); break;};

case (unsigned char)'г' : {index = 5; mouseclick = false; display(); break;};

case (unsigned char)'и' : {index = 6; mouseclick = false; display(); break;};

case (unsigned char)'к' : {index = 7; mouseclick = false; display(); break;};

case (unsigned char)'з' : {index = 8; mouseclick = false; display(); break;};

case (unsigned char)'х' : {index = 9; mouseclick = false; display(); break;};

case (unsigned char)'ш' : {index = 10; mouseclick = false; display(); break;};

case (unsigned char)'м' : {index = k - 1; mouseclick = false; display();break;};

default : {index = -1; break;};

}

}

void skeyboard(int key, int x , int y)

{

switch(key)

{

case GLUT_KEY_UP : {angle+=5; changeangle = false; display(); break;};

case GLUT_KEY_DOWN : {angle-=5; changeangle = false; display(); break;};

}

}

void mouse(int button, int state, int x, int y)

{

switch(button)

{

case GLUT_LEFT_BUTTON :

{

if ((x > size/2) && (x < size) && (y > 0) && (y < size/2) && (state == GLUT_DOWN) && (!mouseclick))

{

mouseclick = true;

display();

}

else if ((mouseclick) && (state == GLUT_DOWN))

{

lookH -= 10;

changeangle = false;

display();

}

break;

};

case GLUT_RIGHT_BUTTON :

{

if ((mouseclick) && (state == GLUT_DOWN))

{

lookH += 10;

changeangle = false;

display();

}

break;

};

}

}

В функции keyboard, как видим, по нажатию клавиши, переключается картинка, за нее отвечает index, это индекс массива текстур:

AUX_RGBImageRec* texturearr[k];

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

texturearr[0] = auxDIBImageLoadA("F:/Казанфар/my university/Виктор Александрович/курсовая/Diamond-Algorithm/Сжатые картинки/2states.bmp");

Функции skeyboard и mouse управляют сгенерированным ландшафтом, изменяя угол angle и высоту lookH. Они используются в стандартной функции gluLookAt для изменения вида камеры:

gluLookAt(size/2*cos(angle) + size/2, lookH, size/2*cos(angle)+ size/2, size/2, 0.0, 0.0, 0.0, 1.0, 0.0);

Скриншоты



Заключение

карта ландшафт алгоритм визуализация

Наши цели были выполнены:

Был сгенерирован на основе имеющихся карт Кавказа ландшафт на базе алгоритма Diamond-Square.

Мы визуализировали получившуюся карту высот с помощью библиотек glut и glaux OpenGL



Литература

Алгоритм «diamond-square» для построения фрактальных ландшафтов

http://habrahabr.ru/post/111538/

Английская Википедия, алгоритм Diamond-Square

http://en.wikipedia.org/wiki/Diamond-square_algorithm.

Размещено на http://www.allbest.ru