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

 

4. Типы фракталов

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

 

 

Именно с них и начиналась история фракталов. Фракталы этого класса самые наглядные. Геометрическими названы фракталы, форма которых может быть описана как последовательность простых геометрических операций. Геометрические фракталы строятся на основе исходной фигуры — линии, полигона, полиэдра — путем ее дробления и выполнения аффинных и логических преобразований (объединения или исключения) полученных фрагментов. В двухмерном случае их получают с помощью некоторой ломаной (или поверхности в трехмерном случае), называемой генератором. За один шаг алгоритма каждый из отрезков, составляющих ломаную, заменяется на ломаную-генератор в соответствующем масштабе. В результате бесконечного повторения этой процедуры получается геометрический фрактал.

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

Кривая Пеано (Рис.А.4) является геометрическим фракталом. На рисунках А.5, А.6 и А.7 приведены другие примеры геометрических фракталов, таких как треугольник Серпинского, ломаная дракона и кривая Леви.

 

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

 

 

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

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

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

где — комплексное число, а некая функция. Расчет данной функции продолжается до выполнения определенного условия. И когда это условие выполнится — на экран выводится точка. При этом значения функции для разных точек комплексной плоскости может иметь разное поведение:

1. С течением времени стремится к бесконечности.

2. Стремится к 0

3. Принимает несколько фиксированных значений и не выходит за их пределы.

4. Поведение хаотично, без каких либо тенденций.

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

Одними из самых известных фракталов этой группы является множества Мандельброта и Жюлиа, представленные на рисунках А.8 и А.9.

 

 

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

 

 

Два профессора математики из Технологического института штата Джорджия в середине 80-х годов разработали широко используемый метод, известный как Системы Итерируемых Функций («Iterated Functions System» — IFS).

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

 

X' = A*X + B*Y + C,        (3.1)

Y' = D*X + E*Y + F.         (3.2)

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

На основании этих идей Барнсли и Слоан создали алгоритм, который, по их утверждению, позволит сжимать информацию в 500—1000 раз[11]. Этот метод можно описать следующим образом. Изображение кодируется несколькими простыми преобразованиями, т.е. коэффициентами этих преобразований (в нашем случае A, B, C, D, E, F). Например, закодировав какое-то изображение двумя аффинными преобразованиями, мы однозначно определяем его с помощью 12-ти коэффициентов. Если теперь задаться какой-либо начальной точкой (например, ) и запустить итерационный процесс, то мы после первой итерации получим две точки, после второй — четыре, после третьей — восемь и т.д. Через несколько десятков итераций совокупность полученных точек будет описывать закодированное изображение. Но проблема состоит в том, что очень трудно найти коэффициенты IFS, которая кодировала бы произвольное изображение.

С помощью этого метода можно создать реалистичные изображения природных объектов, таких как листья папоротника, деревья, при этом неоднократно применяются преобразования, которые двигают, изменяют в размере и вращают части изображения. В IFS используется самоподобие, которое есть у творений природы, и объект моделируется как композиция множества мельчайших копий самого себя.

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

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

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

 

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

 

 

Еще одним известным классом фракталов являются стохастические фракталы, которые получаются в том случае, если в итерационном процессе случайным образом менять какие-либо его параметры. При этом получаются объекты, очень похожие на природные — несимметричные деревья, изрезанные береговые линии и т.д. Кривая Коха, как бы ни была похожа на границу берега, не может выступать в качестве её модели из-за того, что она всюду одинакова, самоподобна, слишком «правильна». Все природные объекты создаются по капризу природы, в этом процессе всегда есть случайность.

 К  этому классу фракталов относится  и фрактальная монотипия, или  стохатипия. Термин «стохастичность» происходит от греческого слова,   обозначающего   «предположение». 

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

Стохастические фракталы отличаются от детерминированных именно способностью симулировать индивидуальность и неповторимость каждого элемента системы. Однако внесение случайных отклонений в процедуры построения фракталов не отменяет определённых закономерностей для групп элементов «в среднем».

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

Примерами таких фракталов являются Плазма (Рис.В.1—В.5), рандомизированный фрактал на основе множества Жюлиа, траектория броуновского движения на плоскости и в пространстве.

 

 

1.5. Шероховатость

 

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

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

 

 

Плазма — это пример использования стохастического фрактала в компьютерной графике. Рассмотрим его рекурсивный алгоритм:

1. Задать оттенок цвета для каждого из четырех углов прямоугольника.
2. Вычислить средние значения оттенков для середин сторон и центра, используя среднее арифметическое.
3. Случайно изменить центральный оттенок. Величина изменения должна зависеть от размеров прямоугольника. Чем больше случайное число — тем более «рваным» будет рисунок.
4. Разделить прямоугольник на четыре равные части, в углах которых будут полученные средние значения цветов.

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

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

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

 

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

 

В разделе описания типов создаем новый тип Color — запись, содержащия три поля цвета Red, Green, Blue. В разделе описания переменных определяем двумерный массив, состоящий из записей Color.

A: array[0..512,0..512] of Color;

Прописываем событие Button1Click. Присваиваем значение оттенка цвета для каждого угла прямоугольника. Если поле Edit с оттенком цвета оказалось пустым, заполняем  случайным значением. Булева переменная ch содержит в себе информацию о корректности вводимых значений.

if edit1.Text='' then A[0,0].red:=Random(256)

else  if (StrToInt(edit1.Text)>=0) and (StrToInt(edit1.Text)<256)

       then A[0,0].red:=StrToInt(edit1.Text)

else ch:=true;

Если ch примет значение true, то нужно вывести на экран сообщение об ошибке.

Application.MessageBox('Ошибка! Введите значение от 0 до 255',    'Внимание!',MB_ICONWARNING+MB_OK);

Далее мы вызываем рекурсивную процедуру Midpoint, указывая  координаты верхнего левого и нижнего правого угла прямоугольника.

Midpoint(0,0,512,512);

Эта процедура содержит в себе подпроцедуру GetIntens(xa,ya,x,y,xb,yb: integer); Получаем новую интенсивность цвета, добавляя элемент случайности, и заносим в массив целое число в соответствующее поле.

d:=Abs(xa-xb)+Abs(ya-yb); // полупериметр

v:=(A[xa,ya].red+A[xb,yb].red)/2+(Random-0.5)*d*k;// k— шероховатость

    if v<1 then v:=1;

    if v>255 then v:=255;

A[x,y].red:=Trunc(v); // возвращает целый результат

Введем условие, которое будет ограничивать рекурсивную процедуру.

Она будет выполняться, пока не заполнятся все пиксели.

if (Cx3-Ax1<2) and (Cy3-Ay1<2) then Exit;

Получим новые значения x и y.

   x:=(Ax1+Cx3) div 2;

   y:=(Ay1+Cy3) div 2;

Рассчитаем интенсивность цвета для  четырех средних точек сторон треугольника.

    GetIntens(Ax1,Ay1,x,Ay1,Cx3,Ay1);

   GetIntens(Cx3,Ay1,Cx3,y,Cx3,Cy3);

   GetIntens(Ax1,Cy3,x,Cy3,Cx3,Cy3);

   GetIntens(Ax1,Ay1,Ax1,y,Ax1,Cy3);

   Для середины прямоугольника:

    v:=(A[Ax1,Ay1].red+A[Cx3,Ay1].red+A[Cx3,Cy3].red+A[Ax1,Cy3].red)/4;

   A[x,y].red:=Trunc(v);

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

   Midpoint(Ax1,Ay1,x,y);

   Midpoint(x,Ay1,Cx3,y);

   Midpoint(x,y,Cx3,Cy3);

   Midpoint(Ax1,y,x,Cy3);

Вывод изображения на канву компонента Image:

   for x:=0 to 512 do

         Begin

            for y:=0 to 512 do

            Image1.Canvas.Pixels[x,y]:=rgb(A[x,y].red, 0, 0);

            Image1.update;

         End;

Процедура Border рисует границы изображения.

     Процедура Edit1KeyPress запрещает ввод всех символов, кроме цифр.

procedure TForm1.Edit1KeyPress(Sender: TObject; var Key: Char);

begin

case Key of

    #8,'0'..'9' : ;

    else key := Chr(0);

    end;

end;

Листинг программы представлен в приложении Б, а интерфейс — в приложении В.