Исторические карты Кавказа
Федеральное
государственное автономное образовательное учреждение
высшего
профессионального образования
«ЮЖНЫЙ
ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ»
Факультет
математики, механики и компьютерных наук
Кафедра
информатики и вычислительного эксперимента
Исторические
карты Кавказа
(направление
подготовки 010400 - Информационные технологии)
Курсовая работа
студента 3 курса
Гаджиева К.С.
Научный
руководитель:
доцент, кандидат
физ.-мат. наук
В.А. Нестеренко
Ростов-на-Дону
Содержание
Введение
Постановка
задачи
Суть
алгоритма 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
Заведем структуру:Node
{x;
int y;h;flag;
color;
float
normal[3];
};
где x, y - координаты, h - высота или глубина,
flag - это флаг того, просматривали ли мы вершину или нет, color нам нужен не
будет, это как вы догадались, цвет, normal - вектор нормали, нужен для
освещения.
Далее инициализируем двумерный массив:
Node bitmap[size][size];
где size - размерint
size = 513;
Размер должен быть равен 2^n + 1.
Затем мы инициализируем начальные значения
двумерного массива. У нас двумерный массив свернут в тор, поэтому
инициализируем начальные значения по краям. Цвет присутствует на всякий случай,
мы его использовать не будем:
void InitBitmap(float beginh)
{(time(0));(int i = 0; i < size;
++i)(int j = 0; j < size; ++j)
{[i][j].x = i;[i][j].y =
j;[i][j].flag = false;[i][j].h = 0;[i][j].color.blue = 0.2;[i][j].color.green =
0.8;[i][j].color.red = 0.2;
}[0][0].h = beginh;[0][0].flag =
true;[0][size-1].h = beginh;[0][size-1].flag = true;[size-1][0].h =
beginh;[size-1][0].flag = true;[size-1][size-1].h =
beginh;[size-1][size-1].flag = true;
}
Т.к. значения по краям мы уже использовали, то
флаги инициализируем истиной.
Далее идет непосредственно сам алгоритм. Мы
будем использовать «классическую» версию, то есть от углов(которые мы уже
инициализировали), мы идем вглубь. Сам алгоритм
рассказан
выше.diamond_square(Node
node1, int shift, int n, bool square = true)
{(n == 0);(time(0));(square)
{(!bitmap[node1.x + shift][node1.y +
shift].flag)[node1.x + shift][node1.y + shift].h =
0.25*(bitmap[node1.x][node1.y].h + bitmap[node1.x + 2*shift][node1.y].h
+[node1.x][node1.y + 2*shift].h + bitmap[node1.x + 2*shift][node1.y +
2*shift].h) +(float)rand()/RAND_MAX*shift;_square(node1, shift, n, false);
}
{b1, b2, b3, b4;
if (node1.x == 0)= bitmap[size -
shift][node1.y + shift].h;= bitmap[node1.x - shift][node1.y + shift].h;
(node1.y == 0)= bitmap[node1.x +
shift][size - shift].h;= bitmap[node1.x + shift][node1.y - shift].h;
(node1.x + 2*shift == size)=
bitmap[shift][node1.y + shift].h;= bitmap[node1.x + 3*shift][node1.y +
shift].h;
(node1.y + 2*shift == 0)=
bitmap[node1.x + shift][shift].h;= bitmap[node1.x + shift][node1.y +
3*shift].h;
(!bitmap[node1.x][node1.y +
shift].flag)[node1.x][node1.y + shift].h = 0.25*(bitmap[node1.x][node1.y].h +
bitmap[node1.x + shift][node1.y + shift].h +[node1.x][node1.y + 2*shift].h +
b1) +(float)rand()/RAND_MAX*shift;(!bitmap[node1.x +
shift][node1.y].flag)[node1.x + shift][node1.y].h =
0.25*(bitmap[node1.x][node1.y].h + bitmap[node1.x + shift][node1.y + shift].h
+[node1.x + 2*shift][node1.y].h + b2)
+(float)rand()/RAND_MAX*shift;
(!bitmap[node1.x + 2*shift][node1.y
+ shift].flag)[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 ++
bitmap[node1.x + 2*shift][node1.y + 2*shift].h)
+(float)rand()/RAND_MAX*shift;(!bitmap[node1.x + shift][node1.y
+2*shift].flag)[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 ++
bitmap[node1.x][node1.y + 2*shift].h) +(float)rand()/RAND_MAX*shift;
auxshift = shift;/= 2;_square(node1,
shift, n - 1);_square(bitmap[node1.x + auxshift][node1.y], shift, n -
1);_square(bitmap[node1.x][node1.y + auxshift], shift, n -
1);_square(bitmap[node1.x + auxshift][node1.y + auxshift], shift, n - 1);
}
Как видно, это рекурсивный алгоритм. Расскажу
подробнее, что здесь да как.
Первое, входные параметры. Первый параметр - это
узел, который мы описывали выше. shift - это сдвиг, n - глубина рекурсии,
square - флаг-переключатель между режимами «квадрата» и «ромба».
Второе, в теле функции этот флаг с помощью
условного оператора и разделяет работу алгоритма между этими двумя режимами.
Реализация полностью соответствует описанию алгоритма.
Далее рассмотрим визуализацию прямоугольниками
:(bRender)
glBegin( GL_QUADS );( GL_LINES );x,
y, z;moving = 0;fColor;(int i = 0; i < size; i += step_size)(int j = 0 ; j
< size; j += step_size)
{avg = 0;= i;= bitmap[i][j].h +
moving;= j;+= y;(y > waterlevel)
{= 0.1f + bitmap[x][z].h / (max -
min);f(0.0f, fColor, 0.0f);i(x, y, z);
}
{f(0.1f, 0.1f, 0.95f);i(x,
waterlevel, z);
}= i;= bitmap[i][j + step_size].h +
moving;= j + step_size;+= y;(y > waterlevel)
{= 0.1f + bitmap[x][z].h / (max -
min);f(0.0f, fColor, 0.0f);i(x, y, z);
}
{f(0.1f, 0.1f, 0.95f);i(x,
waterlevel, z);
}
= i + step_size;=
bitmap[i+step_size][j + step_size].h + moving;= j + step_size;+= y;(y >
waterlevel)
{= 0.1f + bitmap[x][z].h / (max -
min);f(0.0f, fColor, 0.0f);i(x, y, z);
}
{f(0.1f, 0.1f, 0.95f);i(x,
waterlevel, z);
}
= i + step_size;=
bitmap[i+step_size][j].h + moving;= j;+= y;(y > waterlevel)
{= 0.1f + bitmap[x][z].h / (max -
min);f(0.0f, fColor, 0.0f);i(x, y, z);
}
{f(0.1f, 0.1f, 0.95f);i(x,
waterlevel, z);
}/= 4;(avg >
waterlevel)_normals(i, i + step_size, j, j + step_size);_water_normals(i, i +
step_size, j, j + step_size);
}();();
Тут фигурируют неизвестные min, max и установка
нормалей. min, max - минимальная и максимальная высоты соответственно. Они
вычисляются
функцией:get_max_min(int
& min, int & max)
{= 10000;= 0;(int i = 0; i <
size; ++i)(int j = 0; j < size; ++j)
{(bitmap[i][j].h < min)=
bitmap[i][j].h;(bitmap[i][j].h > max)= bitmap[i][j].h;
}
}
Потом шла речь о нормалях. Есть обычные нормали,
есть «водные» нормали. Они реализуются следующими функциями :set_normals(int
x1, int x2, int y1, int y2)
{
float z1 = bitmap[x1][y2].h;z2 =
bitmap[x1][y1].h;z3 = bitmap[x2][y1].h;(int i = x1; i < x2; ++i)(int j = y1;
j < y2; ++j)
{[i][j].normal[0] = y2*(z2 - z3) +
y1*(z3-z1) + y1*(z1 - z2);[i][j].normal[1] = z1*(x1 - x2) + z2*(x2 - x1) +
z3*0;[i][j].normal[2] = x1*0 + x1*(y1 - y2) + x2*(y2 -
y1);fv(bitmap[i][j].normal);i(i, bitmap[i][j].h, j);
}
}
set_water_normals(int x1, int x2,
int y1, int y2)
{(int i = x1; i < x2; ++i)(int j
= y1; j < y2; ++j)
{& n = bitmap[i][j];.normal[0] =
0;.normal[1] = 1;.normal[2] = 0;fv(n.normal);i(i, n.h, j);
}
}
На вход, как видим, подаются двумерные
координаты
В моей программе реализовано освещение, оно
реализовано следующими функциями библиотеки glut:ambientLight[]= {0.5, 0.5,
0.5, 1.0}; //фоновый све
diffuseLight[]= {1.0, 1.0, 1.0, 0.9}; //свет
источникаpositionLight[]= {-100.0, 200.0, 0.1, 1.0}; //положение источника
света(GL_LIGHT1, GL_DIFFUSE, diffuseLight); //освещение источником
glLightfv (GL_LIGHT1, GL_POSITION,
positionLight); //положение
источника
света(GL_LIGHT_MODEL_AMBIENT,
ambientLight); //фоновое
освещение
сцены
glEnable (GL_LIGHT1);//источник света
включен(GL_LIGHTING);//включен механизм рассчета освещенности
glColorMaterial (GL_FRONT,
GL_AMBIENT_AND_DIFFUSE); //свойства
материала
glEnable (GL_COLOR_MATERIAL);
Также в моей работе реализованы функции для
работы с мышью и клавиатурой, они нужны для переключения картинок с картами
Кавказа и управления сгенерированным ландшафтом:
void keyboard(unsigned char c, int
x, int y)
{(c)
{(unsigned char)'у'
: {index = 0; firstpict = true; mouseclick = false; display();
break;};(unsigned char)'т'
: {index = 0; firstpict = false; mouseclick = false; display(); break;};(unsigned
char)'а'
: {index = 1; mouseclick = false; display(); break;};(unsigned char)'л'
: {index = 2; mouseclick = false; display(); break;};(unsigned char)'р'
: {index = 3; mouseclick = false; display(); break;};(unsigned char)'в'
: {index = 4; mouseclick = false; display(); break;};(unsigned char)'г'
: {index = 5; mouseclick = false; display(); break;};(unsigned char)'и'
: {index = 6; mouseclick = false; display(); break;};(unsigned char)'к'
: {index = 7; mouseclick = false; display(); break;};(unsigned char)'з'
: {index = 8; mouseclick = false; display(); break;};(unsigned char)'х'
: {index = 9; mouseclick = false; display(); break;};(unsigned char)'ш'
: {index = 10; mouseclick = false; display(); break;};(unsigned char)'м'
: {index = k - 1; mouseclick = false; display();break;};: {index = -1; break;};
}
}
skeyboard(int key, int x , int y)
{(key)
{GLUT_KEY_UP : {angle+=5;
changeangle = false; display(); break;};GLUT_KEY_DOWN : {angle-=5; changeangle
= false; display(); break;};
}
}
void mouse(int button, int state,
int x, int y)
{(button)
{GLUT_LEFT_BUTTON :
{((x > size/2) && (x <
size) && (y > 0) && (y < size/2) && (state ==
GLUT_DOWN) && (!mouseclick))
{= true;();
}if ((mouseclick) && (state
== GLUT_DOWN))
{-= 10;= false;();
};
};GLUT_RIGHT_BUTTON :
{((mouseclick) && (state ==
GLUT_DOWN))
};
};
}
}
В функции keyboard, как видим, по нажатию
клавиши, переключается картинка, за нее отвечает index, это индекс массива
текстур:_RGBImageRec* texturearr[k];
Вот для этого и нужна библиотека glaux, для
считывания данных с файла. Вот один пример:[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 ://en.wikipedia.org/wiki/Diamond-square_algorithm.