math

Рефакторинг матриц в dlib

  • Дата публикации: 11.10.2013
  • /Метки: d, dlib, math, matrix
  • /Комментарии: 0

На днях состоялось грандиозное обновление пакета линейной алгебры dlib.math. Изменения коснулись, главным образом, реализации матриц. Если раньше матрицы 2×2, 3×3 и 4×4 имели каждая отдельную независимую реализацию, то теперь все они являются частными случаями обобщенной квадратной матрицы Matrix!(T,N) (где T – тип элементов, N – размерность). Она содержит все необходимые общие методы для матриц любого размера (нахождение определителя, нахождение обратной матрицы, нахождение матрицы миноров и алгебраических дополнений и т.д.), оптимизированные, где это возможно, для размерностей 2, 3 и 4. Таким образом, нынешние специализации Matrix2x2f, Matrix3x3f и Matrix4x4f практически идентичны их прежним аналогам.

Новая реализация создана с учетом обратной совместимости, но все-таки есть несколько критичных изменений:

1. Больше нет шаблонов Matrix2x2!(T), Matrix3x3!(T), Matrix4x4!(T). Используйте вместо них Matrix!(T,2), Matrix!(T,3) и Matrix!(T,4). При этом псевдонимы на специализации типа Matrix2x2f и Matrix4x4d сохранены;

2. Нет доступа к элементам матриц 4×4 через поля m*, t* и h*. Возможен только доступ через поля a*. Это справедливо для матриц любого размера:

a11 a12 a13 a14 .. a1N
a21 a22 a23 a24 .. a2N
a31 a32 a33 a34 .. a3N
a41 a42 a43 a44 .. a4N
 :   :   :   :  .
aN1 aN2 aN3 aN4  ' aNN

2. Все аффинные преобразования (функции rotationMatrix, translationMatrix и др.) и утилитарные функции для матриц вынесены в отдельный модуль dlib.math.affine. Там же находятся функции right, up, forward, translation, scaling, которые раньше были опрелены как методы в Matrix4x4!(T). Благодаря UFCS, их и теперь можно использовать как методы – однако все они теперь представляют собой свойства только для чтения. Пока они определены только для Matrix!(T,4), но в будущем функции базиса (right, up, forwartd) будут доступны и для Matrix!(T,3).

3. В целях обратной совместимости сохраняются модули dlib.math.matrix2x2, dlib.math.matrix3x3, dlib.math.matrix4x4, но они помечены как deprecated. Вместо них импортируйте dlib.math.matrix (и dlib.math.affine, если вам нужны аффинные преобразования)

2. Не рекомендуется использовать identityMatrix3x3!(T) и identityMatrix4x4!(T). Единичные матрицы создаются при помощи статического метода identity: например, Matrix3x3f.identity.

3. Не рекомендуется трансформировать векторы методом transform. Вместо этого лучше использовать умножение вектора на матрицу: Vector3f(1, 2, 3) * myMatrix.

4. Любые матрицы можно создавать при помощи функции-фабрики matrixf, которая автоматически определяет размерность на основе входных данных:

auto m1 = matrixf(
    8, 3, 2, 0,
    4, 0, 2, 0,
    1, 3, 3, 0,
    0, 0, 3, 1
);

Это выражение создаст матрицу типа Matrix!(float,4) и присвоит ее переменной m1.

Убедительная просьба всем пользователям dlib сообщить мне (в Issues в репозитории на GitHub, либо на почту – gecko0307@gmail.com), если будут обнаружены какие-то несостыковки и баги, связанные с данным рефакторингом матриц.

WolframAlpha

Совершенно случайно набрел на интереснейший сервис – http://www.wolframalpha.com. Это гибрид поисковика, базы знаний и вычислительной системы, понимающий запросы на литературном английском.

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

32*56-756

…и конвертер величин:

100 kilograms in pounds

Если вам нужна система линейной алгебры, а Matlab/Octave под рукой нет, то сервис поможет и здесь. Например, можно решать уравнения:

solve x^2+2x-1=0

Или рисовать графики функций:

plot f(x)=x^2

Поддерживаются операции с матрицами:

matrix inverse {{8, 3, 2, 0},{4, 0, 2, 0},{1, 3, 3, 0},{0, 0, 3, 1}} decimal

Также у WolframAlpha можно спрашивать какие-нибудь научные факты, например, возраст Вселенной:

universe age in years

Или статистические данные, например, крупнейшие города США:

biggest cities of usa

Сервис умеет показывать погоду в указанном городе или регионе:

weather in moscow

Я еще не успел ознакомиться со всеми возможностями этой замечательной системы – уверен, там есть еще много интересного.

Журнал “FPS” №25

Вышел 25 номер электронного PDF-журнала “FPS”, посвященного разработке игр, программированию, компьютерной графике и звуку.

Читайте в этом номере:

> SIGGRAPH 2013: новости с выставки
> VIGAMUS – музей видеоигр
> Моделирование волос в Blender
> Физический движок своими руками, часть II
> Дуальные числа и автоматическое дифференцирование
> Фильтрация изображений в dlib
> История Git
> Linux – для геймеров?
> Полезные консольные команды в Linux

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

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

Дуальные числа и касательная к кривой Безье

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

import std.stdio;
import dlib.math.dual;

T parabola(T)(T x)
{
    return x*x;
}

void main()
{
    float x = 1.0f;

    Dualf eval = parabola(Dualf(x, 1.0f));
    float value = eval.re;
    float deriv = eval.du;
    
    writeln(deriv);
}

При запуске программа выдаст значение производной – 2 для точки 1. Правильность результата нетрудно проверить, зная формулу производной степенной функции: если f(x) = xn, то f ‘(x) = nxn-1. Следовательно, если f(x) = x2, то f ‘(x) = 2x.

Теперь начинается самое интересное. Попробуем вместо скалярных величин взять векторные и дифференцировать функцию кривой Безье (dlib.geometry.bezier) для двумерного случая:

import dlib.math.dual;
import dlib.math.vector;
import dlib.geometry.bezier;

alias DualVector2f = Vector!(Dualf, 2);

void main()
{
    float t = 0.5f;
    
    DualVector2f eval = bezierCurveFunc2D(
        DualVector2f(Dualf(0.0f), Dualf(0.0f)),
        DualVector2f(Dualf(1.0f), Dualf(1.0f)),
        DualVector2f(Dualf(2.0f), Dualf(1.0f)),
        DualVector2f(Dualf(3.0f), Dualf(0.0f)),
        Dualf(t, 1.0f));
}

Результирующий вектор eval будет содержать в вещественной части точку на кривой, а в дуальной – вектор касательной к кривой в этой точке, который нам остается только нормировать:

Vector2f point = Vector2f(eval.x.re, eval.y.re);
Vector2f tangent = Vector2f(eval.x.du, eval.y.du).normalized;

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

Обновление dlib (r23)

Состоялось обновление набора библиотек dlib.

  • В модуле dlib.math.vector реализованы функция isAlmostZero, шаблоны для целочисленных векторов (Vector2i, Vector2u). vectorDecreaseToZero теперь поддерживает векторы произвольного размера;
  • В dlib.math.utils добавлены функции sign и swap;
  • В dlib.math.matrix3x3 реализовано покомпонентное сложение и вычитание матриц;
  • В dlib.math.matrix4x4 добавлены функции shadowMatrix для построения теневых матриц (проекции вершин на плоскость) и matrixFromAxisAngle для построения матриц вращения из представления “ось-угол”;
  • Для изображений в частотном диапазоне (dlib.image.compleximage) реализованы обратная свертка (deconvolve) и деление (divide).

Изменения доступны в ревизии r23 и выше.

http://code.google.com/p/dlib/