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

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

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

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

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

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

(направление подготовки 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» - и перейти к меньшим квадратам.