Фрактальное пламя — алгоритм построения

в 10:45, , рубрики: Fractal flame, IFS, Алгоритмы, математика, СИФ, Фрактальное пламя, метки: , , ,

Фрактальное пламя — алгоритм построения - 1

Фрактальное пламя (или фрактальные искры, англ. fractal flame) – алгоритм, предложенный Скоттом Дрейвсом (Scott Draves) и использующий для построения изображений системы итерируемых функций (СИФ). Благодаря разным значениям seed для генератора псевдослучайных чисел можно получить множество разнообразных «картин». Хотя фрактальность в них просматривается далеко не всегда, результаты получаются очень интересными.

Под катом – краткое описание основных моментов реализации алгоритма.

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

Фрактальное пламя — алгоритм построения - 2

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

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

Фрактальное пламя — алгоритм построения - 3
Фрактальное пламя — алгоритм построения - 4
Фрактальное пламя — алгоритм построения - 5

Все это относится к коэффициентам, задающим линейное преобразование. Оставшиеся два, Фрактальное пламя — алгоритм построения - 6 и Фрактальное пламя — алгоритм построения - 7, выполняют трансляцию – перемещение точки на некоторое расстояние. Желательно, чтобы Фрактальное пламя — алгоритм построения - 8, Фрактальное пламя — алгоритм построения - 9, Фрактальное пламя — алгоритм построения - 10 и Фрактальное пламя — алгоритм построения - 11 находились на отрезке Фрактальное пламя — алгоритм построения - 12 или Фрактальное пламя — алгоритм построения - 13. Для Фрактальное пламя — алгоритм построения - 14 и Фрактальное пламя — алгоритм построения - 15 это необязательно, однако не стоит задавать слишком большой отрезок, иначе изображение получится разреженным.

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

Теперь необходимо определиться, изображение какого разрешения хотим получить и подготовить массив пикселей, каждый элемент которого будет хранить:

  • координаты x и y;
  • значения R, G и B;
  • число попаданий.

Далее приведены некоторые нелинейные преобразования, которые будут выполняться над значениями x и y, полученными после выполнения одного из аффинных преобразований:

  1. Синусоидальное: Фрактальное пламя — алгоритм построения - 16, Фрактальное пламя — алгоритм построения - 17;
  2. Сферическое: Фрактальное пламя — алгоритм построения - 18, Фрактальное пламя — алгоритм построения - 19;
  3. Полярное: Фрактальное пламя — алгоритм построения - 20, Фрактальное пламя — алгоритм построения - 21;
  4. Сердце: Фрактальное пламя — алгоритм построения - 22, Фрактальное пламя — алгоритм построения - 23;
  5. Диск: Фрактальное пламя — алгоритм построения - 24, Фрактальное пламя — алгоритм построения - 25;

В конце статьи – примеры изображений, полученных с использованием этих и некоторых других преобразований, а далее – псевдокод процедуры рендеринга:

void render(int n, int eqCount, int it, int xRes, int yRes)
{
    Генерируем eqCount аффинных преобразований со стартовыми цветами;
    for(int num=0; num<n; num++)
    {
        //Для изображения размером 1920х1080 можно 
        //взять XMIN=-1.777,XMAX=1.777,YMIN=-1,YMAX=1
        //В этом случае в большинстве нелинейных преобразований с боков не будет оставаться черных областей
        newX=Rand(XMIN,XMAX);
        newY=Rand(YMIN,YMAX);
        //Первые 20 итераций точку не рисуем, т.к. сначала надо найти начальную
        for(int step=-20; step<it; step++)
        {
            //Выбираем одно из аффинных преобразований
            i=Rand(0,eqCount);	
            //и применяем его
            x=coeff[i].a*newX+coeff[i].b*newY+coeff[i].c;
            y=coeff[i].d*newX+coeff[i].e*newY+coeff[i].f;
            Применяем нелинейное преобразование;   
            if(step>=0 && newX∈[XMIN,XMAX] && newY∈[YMIN,YMAX])
            {
                //Вычисляем координаты точки, а затем задаем цвет
                x1=xRes-Trunc(((XMAX-newX)/(XMAX-XMIN))*xRes);
                y1=yRes-Trunc(((YMAX-newY)/(YMAX-YMIN))*yRes);
                //Если точка попала в область изображения
                if(x1<xRes && y1<yRes)
                {
                    //то проверяем, первый ли раз попали в нее
                    if(pixels[x1][y1].counter==0)
                    {
                        //Попали в первый раз, берем стартовый цвет у соответствующего аффинного преобразования
                        pixels[x1][y1].red=coeff[i].red;
                        pixels[x1][y1].green=coeff[i].green;
                        pixels[x1][y1].blue=coeffs[i].blue;
                    } else
                    {
                        //Попали не в первый раз, считаем так:
                        pixels[x1][y1].red=(pixels[x1][y1].red+coeff[i].red)/2;
                        pixels[x1][y1].green=(pixels[x1][y1].green+coeff[i].green)/2;
                        pixels[x1][y1].blue=(pixels[x1][y1].blue+coeff[i].blue)/2;
                    }
                    //Увеличиваем счетчик точки на единицу
                    pixels[x1][y1].counter++;
                }
            }
        }
    }
}

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

void correction(int xRes, int yRes)
{
    max=0.0;
    gamma=2.2;
    for (int row=0; row<xRes; row++)
        for (int col=0; col<yRes; col++)
            if (pixels[row][col].counter != 0)
            {
                pixels[row][col].normal=log10(pixels[row][col].counter);
                if (pixels[row][col].normal>max)
                    max = pixels[row][col].normal;
            }
    for (int row=0; row<xRes; row++)
        for (int col=0; col<yRes; col++)
        {
            pixels[row][col].normal/=max;
            pixels[row][col].red =pixels[row][col].red*pow(pixels[row][col].normal,(1.0 / gamma));
            pixels[row][col].green =pixels[row][col].green*pow(pixels[row][col].normal,(1.0 / gamma));
            pixels[row][col].blue =pixels[row][col].blue*pow(pixels[row][col].normal,(1.0 / gamma));
        }
}

Разница между изображением без коррекции (выше) и с коррекцией (ниже)

Фрактальное пламя — алгоритм построения - 26

Фрактальное пламя — алгоритм построения - 27

Ну а теперь обещанные изображения с различными нелинейными преобразованиями

Синусоидальное

Фрактальное пламя — алгоритм построения - 28

Сферическое

Фрактальное пламя — алгоритм построения - 29

Полярное

Фрактальное пламя — алгоритм построения - 30

Сердце

Фрактальное пламя — алгоритм построения - 31

Диск

Фрактальное пламя — алгоритм построения - 32

«Ракушка»

Фрактальное пламя — алгоритм построения - 33

Гиперболическое

Фрактальное пламя — алгоритм построения - 34

Водоворот

Фрактальное пламя — алгоритм построения - 35

Волны

Фрактальное пламя — алгоритм построения - 36

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

Фрактальное пламя — алгоритм построения - 37

Фрактальное пламя — алгоритм построения - 38

Фрактальное пламя — алгоритм построения - 39

Фрактальное пламя — алгоритм построения - 40

Фрактальное пламя — алгоритм построения - 41

Исходный код

Реализация алгоритма от Джеймса Маккарти на языке Си находится здесь, а статья Скотта Дрейвса на основе которой и создавался алгоритм — здесь.

Автор: docker1

Источник

Поделиться

* - обязательные к заполнению поля