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

Введение

Недавно на Хабре вышла статья «Сложная красота в простой формуле». И статья, и упоминаемый в ней журнал «В мире науки» меня очень заинтересовали. В комментариях kipar предложил свой вариант генерирования необычных изображений с помощью простых формул. Упрощенный алгоритм выглядит так – для получения координат точки {x, y} в диапазоне от 0 до 1 нужно многократно вызывать следующую процедуру:

x := Frac(x+sin(y));
y := Frac(y+cos(x));

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

Первый вариант

Сначала я попробовал отображать черные пикселы на белом фоне с координатами, получаемыми при циклических вызовах упрощенной формулы. Получаемые значения {x, y} в диапазоне {0, 1} умножаются на ширину и высоту картинки. Результат меня не особо впечатлил, хотя интересную особенность я заметил: с увеличением количества вызовов от нескольких десятков тысяч до миллиона в картинке всё более заполняется фон, на котором остаются белые «дыры» в форме эллипсов:

Усовершенствованный алгоритм

Далее kipar предложил более развернутый вариант процедуры:

RandSeed := 1;
for i := 1 to 100 do
begin
  x := random;
  y := random;
  color := Random(MaxLongint);
  for j := 1 to 1000 do
  begin
    pr2d_Pixel(x*W,y*H,color); // отобразить пиксел в картинке шириной W и высотой H пикселов
    x := Frac(x+cos(y));
    y := Frac(y+sin(x));
  end;
end;

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

В псевдокоде её можно представить следующим образом:

int w, h; // ширина и высота выходного изображения в пикселах
double coef1, coef2; //коэффициенты со значениями по умолчанию 1.0 и 0.0
double fx, fy;
int x, y;
for (int j = 0; j < 500; j++) {
  fx <- поместить случайное число от 0.0 до 1.0
  fy <- поместить случайное число от 0.0 до 1.0
  col <- поместить случайный цвет из фиксированной таблицы в 8 цветов
  for (int i = 0; i < 1000; i++) {
    x = int(fx * w); // получить координату X в выходном изображении
    y = int(fy * h); // получить координату Y в выходном изображении
    AddPixel(x, y, col); // добавить цвет точки в контейнер или инкрементировать вес цвета
    fx = frac(fx + sin(fy - coef2));
    fy = frac(fy + cos(fx * coef1));
  }
}
// далее нужно отрисовать пикселы из заполненного контейнера,
// смешивая цвет пиксела с цветом фона с некоторым весом

Основные отличия следующие:

• Значение цвета генерируется не как случайное число, а берется случайное значение из фиксированной таблицы в 8 цветов

• Добавлены дополнительные коэффициенты coef1 и coef2 (по умолчанию со значениями 1.0 и 0 соответственно)

• Функция AddPixel не сразу отображает точку с текущим цветом на экране, а помещает цвет точки в ассоциативный контейнер pixColorMap:

struct pair_hash
{
	template <class T1, class T2>
	std::size_t operator() (const std::pair<T1, T2>& pair) const {
		return std::hash<T1>()(pair.first) ^ std::hash<T2>()(pair.second);
	}
};
using colorMap = std::unordered_map<uint32_t, int>;
using pixColorMap = std::unordered_map<std::pair<int, int>, colorMap, pair_hash>;

Каждый элемент контейнера ставит в соответствие паре координат точки {x, y} ещё один контейнер colorMap, в котором каждый элемент содержит значение цвета и счетчик, который инкрементируется каждый раз, когда в эти же координаты попадает точка этого цвета. Функция AddPixel либо добавляет новую точку в контейнер, если таких координат {x, y} в контейнере ещё нет, либо инкрементирует значение счетчика для значения цвета точки. Если такого цвета в этих координатах не было, значение цвета добавляется со значением счетчика 1.

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

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

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

Анимация

А что, если генерировать последовательность изображений, постепенно изменяя значения коэффициентов coef1 и coef2 за несколько сотен или тысяч шагов? Можно было бы из полученной серии сделать видеоролик, вдруг получится что-то интересное.

Я добавил в программу цикл, последовательно генерирующий изображения за указанное количество шагов (например, 1000), изменяя значение либо одного коэффициента, либо обоих сразу в указанных диапазонах. Также можно задать размеры выходного изображения в пикселах. Программа генерирует нужное количество изображений и сохраняет их в формате PNG. Формат выбран из тех соображений, что он сохраняет изображение без потерь и артефактов (в отличие от JPEG), но при этом файл получается меньше по объему, чем BMP или несжатый TIFF.

Идея сделать видео из такой последовательности, можно сказать, потерпела фиаско. В получаемых картинках очень много отдельных точек на черном фоне и контрастных переходов толщиной в один пиксел, что при сжатии в MPEG-подобные форматы сильно «размазывает» картинку и дает артефакты даже при высоких значениях битрейта. В качестве примера предлагаю посмотреть видеоролик, в котором за 2000 кадров значение параметра coef1 изменяется от 1.0 до 5.0:

По нему можно получить некоторое представление о том, как анимируются фракталы за много шагов. Но гораздо лучше установить быструю программу для просмотра изображений и смотреть в ней исходные картинки, не испорченные дополнительным пересжатием. Например, для этого хорошо подходит FastStone Image Viewer – мне эта программа давно нравится своим быстродействием. При просмотре изображений из папки она заранее подгружает их с диска в память. Достаточно в ней открыть первую картинку в папке, зажать клавишу «стрелка вправо», и программа будет с максимальной скоростью переключаться между ними. Фактически, это воспроизведение видео из последовательности изображений.

Чтобы оценить, какое качество картинки в формате PNG получается по сравнению с видео, я взял увеличенную часть одного кадра (также можно посмотреть на заглавное изображение в статье):

Из этой же части кадра я сделал анимированный GIF (осторожно, файл 8 МБ) – из-за ограничения в количестве цветов имеются некоторые отличия от оригинала, по получить представление о том, как выглядит анимация фрактала, вполне можно. Есть также вариант помедленнее.

Ускорение программы

Изображения генерируются достаточно долго – 500 тысяч шагов в таком алгоритме исполняются несколько секунд. Чтобы ускорить работу программы, я реализовал очевидный подход – генерировать изображения параллельно в нескольких потоках. Допустим, нужно сохранить 1000 изображений в 5 потоках. В первом потоке генерируется каждое 5-е изображение, начиная с первого, во втором потоке – каждое 5-е, начиная со второго, и т.д.

Я заметил, что даже если количество потоков взять равным количеству логических ядер процессора в машине (из функции std::thread::hardware_concurrency), то нагрузка процессора не вырастает до 100%. Причина стала понятна довольно быстро: после того, как изображение сгенерировано, оно в этом же потоке сохраняется в формат PNG, при этом запись на диск занимает некоторое время.

Тогда я сделал следующее: после того, как изображение сгенерировано, запускается ещё один поток, в который передается картинка, после этого вызывающий поток генерирует уже следующее изображение, а в это время в дополнительном потоке готовая картинка сохраняется в формат PNG. После этого при запуске программы на максимальном количестве ядер процессор загружен на 100%, и генерирование последовательности изображений производится максимально быстро.

Готовая программа

Код программы на C++ я выложил в репозиторий. Создана под Windows в Microsoft Visual Studio 2019, также успешно собрана и проверена в Ubuntu 22.04.4 LTS (под WSL). Для сборки требует C++20 и библиотеку libpng.

Запускается из командной строки со следующими параметрами:

fracanim.exe [опции]

Примеры вызова:

fracanim.exe -outfolder D:\tmp\png -coef1 1.2 -coef2 0.1

Создает одну картинку 'D:\tmp\png\image.png' размерами 1280x720, используя коэффициенты: coef1=1.2 и coef2=0.1

fracanim.exe -outfolder D:\tmp\png -steps 1000 -width 1920 -height 1080 -coef1 1.0 -coef1end 5.0 -coef2 0 -coef2end 0 -threads max

Создает 1000 изображений размерами 1920x1080 в папке 'D:\tmp\png' с исполнением на максимальном количестве ядер ЦП. Используется анимация только коэффициента coef1 от 1.0 до 5.0, коэффициент coef2 установлен в 0.

Во время исполнения программа показывает, какое по счету изображение сейчас генерируется:

Нажатие ‘q’ прерывает исполнение работы программы. При этом завершается сохранение тех изображений, которые уже генерируются, поэтому выход может занимать некоторое время.

В той же папке в репозитории имеется файл sincos.html – если его сохранить и открыть в браузере, запускается генерирование одной картинки по тому же алгоритму:

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

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

В заключение хочу поблагодарить samsergey и kipar за погружение в интересную тему.

Ссылки по теме

• Статья «Сложная красота в простой формуле»

• Библиотека libpng

• Пример видео с анимацией фракталов

• Репозиторий с исходным кодом программы fracanim

• Быстрая программа для просмотра изображений FastStone Image Viewer