Стохастические фракталы в компьютерной графике

Министерство образования и науки Российской Федерации

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

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

«Северный  (Арктический) федеральный университет имени М.В. Ломоносова»

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

Клевенская Наталья Владимировна

(фамилия, имя, отчество студента)

Институт

МиКН

курс

1

группа

15

КУРСОВАЯ  РАБОТА

По дисциплине

Информатика и программирование

На тему

Стохастические фракталы в компьютерной графике

Работа допущена к защите

Руководитель

(дата)

Старший преподаватель кафедры

О.А.Юфрякова

(должность)

(подпись)

(и.,о., фамилия)

(дата)

Архангельск 2012

 

ОГЛАВЛЕНИЕ

 

ВВЕДЕНИЕ          3

ГЛАВА I. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ      4

1. Понятие «Фрактал»       4
2. История возникновения фракталов     5
3. Фрактальная размерность      8
4. Типы фракталов        10

  1.4.1 Геометрические фракталы .     10

  1.4.2 Алгебраические фракталы .     11 

  1.4.3 Системы итерируемых функций.     12

  1.4.4 Стохастические фракталы.     14

5. Шероховатость        16

ГЛАВА II. ПРАКТИЧЕСКАЯ ЧАСТЬ      17

2.1  Алгоритм построения фрактала «Плазма»   17

2.2 Разработка программного кода     18

2.3. Описание работы программы      20

 

ЗАКЛЮЧЕНИЕ          22

СПИСОК ЛИТЕРАТУРЫ        23

ПРИЛОЖЕНИЯ          24

ПРИЛОЖЕНИЕ А.        24

ПРИЛОЖЕНИЕ Б.        27

ПРИЛОЖЕНИЕ В.        34

 

 

ВВЕДЕНИЕ

 

 

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

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

Основными задачами являются ознакомление с историей и видами фракталов, определение их роли в компьютерной графике, изучение алгоритма построения стохастического фрактала.

Объектом исследования стала фрактальная графика.

Предметом исследования является методика построения фрактальных множеств.

Программа будет полезна при моделировании плазмы, а также при генерации некоторых природных форм.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ГЛАВА I. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

 

1. Понятие «Фрактал»

 

 

 

Термин фрактал (от латинского слова fractus — «дробный, изломанный, состоящий из частей») был введен в 1975 году известным французским математиком Бенуа Мандельбротом и использован для описания нерегулярных, но самоподобных структур. Определение фрактала, данное Мандельбротом, звучит так: «Фракталом называется структура, состоящая из частей, которые в каком-то смысле подобны целому»1. Фракталы самоподобны, а это означает, что их форма воспроизводится на различных масштабах. Так, при увеличении маленькие фрагменты становятся очень похожи на большие. Фрактал можно приближать до бесконечности, при этом он не изменит своих геометрических особенностей.

Другим свойством, которым обладают фракталы, является фрактальная, дробная размерность. На основании этого Мандельброт дает еще одно определение: «Фракталом называется множество, размерность Хаусдорфа — Безиковича для которого строго больше его топологической размерности».2

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

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

2. История возникновения фракталов

 

 

 

В 1922 году английский математик и метеоролог Льюис Фрай Ричардсон опубликовал работу, посвященную математическим моделям предсказания погоды. Он обратил внимание на то, что в «ожесточенном пении ветров» есть порядок. При исследовании турбулентности (хаотических вихрей) воздушных потоков он обнаружил каскад энергии — от больших вихрей к малым, то есть своеобразную гармонию: маленькие вихри возникают внутри больших и как бы повторяют их форму и поведение.[3]

Позже Ричардсон провел эксперимент по определению длины береговой линии Британии способом, применяемым для оценки гладких кривых. Померив берег с помощью километровой линейки, мы получим какую-то длину. Однако мы пропустим много небольших заливчиков и полуостровков, которые по размеру намного меньше нашей линейки. Уменьшив размер линейки до, скажем, 1 метра — мы учтем эти детали ландшафта, и, соответственно длина берега станет больше. Пойдем дальше и измерим длину берега с помощью миллиметровой линейки, мы тут учтем детали, которые больше миллиметра, длина будет еще больше. В итоге ответ на такой, казалось бы, простой вопрос может поставить в тупик кого угодно — длина берега Британии бесконечна.[5]

В 1961 году в его работе, опубликованной после смерти, Мандельброт нашел формулу, по которой была вычислена длина западного участка Британского побережья и испано-португальской границы[9]. Ричардсон заметил, что результаты измерения сильно зависят от масштаба карты. Выяснилось, что чем крупнее берется масштаб, тем более длинной оказывается береговая линия, и наоборот.

 

 

 

Длина береговой линии L увеличивается по степенному закону

 

(1)

 

где а — масштаб;

R — длина измеряемого контура;

D>1 — некоторый показатель степени, называемый фрактальной размерностью береговой линии[12].

Мандельброт, исследуя геометрические свойства морских побережий, обнаружил, что они не подчиняются привычным правилам подобия, и отметил: «Береговые линии по своей структуре фрактальны»3. Он показал, что при бесконечном уменьшении мерки длина береговой линии неограниченно растёт. Мандельброт привел свою оценку дробной размерности для западного побережья Великобритании равную 1,3.

История фрактальной геометрии тесно связана с именами таких известных математиков, как Вейерштрасс, Кантор, Пеано, Хаусдорф, Безикович, Кох, Серпинский и др. Вейерштрасс впервые ввел в обращение непрерывную, но нигде не дифференцируемую функцию, а Хаусдорф в 1919г. — понятие о дробной размерности множеств и привел первые примеры таких множеств[4]. Среди них были канторовское множество (Рис.А.1), кривая Коха (Рис.А.2) и другие экзотические объекты, мало в то время известные за пределами чистой математики. Оригинальные идеи Хаусдорфа впоследствии были существенно развиты Безиковичем.

Большой вклад в будущую фрактальную геометрию внесли также знаменитые работы французских математиков Г. Жюлиа и П. Фату, которые в начале 20 века занимались теорией рациональных отображений в комплексной плоскости. В их работах содержатся многочисленные примеры «хаотических траекторий», символическая динамика, а в завуалированной форме и странные аттракторы, бифуркация удвоения периода и многое другое, составляющее фундамент современной теории хаоса[13]. Практически полностью забытая их деятельность получила неожиданное развитие в начале восьмидесятых годов, когда с помощью компьютеров математикам удалось получить прекрасные картины, показывающие примеры таких отображений.

Рождение фрактальной геометрии принято связывать с выходом в 1977 году книги Мандельброта «The Fractal Geometry of Nature». В его работах использованы научные результаты выше названных ученых, работавших в период 1875-1925 годов в той же области. Мандельброт писал, сопоставляя классическую геометрию с новой - фрактальной геометрией: «Почему геометрию часто называют холодной и сухой? Одна из причин - её неспособность описать форму облака, горы, дерева или береговой линии. Облака не являются сферами, горы – конусами, береговые линии нельзя изобразить с помощью окружностей, кору деревьев не назовешь гладкой, а путь молнии прямолинейным. Природа демонстрирует не просто более высокую степень, но совершенно иной уровень сложности. Количество различных масштабов длины в естественных формах можно считать бесконечным для каких угодно практических задач. Существование таких феноменов бросает нам вызов и побуждает заняться подробным изучением тех из форм, которые Евклид отложил в сторону из-за их бесформенности – исследовать, так сказать морфологию аморфного».4 Математики получили новый мир геометрических объектов. Мир фрактальной геометрии.

 

3. Фрактальная размерность

 

 

Независимо от природы или метода построения у всех фракталов есть одно важное общее свойство: степень изрезанности или сложности их структуры может быть измерена неким характеристическим числом — фрактальной размерностью. Различные определения понятия фрактальной размерности в большей или меньшей степени восходят к работе Ф. Хаусдорфа, опубликованной в 1919 году. Он определил α-меру для любого α ≥ 0 и на этой основе каждому множеству в евклидовом пространстве сопоставил число, названное им метрической размерностью[1].

Известно, что линия имеет размерность 1. Это означает, что, выбрав точку отсчета, мы можем любую точку на этой линии определить с помощью 1 числа — положительного или отрицательного. Причем это касается всех линий — окружность, квадрат, парабола и т.д.

Размерность 2 означает, что любую точку мы можем однозначно определить двумя числами. Двумерный — не значит плоский. Поверхность сферы тоже двумерна.

Если смотреть с математической точки зрения, то размерность определяется следующим образом: для одномерных объектов — увеличение в два раза их линейного размера приводит к увеличению размеров, в данном случае длины, в два раза .

Для двумерных объектов увеличение в два раза линейных размеров приводит к увеличению размера (например, площадь прямоугольника) в четыре раза .

Для 3-х мерных объектов увеличение линейных размеров в два раза приводи к увеличению объема в восемь раз и так далее[11].

Таким образом, размерность D можно рассчитать исходя из зависимости увеличения «размера» объекта M от увеличения линейных размеров L. (Рис.А.3).

 

.        (2)

 

Так, для линии

для плоскост,

для объема

 

Следуя идее Мандельброта, фрактальную размерность можно определить методом подсчёта квадратиков. Представим себе объект сложной формы, который сплошь покрыт квадратиками, как миллиметровая бумага. Часть квадратиков будет содержать элементы множества, другие квадратики будут пустыми. Число непустых клеток N зависит от формы объекта и от размеров квадратной ячейки E. Постулируется, что N пропорционально (чем мельче решётка, тем больше непустых ячеек). Показатель степени D и является размерностью объекта. Например, для такой сплошной плоской фигуры, как круг, уменьшение размера решётки вдвое приведёт к увеличению количества непустых клеток в четыре раза (два в квадрате), потому что фигура обладает размерностью два. Для фрактала количество непустых клеток будет возрастать с несколько меньшим, дробным показателем степени.