Сегодня я расскажу о том, как я осуществил перенос наработок из проекта нашей библиотеки для обработки изображений Raster and Image Processor (RIP) в библиотеку «швейцарский нож для D» dlib. В статье я немного расскажу о том, как при минимуме усилий и использованной инфраструктуре проекта rip, мне удалось подарить вторую жизнь старой идее реализации Итерируемой Системы Функций (ИФС) и перенести ее со старой dgui (об этом я уже как-то писал) в новую среду.
Итерируемая система функций (более известна под названием итерированная система функций) или ИФС – это удобный математический аппарат для описания фрактальных или фракталоподобных изображений через задание системы уравнений. Система уравнений задается для некоторой начальной точки (обычно, эта точка с координатами (0;0), т.е начало координат) и применяется к ней итеративно, причем, каждое уравнение из системы имеет свою вероятность «быть примененным» к точке. Исходя из этого, для получения некоторого изображения из единственной точки нам нужна система уравнений и некоторое количество раз применения для уравнений, каждое из которых применяется единственный раз в некоторый момент времени. Следуя традиции, один раз применения системы к точке (т.е применения какого-либо уравнения из системы) называется одним поколением ИФС.
Также, для удобства позиционирования графического образа системы на плоскость, можно ввести еще ряд параметров, а именно, масштабы по осям X и Y, а также коэффициенты смещения относительно стартовой точки по тем же самым осям.
Применяя все эти допущения, математический аппарат не содержит ничего серьезного, кроме простой подстановки текущих значений X и Y, в простые линейные уравнения, содержащие шесть коэффициентов. Эти коэффициенты удобно обозначить латинскими буквами: a, b, c, d, e, f и ввести еще один коэффициент p, обозначающий вероятность использования уравнения на текущем шаге. Детали реализации вычисления по этим коэффициентам были нами рассмотрены в статье «Усовершенствуем лист папоротника», но в контексте библиотеки dgui.
Теперь, когда обозначены многие аспекты относительно предыдущей реализации ИФС, можно перейти к непосредственному переносу разработок из rip в dlib.
В rip были использованы несколько иные соображения, чем в dlib. Дело в том, что при создании rip, мы предполагали, что в пределах этой библиотеки можно будет использовать в функциях любые числовые типы (или приводимые к таковым), что позволило бы снизить нагрузку на программиста и сделало бы использование библиотеки более комфортным. Этого мы добились тем, что ввели автоматическую проверку на то, все ли из используемых в шаблонах параметров типов, являются числовыми, а также автоматическим приведением к некоторому удобному для расчетов арифметическому типу.
И этот факт нужно учесть, взяв из модуля templates библиотеки rip шаблон allArithmetic.
Помимо этого, в rip мы ввели еще один интересный шаблон addTypedGetter, который позволял нам автоматически генерировать свойства многих объектов библиотеки, которые могли бы давать конкретный нужный в данный момент тип с помощью прямого его указания после имени свойства.
Эти шаблоны одного из базовых модулей rip мы разместим в файле concepts.d:
module concepts;
private
{
import std.meta : allSatisfy;
import std.traits : isIntegral, isFloatingPoint, Unqual;
}
// Проверяем все ли типы арифметические (т.е числовые)
template allArithmetic(T...)
if (T.length >= 1)
{
template isNumberType(T)
{
enum bool isNumberType = isIntegral!(Unqual!T) || isFloatingPoint!(Unqual!T);
}
enum bool allArithmetic = allSatisfy!(isNumberType, T);
}
// Генерируем универсальный геттер
template addTypedGetter(string propertyVariableName, string propertyName)
{
import std.string : format;
const char[] addTypedGetter = format(
`
@property
{
T %2$s(T)() const
{
import std.conv : to;
alias typeof(return) returnType;
return to!(returnType)(%1$s);
}
}`,
propertyVariableName,
propertyName
);
}
В этом коде, используется наш привычный прием с кодогенерацией на стадии компиляции, но кроме этого мы реализуем генерацию геттера с требуемым типом с помощью приведения к «универсальному типу» возвращаемого значения (эта конструкция неплохо описана в руководстве по D).
А теперь можно перейти к реализации непосредственно ИФС для чего создадим файл ifs.d и добавим туда очень много импортов из стандартной библиотеки Phobos (и из модуля concepts), причем в приватном режиме:
module ifs;
private
{
import std.algorithm;
import std.math;
import std.range;
import std.random;
import std.string;
import concepts;
import dlib.image;
import std.stdio;
}
Создадим структуру данных, которая будет описывать стартовую точку для отрисовки итерируемой системы функций:
// Стартовая точка для IFS
class IFS_StartPoint
{
private
{
float x;
float y;
}
// Универсальный конструктор
this(T, U)(T x, U y)
if (allArithmetic!(T, U))
{
this.x = cast(float) x;
this.y = cast(float) y;
}
// Получить X координату
mixin(addTypedGetter!("x", "getX"));
// Получить Y координату
mixin(addTypedGetter!("y", "getY"));
// Установить X координату
void setX(T)(T x)
if (allArithmetic!T)
{
this.x = cast(float) x;
}
// Установить Y координату
void setY(T)(T y)
if (allArithmetic!T)
{
this.y = cast(float) y;
}
}
В данном случае, мы создаем класс, отражающий наше понимание некоторой точки плоскости: в этом классе есть универсальный конструктор, способный принять любой числовой тип данных, набор сеттеров для X и Y координат точки, а также микшины, которые встраивают «универсальный геттер» (который взят из модуля concepts).
Аналогично этому классу создаем класс, который будет представлять собой набор масштабирующих (управляют масштабом ИФС по осям) и смещающих (управляют смещением ИФС относительно стартовой точки):
// Масштабирование ИФС
class IFS_Scales
{
private
{
float scaleX;
float scaleY;
float offsetX;
float offsetY;
}
this(T, U, V, W)(T scaleX, U scaleY, V offsetX, W offsetY)
if (allArithmetic!(T, U, V, W))
{
this.scaleX = scaleX;
this.scaleY = scaleY;
this.offsetX = offsetX;
this.offsetY = offsetY;
}
// Масштаб по оси X
mixin(addTypedGetter!("scaleX", "getScaleX"));
// Масштаб по оси Y
mixin(addTypedGetter!("scaleY", "getScaleY"));
// Смещение по оси X
mixin(addTypedGetter!("offsetX", "getOffsetX"));
// Смещение по оси Y
mixin(addTypedGetter!("offsetY", "getOffsetY"));
// Установить масштаб для оси X
void setScaleX(T)(T scaleX)
if (allArithmetic!T)
{
this.scaleX = cast(float) scaleX;
}
// Установить масштаб для оси Y
void setScaleY(T)(T scaleY)
if (allArithmetic!T)
{
this.scaleY = cast(float) scaleY;
}
// Установить смещение по оси X
void setOffsetX(T)(T offsetX)
if (allArithmetic!T)
{
this.offsetX = cast(float) offsetX;
}
// Установить смещение по оси Y
void setOffsetY(T)(T offsetY)
if (allArithmetic!T)
{
this.offsetY = cast(float) offsetY;
}
}
И, теперь мы можем описать одно уравнение системы итерируемых функций со всеми коэффициентами и удобным методом отображения:
// Одно уравнение ИФС
class IFS_Equation
{
private
{
float a;
float b;
float c;
float d;
float e;
float f;
float p;
}
// Получение коэффициентов ИФС
mixin(addTypedGetter!("a", "getA"));
mixin(addTypedGetter!("b", "getB"));
mixin(addTypedGetter!("c", "getC"));
mixin(addTypedGetter!("d", "getD"));
mixin(addTypedGetter!("e", "getE"));
mixin(addTypedGetter!("f", "getF"));
mixin(addTypedGetter!("p", "getP"));
// Универсальный конструктор строк для задания коэффициентов ИФС
this(R, S, T, U, V, W, Z)(R a, S b, T c, U d, V e, W f, Z p)
if (allArithmetic!(R, S, T, U, V, W, Z))
{
this.a = a;
this.b = b;
this.c = c;
this.d = d;
this.e = e;
this.f = f;
this.p = p;
}
void setA(T)(T a)
if (allArithmetic!T)
{
this.a = cast(float) x;
}
void setB(T)(T b)
if (allArithmetic!T)
{
this.b = cast(float) b;
}
void setC(T)(T c)
if (allArithmetic!T)
{
this.c = cast(float) c;
}
void setD(T)(T d)
if (allArithmetic!T)
{
this.d = cast(float) d;
}
void setE(T)(T e)
if (allArithmetic!T)
{
this.e = cast(float) e;
}
void setF(T)(T f)
if (allArithmetic!T)
{
this.f = cast(float) f;
}
// Установить вероятность применения уравнения
void setP(T)(T p)
if (allArithmetic!T)
{
this.p = cast(float) p;
}
override string toString()
{
return format("IFS_Equation(%f, %f, %f, %f, %f, %f, probability = %f)", a, b, c, d, e, f, p);
}
}
Здесь мы используем все те же приемы, что и рассмотренные ранее, в том числе и ограничение сигнатуры методов-сеттеров с помощью соответствующего шаблона (template constrain, так кажется называется эта идея). Также, сам класс берет на себя обязанность по приведению любых параметров к удобному для расчетов float.
Имея одно уравнение ИФС, которое просто служит хранилищем параметров, можно удобным образом построить контейнер, который будет хранить все уравнения некоторой системы и для этого введем псевдоним для массива уравнений системы и создадим новый класс, который будет управлять расчетами над текущей системой уравнений:
// Система уравнений ИФС
alias IFS_EquationSystem = IFS_Equation[];
// Сама ИФС
class IFS
{
private
{
SuperImage surface;
Color4f color;
IFS_EquationSystem equationSystem;
IFS_StartPoint point;
IFS_Scales scales;
ulong numberOfGeneration;
float[] probabilities;
}
this(W)(SuperImage surface, Color4f color, IFS_EquationSystem equationSystem, IFS_StartPoint point, IFS_Scales scales, W numberOfGeneration)
if (allArithmetic!(W))
{
this.surface = surface;
this.color = color;
this.equationSystem = equationSystem;
this.numberOfGeneration = cast(ulong) numberOfGeneration;
this.point = point;
this.scales = scales;
this.probabilities = equationSystem.map!(a => a.getP!float).array;
}
IFS_EquationSystem execute()
{
float x = point.getX!float;
float y = point.getY!float;
for (ulong i = 0; i < numberOfGeneration; i++)
{
auto d = dice(probabilities);
IFS_Equation eq = equationSystem[d];
auto mul0 = eq.getA!float * x + eq.getB!float * y;
auto mul1 = eq.getC!float * x + eq.getD!float * y;
x = mul0 + eq.getE!float;
y = mul1 + eq.getF!float;
// surface.drawPoint(
// color,
// scales.getOffsetX!float + scales.getScaleX!float * x,
// scales.getOffsetY!float + scales.getScaleY!float * y
// );
surface[
cast(int) (scales.getOffsetX!float + scales.getScaleX!float * x),
cast(int) (scales.getOffsetY!float + scales.getScaleY!float * y)
] = color;
}
return equationSystem;
}
}
Конструктор класса IFS примет в себя некоторую двумерную поверхность (ее роль будет играть обобщенный класс изображения SuperImage из dlib), цвет (которым и будет отрисована сама система), набор уравнений ИФС, стартовую точку и количество поколений (оно должно быть достаточно большим, чтобы пронаблюдать все интересное). Далее, метод execute описывает собственно говоря саму процедуру итерации через поколения ИФС и на основе расчетов окрашивает нужным цветом рассчитанные с помощью уравнений точки.
В самой процедуре расчета только один момент реально заслуживает отдельного упоминания - это процедура выбора уравнения на основе вероятности, которая осуществляется в одну строку с помощью интересной функции из std.random под названием dice. Эта функция принимая набор вероятностей генерирует число от 0 до n, где n - это количество вероятностей в наборе. Сгенерированное с помощью dice значение используется как индекс для выбора уравнения, а сами вероятности берутся из переменной probabilities класса IFS, которое в свою очередь получается с помощью пробега по массиву уравнений с помощью map и последующей трансформацией диапазона в обычный массив из float`ов.
Прежде чем перейти к испытаниям, я предлагаю вам ненадолго вернуться к статье «Усовершенствуем лист папоротника» и освежить в памяти одну деталь: дело в том, что я уже описывал откуда я брал коэффициенты для уравнений... Вся суть в том, что существует много ресурсов, посвященных фрактальным изображениям и на некоторых из них описания фракталов даются в форме понятного и легкочитаемого формата, использованного когда-то в старой программе FRACTINT.
Именно, использование формата этой программки, а также некоторое его описание в упомянутой статье, поможет нам облегчить испытание универсального модуля для построения ИФС, а парсер этого формата легко написать в несколько строк, используя функциональный подход:
// from FRACTINT format to standart IFS equations
IFS_EquationSystem fromFRACTINT(string description)
{
import std.algorithm;
import std.conv : to;
import std.range;
import std.string;
IFS_EquationSystem ifs_system;
auto startDescription = description.indexOf("{");
auto endDescription = description.indexOf("}");
IFS_Equation toEquation(float[] equation)
{
return new IFS_Equation(
equation[0],
equation[1],
equation[2],
equation[3],
equation[4],
equation[5],
equation[6],
);
}
description[startDescription+1..endDescription]
.split
.map!(a => to!float(strip(a)))
.chunks(7)
.map!(a => toEquation(a.array))
.each!(a => ifs_system ~= a);
return ifs_system;
}
В этом коде, мы используем тот факт, что описание во FRACTINT-формате начинается с имени ИФС, после которого следуют фигурные скобки, внутри которых и заключены интересующие нас коэффициенты. Эти коэффициенты расположены внутри описания построчно, т.е одной строке соответствует одно уравнение с шестью коэффициентами и одним параметром вероятности применения уравнения. Таким образом с помощью indexOf мы определяем позиции скобок и с помощью них отделяем от строки описание, оставляя только голую строку с числами. После этого, разбиваем строку по пробелам, формируя таким образом, список из чистых значений, но в строковой форме. Данную форму мы преобразуем с помощью шаблона to и алгоритма map в диапазон элементов типа float (на всякий случай убираем все лишнее с помощью strip). Теперь, помня про то, что каждое уравнение - это ровно семь значений, разбиваем диапазон на блоки по семь элементов в каждом и проходим по блокам, преобразуя каждый из них с помощью уже подготовленной ранее функции toEquation в уравнение. Заключительным этапом работы парсера является накапливание всех уравнений с помощью алгоритма each в единый массив, описывающий систему уравнений ИФС.
Испытаем созданный код в проекте dub с добавленной в качестве зависимости библиотеки dlib, используя следующий код:
import std.stdio;
import dlib.image;
import ifs;
void main()
{
// Поверхность
auto surface = image(8000, 8000);
// Система уравнений в удобном формате
string description = "
Fern {
0.00 0.00 0.00 0.16 0.00 0.00 0.01
0.85 0.04 -0.04 0.85 0.00 1.60 0.85
0.20 -0.26 0.23 0.22 0.00 1.60 0.07
-0.15 0.28 0.26 0.24 0.00 0.44 0.07
}
";
// Готовая система уравнений
IFS_EquationSystem equations = fromFRACTINT(description);
// Задание цвета
Color4f color = Color4f(0.0f, 120 / 255.0f, 200 / 255.0f);
// Начальная точка
IFS_StartPoint startPoint = new IFS_StartPoint(0 , 0);
// Масштабирующие и смещающие коэффициенты
IFS_Scales scales = new IFS_Scales(2500, 700, 0.00001, 0.00001);
// Итерируемая система функций
IFS ifs = new IFS(surface, color, equations, startPoint, scales, 100_000_000);
// Запускаем генерацию IFS
ifs.execute;
// Сохраняем изображение
surface.savePNG("ifs_draw.png");
}
Результатом испытания будет нечто с потрясающей степенью детализации:
Красиво, а? И теперь, вы тоже так можете.
P.S: Имейте в виду, что вы не найдете этих блоков в текущей версии rip из репозитория dub, поскольку эти наработки не были включены в текущую ветвь. Кроме того, функция fromFRACTINT планировалась как скрытая функция внутри модуля, доступная тем, кто не поленился покопаться в исходном коде библиотеки (оставлена как "пасхальное яйцо" для демонстрации возможностей).
Описание ИФС в виде формата FRACTINT вы можете найти здесь