Векторная графика в dlib

Моя статья 2017 года, изначально написанная для блога LightHouse Software. Приведенный код актуален и сегодня.

Коллекция библиотек dlib предоставляет функции для рисования отрезков и окружностей (см. dlib.image.render.shapes). Однако при построении сложной векторной графики не обойтись без рендеринга более интересных объектов – в этой статье я рассмотрел рисование закрашенных многоугольников и фигур Безье на их основе.

Рендеринг произвольного многоугольника сводится к задаче о принадлежности точки многоугольнику – мы просто проходим по всем пикселям изображения и проверяем, попадает ли каждый в многоугольник. В качестве алгоритма для этого можно использовать even-odd rule (правило четности-нечетности): мы подсчитываем количество пересечений луча, исходящего из заданной точки, с ребрами многоугольника – если оно четное, точка не принадлежит многоугольнику.

import dlib;

bool pointInPolygon(Vector2f p, Vector2f[] poly)
{
    size_t i = 0;
    size_t j = poly.length - 1;
    bool inside = false;

    for (i = 0; i < poly.length; i++) {
        Vector2f a = poly[i];
        Vector2f b = poly[j];
        if ((a.y > p.y) != (b.y > p.y) &&
            (p.x < (b.x - a.x) * (p.y - a.y) / (b.y - a.y) + a.x))
            inside = !inside;
        j = i;
    }

    return inside;
}

Теперь, используя функцию pointInPolygon, мы можем написать следующее:

auto img = image(300, 300, 3);

Vector2f[] poly = [
    Vector2f(150.0f, 50.0f),
    Vector2f(250.0f, 250.0f),
    Vector2f(50.0f, 250.0f)
];

Color4f fillColor = Color4f(1.0f, 0.5f, 0.0f, 1.0f);

foreach(y; 0..img.height)
foreach(x; 0..img.width)
{
    if (pointInPolygon(Vector2f(x, y), poly))
        img[x, y] = fillColor;
}

img.savePNG("triangle.png");

Треугольник выглядит ступенчатым, поэтому неплохо бы добавить сглаживание. Методов сглаживания существует достаточно много, но самый простой и универсальный – это суперсэмплинг. Метод основан на разбиении каждого пикселя на несколько субпикселей – мы вычисляем цвет отдельно для каждого из них, а затем находим среднее арифметическое, которое и используется в качестве итогового цвета пикселя. Есть различные способы разбивать пиксель на субпиксели, я использовал просто сетку 4×4.

uint subpixRes = 4;
float subpixSize = 1.0f / subpixRes;
float subpixContrib = 1.0f / (subpixRes * subpixRes);

foreach(y; 0..img.height)
foreach(x; 0..img.width)
{
    fillColor.a = 0.0f;

    foreach(sy; 0..subpixRes)
    foreach(sx; 0..subpixRes)
    {
        auto p = Vector2f(x + sx * subpixSize, y + sy * subpixSize);
        if (pointInPolygon(p, poly))
            fillColor.a += subpixContrib;
    }

    img[x, y] = alphaOver(img[x, y], fillColor);
}

img.savePNG("triangle-smooth.png");

Поскольку мы накладываем наш треугольник на фон, то фактически можно вычислять для субпикселей не цвет, а значение прозрачности, а затем использовать его для альфа-смешивания цвета треугольника с цветом фона (alphaOver). Также в целях оптимизации я вынес деление из цикла – средняя прозрачность вычисляется путем суммирования заранее поделенных значений.

Если мы можем рисовать многоугольники, то можем также и фигуры, составленные из кривых – например, фигуры Безье. Вместо того, чтобы проверять на пересечение отрезок и кривую, гораздо проще построить многоугольник, который будет упрощенно представлять кривую. В dlib есть функции для построения 2- и 3-мерных кубических кривых Безье – модуль dlib.geometry.bezier, с помощью которого мы можем сделать следующее:

Vector2f[] poly;

uint numBezierCurves = 4;
uint curveRes = 20;
float tessStep = 1.0f / curveRes;
float t = 0.0f;

foreach(i; 0..numBezierCurves)
{
    Vector2f a = bezierPoints[i * 4];
    Vector2f b = bezierPoints[i * 4 + 1];
    Vector2f c = bezierPoints[i * 4 + 2];
    Vector2f d = bezierPoints[i * 4 + 3];

    t = 0.0f;
    poly ~= a;
    while(t < 1.0f)
    {
        t += tessStep;
        Vector2f p = bezierCurveFunc2D(a, b, c, d, t);
        poly ~= p;
    }
    poly ~= d;
}

Массив bezierPoints должен представлять собой последовательный набор опорных точек, описывающих кривые, количество которых задается параметром numBezierCurves. Общее количество опорных точек равно numBezierCurves * 4 (для кубической кривой). Вот для примера опорные точки для построения сердечка:

Vector2f[] bezierPoints = [
    Vector2f(50, 120),
    Vector2f(50, 50),
    Vector2f(150, 50),
    Vector2f(150, 120),

    Vector2f(150, 120),
    Vector2f(150, 50),
    Vector2f(250, 50),
    Vector2f(250, 120),

    Vector2f(250, 120),
    Vector2f(250, 200),
    Vector2f(150, 200),
    Vector2f(150, 250),

    Vector2f(150, 250),
    Vector2f(150, 200),
    Vector2f(50, 200),
    Vector2f(50, 120)
];

Можно трансформировать фигуру при помощи аффинных матриц 3×3 – модуль dlib.math.transformation предоставляет для этого все необходимые функции. Если вы, к примеру, хотите повернуть фигуру относительно центра изображения, нужно составить следующую матрицу:

float angle = 45.0f;
Vector2f center = Vector2f(img.width, img.height) * 0.5f;
Matrix3x3f m =
    translationMatrix2D(center) *
    rotationMatrix2D(degtorad(angle)) *
    translationMatrix2D(-center);

А затем, при построении фигуры, трансформировать матрицей m опорные точки:

Vector2f a = bezierPoints[i * 4].affineTransform2D(m);
Vector2f b = bezierPoints[i * 4 + 1].affineTransform2D(m);
Vector2f c = bezierPoints[i * 4 + 2].affineTransform2D(m);
Vector2f d = bezierPoints[i * 4 + 3].affineTransform2D(m);