DGL без сборки мусора

На данный момент на D, к сожалению, нет полноценных игровых движков с ручным управлением памятью. И, если в общем случае с производительностью мы ничего сделать не можем (Benjamin Thaut, чтобы оптимизировать производительность игровых приложений, использовал модифицированный рантайм языка), то пусть хотя бы управление ресурсами будет детерминированным.
Новая ветка проекта DGLgc-free — является попыткой достичь этого путем полного отказа от выделения динамической памяти через сборщик мусора. Вместо этого все классы  используют dlib.core.memory и dlib.container.array вместо оператора new и встроенных динамических массивов D.
В данный момент переписана примерно половина функциональности DGL, добавлено и много нового: например, новая система событий, поддержка многоязыкового ввода с клавиатуры и т.д.

dlib 0.5

Не так давно состоялось очередное крупное обновление коллекции библиотек dlib — вышла версия 0.5, наиболее значительным нововведением которой стала поддержка ручного управления памятью (РУП). Но — обо всем по порядку…

  • Новый модуль dlib.core.memory предоставляет средства для ручного выделения и высвобождения динамической памяти, независимые от сборщика мусора и основанные на malloc/free. Имеется поддержка структур, классов и массивов. При использовании классов рекомендуется использовать интерфейс ManuallyAllocatable и перегружать метод free, который ответственен за удаление объекта — в противном случае корректное удаление в некоторых случаях не гарантировано (например, при доступе через интерфейс или родительский класс).
  • Началась работа по переводу всей dlib на РУП. Так, загрузчики изрбражений (PNG, JPEG, TGA, BMP) в новой версии полностью независимы от сборщика мусора. Для этого активно используется паттерн абстрактной фабрики, ответственный за создание изображений  в памяти. Кстати, в загрузчике PNG значительно улучшена поддержка индексированных изображений, для них добавлена поддержка альфа-канала.
  • Кроме того, на РУП переведены некоторые контейнеры из dlib.container — BST, ассоциативный массив. Реализован полностью ручной динамический массив (dlib.container.array).
  • Еще одна новинка — ООП для структур (dlib.core.oop). Это экспериментальный модуль, реализующий для структур прототипный стиль ООП с поддержкой множественного наследования и параметрического полиморфизма. Полностью заменить классы он, конечно, не может, но окажется весьма полезен, если нужно создавать объекты с наследованием в стеке. В будущем планируется переписать некоторые внутренние механизмы dlib с использованием этой легковесной объектной системы.
  • В пакете dlib.math появилась поддержка дуальных кватернионов. Это частный случай алгербы Клиффорда, обобщение кватернионов на поле дуальных чисел. Их можно использовать, например, для описания движения тел в кинематике — один дуальный кватернион охватывает и перенос, и вращение. Кстати, реализация обычных кватернионов через инкапсуляцию теперь совместима с векторами.
  • Изменения коснулись и пакета вычислительной геометрии. Усеченная пирамида (dlib.geometry.frustum) теперь задается с нормалями ограничивающих плоскостей, указывающими наружу пирамиды. Подвергся изменению API проверки пересечения Frustum с AABB. Исправлены ошибки в реализации AABB и плоскости.

Итоги года

Вот и пролетел еще один год — самое время подводить итоги по проделанной работе!

  • Вышли подряд нескольно новых версий dlib (0.3 и 0.4). Появилась поддержка абстрактных потоков ввода/вывода, а также платформонезависимый интерфейс файловой системы и его реализации для Windows и POSIX. Пакет обработки изображений теперь поддерживает JPEG, TGA и BMP, распараллеливание, HDRI. В пакете линейной алгебры состоялся серьезный рефакторинг матриц, появилась поддержка инверсии через LU-разложение.
  • Было выпущено 6 номеров электронно-познавательного журнала «FPS» (№№ 28, 29, 30, 31, 32, 33). Появился новый сайт проекта (http://fps-magazine.cf). Также «FPS» теперь доступен в качестве мобильного приложения для Android и iOS. Кстати, в феврале 2015 года журналу исполняется уже 7 лет!
  • Вышла игра 2048х2 — клон 2048 для двух игроков.
  • Улучшен физический движок dmech: реализован новый кэш контактов, добавлена поддержка составных тел, улучшена поддержка ограничений, добавлены статические тримеши, поддержка raycast и игровой кинематики.
  • Графический движок Atrium теперь развивается как самостоятельный проект — DGL. Это объектно-ориентированная надстройка над OpenGL, SDL и Freetype с собственной системой событий, виртуальной файловой системой с поддержкой ZIP-архивов, своим форматом хранения сцен, поддержкой шейдеров, мультитекстурирования, скелетной анимации, выводом текста в UTF-8, а также встроенными средствами интернационализации.
  • Разработан скриптовый язык GScript — минималистичный императивный язык с динамической типизацией, идейно близкий к D, JavaScript и Python. GScript можно будет использовать в качестве скриптовой системы в игровых движках.
  • Вышла новая версия системы сборки проектов Cook 2.0.1 — с новой системой аргументов командной строки, обновленным парсером импортов, поддержкой внешних зависимостей (в том числе из Git-репозиториев), улучшенной системой конфигурации.
  • Обновилась страница проекта Atrium.

Поддержка JPEG в dlib

Коллекция библиотек dlib обзавелась начальной поддержкой декодирования формата JPEG (dlib.image.io.jpeg). Пока поддерживается только baseline-часть стандарта, декодер читает только изображения с прореживанием 4:2:0 и не загружает метаданные EXIF (эти ограничения постепенно будут исправлены). Как и другие декодеры графических форматов в dlib, модуль работает на основе абстрактных потоков ввода/вывода (dlib.core.stream).
Поддержка сохранения в JPEG в ближайшем будущем не планируется.

Chroma Key с использованием dlib

Эффект Chroma Key (“цветовой ключ”) заключается в сегментации изображения с тем, чтобы отделить объект переднего плана от фона. При этом цвет фона должен быть сплошным и равномерным – как правило, выбирают либо зеленый, либо синий, в зависимости от того, какой цвет отсутствует на объекте. Отделенное изображение затем накладывается на другой фон – например, на фотографию или рендер виртуальной сцены.

Существуют различные алгоритмы подобной сегментации, мы рассмотрим один из самых простых. Несмотря на простоту, он достаточно эффективен. Метод основан на нахождении евклидового расстояния в пространстве RGB – между цветом исходного пикселя и цветом фона. Если рассматривать цвета как точки в трехмерном пространстве, то пиксели, например, зеленого фона будут представлять собой облако точек, сосредоточенное вокруг “абсолютно зеленой” точки – (0, 1, 0). Чтобы получить значение альфа-канала (0 – пиксель принадлежит фону, 1 – не принадлежит), мы просто нормируем расстояние в заранее выбранном диапазоне.

import dlib.math.vector;
import dlib.math.utils;
import dlib.image.image;
import dlib.image.color;

SuperImage chromaKey(
    SuperImage img, 
    Color4f keyColor, 
    float minDist,
    float maxDist)
{
    auto res = new ImageRGBA8(img.width, img.height);
   
    foreach(y; img.col)
    foreach(x; img.row)
    {       
        Color4f col = img[x, y];
        
        Color4f delta = col - keyColor;
        float distSqr = dot(delta, delta);
        col.a = clamp(
            (distSqr - minDist) / (maxDist - minDist), 
            0.0f, 1.0f);
        res[x, y] = col;
    }
    
    return res;
}

Вот пример использования этой функции:

import dlib.image.io.io;

auto img = load("input.png");
auto res = img.chromaKey(Color4f(0, 1, 0), 0.3f, 0.7f);
res.save("output.png");

Как нетрудно заметить, результат не идеален – если наложить изображение на фон, вокруг актера наблюдается зеленоватый контур. От него можно избавиться путем эрозии альфа-канала: изображение пропускается через дискретный оконный фильтр 3х3, который присваивает пикселю наименьшее значение в окне. В результате, непрозрачная область “теряет” несколько пикселей контура, и зеленый ореол практически исчезает.

SuperImage erodeAlpha(SuperImage img)
{
    uint kw = 3, kh = 3;
    
    auto res = img.dup;
    
    foreach(y; img.col)
    foreach(x; img.row)
    {
        auto c = img[x, y];
        
        foreach(ky; 0..kh)
        foreach(kx; 0..kw)
        {
            int iy = y + (ky - kh/2);
            int ix = x + (kx - kw/2);

            if (ix < 0) ix = 0;
            if (ix >= img.width) ix = img.width - 1;
            if (iy < 0) iy = 0;
            if (iy >= img.height) iy = img.height - 1;
            
            float a = img[ix, iy].a;
            
            if (a < c.a) 
                c.a = a;
        }

        res[x, y] = c;
    }
    
    return res;
}

Cook 2.0.1

Вышел первый стабильный релиз Cook2 — программы сборки проектов на языке D. По сравнению с первой версией проекта, Cook2 перенес множество серьезных изменений и нововведений:

  • Полностью переделана система обработки параметров командной строки — теперь она работает с помощью std.getopt. Подробнее читайте в конольной справке (—help) и в документации по проекту.
  • Произведен рефакторинг парсера импортов. Появилась поддержка условий «version» и «debug» (в настоящее время других инструментов сборки для D с подобной функциональностью практически нет).
  • Появилась поддержка разрешения внешних зависимостей у проектов: в качестве таковых можно указать удаленные Git-репозитории или локальные каталоги в системе. Загрузка кода из репозиториев возможна с использованием HTTPS и SSH. Исходники зависимостей и соответствующие объектные файлы хранятся в специальной папке в домашнем каталоге пользователя (~/.cook2) и являются общими для всех проектов, которые объявляют эти зависимости.
  • Улучшена система конфигурации: так, в папке ~/.cook2 можно хранить файл глобальной конфигурации default.conf, который будет использован по умолчанию всеми проектами.
  • Исправлено множество багов — в частности, серьезный баг с отслеживанием обратных зависимостей у модулей D.

Скачать Cook 2.0.1
Репозиторий Cook2 на GitHub

dlib 0.3

Состоялся релиз коллекции библиотек dlib 0.3. Нововведения этой версии:

  • Добавлены абстрактные потоки ввода/вывода (dlib.core.stream), независимые от Phobos, а также интерфейс файловой системы (dlib.filesystem) с готовыми реализациями для POSIX и Windows — этот интерфейс можно использовать, например, для построения виртуальных ФС.
  • Добавлена начальная поддержка HDRI в dlib.image (реализация формата изображений с плавающей запятой в dlib.image.hdri). Кроме того, обеспечена поддержка распараллеливания обработки изображений (dlib.image.parallel), добавлена поддержка чтения форматов TGA и BMP. Чтение/запись графических форматов теперь основаны на потоках, поэтому имеется возможность загружать изображения, например, напрямую из архивов.
  • Элементы матриц (dlib.math.matrix) теперь располагаются по столбцам, а не по строкам. Это серьезно нарушило обратную совместимость, но если вы не используете внутренние данные матриц и пользуетесь только внешним API, то это изменение не должно повлечь никаких проблем.

Более полный чейнджлог, а также исходники релиза вы можете найти на GitHub:
https://github.com/gecko0307/dlib/releases/tag/v0.3.0

Журнал «FPS» №28

К выходу FPS №28 мы решили приурочить открытие сайта-блога http://fps-magazine.blogspot.ru, в котором постепенно собираемся разместить всю информацию из нашего старого, ныне несуществующего сайта (fpsmag.zymichost.com). Надеемся, этот ресурс поможет читателям, не зарегистрированным в Google+, не терять нас на просторах Интернета и быть в курсе обо всех событиях из жизни журнала.

А в этом выпуске FPS вы найдете следующие материалы:

  • Подборка новостей по Blender
  • Интервью с Ларри Гритцем, создателем OSL
  • Рисуем фрактал на D
  • Обзор альтернативных ОС
  • Игровые новости из мира Linux
  • Кому нужен Linux? Правда и вымыслы
  • Культовые игры: The Elder Scrolls V
  • Angry Birds в России
  • Как создавались игры 80-х и 90-х
  • Каково быть гиком в тюрьме? Исповедь Анонимуса

Журнал доступен для онлайн-чтения и загрузки на Документах Google, на Dropbox, а также на Issuu.com.

Последние новости по проекту вы можете узнать в публичной странице журнала в социальной сети Google+: http://gplus.to/fpsmag. Добавляйте нас в круги, оставляйте свои комментарии и отписывайтесь в нашем сообществе.

Архив номеров журнала вы можете найти здесь.

GScript — скриптовый язык для D

В игровом движке трудно обойтись без какого-либо способа динамического задания логики и поведения объектов, поэтому я решил написать для Atrium скриптовый язык. Это очень простой императивный язык с динамической типизацией и (пока) всего одним внутренним типом – float.

Что уже реализовано:

  • Модульная система, как в D;
  • Функции (есть поддержка рекурсии);
  • Локальные переменные;
  • Передача аргументов по значению и по ссылке. Что интересно, передача по ссылке возможна в любую функцию, так как ссылочный тип указывается при конкретном вызове функции, а не при ее объявлении;
  • Условный переход if…else;
  • Цикл while;
  • Возможность расширять язык собственными функциями на D.

Кодогенератор и виртуальная машина к языку пока находятся на стадии прототипа (реализация рабочая, но далека от оптимальной).

Пример кода на GScript:

import myPackage.myModule;

func main()
{
    var x = 10;
    var a, b;

    a = x * 2 + 1;

    while(a > 0)
    {
        a = a - 1;
        b = b + 1;
    }

    writeln(x, a, b);
}

Исходники проекта доступны на GitHub:
https://github.com/gecko0307/gscript
Примеры скриптов

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

Распараллеливание обработки изображений

API dlib.image позволяет создавать фильтры, которые легко распараллеливать на несколько процессоров. Изображение условно разбивается на несколько блоков заданного размера, которые затем обрабатываются фильтром через std.parallelism.

import std.parallelism;
import dlib.functional.range;
import dlib.image.image;

struct Block
{
    uint x1, y1;
    uint x2, y2;
}

alias Range!uint PixRange;

void parallelFilter(
     SuperImage img, 
     void delegate(PixRange blockRow, PixRange blockCol) ffunc, 
     uint bw = 100,
     uint bh = 100)
{
    if (bw > img.width)
        bw = img.width;
    if (bh > img.height)
        bh = img.height;

    uint numBlocksX = img.width / bw + ((img.width % bw) > 0);
    uint numBlocksY = img.height / bh + ((img.height % bh) > 0);

    Block[] blocks = new Block[numBlocksX * numBlocksY];
    foreach(x; 0..numBlocksX)
    foreach(y; 0..numBlocksY)
    {
        uint bx = x * bw;
        uint by = y * bh;

        uint bw1 = bw;
        uint bh1 = bh;

        if ((img.width - bx) < bw)
            bw1 = img.width - bx;
        if ((img.height - by) < bh)
            bh1 = img.height - by;

        blocks[y * numBlocksX + x] = Block(bx, by, bx + bw1, by + bh1);
    }

    foreach(i, ref b; taskPool.parallel(blocks))
    {
        ffunc(range!uint(b.x1, b.x2),
              range!uint(b.y1, b.y2));
    }
}

Пример (закрашивание сплошным цветом):

SuperImage filterTestMultithreaded(SuperImage img)
{
    auto res = img.dup;
    
    img.parallelFilter((PixRange row, PixRange col)
    {
        foreach(x; row)
        foreach(y; col)
        {
            res[x, y] = hsv(180.0f, 1.0f, 0.5f);
        }
    });
    
    return res;
}

Для сравнения — однопоточный вариант:

SuperImage filterTestSinglethreaded(SuperImage img)
{
    auto res = img.dup;
    
    foreach(x; img.row)
    foreach(y; img.col)
    {
        res[x, y] = hsv(180.0f, 1.0f, 0.5f);
    }
   
    return res;
}

На двухъядерном Intel Dual Core T2390 (1.86 ГГц) многопоточный вариант показывает прирост производительности на 70%.