В настоящий момент появилось достаточно большое количество библиотек дополненной реальности с богатым функционалом (ARCore, ARKit, Vuforia). Тем не менее я решил начать свой открытый проект, попутно описывая как это работает изнутри. Если повезет, то позже получится добавить какой-то особый интересный функционал, которого нет в других библиотеках. В качестве целевых платформ пока возьмем Windows и Android. Библиотека пишется на C++, и сторонние библиотеки будут задействованы по минимуму, т.е. преимущественно не будет использовано ничего готового. Фокус в статьях будет направлен на алгоритмы и математику, которые постараюсь описать максимально доступно и подробно. В этой статье пойдет речь про основы векторной алгебры.
Дополненная реальность — это совмещение виртуального мира и реального. Для этого, нам нужно представить окружающее реальное пространство в виде математической модели, понимая закономерности которой, мы сможем получить данные для совмещения. Начнем с основ векторной алгебры.
Вектора — это частный случай матриц, состоящие либо из одного столбца, либо из одной строки. Когда мы говорим о векторе, обычно имеется вектор-столбец . Но записывать вектор как столбец неудобно, поэтому будем его транспонировать —
.
Длина вектора
Первое, что мы рассмотрим — получение длины вектора — , где
— значение длины,
— наш вектор. Для примера возьмем двумерный вектор:
, где
и
— компоненты вектора, значения проекций вектора на оси двумерных координат. И мы видим прямоугольный треугольник, где
и
— это длины катетов, а
— длина его гипотенузы. По теореме Пифагора получается, что
. Значит
. Вид формулы сохраняется и для векторов большей размерности, например —
.
Скалярное произведение
Скалярное произведение векторов — это сумма произведение их компонентов: . Но так как мы знаем, что вектора — это матрицы, то тогда удобнее записать это в таком виде:
. Это же произведение можно записать в другой форме:
, где
— угол между векторами
и
(для двумерного случая эта формула доказывается через теорему косинусов). По этой формуле можно заключить, что скалярное произведение — это мера сонаправленности векторов. Ведь, если
, то
, и
— это просто произведение длин векторов. Так как
— не может быть больше 1, то это максимальное значение, которые мы можем получить, изменяя только угол
. Минимальное значение
будет равно -1, и получается при
, т.е. когда вектора смотрят в противоположные направления. Также заметим, что при
, а значит какие бы длины не имели вектора
и
, все равно
. Можно в таком случае сказать, что вектора не имеют общего направления, и называются ортогональными.
Также при помощи скалярного произведения, мы можем записать формулу длины вектора красивее: ,
.
Проекция вектора на другой вектор
Возьмем два вектора: и
.
Проекцию вектора на другой вектор можно рассматривать в двух смыслах: геометрическом и алгебраическом. В геометрическом смысле проекция вектора на ось — это вектор, а в алгебраическом – число.
Вектора — это направления, поэтому их начало лежит в начале координат. Обозначим ключевые точки: — начало координат,
— конечная точка вектора
,
— конечная точка вектора
.
В геометрическом смысле мы ищем такой , чтобы конечная точка вектора (обозначим ее как —
) была ближайшей точкой к точке
, лежащей на прямой
.
Иначе говоря, мы хотим найти составляющую в
, т.е. такое значение
, чтобы
и
Расстояние между точками и
будет минимальным, если
. Получаем прямоугольный треугольник —
. Обозначим
. Мы знаем, что
по определению косинуса через соотношение сторон прямоугольного треугольника
( — гипотенуза,
— прилежащий катет).
Также возьмем скалярное произведение . Отсюда следует, что
. А значит
.
Тут вспоминаем, что — это искомый вектор
, а
—
, и получаем
. Умножаем обе части на
и получаем —
. Теперь мы знаем длину
. Вектор
отличается от вектора
длинной, но не направлением, а значит через соотношение длин можно получить:
. И мы можем вывести финальные формулы:
и
Нормализованный вектор
Хороший способ упростить работу над векторами — использовать вектора единичной длины. Возьмем вектор и получим сонаправленный вектор
единичной длины. Для этого вектор разделим на его длину:
. Эта операция называется нормализацией, а вектор — нормализованным.
Зная нормализованный вектор и длину исходного вектора, можно получить исходный вектор: .
Зная нормализованный вектор и исходный вектор, можно получить его длину: .
Хорошим преимуществом нормализованных векторов является то, что сильно упрощается формула проекции (т.к. длина равна 1, то она сокращается). Проекция вектора на
единичной длины:
Матрица поворота двумерного пространства
Предположим у нас есть некая фигура:
Чтобы ее нарисовать, заданы координаты ее вершин, от которых строятся линии. Координаты заданы в виде набора векторов следующим образом . Наша координатная сетка задана двумя осями — единичными ортогональными (перпендикулярными) векторами. В двумерном пространстве можно получить два перпендикулярных вектора к другому вектору такой же длины следующим образом:
— левый и правый перпендикуляры. Берем вектор, задающим ось
—
и ось
— левый к нему перпендикуляр —
.
Выведем новый вектор, получаемый из наших базисный векторов:
Сюрприз — он совпадает с нашим исходным вектором.
Теперь попробуем как-то изменить нашу фигуру — повернем ее на угол . Для этого повернем векторы
и
, задающих оси координат. Поворот вектора
задается косинусом и синусом угла —
. А чтобы получить вектор оси
, возьмем перпендикуляр к
:
. Выполнив эту трансформацию, получаем новую фигуру:
Вектора и
являются ортонормированным базисом, потому как вектора ортогональны между собой (а значит базис ортогонален), и вектора имеют единичную длину, т.е. нормированы.
Теперь мы говорим о нескольких системах координат — базовой системы координат (назовем ее мировой), и локальной для нашего объекта (которую мы поворачивали). Удобно объединить наш набор векторов в матрицу —
Тогда .
В итоге — .
Матрица , составляющая ортонормированный базис и описывающая поворот, называется матрицей поворота.
Также матрица поворота имеет ряд полезных свойств, которые следует иметь ввиду:
- При
, где
— единичная матрица, матрица соответствует нулевому повороту (угол
), и в таком случае локальные оси совпадают с мировыми. Как рассматривали выше, матрица никак не меняет исходный вектор.
— определитель матрицы равен 1, если у нас, как обычно бывает, правая тройка векторов.
, если тройка векторов левая.
.
.
.
, поворот не меняет длины вектора.
- зная
и
, можем получить исходный вектор
—
. Т.е. умножая вектор на матрицу поворота мы выполняем преобразование координат вектора из локальной системы координат объекта в мировую, но также мы можем поступать и наоборот — преобразовывать мировые координаты в локальную систему координат объекта, умножая на обратную матрицу поворота.
Теперь попробуем повернуть наш объект два раза, первый раз на угол , второй раз на угол
. Матрицу, полученную из угла
, обозначим как
, из угла
—
. Распишем наше итоговое преобразование:
.
Обозначим , тогда
. И из двух операций мы получили одну. Так как поворот — это линейное преобразование (описали ее при помощи одной матрицы), множество преобразований можно описать одной матрицей, что сильно упрощает над ними работу.
Масштабирование в двумерном пространстве
Масштабировать объект достаточно просто, нужно только умножить координаты точек на коэффициент масштаба: . Если мы хотим масштабировать объект на разную величину по разным осям, то формула принимает вид:
. Для удобства переведем операцию в матричный вид:
.
Теперь предположим, что нам нужно повернуть и масштабировать наш объект. Нужно отметить, что если сначала масштабировать, а затем повернуть, то результат будет отличаться, от того результата, где мы сначала повернули, а затем масштабировали:
Сначала поворот, а затем масштабирование по осям:
Сначала масштабирование по осям, а затем поворот:
Как мы видим порядок операций играет большое значение, и его нужно обязательно учитывать.
Также здесь мы также можем объединять матрицы преобразования в одну:
Хотя в данном случае, если , то
. Тем не менее, с порядком преобразований нужно быть очень аккуратным. Их нельзя просто так менять местами.
Векторное произведение векторов
Перейдем в трехмерное пространство и рассмотрим определенное на нем векторное произведение.
Векторное произведение двух векторов в трёхмерном пространстве — вектор, ортогональный к обоим исходным векторам, длина которого равна площади параллелограмма, образованного исходными векторами.
Для примера возьмем два трехмерных вектора — ,
. И в результате векторного произведения получим
Визуализируем данную операцию:
Здесь наши вектора ,
и
. Вектора начинаются с начала координат, обозначенной точкой
. Конечная точка вектора
— точка
. Конечная точка
— точка
. Параллелограмм из определения формируются точками
,
,
,
. Координаты точки
находим как —
. В итоге имеем следующие соотношения:
, где
— площадь,
,
.
Два вектора образуют плоскость, а векторное произведение позволяет получить перпендикуляр к этой плоскости. Получившиеся вектора образуют образуют правую тройку векторов. Если берем обратный вектор, то получаем второй перпендикуляр к плоскости, и тройка векторов будет уже левой.
Для запоминания этой формулы удобно использовать мнемонический определитель. Пусть , и мы раскладываем определить по строке как сумму определителей миноров исходной матрицы
:
Некоторые удобные свойства данного произведения:
- Если два вектора ортогональны и нормализованы, то вектор также будет иметь единичную длину. Параллелограмм, который образуется двумя исходными векторами, станет квадратом с длинной сторон равной единице. Т.е. площадь равна единице, отсюда длина выходного вектора — единица.
Матрица поворота трехмерного пространства.
С тем, как формировать матрицу в двумерном пространстве мы разобрались. В трехмерном она формируется уже не двумя, а тремя ортогональными векторами — . По свойствам, описанным выше, можно вывести следующие отношения между этими векторам:
Вычислить вектора этих осей сложнее, чем в матрице поворота двумерного пространства. Для примера получения этих векторов рассмотрим алгоритм, который в трехмерных движках называется lookAt. Для этого нам понадобятся вектор направления взгляда — и опорный вектор для оси
—
. Сам алгоритм:
- Обычно направление камеры совпадает с осью
. Поэтому нормализуем
и получаем ось
—
.
- Получаем вектор оси
—
. В итоге у нас есть два нормализованных ортогональных вектора
и
, описывающих оси
и
, при этом ось
сонаправлена с входным вектором
, а ось
перпендикулярна к входному опорному вектору
.
- Получаем вектор оси
из полученных
и
—
.
- В итоге
В трехмерных редакторах и движках в интерфейсах часто используются углы Эйлера для задания поворота. Углы Эйлера более интуитивно понятны — это три числа, обозначающие три последовательных поворота вокруг трех основных осей . Однако, работать с ними не очень то просто. Если попробовать выразить итоговый вектор напрямую через эти повороты, то получим довольно объемную формулу, состоящую из синусов и косинусов наших углов. Есть еще пара проблем с этими углами. Первая проблема — это то, что сами по себе углы не задают однозначного поворота, так как результат зависит от того, в какой последовательности происходили повороты —
или
или как-то еще. Углы Эйлера — это последовательность поворотов, а как мы помним, смена порядка трансформаций меняет итоговый результат. Вторая проблема — это gimbal lock.
Внутри же трехмерные движки чаще всего используют кватернионы, которых мы касаться не будем.
Существуют разные способы задания поворота в трехмерном пространстве, и каждый имеет свои плюсы и минусы:
- Матрица поворота. С ней просто работать (т.к. это просто матрицы). Но есть логическая избыточность данных — все элементы матрицы связаны определенными условиями, так как количество элементов больше степеней свободы (12 элементов против трех степеней). Т.е. мы не можем взять матрицу и наполнить ее случайными числами, так при несоблюдении условий матрица просто не будет являться матрицей поворота.
- Углы Эйлера. Они интуитивно понятны, но работать с ними сложно.
- Вектор оси вращения и угол порота вокруг нее. Любой возможный поворот можно описать таким образом. Поворота вектора вокруг заданной оси рассмотрим ниже.
- Вектор поворота Родрига. Это трехмерный вектор, где нормализованный вектор представляет собой ось вращения, а длина вектора угол поворота. Этот способ задания поворота похож на предыдущий способ, но количество элементов здесь равно числу степеней свободы, и элементы не связаны между собой жесткими ограничениями. И мы можем взять трехмерный вектор с абсолютно случайными числами, и любой полученный вектор будет задавать какое-то возможное вращение.
Поворот вектора вокруг заданной оси
Теперь рассмотрим операцию, позволяющую реализовать поворот вектора вокруг оси.
Возьмем вектор — описывающий ось, вокруг которой нужно повернуть вектор
на угол
. Результирующий вектор обозначим как
. Иллюстрируем процесс:
Вектор мы можем разложить сумму векторов: вектора, параллельный к вектору
—
, и вектора, перпендикулярному к вектору к вектору
—
.
.
Вектор — это проекция вектора
на вектор
. Т.к.
— нормализованный вектор, то:
Та часть , которая принадлежит оси вращения (
) не измениться во время вращения. Повернуть нам нужно только
в плоскости перпендикулярной к
на угол
, Обозначим этот вектор как
. Тогда наш искомый вектор —
.
Вектор можем найти следующим образом:
Для того, чтобы повернуть , выведем оси
и
в плоскости, в которой будем выполнять поворот. Это должны быть два ортогональных нормализованных вектора, ортогональных к
. Один ортогональный вектор у нас уже есть —
, нормализуем его и обозначим как ось
—
.
Теперь получим вектор оси . Это должен быть вектор, ортогональный к
и
(т.е. и к
). Получить его можно через векторное произведение:
. Значит
. По свойству векторного произведения
будет равно площади параллелограмма, образуемого двумя исходными векторами (
и
). Так как вектора ортогональны, то у нас будет не параллелограмм, а прямоугольник, а значит
.
. Значит
.
Поворот двумерного вектора на угол
можно получить через синус и косинус —
. Т.к.
в координатах полученной плоскости сонаправлен с осью
, то он будет равен
. Этот вектор после поворота —
. Отсюда можем вывести:
Теперь мы можем получить наш искомый вектор:
Мы разобрались с тем, как поворачивать вектор вокруг заданной оси на заданный угол, значит теперь мы умеем использовать поворот, заданный таким образом.
Получить вектор оси вращения и угол из вектора Родрига не составляет большого труда, а значит мы теперь умеем работать и с ним тоже.
Напоминаю, что матрица поворота представляет собой три базисных вектора , а углы Эйлера — три последовательных поворота вокруг осей
,
,
. Значит мы можем взять единичную матрицу, как нулевой поворот
, а затем последовательно поворачивать базисные вектора вокруг нужных нам осей. В результате получим матрицу поворота соответствующую углам Эйлера. Например:
Также можно отдельно вывести матрицы вращения по каждой из осей ,
,
(
,
,
соответственно) и получить итоговую матрицу последовательным их умножением:
Таким же образом можно перевести вектор поворота Родрига в матрицу поворота: также поворачиваем оси матрицы поворота, полученные от единичной матрицы.
Итак, с вращением объекта разобрались. Переходим к остальным трансформациям.
Масштабирование в трехмерном пространстве
Все тоже самое что и двумерном пространстве, только матрица масштабирования принимает вид:
Перемещение объекта
До этого момента точка начала локальных координат не смещалась в мировом пространстве. Так как точка начала координат нашего объекта — это его центр, то центр объект никуда не смещался. Реализовать это смещение просто: , где
— вектор, задающий смещение.
Теперь мы умеем масштабировать объект по осям, поворачивать его и перемещать.
Объединим все одной формулой: :
Чтобы упростить формулу, мы можем, как уже делали ранее, объединить матрицы . В итоге наше преобразование описывает матрица
и вектор
. Объединение вектора
с матрицей
еще более бы упростило формулу, однако сделать в данном случае не получится, потому как сложение здесь — это не линейная операция. Тем не менее сделать это возможно, и рассмотрим этот момент уже в следующей статье.
Заключение
Для какого-то покажется, что статья описывает очевидные вещи, кому-то может показаться наоборот немного запутанной. Тем не менее это базовый фундамент, на котором будет строиться все остальное. Векторная алгебра — является фундаментом для многих областей, так что статья может вам оказаться полезной не только в дополненной реальности. Следующая статья будет уже более узконаправленной.