Функциональное программирование на примере работы с матрицами из теории линейной алгебры
Вступление
Определение матрицы и реализация на F#
Прямоугольная таблица чисел, содержащая m строк и n столбцов, называется матрицей размера m x n
Матрицы, как правило, обозначаются прописными буквами латинского алфавита и записываются в виде
Для работы с матрицами в F# создадим запись, основанную на двумерной таблице, которую в дальнейшем будем расширять полезными методами для того, чтобы совершать необходимые математические операции над ней.
Добавим вспомогательный метод для инициализации записи двумерным массивом
Входным аргументом функции будет двумерный массив, а на ее выходе — запись типа Matrix. Ниже приведем пример инициализации записи.
Две матрицы A=(aij) и B=(bij) называются равными, если они совпадают поэлементно, т.е. aij=bij для всех i=1,2. m и j=1,2. n
Для реализации этого правила будем использовать переопределенный оператор == и добавим пару полезных функций, которые также понадобятся нам в дальнейшем.
Давайте подробнее рассмотрим код выше. Как можно заметить, здесь есть три функции. Первая функция sizes возвращает размерность матрицы в виде кортежа. Так как мы работаем только с прямоугольными матрицами, то для получения количества строк мы берем полный срез первой колонки и возвращаем ее длину.
Аналогичным способом работает определение количества колонок — получаем полный срез первой строки и возвращаем ее длину.
Следующая функция isEquallySized сравнивает размерность двух матриц и возвращает true если они равны. Для этого она использует уже готовую функцию sizes и просто сравнивает результаты.
Оператор == для поэлементного сравнения двух матриц кажется сложнее, но сейчас вы увидите, что он также простой.
Перед тем, как сравнивать две матрицы, сравним их размерность. Если они не равны, то нет дальше смысла проводить проверку, так как уже понятно, что и матрицы будут не равны.
Далее, на основе исходных матриц matrix1 и matrix2 мы формируем новую матрицу, заполненную true или false, в зависимости от того, совпадают ли соответствующие ячейки обеих матриц.
Функция Array2D.mapi перебирает все элементы matrix1 и передает в обработчик три параметра
x — индекс строки
y — индекс колонки
v — содержимое ячейки
Содержимое ячейки v мы сравниваем с соответствующей ячейкой matrix2 и если они равны, то пишем true, иначе — false.
Если есть хоть одна ячейка с элементом false, то это означает, что матрицы не равны между собой.
Так как Array2D не содержит в себе методов для фильтрации или поиска, то реализуем это сами. Для этого разложим матрицу в линейный список
И найдем хоть одно несовпадение
Функция Seq.contains вернет true если в разложенном списке будет найдено хоть одно значение false. Поэтому нам нужно инвертировать полученный результат, чтобы оператор == работал так, как мы хотим
Матрица O называется нулевой или нуль-матрицей, если все ее элементы равны нулю.
Пример использования этой функции
Полагаю, что здесь нет ничего сложного, что требует пояснений, поэтому продолжаем.
Матрица, число строк которой равно числу столбцов и равно n, называется квадратной матрицей порядка n
В рамках этого правила мы создадим функцию, которая прямоугольную матрицу трансформирует в квадратную путем отсечения всех элементов, которые не попадают в квадрат.
Комментариев в исходном коде поясняют принцип работы функции, поэтому продолжим.
Квадратная матрица называется треугольной, если все ее элементы ниже главной диагонали равны нулю, т.е. треугольная матрица имеет вид
Ниже приведен код функции, который преобразует исходную матрицу в треугольную. Но в нашей функции мы будем работать с прямоугольной матрицей, то есть она может быть не квадратной. Читатель легко может модифицировать код функции так, чтобы она возвращала квадратную треугольную матрицу, используя функцию, которую мы рассмотрели ранее.
Функция Array2D.mapi преобразовывает исходный двумерный массив в новый при помощи обработчика, который принимает три параметра
x — номер строки
y — номер колонки
v — содержимое ячейки
Здесь мы делаем проверку, находится ли элемент ниже главной диагонали и если да, то заполняем ячейку 0. В противном случае — исходным значение из входной матрицы.
Ниже приведен пример использования этой функции.
Получаем следующий результат
Квадратная матрица называется диагональной, если все ее элементы, расположенные вне главной диагонали, равны нулю
Эта функция очень похожа на предыдущую, отличается только условие проверки. Ниже пример использования
Диагональная матрица является единичной и обозначается E, если все ее элементы, расположенные на главной диагонали, равны единице
Реализация такой матрицы на F# выглядит так
Операции над матрицами при помощи F#
Суммой двух матриц Amn=(aij)и Bmn=(bij)одинаковых размеров называется матрица того же размера A+B=Cmn=(cij), элементы которой равны сумме элементов матриц A и B, расположенных на соответствующих местах
Пример, для заданных матриц A и B находим сумму A+B
Рассмотрим код для сложения двух матриц
Перед тем, как складывать матрицы, нужно убедиться, что их размерность совпадает, в противном случае функция генерирует исключение. Ниже приведем пример использования данной функции
Произведением матрицы A=(aij) на число k называется матрица kA=(kaij) такого же размера, что и матрица A, полученная умножением всех элементов матрицы A на число k
Матрицу -A=(-1)*A будем называть противоположной матрице A. Из этого определения плавно переходим к следующему
Разностью матриц A и B одинаковых размеров называется сумма матрицы A и матрицы, противоположной к B
Две матрицы называются согласованными, если число столбцов первой равны числу строк второй
Проверка согласованности матриц требуется для их перемножения.
Произведением AB согласованных матриц Amn=(aij) и Bnp=(bjk) называется матрица Cmn=(cik), элемент cik которой вычисляется как сумма произведений элементов i-й строки матрицы A и соответствующих элементов k-го столбца матрицы B
Решение по определению произведения матриц
Рассмотрим код для умножения двух матриц
Давайте разберемся с кодом подробнее.
Перед умножением нужно убедиться, что матрицы являются согласованными
Итоговая матрица будет иметь размерность, в которой количество строк такое же, как у первой матрицы и количество столбцов такое же, как у второй матрицы
После этого мы последовательно перебираем все строки и все столбцы исходных матриц
Вычисляем итоговое значение каждой ячейки
Функция List.fold2 на вход получает два списка (строку и колонку) и передает в обработчик следующие параметры
acc — аккумулятор, содержащий результат предыдущего вычисления
val1 — содержимое ячейки из первого массива. В нашем случае это строка из первой матрицы
val2 — содержимое ячейки из второго массива, то есть колонки второй матрицы
Так как матрицы являются согласованными, то мы уверены, что у нас не произойдет выхода за пределы массивов.
Обработчик добавляет к аккумулятору произведение ячеек из строк и столбца и полученное значение будет передано следующей итерации. Таким образом конечным итогом работы функции List.fold2 будет итоговое значение произведений двух матриц. Остается только заполнить им предварительно созданную пустую матрицу
Которая вернется как результат
Ниже приведем пример использования данной функции
Если k ∈ N, то k-й степенью квадратной матрицы Aназывается произведение k матриц A
Рассмотрим код на F# для произведения матрицы в степень. Здесь будет использоваться хвостовая рекурсия для того, чтобы не переполнить стек при больших значениях степеней. Хвостовая рекурсия — это такая рекурсия, которая компилятором в итоге преобразуется в цикл. По возможности рекомендуется всегда использовать именно хвостовую рекурсию вместо обычной, но для этого нужно чтобы каждый кадр рекурсии возвращал итоговое вычисленное значение. Это значение обычно называется аккумулятором и передается в следующий кадр рекурсии. То есть, в отличие от обычной рекурсии, которая возвращает вычисленное значение вверх по стеку, хвостовая рекурсия передает вычисленное значение вниз по стеку. Каждый новый кадр рекурсии делает свои вычисления и добавляет их к уже ранее вычисленному значению, которое хранится в аккумуляторе. После того, как последний кадр рекурсии отработал, в аккумуляторе уже есть вычисленное значение, которое просто возвращается как результат.
Таким образом, компилятор может оптимизировать код и преобразовать его в обычный цикл.
Код содержит подробные комментарии о том, как он работает. Требует небольшого пояснения, зачем используется единичная матрица? Она нужна для первого кадра рекурсии и служит в качестве базового значения аккумулятора, в котором будет накапливаться итоговый результат.
Ниже рассмотрим пример использования нашей функции
Вычислим следующее произведение
Где E — это единичная матрица. Так как мы не можем к матрице прибавить число, то мы должны прибавлять 3E.
Итоги
В этот статье мы рассмотрели примеры реализации и использования матриц из теории линейной алгебры. А также основных математических операций над ними, с использованием функционального подхода на языке F#. Я надеюсь, что читатель смог оценить ту гибкость, которую дают функциональные языки.
Полный исходный код модуля матриц, фрагменты которого были рассмотрены в рамках статьи, вы сможете найти на гитхабе.
Введение в матрицы для начинающих
Дата публикации Sep 19, 2019
Матрицы являются строительными блоками науки о данных. Они появляются в различных аватарах на разных языках. От массива в Python до массивов данных в R и матриц в MATLAB.
Матрица в своей основной форме представляет собой набор чисел, расположенных в прямоугольной или массивной форме. Это может представлять изображение, или сеть, или даже абстрактную структуру.
Матрицы, множественное число для матрицы, на удивление встречаются чаще, чем вы думаете.
Все наши мемы, созданные с помощью Adobe Photoshop, используют матрицы для обработки линейных преобразований для визуализации изображений.квадратная матрицаможет представлять линейное преобразование геометрического объекта.
Например, в декартовой плоскости X-Y матрица
используется для создания отражения объекта по вертикальной оси Y. В видеоигре это отразит перевернутое изображение убийцы в кровавом пруду. Если бы в видеоигре были изогнутые отражающие поверхности, такие как комната зеркал, матрица была бы более сложной, чтобы растянуть или уменьшить отражение.
В прикладной физике матрицы используются для изучения электрических цепей, квантовой механики и оптики. Аэрокосмическая инженерия, химическая инженерия и т. Д. Требуют идеально откалиброванных вычислений, полученных в результате матричных преобразований. В больницах, медицинских изображениях, компьютерной томографии и МРТ для получения результатов используются матрицы.
В программировании матрицы и обратные матрицы используются для кодирования и шифрования сообщений. В робототехнике и автоматизации матрицы являются основными компонентами движений робота. Входные данные для управления роботами получены на основе расчетов с использованием матриц.
На что они похожи?
Условно число строк в матрице обозначаетсями количество столбцов поN, Так как площадь прямоугольникаростИксширина,мы обозначаем размер матрицымИксп.Таким образом, матрица должна была быть названаA,это будет записано в нотации как
Здесь m = 3 и n = 4. Таким образом, в матрице А 12 элементов. Квадратная матрица имеетт = п,
Матрица с одной строкой называетсяматрица строки матрица с одним столбцом называетсяматрица столбцов.
Что мы можем с ними сделать?
Матрицы так же, как числа могут быть добавлены, вычтены и умножены. Разделение немного нюанс. Не все матрицы могут быть разделены.
Существуют определенные правила даже для сложения, вычитания и умножения.
Дополнение матриц
Сложение двух матриц А (м * п) а также B (м * п) дает матрицу С (м * п). Элементы C являются суммой соответствующих элементов в A и B
Вычитание работает аналогично.
Здесь следует отметить, что вы можете только добавлять / вычитать матрицы с одинаковым количеством строк и столбцов, т.е.тот же порядок (порядок = строки х столбцы)
Указывает на заметку
Умножение хоть немного сложнее
Умножение матриц
Умножение двух матриц A (м * п) а также В (п*п) дает матрицу С (м * р). Обратите внимание, что для умножения вам не нужно, чтобы строки / столбцы A и B были одинаковыми. Вам нужно только
Чтобы вычислить верхний левый элемент полученной матрицы C, умножьте элементы 1-й строки A на 1-й столбец B и сложите их
Указывает на заметку
В следующем издании этой статьи мы увидим больше операций, которые могут быть выполнены над матрицами, например, Инверсия матрицы, определитель матрицы, сопряжение матрицы и т. Д.
Мы также увидим, как эти матрицы действительно помогают в областинейронные сетии обработка изображений.
Матрицы имеют огромное значение почти во всех алгоритмах машинного обучения изКНН(Алгоритм ближайшего соседа) вплоть доСлучайные Леса,
3D своими руками. Часть 2: оно трехмерное
В предыдущей части мы разобрались, как выводить на экран двумерные объекты, такие как пиксель и линия (отрезок), но ведь хочется поскорее создать что-то трехмерное. В этой статье впервые попробуем вывести 3D-объект на экран и познакомимся с новыми математическими объектами, такими как вектор и матрица, а также некоторыми операциями над ними, но только с теми, которые применим на практике.
Во второй части мы рассмотрим:
Системы координат
Хочется отметить, что некоторые примеры и операции в статьях изложены неточно и сильно упрощены для улучшения понимания материала, ухватив суть, вы сможете самостоятельно найти лучшее решение или исправить ошибки и неточности в демонстрационном коде. Перед тем как нарисуем что-то трехмерное, важно помнить, что все трехмерное на экране выводится двухмерными пикселями. Для того, чтобы объекты нарисованные пикселями выглядели трехмерными, нам необходимо разобрать немного математики. Мы не будем рассматривать формулы и объекты, не видя их применения. Именно поэтому, все математические операции, которые вы встретите в данной статье, будут применены на практике, что упростит их понимание.
Первое что необходимо разобрать – это системы координат. Посмотрим, какие системы координат используются, а также выберем, какую использовать нам.
Что такое система координат? Это способ определять положение точки или персонажа игры состоящего из точек при помощи чисел. Система координат имеет 2 направления осей (будем их обозначать как X, Y), если мы работаем с 2D графикой. Если мы 2D-объекту зададим больший Y и он станет выше, чем был до этого – это значит, что ось Y направлена вверх. Если мы объекту зададим больший Х и он станет правее – это значит, что ось Х направлена вправо. Это и есть направления осей, а вместе они называются системой координат. Если в месте пересечения осей Х и Y образуется угол 90 градусов, то такую систему координат называют прямоугольной (еще называют Декартовой системой координат) (см. Рисунок выше).
Но это была система координат в 2D мире, в трехмерном же, появляется еще одна ось – Z. Если ось Y (еще говорят ордината) позволяет рисовать выше/ниже, ось Х (еще говорят абсцисса) левее/правее, то ось Z (еще говорят аппликата) позволяет отдалять/приближать объекты. В трехмерной графике часто (но не всегда) используется система координат, в которой ось Y направлена вверх, ось Х направлена вправо, а вот Z может быть направлена, либо в одном направление, либо в другом. Именно поэтому системы координат мы разделим на 2 типа – левостороннюю и правостороннюю (см. Рисунок выше).
Как видно из рисунка, левосторонней системой координат (еще говорят левая система координат) называют когда ось Z, направлена от нас (чем больше Z, тем дальше объект), если же ось Z направлена к нам, то это – правосторонняя система координат (еще говорят правая система координат). Почему их так назвали? Левая, потому что, если левую руку направить ладонью вверх, а пальцами в сторону оси Х, то большой палец укажет направление Z, то есть, будет направлен в сторону монитора, если Х направлен вправо. Тоже проделайте с правой рукой, и ось Z будет направлена от монитора, при Х вправо. Запутались с пальцами? В интернете есть разные способы ставить руку и пальцы, чтобы получить нужные направления осей, но это не обязательная часть.
Для работы с 3D-графикой есть много библиотек для разные языков, где используются разные системы координат. Например, в библиотеке Direct3D используется левосторонняя система координат, а в OpenGL и WebGL правосторонняя, в VulkanAPI ось Y направлена вниз (чем меньше Y тем выше будет объект) а Z от нас, но это всего лишь соглашения, в библиотеках мы можем сами указать ту систему координат, которую считаем более удобной.
Какую систему координат выбрать нам? Подойдет любая, мы только учимся и направления осей сейчас на усвоение материала не повлияют. В примерах мы будем использовать правостороннюю систему координат и чем меньше мы укажем Z для точки, тем дальше она будет от экрана, при этом X,Y будут направлены вправо/вверх.
Точка и вектор
Теперь вы базово знаете, что такое системы координат и какие есть направления осей. Далее необходимо разобрать, что такое точка и вектор, т.к. они нам понадобятся в этой статье для практики. Точкой в 3D-пространстве называют какое-то местоположение, заданное через [X, Y, Z]. Например, мы своего персонажа хотим разместить в самом начале координат (возможно, в центре окна), тогда его положение будет [0, 0, 0], или же можно сказать, что он расположен в точке [0, 0, 0]. Теперь, мы хотим разместить противника левее игрока на 20 единиц (к примеру, пикселей), значит, он будет расположен в точке [-20, 0, 0]. Мы постоянно будем работать с точками, поэтому подробнее их разберем позже.
У вектора нет положения, а [X, Y, Z] обозначают направление. Вектор можно прибавлять к точке, для того, чтобы получить новую точку, смещенную на вектор. Например, выше я уже упомянул, что если мы хотим двигать 3D-объект (например, игрового персонажа) каждую секунду на 5 единиц вверх, то вектор смещения будет таким: [0, 5, 0]. Но как его использовать для перемещения?
Допустим, персонаж находится в точке [5, 7, 0], а вектор смещения [0, 5, 0]. Если мы прибавим к точке вектор, то получим новое положение игрока. Складывать точку с вектором, или вектор с вектором можно по следующему правилу.
Пример сложения точки и вектора :
Мы уже знаем, что такое точка, вектор, как суммировать точку и вектор (или 2 вектора), и как вычислять длину вектора. Давайте добавим класс вектора и реализуем в нем суммирование и вычисление длины. Хочу также обратить внимание на то, что мы не будем создавать класс для точки, если нам понадобится точка, то мы будем использовать класс вектора, т.к. и точка и вектор хранят в себе X, Y, Z, просто для точки это положение, а для вектора направление.
Добавьте в проект с предыдущей статьи класс вектора, можно его добавить ниже класса Drawer. Я свой класс назвал Vector и добавил в него 3 свойства X, Y, Z:
Заметьте, что поля x, y, z без функций «аксессоров», так мы можем напрямую обращаться к данным в объекте, это сделано для более быстрого доступа. Позднее, мы оптимизируем этот код еще сильнее, но сейчас оставим так, чтобы улучшить читаемость.
Теперь реализуем суммирование векторов. Функция будет принимать 2 суммируемых вектора, поэтому я думаю сделать ее статической. Тело функции будет работать согласно формуле выше. Результатом нашего суммирования получится новый вектор, которым мы и будем возвращать:
Осталось реализовать функцию вычисления длины вектора. Опять же, все реализовываем по формулам, которые были выше:
Метод normalize нормализует вектор и возвращает его (this), это нужно чтобы в дальнейшем можно было normalize использовать в выражениях.
Теперь, когда мы знаем что такое нормализация вектора, и знаем что ее лучше выполнять перед использованием вектора, возникает вопрос. Если нормализация вектора – это приведение к единичной длине, то есть скорость перемещения объекта (персонажа) будет равна 1, то как ускорить персонаж? Например, при перемещении персонажа по диагонали вверх/вправо со скоростью 1, его вектор будет [0.707, 0.707, 0], а какой вектор будет если мы захотим персонажа перемещать в 6 раз быстрее? Для этого существует операция, которая называется «умножение вектора на скаляр». Скаляром называют обычное число на которое умножают вектор. Если скаляр будет равен 6, то вектор станет в 6 раз длиннее, а наш персонаж в 6 раз быстрее соответственно. Как же выполнить умножение на скаляр? Для этого необходимо умножить каждую компоненту вектора на скаляр. Например, решим задачу выше, когда персонажа перемещающегося на вектор [0.707, 0.707, 0] (скорость 1) необходимо ускорить в 6 раз, то есть умножить вектор на скаляр 6. Формула умножения вектора «V» на скаляр «s» следующая:
В нашем случае это будет:
– новый вектор перемещения, длина которого равна 6.
Важно знать, что положительный скаляр масштабирует вектор не меняя его направления, если же скаляр отрицательный, то он также масштабирует вектор (увеличивает его длину) но вдобавок меняет направление вектора на противоположное.
Давайте реализуем функцию multiplyByScalar умножения вектора на скаляр в нашем классе Vector:
Матрица
Мы немного разобрались с векторами и некоторыми операциями над ними, которые понадобятся в этой статье. Далее необходимо разобраться с матрицами.
Можно сказать, что матрица – это самый обычный двумерный массив. Просто в программирования используют термин «двумерный массив», а в математике «матрица». Для чего же в 3D-программировании нужны матрицы? Это мы разберем, как только немного научимся с ними работать.
Мы будем использовать только числовые матрицы (массив чисел). У каждой матрицы есть свой размер (как у любого 2-мерного массива). Вот несколько примеров матриц:
Из всех операций над матрицами, мы сейчас рассмотрим лишь умножение (остальные позже). Так получается, что умножение матриц не самая простая операция, она способна легко запутать, если не внимательно проследить за порядком умножения. Но не переживайте, у вас все получится, т.к. тут мы будем только умножать и суммировать. Для начала, нужно запомнить пару особенностей умножения, которые нам понадобятся:
Умножение M1 на M2 возможно, т.к. в первой матрице 2 столбца, а во второй 2 строки.
Умножение М1 на М2 возможно, т.к. в первой матрице 3 столбца, а во второй 3 строки.
Умножение М1 на М2 невозможно, т.к. в первой матрице 2 столбца, а во второй 3 строки.
Думаю, данные примеры немного разъяснили картину, когда возможно умножение. Результатом умножения матриц, будет всегда матрица, количество строк которой будет равно количеству строк 1-й матрицы, а количество столбцов, равно количеству столбцов 2-й. Например, если умножить матрицу 2 на 6 и 6 на 8, то получится матрица размером 2 на 8. Теперь перейдем, непосредственно к самому умножению.
Для умножения важно помнить, что столбцы и строки в матрице нумеруются начиная с 1, а в массиве с 0. Первый индекс в элементе матрицы, указывает на номер строки, а второй на номер столбца. То есть, если элемент матрицы (элемент массива) записан в виде: m28, это значит что мы обращаемся ко второй строке и восьмому столбцу. Но поскольку в коде мы будем работать с массивами, вся индексация строк и столбцов у нас будет начинаться с 0.
Давайте попробуем перемножить 2 матрицы A и B с конкретными размерами и элементами:
Видно, что матрица А имеет размер 3 на 2, а матрица В размер 2 на 2, умножение возможно:
Как видим, у нас получилась матрица 3 на 2, умножение поначалу запутанное, но если есть цель научиться умножать «без напряга», необходимо решить несколько примеров. Вот еще пример умножения матриц A и В:
Если не до конца понятно умножение – ничего страшного, т.к. умножать на листике нам не придется. Мы напишем один раз функцию умножения матриц и будем использовать её. Вообще, все эти функции уже написаны, но мы делаем все самостоятельно.
Теперь еще немного терминов, которые будут в дальнейшем использоваться:
Квадратная матрица 2 на 2
Квадратная матрица 3 на 3
Квадратная матрица 4 на 4
Еще важно запомнить такое свойство, что если умножить любую матрицу M на подходящую по размеру единичную матрицу, к примеру назовем ее I, то получим исходную матрицу M, например: M * I = M или I * M = M. Т.е. умножение матрицы на единичную матрицу никак не влияет на результат. К единичной матрице мы вернемся позднее. В 3D-программировании мы часто будем использовать квадратную матрицу 4 на 4.
Теперь немного разберем, зачем нам нужны будут матрицы и зачем их умножать? В 3D-программировании существует множество различных матриц 4 на 4, которые если умножить на вектор или точку, будут выполнять нужные нам действия. Например, нам необходимо повернуть персонажа в трехмерном пространстве вокруг оси Х, как это сделать? Умножить вектор на специальную матрицу, которая отвечает за поворот вокруг оси X. Если нужно переместить и повернуть точку вокруг начала координат, то нужно умножить эту точку на специальную матрицу. У матриц есть прекрасное свойство – комбинирования преобразований (рассмотрим в этой статье). Допустим, нам необходимо персонажа состоящего из 100 точек (вершин, но об этом тоже будет немного ниже) в приложении увеличить в 5 раз, потом повернуть на 90 градусов по Х, потом перенести на 30 единиц вверх. Как уже было сказано – для разных действий уже существуют специальные матрицы, которые мы рассмотрим. Для выполнения задачи выше, мы, к примеру, в цикле перебираем все 100 точек и каждую сначала умножаем на 1-ю матрицу, чтобы увеличить персонажа, затем умножаем на 2-ю матрицу, чтобы повернуть на 90 градусов по Х, потом умножаем на 3-ю для перемещения на 30 единиц вверх. Итого, для каждой точки у нас 3 умножения матрицы, а точек 100, значит, умножений будет 300. Но если мы возьмем и перемножим между собой матрицы для увеличения в 5-ть раз, поворота на 90 градусов по Х и перемещение на 30 ед. вверх, то получим матрицу, которая в себе содержит все эти действия. Умножив точку на такую матрицу, точка окажется там, где нужно. Подсчитаем теперь, сколько действий выполняется: 2 умножения для 3-х матриц, и 100 умножений для 100 точек, итого 102 умножения – точно лучше, чем 300 умножений до этого. Тот момент, когда мы перемножили 3 матрицы для объединения различных действий в одну матрицу – называется комбинированием преобразований и мы его обязательно сделаем на примере.
Как умножить матрицу на матрицу мы разбирали, но в прочитанном выше абзаце говорится об умножении матрицы на точку или вектор. Для умножения точки или вектора достаточно их представить матрицей.
Например, у нас есть вектор [10, 2, 5] и есть матрица:
Видно, что вектор можно представить матрицей 1 на 3 или матрицей 3 на 1. Поэтому мы можем умножить вектор на матрицу 2 способами:
Здесь мы представили вектор, как матрицу 1 на 3 (еще говорят вектор-строка). Такое умножение возможно, т.к. в первой матрице (векторе-строке) 3 столбца, а во второй матрице 3 строки.
Здесь мы представили вектор, как матрицу 3 на 1 (еще говорят вектор-столбец). Такое умножение возможно, т.к. в первой матрице 3 столбца, а во второй (векторе-столбце) 3 строки.
Как видно, мы можем представить вектор как вектор-строку и умножать его на матрицу, или представить вектор, как вектор-столбец и умножать матрицу на него. Давайте проверим, будет ли результат умножения одинаковым в обоих случаях:
Умножаем вектор-строку на матрицу:
Теперь, умножим матрицу на вектор-столбец:
Мы видим, что умножая вектор-строку на матрицу и матрицу на вектор-столбец, мы получили совершенно разные результаты (вспоминаем про коммутативность). Поэтому, в 3D-программировании существую матрицы, которые предназначены для умножения только на вектор строку, или только на вектор столбец. Если мы умножим матрицу предназначенную для вектора-строки на вектор-столбец, то получим результат, который нам ничего не даст. Используйте удобное вам представление вектора/точки (строка или столбец), только в дальнейшем используйте для вашего представления вектора/точки соответствующие матрицы. В Direct3D, например, используют строковое представление векторов, и все матрицы в Direct3D предназначение для умножения вектора-строки на матрицу. В OpenGL используется представление вектора (или точки), как столбца, и все матрицы предназначены для умножения матрицы на вектор-столбец. В статьях будем использовать вектор-столбец и будем умножать, матрицу на вектор-столбец.
Подведем небольшой итог прочитанного про матрицы.
Давайте добавим в проект класс Matrix. Еще иногда класс для работы с матрицами 4 на 4 называют Matrix4, и эта 4 в названии говорит нам о размере матрицы (еще говорят матрица 4-го порядка). Все данные матриц мы будем хранить в двумерном массиве 4 на 4.
Перейдем к реализации операций умножения. Я не рекомендую использовать циклы для этого. Чтобы повысить быстродействие, мы все должны умножать построчно – так получится сделать за счет того, что все умножения у нас будут происходить с матрицами фиксированного размера. Я буду использовать циклы для операции умножения, только для экономии объема кода, вы же можете написать все умножение без циклов вообще. У меня код умножения выглядит так:
Как видите, метод принимает матрицы a и b, умножает их и возвращает результат в виде такого же массива 4 на 4. В начале метода я создал матрицу m заполненную нулями, но это не обязательно, так я хотел показать какой размерности будет результат, вы же можете создать массив 4 на 4, без каких либо данных.
Теперь необходимо реализовать умножение матрицы на вектор-столбец, как обсудили выше. Но если представить вектор столбцом, то получится матрица вида: 
на которую нам нужно будет умножать на матрицы 4 на 4 для выполнения различных действий. Но на этом примере прекрасно видно, что такое умножение выполнить нельзя, ведь у вектора-столбца 3 строки, а у матрицы 4 столбца. Что же тогда делать? Нужен какой-то четвертый элемент, тогда у вектора станет 4 строки, которые будут равны количеству столбцов у матрицы. Давайте добавим вектору такой 4-й параметр и назовем его W, теперь у нас все вектора в 3D будут вида [X, Y, Z, W] и такие вектора уже можно будет умножать на матрицу 4 на 4. На самом деле у компоненты W более глубокое назначение, но с ним мы познакомимся в следующей части (ведь не зря у нас матрица 4 на 4, а не 3 на 3). Добавляем в класс Vector, который мы создавали выше компоненту w. Теперь начало класса Vector выглядит так:
Я проинициализировал W единицей, но почему 1? Если мы присмотримся к тому, как умножаются компоненты матрицы и вектора (пример кода ниже), можно заметить, что если поставить в качестве W значение 0 или любое другое отличное от 1, тогда при умножении этот W будет влиять на результат, а мы пока не знаем, как им пользоваться, а если мы его сделаем 1, то он в векторе будет, но результат никак не поменяет.
Теперь вернемся к матрице и реализуем в классе Matrix (можно и в классе Vector, разницы нет) умножения матрицы на вектор, которое уже возможно, благодаря W:
Обратите внимание, что матрицу мы представили массивом 4 на 4, а вектор объектом со свойствами x, y, z, w, в будущем мы вектор поменяем и он тоже будет представлен массивом 1 на 4, т.к. это ускорит умножение. Но сейчас, для того чтобы лучше видеть, как происходит умножение и улучшить понимание кода, мы менять вектор не будем.
Код для умножения матриц между собой и умножения матрицы на вектор мы написали, но все еще не понятно как это нам поможет в трехмерной графике.
Хочу также напомнить, что я вектором называю как точку (положение в пространстве) так и направление, т.к. оба объекта содержат одинаковую структуру данных x, y, z и нововведенный w.
Давайте рассмотрим некоторые из матриц, которые выполняют базовые операции над векторами. Первой из таких матриц будет матрица перемещения (Translation matrix). Умножив матрицу перемещения на вектор (местоположение) он сместится на указанное число единиц в пространстве. А вот и матрица перемещения:
В этом примере, в матрицу перемещения мы подставили нужное смещение персонажа (translationMatrix), проинициализировали его начальное положение (characterPosition) и потом перемножили его с матрицей, а результат вывели через console.log (это отладочный вывод в JS). Если вы используете не JS, то выведите X, Y, Z самостоятельно при помощи инструментов вашего языка. Результат, который мы получили в консоли: [20, 15, 9, 1], все сходится с результатом, который мы посчитали выше. У вас может возникнуть вопрос, зачем получать такой же результат умножением вектора на специальную матрицу, если мы его гораздо проще получили просуммировав вектор со смещением покомпонентно. Ответ не самый простой и мы подробнее его еще обсудим, но сейчас можно отметить что как обсуждалось ранее, мы матрицы с разными преобразованиями можем комбинировать между собой, таким образом сокращая очень много вычислений. Матрицу translationMatrix в примере выше, мы создали в виде массива вручную и подставили туда необходимое смещение, но поскольку мы этой и другими матрицами будем пользоваться часто, то давайте вынесем ее в метод в классе Matrix, и смещение в нее будем передавать аргументами:
Присмотритесь еще раз к матрице перемещения, вы увидите, что dx, dy, dz находятся в последнем столбце и если мы посмотрим код умножения матрицы на вектор, то заметим, что именно этот столбец умножается на W компоненту вектора. И если бы она была, например 0, то dx, dy, dz, мы бы умножали на 0 и перемещение не работало бы. Но мы можем W делать равное 0, если мы хотим в классе Vector хранить направление, т.к. направление перемещать нельзя, то так бы мы обезопасили себя, и даже если мы умножим такое направление на матрицу перемещения, то это никак не поломает вектор направления, т.к. все перемещение будем умножаться на 0.
Итого можем применить такое правило, местоположение мы создаем так:
А направление создам так:
Так мы сможем отличать местоположение и направление, и при умножении направления на матрицу перемещения мы случайно не сломаем вектор направления.
Вершины и индексы
Прежде чем посмотрим какие еще есть матрицы, разберемся немного с тем, как нам применить уже имеющиеся знания для вывода чего-то трехмерного на экран. Все что мы выводили до этого – линии и пиксели. Но давай теперь при помощи этих инструментов, выведем, например куб. Для того чтобы это сделать нам необходимо разобраться из чего состоит трехмерная модель. Самая основная составляющая любой 3D-модели – это точки (далее будем называть вершины) по которым мы можем ее нарисовать, это, по сути, много векторов местоположений, которые, если мы правильно их соединим между собой линиями, получим 3D-модель (сетку модели) на экране, она будет без текстуры и без многих других свойств, но всему свое время. Взглянем на куб, который мы хотим вывести, и попробуем понять сколько у него вершин:
На изображении мы видим, что у куба 8 вершин (для удобства я их пронумеровал). И все вершины между собой соединены линиями (ребра куба). Т.е., чтобы описать куб и нарисовать его линиями, нам нужно 8 координат каждой вершины, и также нужно указать из какой вершины до какой нам рисовать линию, чтобы получился куб, ведь если мы мы неправильно соединим вершины, например проведем линию из вершины 0 в вершину 6, то это точно будет не куб, а другой объект. Давайте сейчас опишем координаты каждой из 8 вершин. В современной графике 3D-модели могут состоять из десятков тысяч вершин, и конечно же никто вручную их не прописывает. Модели рисуют в 3D-редакторах и когда экспортируют 3D-модель, в ее коде уже есть все вершины, нам нужно только их загрузить и нарисовать, но мы пока что учимся и не умеем читать форматы 3D-моделей, поэтому куб опишем вручную, он очень простой.
Представим, что куб выше, находится в центре координат, его середина находится в точке 0, 0, 0 и он должен отображаться вокруг этого центра:
Каждую вершину я положил в экземпляр класса Vector, это не лучший вариант для производительности (лучше в массиве), но сейчас наша цель разобраться как все работает.
Давайте сейчас воспринимать значения координат вершин куба как пиксели, которые мы будем рисовать на экране, в таком случае мы видим что размер куба 2 на 2 на 2 пикселей. Мы создали такой маленький куб, чтобы в т.ч. посмотреть на работу матрицы масштабирования, при помощи которой мы его увеличим. В дальнейшем очень хорошая практика делать модели маленькими, даже еще меньше, чем у нас, чтобы увеличивать их до нужного размера не сильно разными скалярами.
Просто точки куба рисовать пикселями не очень наглядно, т.к. все что мы увидим – это 8 пикселей, по одному на каждую вершину, гораздо лучше нарисовать куб линиями используя функцию drawLine из прошлой статьи. Но для этого нам нужно понять из каких вершин в какие у нас проходят линии. Взглянем на изображение куба с индексами еще раз и мы увидим, что он состоит из 12 линий (или ребер). Также очень легко увидеть что мы знаем координаты начала и конца каждой линии. Например одна из линий (верхняя ближняя) должна быть нарисована из вершины 0 в вершину 3, или же из координат [-1, 1, 1] в координаты [1, 1, 1]. Информацию о каждой линии нам придется записать в коде вручную смотря на изображение куба, но как правильно это сделать? Если у нас 12 линий и у каждой линии есть начало и конец, т.е. 2 точки, тогда, чтобы нарисовать куб нам понадобится 24 точки? Это правильный ответ, но давайте взглянем на изображение куба еще раз и обратим внимание на то что у куба каждая линия имеет общие вершины, например, в вершине 0 соединяются 3 линии, и так с каждой вершиной. Мы можем сэкономить память и не записывать координаты начала и конца каждой линии, достаточно создать массив и указать индексы вершин из массива vertices в которых эти линии начинаются и заканчиваются. Давайте создадим такой массив и опишем его только индексами вершин, по 2 индекса на каждую линию (начало линии и конец). А немного далее, когда будем рисовать эти линии, мы с легкостью достанем их координаты из массива vertices. Мой массив линий (я назвал его edges, т.к. это ребра куба) я создал ниже массив вершин и выглядит он так:
В этом массиве 12 пар индексов, по 2 индекса вершин на каждую линию.
Давайте сейчас познакомимся еще с одной матрицей, которая увеличит наш куб, и наконец, попробуем его нарисовать на экране. Матрица масштабирования (Scale Matrix) выглядит так:
Параметры sx, sy, sz на главной диагонали означают во сколько раз мы хотим увеличить объект. Если мы в матрицу подставим 10, 10, 10 вместо sx, sy, sz, и умножим эту матрицу на вершины куба, это сделает что наш куб в десять раз больше и он уже будет не 2 на 2 на 2, а 20 на 20 на 20.
Для матрицы масштабирования, так же, как и для матрицы перемещения реализуем метод в классе Matrix, который будет возвращать матрицу с уже подставленными аргументами:
Конвейер визуализации
Если мы сейчас попытаемся нарисовать куб линиями используя текущие координаты вершин, то мы получим очень маленький двухпиксельный куб, в верхнем левом углу экрана, т.к. начало координат canvas находится именно там. Давайте пройдем циклом по всем вершинам куба и умножим их на матрицу масштабирования, чтобы сделать куб больше, а потом еще и на матрицу смещения, чтобы увидеть куб не в верхнем левом углу, а посередине экрана, у меня код перебора вершин с умножением матриц находится ниже массива edges, и выглядит так:
С вершинам мы пока что закончили, но еще нужно все это нарисовать используя drawLine и массив edges, давайте ниже цикла с вершинами напишем еще один цикл для перебора edges и в нем нарисуем все линии:
Вспомним, в прошлой статье все рисование мы начинаем с очистки экрана от предыдущего состояния вызовом метод clearSurface, затем я перебираю все грани куба и рисую куб линиями синего цвета (0, 0, 255), а сами координаты линий я беру из массива sceneVertices, т.к. там лежат уже отмасштабированные и перемещенные вершины в предыдущем цикле, но индексы этих вершин совпадают с индексами оригинальных вершин из массива vertices, т.к. я обрабатывал их и ложил в массив sceneVertices без изменения порядка.
Если мы сейчас запустим код, то ничего не увидим на экране. Это потому что в нашей системе координат Y смотрит вверх, а в системе координат canvas вниз. Получается, что наш куб есть, но он находится за пределами экрана и чтобы это исправить, нам нужно перед рисованием пикселя в классе Drawer перевернуть картинку по Y (отзеркалировать). Пока что такого варианта нам будет достаточно, в итоге код рисования пикселя у меня выглядит так:
Видно что в формуле получения offset, Y теперь со знаком минус и ось теперь смотрит в нужном нам направлении, также в этом методе я добавил проверку выхода за пределы массива пикселей. В классе Drawer появились и некоторые другие оптимизации благодаря комментариям к предыдущей статье, поэтому выкладываю весь класс Drawer с небольшими оптимизациями и вы можете заменить старый Drawer на этот:
Если сейчас вы запустите код, то на экране будет такое изображение:
Матрица поворота вокруг оси X
Матрица поворота вокруг оси Y
Матрица поворота вокруг оси Z
Если мы умножим вершины куба на одну из этих матриц, то куб повернется на указанный угол (a) вокруг той оси, матрицу поворота вокруг которой мы выберем. Тут есть некоторые особенности при повороте вокруг сразу нескольких осей и на них мы посмотрим ниже. Из примера матриц видно, что они используют 2 функции sin и cos и в JavaScript уже есть функционал для их вычисления Math.sin(a) и Math.cos(a), но они работают с радианной мерой углов, которая может показаться не самой удобной, если мы хотим повернуть модель. Мне, например, гораздо удобнее что-то повернуть на 90 градусов (градусная мера), что в радианной мере будет означать Pi / 2 (В JS также есть приблизительное значение Pi это константа Math.PI). Давайте в класс Matrix добавим 3 метода для получения матриц вращения, с принимаемым углом поворота в градусах, который мы преобразуем в радианы, т.к. они нужны для работы функций sin / cos:
Все 3 метода начинаются с преобразования градусов в радианы, после чего мы подставляем угол поворота в радианах в матрицу поворота, передавая углы в функции sin и cos. Почему матрица именно такая, вы можете подробнее прочитать на хабре в тематических статьях, с очень подробным разъяснением, в противном случае – вы можете воспринимать эти матрицы как формулы, которые вычислили для нас и мы можем быть уверенными в том, что они рабочие.
Выше в коде мы реализовали 2 цикла, первый – преобразовывает вершины, второй – выводит линии по индексам вершин, в итоге мы получаем из вершин картинку на экране, и давайте этот участок кода назовем конвейер визуализации. Конвейер потому что мы берем вершину и поочередно делаем с ней разные операции, масштаб, сдвиг, поворот, отрисовку, как на обычном промышленном конвейере. Теперь давайте в первый цикл в конвейере визуализации добавим помимо масштабирования, еще и поворот вокруг осей. Сначала я поверну вокруг X, потом вокруг Y, затем увеличу модель и перемещу ее (2 последних действия уже есть), итого весь код цикла у меня будет таким:
В этом примере я повернул все вершины вокруг оси X на 20 градусов, потом вокруг Y на 20 градусов и 2 оставшихся преобразования у меня уже были. Если вы все сделали правильно, то ваш куб, теперь должен выглядеть трехмерным:
У поворота вокруг осей есть одна особенность, например, если вы повернете куб сначала вокруг оси Y, а потом вокруг оси X, то результаты будут отличаться:
Есть и другие особенности, например, если куб повернуть на 90 градусов по оси Х, затем на 90 градусов по оси Y, и наконец, на 90 градусов вокруг оси Z, то последний поворот вокруг Z, отменит поворот вокруг Х, и получится такой же результат как если бы вы просто повернули фигуру на 90 градусов вокруг оси Y. Чтобы посмотреть почему так происходит, возьмите любой прямоугольный (или кубический) объект в руки (напр. собранный кубик Рубика), запомните начальное положение объекта и проверните его сначала на 90 градусов вокруг воображаемого Х, а затем на 90 градусов вокруг Y и на 90 градусов вокруг Z и запомните, какой стороной он к вам стал, затем начните с запомненного ранее начального положения и проделайте то же самое, убрав повороты повороты X и Z, повернути только вокруг Y — вы увидите, что результат одинаковый. Сейчас мы не будем решать эту проблему и вдаваться в ее подробности, такое вращение на данный момент нас полностью устраивает, но мы эту проблему еще упомянем в третьей части (если хочется подробнее разобраться сейчас, попробуйте поискать статьи на хабре по запросу «шарнирный замок»).
Теперь давайте немного оптимизируем наш код, выше упоминалось, что матричные преобразования можно комбинировать между собой, путем перемножения матриц преобразований. Давайте попробуем не умножать каждый вектор сначала на матрицу поворота вокруг X, затем вокруг Y, затем масштабирования и в конце перемещения, а сначала, до цикла, перемножим все матрицы, а в цикле будем умножать каждую вершину лишь на одну результирующую матрицу, у меня код вышел таким:
В данном примере комбинирование преобразований выполняется до цикла 1 раз, и поэтому у нас всего 1 умножение матрицы с каждой вершиной. Если вы запустите этот код, то рисунок куба должен остаться прежним.
Давайте добавим простейшую анимацию, а именно – будем менять угол вращения вокруг оси Y в интервале, например, будем изменять угол вращения вокруг оси Y на 1 градус, каждые 100 миллисекунд. Для этого нужно положить код конвейера визуализации в функцию setInterval, которую мы впервые использовали в 1-й статье. Код конвейера с анимацией выглядит так:
Результат должен быть таким:
Последнее, что мы сделаем в этой части – вывод осей системы координат на экран, чтобы было видно вокруг чего вращается наш куб. Ось Y нарисуем из центра вверх, длинной в 200 пикселей, ось X – вправо, тоже длинной 200 пикселей, а ось Z, нарисуем вниз и влево (по диагонали) длинной 150 пикселей, как это показано в самом начале статьи на рисунке правосторонней системы координат. Начнем с самой простой части, это оси X, Y, т.к. их линия смещается лишь в одном направлении. После цикла, который рисует куб (цикл перебора edges) добавим отрисовку X, Y осей:
И в результате вы получите все 3 оси нужной длины:
В этом примере ось Z, лишь показывает какая у нас система координат, мы ее нарисовали по диагонали чтобы ее было видно, т.к. настоящая ось Z перпендикулярна нашем взгляду, и ее мы могли бы нарисовать точкой на экране, что было бы не красиво.
Итого, в это статье мы базово разобрались в системах координат, векторах и с некоторыми операциями над ними, матрицами и их роли в преобразованиях координат, разобрались с вершинами и написали простенький конвейер визуализации куба и осей системы координат, закрепив теорию практикой. Весь код приложения доступен под спойлером: