![](https://habrastorage.org/files/7b0/4ac/6a8/7b04ac6a87c841398f5e6f1bfb1293e3.png)
Фрактальное пламя (или фрактальные искры, англ. fractal flame) – алгоритм, предложенный Скоттом Дрейвсом (Scott Draves) и использующий для построения изображений системы итерируемых функций (СИФ). Благодаря разным значениям seed для генератора псевдослучайных чисел можно получить множество разнообразных «картин». Хотя фрактальность в них просматривается далеко не всегда, результаты получаются очень интересными.
Под катом – краткое описание основных моментов реализации алгоритма.
Для начала, как и в обычных СИФ, нам понадобится узнать коэффициенты для каждого аффинного преобразования плоскости (их может быть несколько; каждое следующее будет вносить свои «мазки» на картину, а также изменять вклад предыдущих). В матричной форме это преобразование выглядит следующим образом:
![](https://habrastorage.org/files/a6a/30d/99b/a6a30d99bfe143428ac419c2171655fc.gif)
Необходимо подобрать такие коэффициенты, чтобы полученное преобразование было сжимающим, то есть таким, что его коэффициент масштабирования меньше единицы. Этих преобразований должно быть несколько, и если выбирать случайным образом одно из них, чтобы вычислить новые координаты точки и отобразить ее на экране, мы получим аттрактор — множество точек, из которых и будет состоять изображение.
Используя датчик псевдослучайных чисел, получить такие коэффициенты несложно. При этом надо проверить 3 условия:
![](https://habrastorage.org/files/32a/954/0c7/32a9540c7eae472aad79623806006c62.gif)
![](https://habrastorage.org/files/78d/898/1a4/78d8981a4f814f838c82e9b1c7f6cf1e.gif)
![](https://habrastorage.org/files/0a3/f9d/cf6/0a3f9dcf67a348e3900a4f5d6c2336c1.gif)
Все это относится к коэффициентам, задающим линейное преобразование. Оставшиеся два,
![](https://habrastorage.org/files/466/be3/8f4/466be38f400348adaf58450344726a6a.gif)
![](https://habrastorage.org/files/2be/c16/22a/2bec1622a29549f7848bd142880bf544.gif)
![](https://habrastorage.org/files/6da/18d/e75/6da18de753ce4e2cb6240474c568d72c.gif)
![](https://habrastorage.org/files/689/67a/db5/68967adb55484926a0baa4235f81008b.gif)
![](https://habrastorage.org/files/7d2/267/110/7d22671101214e35886f49e4c6f3f0fe.gif)
![](https://habrastorage.org/files/ce9/9c0/021/ce99c0021628462caec8c946ede58d23.gif)
![](https://habrastorage.org/files/b36/ebf/582/b36ebf5827d943fc8cdb02084ba306d5.gif)
![](https://habrastorage.org/files/9cc/1f6/c72/9cc1f6c723c04e9887d5ccf6dd34adec.gif)
![](https://habrastorage.org/files/466/be3/8f4/466be38f400348adaf58450344726a6a.gif)
![](https://habrastorage.org/files/2be/c16/22a/2bec1622a29549f7848bd142880bf544.gif)
Кроме того, вместе с каждым набором коэффициентов, нужно сохранить стартовые значения трех цветовых составляющих модели RGB, которые будут присваиваться пикселю, в который попали первый раз. Это также делается с помощью датчика случайных чисел и особых трудностей не представляет.
Теперь необходимо определиться, изображение какого разрешения хотим получить и подготовить массив пикселей, каждый элемент которого будет хранить:
- координаты x и y;
- значения R, G и B;
- число попаданий.
Далее приведены некоторые нелинейные преобразования, которые будут выполняться над значениями x и y, полученными после выполнения одного из аффинных преобразований:
- Синусоидальное:
,
;
- Сферическое:
,
;
- Полярное:
,
;
- Сердце:
,
;
- Диск:
,
;
В конце статьи – примеры изображений, полученных с использованием этих и некоторых других преобразований, а далее – псевдокод процедуры рендеринга:
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));
}
}
Разница между изображением без коррекции (выше) и с коррекцией (ниже)![](//habrastorage.org/r/w1560/files/ba2/8d4/cb4/ba28d4cb4d6e45a4983135bdc2b54d5c.png)
![](//habrastorage.org/r/w1560/files/b4f/a90/834/b4fa908348414161825b1c6b97b9d0f1.png)
![](http://habrastorage.org/files/ba2/8d4/cb4/ba28d4cb4d6e45a4983135bdc2b54d5c.png)
![](http://habrastorage.org/files/b4f/a90/834/b4fa908348414161825b1c6b97b9d0f1.png)
Ну а теперь обещанные изображения с различными нелинейными преобразованиями
Синусоидальное
![](//habrastorage.org/r/w1560/files/4f3/102/2d9/4f31022d9ea347f4a74e134e56c07dc9.png)
Сферическое
![](//habrastorage.org/r/w1560/files/416/14c/64a/41614c64a2bc4fefb8a1ba5ef9486798.png)
Полярное
![](//habrastorage.org/r/w1560/files/bb4/334/3d7/bb43343d757d43b9ac745fe951452d05.png)
Сердце
![](//habrastorage.org/r/w1560/files/ab2/648/fa4/ab2648fa496d4875b10d39da02503016.png)
Диск
![](//habrastorage.org/r/w1560/files/b05/b62/155/b05b621551fc41e5aae6407c63494cb9.png)
«Ракушка»
![](//habrastorage.org/r/w1560/files/f82/d59/6dc/f82d596dc3794da99662e148c3c0a933.png)
Гиперболическое
![](//habrastorage.org/r/w1560/files/c91/b8b/fca/c91b8bfca2884d2ea8bbd3874b090530.png)
Водоворот
![](//habrastorage.org/r/w1560/files/5f3/057/45b/5f305745bc034a279bdff932e850b05d.png)
Волны
![](//habrastorage.org/r/w1560/files/fd6/c5b/08f/fd6c5b08f20549ee913640091574cafb.png)
![](http://habrastorage.org/files/4f3/102/2d9/4f31022d9ea347f4a74e134e56c07dc9.png)
Сферическое
![](http://habrastorage.org/files/416/14c/64a/41614c64a2bc4fefb8a1ba5ef9486798.png)
Полярное
![](http://habrastorage.org/files/bb4/334/3d7/bb43343d757d43b9ac745fe951452d05.png)
Сердце
![](http://habrastorage.org/files/ab2/648/fa4/ab2648fa496d4875b10d39da02503016.png)
Диск
![](http://habrastorage.org/files/b05/b62/155/b05b621551fc41e5aae6407c63494cb9.png)
«Ракушка»
![](http://habrastorage.org/files/f82/d59/6dc/f82d596dc3794da99662e148c3c0a933.png)
Гиперболическое
![](http://habrastorage.org/files/c91/b8b/fca/c91b8bfca2884d2ea8bbd3874b090530.png)
Водоворот
![](http://habrastorage.org/files/5f3/057/45b/5f305745bc034a279bdff932e850b05d.png)
Волны
![](http://habrastorage.org/files/fd6/c5b/08f/fd6c5b08f20549ee913640091574cafb.png)
А что если применять не одно и то же нелинейное преобразование, а случайным образом выбирать из нескольких?![](//habrastorage.org/r/w1560/files/539/8f2/d88/5398f2d88f64468faaf8e143d574ce98.png)
![](//habrastorage.org/r/w1560/files/25d/625/d99/25d625d9947b42e19d2ad91b8f32cc96.png)
![](//habrastorage.org/r/w1560/files/034/758/83d/03475883d42344d7bd4e66d2565a3534.png)
![](//habrastorage.org/r/w1560/files/635/c83/a4a/635c83a4ad004409b39322269527b869.png)
![](//habrastorage.org/r/w1560/files/e39/272/c35/e39272c3592a42a2ab9d0556c617faeb.png)
![](http://habrastorage.org/files/539/8f2/d88/5398f2d88f64468faaf8e143d574ce98.png)
![](http://habrastorage.org/files/25d/625/d99/25d625d9947b42e19d2ad91b8f32cc96.png)
![](http://habrastorage.org/files/034/758/83d/03475883d42344d7bd4e66d2565a3534.png)
![](http://habrastorage.org/files/635/c83/a4a/635c83a4ad004409b39322269527b869.png)
![](http://habrastorage.org/files/e39/272/c35/e39272c3592a42a2ab9d0556c617faeb.png)
Исходный код
Реализация алгоритма от Джеймса Маккарти на языке Си находится здесь, а статья Скотта Дрейвса на основе которой и создавался алгоритм — здесь.