Разработка программы генерации ландшафта на основе фракталов

Разработка программы генерации ландшафта на основе фракталов

ВВЕДЕНИЕ

Целью данной курсовой работы является освоение темы «Фракталы» и последующая реализация программы генерации ландшафта на основе фракталов с помощью языка Delphi.

Само понятие фрактал возникло относительно недавно лет 15-20 назад. В связи с необходимостью генерации облаков, гор, береговых линий, растительности. Стандартные геометрические фигуры: круг, квадрат, прямоугольник, треугольник уже не могли справляться с растущими потребностями в детализации и скорости генерации.

Термин «фрактал» был введён Бенуа Мандельбротом в 1975 году и получил широкую популярность с выходом в 1977 году его книги «Фрактальная геометрия природы».

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

1.     
ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

фрактал ландшафт программа

1.1 Понятие фрактала

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

.2 Принцип построения

Фрактальное изображение создается применением некоторой геометрической операции к простой фигуре и последующим многократным применением той же операции к полученному результату. В этой программе используется алгоритм построения, похожий на салфетку Серпинского (Рисунок 1).

Рисунок 1. - Салфетка Серпинского.

Этот фрактал описал в 1915 году польский математик Вацлав Серпинский. Чтобы его получить, нужно взять (равносторонний) треугольник с внутренностью, провести в нём средние линии и выкинуть центральный из четырех образовавшихся маленьких треугольников. Дальше эти же действия нужно повторить с каждым из оставшихся трех треугольников, и т. д.

Свойства салфетки Серпинского :

1.Фрактальная размерность log23 ≈ 1,584962.... Треугольник Серпинского состоит из трех копий самого себя, каждая в два раза меньше. Взаимное расположение их таково, что если уменьшить клеточки сетки в два раза, то число квадратиков, пересекающихся с фракталом, утроится. То есть N(д/2) = 3N(д). Если сначала размер клеток был 1, а с фракталом пересекалось N0 из них (N(1) = N0), то N(1/2) = 3N0, N(1/4) = 32N0, ..., N(1/2k) = 3kN0. Отсюда получается, что N(д) пропорционально , и по определению фрактальной размерности она равна как раз log23.

Треугольник Серпинского имеет нулевую площадь

Однако чтобы сгенерировать ландшафт, нужно изменить алгоритм Серпинского. А именно, присвоить случайные высоты трем вершинам равностороннего треугольника, а затем «изогнуть» каждое ребро, поднимая или опуская его середину на случайную величину. Соединяя линиями середины трех сторон - исходный треугольник разделится на четыре треугольника (Рисунок 2). Теперь применяются операции изгиба и деления к каждому из получившихся треугольников(в этом главное отличие от алгоритма Серпинского), и получается нечто похожее на реальный ландшафт.

Рисунок 2 - Деление треугольника.

В результате выполнения этих операций получается поверхность, сильно напоминающая ландшафт, но также нужно следить за тем, чтобы грани треугольников, имеющих несколько общих граней, изгибались на одинаковую величину. Иначе получатся как бы группы треугольников по четыре штуки с несоприкасающимися гранями. Также в программе есть «уровень моря»: любой треугольник, полностью находящийся над уровнем моря, рисуется нормально, а любой треугольник, полностью погруженный в воду, рисуется синим цветом на уровне моря. Если треугольник пересекает уровень моря, программа интерполирует точки пересечения, после чего отдельно рисует надводную и подводную части. После компиляции вы увидите ландшафт типа (рисунок 3).

Рисунок 3 - Пример ландшафта.

.3 Ландшафт каркасный

В этом режиме ландшафт рисуется как набор треугольников, при этом координаты отдельных вершин TTriple с помощью преобразования пересчитываются в экранные пиксели TPixel, а затем получившийся треугольник рисуется с помощью функции PolyLine или Polygon, без отсечения невидимых линий. В это режиме рисуются контуры треугольников: «земля» - зеленым цветом, а «вода» - синим. Пример данного ландшафта (Рисунок 4).

Рисунок 4 - Пример каркасного ландшафта.

.4 Ландшафт заполненный

В этом режиме ландшафт рисуется как набор треугольников, при этом координаты отдельных вершин TTriple с помощью перспективного преобразования пересчитываются в экранные пиксели TPixel, а затем получившийся треугольник рисуется с помощью функции PolyLine или Polygon, с отсечением невидимых линий методом «грубой силы». А именно DrawTriangle() сначала рисует задние треугольники, чтобы передние треугольники рисовались позже и закрывали их. При исходном вызове DrawTriangle() этой процедуре передается треугольник, расположенный «вершиной вниз» - вершина A расположена спереди, в нижней части окна, а вершины B и С - сзади, ближе к верхней части окна (смотри рисунок 5.1.). Следовательно, фрагмент

DrawTriangle(Canvas, CA, BC, C, Plys, True);(Canvas, AB, B, BC, Plys, True);(Canvas, BC,CA,AB, Plys, False);(Canvas, A, AB, CA, Plys, True);

сначала рисует левый субтреугольник, а затем - правый. Ориентация этих «внешних» субтреугольников совпадает с ориентацией треугольника ABC, а порядок перечисления параметров в рекурсивных вызовах DrawTriangle() гарантирует, что новая точка A будет расположена спереди, а точки B и C - сзади. Третья строка вызова рисует «внутренний» субтреугольник, который визуально находится перед вторым (правым верхним) треугольником. Внутренний субтреугольник всегда перевёрнут по отношению к своему внешнему треугольнику, поэтому при вызове DrawTriangle() он располагается «вершиной вверх». Порядок перечисления параметров гарантирует, что при таком вызове вершина A остается сзади, а B и C - спереди, в нижней части экрана. Четвертый вызов DrawTriangle() рисует последний, передний субтреугольник.

Рисунок 5.1. - Порядок рисования и ориентация треугольников.

Пример данного ландшафта (рисунок 5.2.).

Рисунок 5.2. - Пример заполненного ландшафта.

.5 Ландшафт светотень

В этом режиме ландшафт рисуется как набор треугольников, при этом координаты отдельных вершин TTriple с помощью простого перспективного преобразования пересчитываются в экранные пиксели TPixel, а затем получившийся треугольник рисуется с помощью функции PolyLine или Polygon. В свою очередь цвет каждого треугольника в нем зависит от угла, под которым данная грань расположена по отношению к «солнцу». Треугольники, расположенные перпендикулярно лучам, выглядят светлее тех, что расположены под углом. Пример данного ландшафта (рисунок 6.).

Рисунок 6. - Пример ландшафта светотень.

2.     
ОПИСАНИЕ ПРОГРАММНОЙ ЕДИНИЦЫ

2.1    Общие сведения

Программная единица представляет собой программу, которая имеет название FracLandscapes.exe.

Программа написана на языке Delphi в среде разработки Delphi 10.

Программное обеспечение, необходимое для функционирования: операционная система Windows XP/7.

2.2    Функциональное назначение

Программа может использоваться для генерации береговой линии и гор на основе фракталов.

2.3    Описание логической структуры

Программа состоит из пяти модулей: MAIN.PAS, DISPLAY.PAS, DATABASE.PAS , OPTIONS.PAS , GLOBAL.PAS. Модули и их назначение приведены в таблице 1.

Таблица 1.

Модуль MAIN.PAS состоит из процедур и функций:

1.      procedure FileNew(Sender: TObject) - процедура генерирует новый ландшафт.

2.      procedure FileOpen(Sender: TObject) - процедура открывает ранее созданный ландшафт.

3.      procedure FileSaveAs(Sender: TObject) - процедура сохраняет ландшафт.

.        procedure FilePrint(Sender: TObject) - процедура выводит на печать ландшафт.

.        procedure FilePrintSetup(Sender: TObject) - процедура вызывающая настройку печати.

.        procedure FileExit(Sender: TObject) - процедура выхода из программы.

.        procedure EditCopy(Sender: TObject) - процедура копирования ландшафта в буфер обмена.

.        procedure FormResize(Sender: TObject) - процедура создание формы.

.        procedure FormKeyPress(Sender: TObject; var Key: Char) - процедура обработки кнопок клавиатуры, где Key - символ клавиатуры.

.        procedure DisplayOptions1Click(Sender: TObject) - процедура открывает настройки.

.        procedure ModeBtnClick(Sender: TObject) - процедура генерирует новый ландшафт, если изменились модификации.

.        procedure PlyBtnClick(Sender: TObject) - процедура генерирует новый ландшафт, если изменяется количество изгибов.

14.    procedure SealevelPnlResize(Sender: TObject) - процедура уровня моря.

.        procedure SeaLevelSldrScroll(Sender: TObject; ScrollCode: TScrollCode; var ScrollPos: Integer) - процедура изменения плоскости уровня моря, где ScrollCode - координаты при изменении плоскости; ScrollPos-позиция ползунка.

.        procedure HelpMenuClick(Sender: TObject) - процедура вызова справки.

.        procedure DrawLandscape(Canvas: TCanvas; Height, Width: integer; Tag: string) - процедура вывода ландшафта на дисплей, где Canvas-поверхность рисунка; Height, Width-высота, ширина;

.        procedure SetPlys(NewPlys: integer) - процедура задания количества изгибов, где NewPlys- новый изгиб.

.        procedure SetDrawMode(NewDrawMode: DrawModes) - процедура выбора режима отображения, где NewDrawMode - режим отображения

.        procedure GenerateLandscape - процедура генерации ландшафта.

.        procedure ShowLandscape - процедура вызова ландшафта.

.        procedure DrewSomeTriangles(N: word) - процедура рисования треугольников, где N - коэффициент умножения.

Модуль DISPLAY.PAS содержит процедуры и функции:

1.      procedure ScreenColors - процедура задаёт цвет элементам ландшафта.

2.      procedure PrinterColors - процедура задаёт цвет элементов ландшафта при печати.

3.      function Surface(Outline, Fill: TColor): Surfaces - функция присваивает результату режим цвета, где Outline-только границы; Fill-заливка.

4.      function FloatTriple(T: TTriple): TFloatTriple - функция вычисления координат, где Т - преобразует в тип TTriple; TFloatTriple - координаты x, y,z.

5.      function Project(const Tr: TTriple): TPixel - эта функция проводит линию между двумя точками : текущей и точкой перспективы и определяет, где эта линия пересекается с плоскостью экрана, где Tr - преобразует в тип TTriple.

6.      procedure DrawTriangle( Canvas: TCanvas; const A, B, C: TVertex; Plys: word; PointDn: boolean) - процедура рисования треугольников, где Canvas форма для рисования; A, B, C - вершины треугольника, Plys - изгиб, PointDn- средняя точка.

7.      procedure DrawPixels(const Canvas: TCanvas;const A, B, C, D: TPixel; const N: word; const Surface: Surfaces) - процедура прорисовки каркаса, где Canvas - форма для рисования; A, B, C, D - вершины; N - чило для проверки условия, Surface - земная поверхность.

8.      procedure CalcCrossing(var Low, High, Crossing: TTriple; SetLow: boolean) - процедура определяет расстояние от точки пересечения до вершины. Где Low, High, Crossing - нижняя, верхняя, пересечение координат; SetLow - для проверки уровня моря.

9.      procedure DrawVerticals(Canvas: TCanvas) - процедура преобразования TTriple в TPixel.

.        procedure Step(const Start: TVertex; var Front: Triad; var StepDn: GridCoordinate ) - процедура смотрит какая из точек треугольника находиться в море, а какая нет, где Start - начало координат; Front -тройка координат; StepDn - координатная сетка.

.        function InnerProduct( A, B: TTriple): LongInt - функция вычисляет скалярное произведение вершин, где A, B - вершины .

.        function Delta(A, B: TTriple): TTriple - функция вычисления разности вершин, где A, B - вершины.

.        function LandColor(const A, B, C: TTriple): TColor - функция определения цвета ландшафта, где A, B, C -вершины треугольника.

.        procedure Draw3Vertices( Canvas: TCanvas; const A, B, C: TVertex; Display: boolean) - процедура реализует уровень моря, Canvas - форма для рисования; A, B, C - вершины треугольника; Display- количество вершин под водой или над водой.

Модуль DATABASE.PAS содержит процедуры и функции:

1.      procedure ResetDB - процедура расчета троек координат для параметров, зависящих от числа изгибов.

2.      function IMUL(A, B: Int16): LongInt - функция умножения; А,В - числа

3.      function LoadLandscape(const FileName: TFileName): Boolean - функция загрузки сохранённого ландшафта.

4.      function SaveLandscape(const FileName: TFileName): Boolean - функция сохранения ландшафта.

.        procedure SwapTriples(var A, B: TTriple) - процедура замены вершин, A, B - вершины.

.        procedure FractureTriangle(const A, B, C: TVertex; Plys: word) - процедура рисующая треугольники, если число изгибов > 1, где A, B, C - вершины треугольника, Plys - изгиб.

.        function Unscale(ScaledCoordinate: LongInt): TCoordinate - функция масштабирования.

.        function IDIV(Numerator: LongInt; Denominator: Int16): Int16 - функция деления; Numerator - числитель; Denominator - знаменатель.

.        function Rand(Envelope: integer): integer - функция нормального распределения в интервале 2Envelope, Envelope - половина стороны отрезка.

.        function Vertices(N: word): word - функция подсчёта числа вершин, где N - длина стороны.

11.    procedure FractureLine( var vM: TVertex; const vA, vB: TVertex; Envelope: integer ) - процедура для расчёта высот средних отрезков, где vM - преобразованная вершина, vA, vB -вершины, Envelope - половина стороны отрезка.

Модуль GLOBAL.PAS содержит функции:

1.      function Triple(X, Y, Z: TCoordinate): TTriple - функция получения координат, где X, Y, Z - координаты.

2.      function Vertex(AB, BC, CA: GridCoordinate): TVertex - функция получения отрезков, где AB, BC, CA - отрезки.

Модуль OPTIONS.PAS хранит формы настроек ландшафта.

Описание алгоритмов

В этом пункте приведены алгоритмы, играющие главную роль в генерации ландшафта. Прежде всего это процедуры: procedure FractureLine (рисунок 7.) и procedure FractureTriangle (Рисунок 8.)

Рисунок 7. - Алгоритм процедуры FractureLine.

Рисунок 8. - Алгоритм процедуры FractureTriangle.

При генерации нового ландшафта вызываются процедуры GenerateLandscape (Рисунок 9.) и ShowLandscape (Рисунок 10.). Которые и генерируют ландшафт.

Рисунок 9. - Алгоритм процедуры GenerateLandscape.

Рисунок 10. - Алгоритм процедуры ShowLandscape.

.5 Используемые технические средства

Персональный компьютер на базе Intel, с установленной ОС Windows XP.

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

2.6 Вызов и загрузка

Программа запускается через файл FracLandscapes.exe.

3.     
ОПИСАНИЕ ПРИМЕНЕНИЯ ПРОГРАММНОЙ ЕДИНИЦЫ

Программа FracLandscapes может применяться для построения простейших изображений береговых линий и гор на основе фракталов.

4.     
ОПИСАНИЕ КОНТРОЛЬНОГО ПРИМЕРА

Программа FracLandscapes.exe имеет уникальную пиктограмму (рисунок 11).

Рисунок 11. - Пиктограмма программы FracLandscapes.exe

После запуска программы на экране появиться главное окно программы со сгенерированным ландшафтом (по умолчанию установлено 7 изгибов и режим каркасный). (Рисунок 12).

Рисунок 12. - Главное окно программы.

·        Файл ;

·        Правка;

·        Опции;

·        Справка;

Пункт меню Файл содержит подпункты:

·        Новый

·        Открыть…

·        Сохранить как…

·        Печать

·        Настройка печати…

·        Выход

Пункт Правка содержит подпункт Копирование.

Пункт Опции содержит подпункт Опции дисплея, при нажатии на который вызывается окно Фрактальные параметры ландшафта (рисунок 13).

Пункт Справка вызывает информацию по использованию программы и информацию о разработчике.

Рисунок 13. - Окнофрактальных параметров ландшафта.

На главном окне расположены кнопки повторяющие действия пункта Файл из меню (рисунок 13.1.).

Рисунок 13.1. - Кнопки пункта Файл из меню

Также сразу после них идут кнопки которые отвечают за количество изгибов (рисунок 13.2.).

Рисунок 13.2. - Кнопки количества изгибов.

За ними следуют кнопки выбора режима отображения ландшафта: O - каркасный, R - заполненный, F - светотень (рисунок 13.3.).

Рисунок 13.3. - Кнопки выбора режима отображения ландшафта.

Справой стороны окна расположен ползунок, с помощью которого регулируется плоскость «моря» (рисунок 13.4.).

Рисунок 13.4. - панель регуляции уровня моря.

Примеры построения ландшафта на программе FracLandscapes с использованием различных режимов и количества изгибов (Рисунки 14,15,16).

Рисунок 14. - Каркасный ландшафт построенный с помощью программы FracLandscapes.

Рисунок 15. - Заполненный ландшафт построенный с помощью программы FracLandscapes.

Рисунок 16. - Светотеневой ландшафт построенный с помощью программы FracLandscapes.