![](https://habrastorage.org/webt/19/oz/o_/19ozo_eewfsavdog--vnmd-nahy.png)
Обсуждение недавно опубликованной статьи натолкнуло меня на мысль написать свою программу, генерирующую последовательности изображений с анимацией фракталов.
Введение
Недавно на Хабре вышла статья «Сложная красота в простой формуле». И статья, и упоминаемый в ней журнал «В мире науки» меня очень заинтересовали. В комментариях kipar предложил свой вариант генерирования необычных изображений с помощью простых формул. Упрощенный алгоритм выглядит так – для получения координат точки {x, y} в диапазоне от 0 до 1 нужно многократно вызывать следующую процедуру:
x := Frac(x+sin(y));
y := Frac(y+cos(x));
Здесь Frac – функция получения дробной части числа. Мне захотелось самому написать программу, генерирующую изображения по такому алгоритму. На Паскале я писать не умею (последний раз писал на нем в школе много лет назад), поэтому написал на привычном C++.
Первый вариант
Сначала я попробовал отображать черные пикселы на белом фоне с координатами, получаемыми при циклических вызовах упрощенной формулы. Получаемые значения {x, y} в диапазоне {0, 1} умножаются на ширину и высоту картинки. Результат меня не особо впечатлил, хотя интересную особенность я заметил: с увеличением количества вызовов от нескольких десятков тысяч до миллиона в картинке всё более заполняется фон, на котором остаются белые «дыры» в форме эллипсов:
![](https://habrastorage.org/webt/dc/e9/3e/dce93egbgfk3tnrpl9ewdoojyje.gif)
Усовершенствованный алгоритм
Далее 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 тысяч итераций), далее осуществляется отрисовка всех точек в контейнере. При этом, для каждой точки каждый цвет смешивается с уже имеющимся фоном в этих координатах с весом, который тем выше, чем больше значение счетчика цвета. Пример изображения, полученного по такому алгоритму:
![](https://habrastorage.org/webt/qg/6i/gw/qg6igwezwrhkwgcisfr26roizee.png)
Изменение значений дополнительных коэффициентов позволяет разнообразить получаемые изображения. Пример для других значений coef1 и coef2 (выбраны случайным образом):
![](https://habrastorage.org/webt/jf/ry/z4/jfryz4jpe3k_2gxwss_q3y2yqra.png)
На мой взгляд, получаются довольно интересные фрактальные изображения. Изменяя значения параметров, можно получать самые разнообразные результаты.
Анимация
А что, если генерировать последовательность изображений, постепенно изменяя значения коэффициентов coef1 и coef2 за несколько сотен или тысяч шагов? Можно было бы из полученной серии сделать видеоролик, вдруг получится что-то интересное.
Я добавил в программу цикл, последовательно генерирующий изображения за указанное количество шагов (например, 1000), изменяя значение либо одного коэффициента, либо обоих сразу в указанных диапазонах. Также можно задать размеры выходного изображения в пикселах. Программа генерирует нужное количество изображений и сохраняет их в формате PNG. Формат выбран из тех соображений, что он сохраняет изображение без потерь и артефактов (в отличие от JPEG), но при этом файл получается меньше по объему, чем BMP или несжатый TIFF.
Идея сделать видео из такой последовательности, можно сказать, потерпела фиаско. В получаемых картинках очень много отдельных точек на черном фоне и контрастных переходов толщиной в один пиксел, что при сжатии в MPEG-подобные форматы сильно «размазывает» картинку и дает артефакты даже при высоких значениях битрейта. В качестве примера предлагаю посмотреть видеоролик, в котором за 2000 кадров значение параметра coef1 изменяется от 1.0 до 5.0:
По нему можно получить некоторое представление о том, как анимируются фракталы за много шагов. Но гораздо лучше установить быструю программу для просмотра изображений и смотреть в ней исходные картинки, не испорченные дополнительным пересжатием. Например, для этого хорошо подходит FastStone Image Viewer – мне эта программа давно нравится своим быстродействием. При просмотре изображений из папки она заранее подгружает их с диска в память. Достаточно в ней открыть первую картинку в папке, зажать клавишу «стрелка вправо», и программа будет с максимальной скоростью переключаться между ними. Фактически, это воспроизведение видео из последовательности изображений.
Чтобы оценить, какое качество картинки в формате PNG получается по сравнению с видео, я взял увеличенную часть одного кадра (также можно посмотреть на заглавное изображение в статье):
![](https://habrastorage.org/webt/kj/2h/12/kj2h12glwvmolumvraginahbhom.png)
Из этой же части кадра я сделал анимированный GIF (осторожно, файл 8 МБ) – из-за ограничения в количестве цветов имеются некоторые отличия от оригинала, но получить представление о том, как выглядит анимация фрактала, вполне можно. Есть также вариант помедленнее.
Update: я сделал ещё один вариант видео - исходное изображение в разрешении 720p просто растянул (upscale) до разрешения 4K. Никаких дополнительных деталей, конечно, это не добавило, однако, YouTube гораздо меньше портит такое видео пересжатием:
При просмотре лучше вручную выбрать разрешение 4К, если оно не выбралось автоматически. Необходимо, чтобы скорости канала связи и производительности компьютера хватало для плавного воспроизведения. Но лучше всего сгенерировать последовательность изображений на своем компьютере и просматривать их локально для получения максимального качества. В конце статьи имеется ссылка на репозиторий с исполняемым файлом программы.
Ускорение программы
Изображения генерируются достаточно долго – 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 [опции]
-help | показать подсказку по опциям в командной строке | |
-width {N} | ширина выходной картинки в пикселах (1280 по умолчанию) | |
-height {N} | высота выходной картинки в пикселах (720 по умолчанию) | |
-mix | если этот параметр задан, то при генерировании изображения цвет точки сразу смешивается с цветом фона, а не помещается в ассоциативный контейнер (ускоряет работу программы) | |
-outfolder {path} | путь к выходной папке для сохранения изображений | |
-steps {N} | количество выходных изображений/шагов анимации, 1 по умолчанию | |
-coef1 {v} | значение (float) коэффициента 1, 1.0 по умолчанию | |
-coef2 {v} | значение (float) коэффициента 2, 0.0 по умолчанию | |
-coef1end {v} | конечное значение (float) коэффициента 1, 2.0 по умолчанию | |
-coef2end {v} | конечное значение (float) коэффициента 2, 0.5 по умолчанию | |
-threads {N} | количество потоков исполнения программы | |
-threads half | использовать половину количества ядер ЦП в качестве количества потоков (по умолчанию) | |
-threads max | использовать полное количество ядер ЦП | |
При вызове справки -help также показывается полное количество доступных ядер ЦП |
Примеры вызова:
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.
Во время исполнения программа показывает, какое по счету изображение сейчас генерируется:
![](https://habrastorage.org/webt/2y/ds/av/2ydsavoeygcxntuzhe5n79krc48.png)
Нажатие ‘q’ прерывает исполнение работы программы. При этом завершается сохранение тех изображений, которые уже генерируются, поэтому выход может занимать некоторое время.
В той же папке в репозитории имеется файл sincos.html – если его сохранить и открыть в браузере, запускается генерирование одной картинки по тому же алгоритму:
![](https://habrastorage.org/webt/5f/fl/4n/5ffl4ncix2vpxj5tc7h8tufucio.png)
Параметры a и b соответствуют коэффициентам coef1 и coef2. Следует заметить, что в браузере изображения на вид несколько отличаются от сгенерированных программой.
В подпапке win имеется архив с собранной программой для Windows, чтобы желающие могли её запустить самостоятельно без сборки.
В заключение хочу поблагодарить samsergey и kipar за погружение в интересную тему.
Ссылки по теме
Статья «Сложная красота в простой формуле»
Библиотека libpng
Пример видео с анимацией фракталов (также вариант в разрешении 4K)
Репозиторий с исходным кодом программы fracanim
Быстрая программа для просмотра изображений FastStone Image Viewer
Продолжение: анимация фрактала Lozi map