Поворот вектора по двум углам

Объект обычно определяется в удобной для его описания локальной системе координат (ЛСК), а его положение в пространстве — в глобальной системе координат (ГСК).

В трёхмерном пространстве переход из одной СК в другую описывается в общем случае системой линейных уравнений:

Уравнения могут быть записаны через матрицы аффинных преобразований в однородных координатах одним из 2-х способов:

В ортогональных СК оси X, Y и Z взаимно перпендикулярны и расположены по правилу правой руки:

На рисунке справа большой палец определяет направление оси, остальные пальцы — положительное направление вращения относительно этой оси.

Все три вектора направлений есть единичными.

Ниже приводится единичная матрица для 2-х способов записи уравнений геометрических преобразований. Такая матрица не описывает ни перемещения, ни вращения. Оси ЛСК и ГСК совпадают.

Далее рассматривается матрица для второго способа матричной записи уравнений (матрица справа). Этот способ встречается в статьях значительно чаще.

При использовании матрицы вы можете игнорировать нижнюю строку. В ней всегда хранятся одни и те же значения 0, 0, 0, 1. Она добавлена для того, чтобы мы могли перемножать матрицы (напомню правило перемножения матриц и отмечу, что всегда можно перемножать квадратные матрицы). Подробнее см. Композиция матриц. Однородные координаты.

Остальные 12 значений определяют координатную систему. Первый столбец описывает компоненты направления оси X(1,0,0). Второй столбец задает направление оси Y(0,1,0), третий – оси Z (0,0,1). Последний столбец определяет положение начала системы координат (0,0,0).

Как будет выглядеть матрица Евклидового преобразования (преобразование движения) для задания ЛСК , с началом в точке (10,5,0) и повёрнутой на 45° вокруг оси Z глобальной СК, показано на рисунке.

Рассмотрим сначала ось X. Если новая система координат повернута на 45° вокруг оси z, значит и ось x повернута относительно базовой оси X на 45° в положительном направлении отсчета углов. Таким образом, ось X направлена вдоль вектора (1, 1, 0), но поскольку вектор системы координат должен быть единичным, то результат должен выглядеть так (0.707, 0.707, 0). Соответственно, ось Y имеет отрицательную компоненту по X и положительную по Y и будет выглядеть следующим образом (-0.707, 0.707, 0). Ось Z направления не меняет (0, 0, 1). Наконец, в четвертом столбце вписываются координаты точки начала системы координат (10, 5, 0).

Частным случаем матриц геометрических преобразований есть матрицы поворота ЛСК относительно базовых осей ГСК. Вектора осей ЛСК здесь выражены через синусы и косинусы углов вращения относительно оси, перпендикулярной к плоскости вращения.

От матрицы преобразований размером 4*4 можно перейти непосредственно к матрице поворота 3*3, убрав нижний ряд и правый столбец. При этом, система линейных уравнений записывается без свободных элементов (лямда, мю, ню), которые определяют перемещение вдоль осей координат.

Путем перемножения базовых матриц можно получать комбинированные вращения. Ниже рассмотрены возможности комбинировать вращениями через матрицы поворота на примерах работы с углами Эйлера.

Видео:Матрица поворотаСкачать

Матрицы поворота и углы Эйлера

От выбора осей и последовательности вращения зависит конечный результат. На рисунках отображена следующая последовательность вращения относительно осей ЛСК:

• оси Z (угол alpha);
• оси X (угол beta);
• оси Z (угол gamma).

Получил от читателя этой статьи вопрос: «Как понять, из каких углов поворота вокруг осей X,Y,Z можно получить текущее положение объекта, когда в качестве задания мы уже имеем повернутый объект, а нужно вывести его в это положение, последовательно повернув его из какого-то начального положения до полного совмещения с заданным?»

Мой ответ: «Если я правильно понял вопрос, то Вас интересует, как от начального положения перейти к заданному положению объекта, используя для этого элементарные базовые аффинные преобразования.

Начну с аналогии. Это как в шахматах. Мы знаем как ходит конь. Необходимо переместить его в результате многоходовки в нужную клетку на доске — при условии, что это возможно.

Подробно эта проблематика рассмотрена в статье Преобразование координат при калибровке роботов.

Умение правильно выбирать последовательность элементарных геометрических преобразований помогает в решении множества других задач (см. Примеры геометрических преобразований).»

Можно получить результирующую матрицу, которая определяет положение ГСК относительно ЛСК. Для этого необходимо перемножить матрицы с отрицательными углами в последовательности выполнения поворотов:

Почему знак угла поворота меняется на противоположный? Объяснение этому простое. Движение относительно. Абстрагируемся и представим, что ГСК меняет положение относительно неподвижной ЛСК. При этом направление вращения меняется на противоположное.

Перемножение матриц даст следующий результат:

Результирующую матрицу можно использовать для пересчета координат из ГСК в ЛСК:

Для пересчета координат из ЛСК в ГСК используется результирующая обратная матрица.

В обратной матрице последовательность поворота и знаки углов меняются на противоположные (в рассматриваемом примере снова на положительные) по сравнению с матрицей определения положения ГСК относительно ЛСК.

Перемножение матриц даст следующий результат:

Выше был рассмотрен случай определения углов Эйлера через вращение относительно осей ЛСК. То же взаимное положение СК можно получить, выполняя вращение относительно осей ГСК:

• оси z (угол (gamma+pi/2));
• оси y (угол угол beta);
• оси z (угол (-alpha)).

Определение углов Эйлера через вращение относительно осей ГСК позволяет также просто получить зависимости для пересчета координат из ЛСК в ГСК через перемножение матриц поворота.

В рамках рассматриваемой задачи вместо угла gamma в матрицe Az используем угол gamma+pi/2.

Также легко можно перейти к зависимостям для пересчета координат из ГСК в ЛСК.

Обратная матрица получается перемножением обратных матриц в обратном порядке по сравнению с прямым преобразованием. При этом каждая из обратных матриц вращения может быть получена заменой знака угла на противоположный.

Детально с теоретическими основами аффинных преобразований (включая и вращение) можно ознакомиться в статье Геометрические преобразования в графических приложениях

Примеры преобразований рассмотрены в статьях:

Видео:Угол между векторами. 9 класс.Скачать

Axis Angle представление вращения

Выбрав подходящую ось (англ. rotation axis) и угол (англ. rotation angle) можно задать любую ориентацию объекта.

Обычно хранят ось вращения в виде единичного вектора и угол поворота вокруг этой оси в радианах или градусах.

q = [ x, y, z, w ] = [ v, w ]

В некоторых случаях удобно хранить угол вращения и ось в одном векторе. Направление вектора при этом совпадает с направлением оси вращения, а его длина равна углу поворота:

q = [ x, y, z]; w=sqrt (x*x +y*y +z*z)

В физике, таким образом хранят угловую скорость. Направление вектора совпадает с направлением оси вращения, а длина вектора равна скорости (в радианах в секунду).

Можно описать рассмотренные выше углы Эйлера через Axis Angle представление в 3 этапа:

q1 = [ 0, 0, 1, alpha]; q2 = [ 1, 0, 0, beta]; q3 = [ 0, 0, 1, gamma ]

Здесь каждое вращение выполняется относительно осей текущего положения ЛСК. Такое преобразование равнозначно рассмотренному выше преобразованию через матрицы поворота:

Возникает вопрос, а можно ли 3 этапа Axis Angle представления объединить в одно, подобно матрицам поворота? Попробуем решить геометрическую задачу по определению координат последнего вектора вращения в последовательности преобразований через Axis Angle представления:

q = [ x, y, z, gamma ]

Есть ли представление q= [x, y, z, gamma] композицией последовательности из 3-х этапов преобразований? Нет! Координаты x, y, z определяют всего лишь положение оси Z ЛСК после первого и второго этапов преобразований:

При этом ось Z, отнюдь, не есть вектор вращения для Axis Angle представления, которое могло бы заменить рассмотренные 3-х этапа преобразований.

Еще раз сформулирую задачу, которая математически пока не решена: «Необходимо найти значение угла (rotation angle) и положение оси (rotation axis), вращением относительно которой на этот угол можно заменить комбинацию из 3-х поворотов Эйлера вокруг осей координат».

К сожалению, никакие операции (типа объединения нескольких преобразований в одно) с Axis Angle представлениями нельзя выполнить. Не будем расстраиваться. Это можно сделать через кватернионы, которые также определяют вращение через параметры оси и угол.

Видео:9 класс, 1 урок, Разложение вектора по двум неколлинеарным векторамСкачать

Кватернионы

Кватернион (как это и видно по названию) представляет собой набор из четырёх параметров, которые определяют вектор и угол вращения вокруг этого вектора. По сути такое определение ничем не отличается от Axis Angle представления вращения. Отличия лишь в способе представления. Как же хранят вращение в кватернионе?

q = [ V*sin(alpha/2), cos(alpha/2) ]

В кватернионе параметры единичного вектора умножается на синус половины угла поворота. Четвертый компонент — косинус половины угла поворота.

Таблица с примерами значений кватернионов:

Представление вращения кватернионом кажется необычным по сравнению с Axis Angle представлением. Почему параметры вектора умножаются на синус половины угла вращения, четвертый параметр — косинус половины угла вращения, а не просто угол?

Откуда получено такое необычное представление кватерниона детально можно ознакомиться в статье Доступно о кватернионах и их преимуществах. Хотя программисту не обязательно знать эти детали, точно также как и знать, каким образом получены матрицы преобразования пространства. Достаточно лишь знать основные операции с кватернионами, их смысл и правила применения.

Видео:Часть 3 Поворот вектораСкачать

Основные операции над кватернионами

Кватернион удобно рассматривать как 4d вектор, и некоторые операции с ним выполняются как над векторами.

Видео:89. Разложение вектора по двум неколлинеарным векторамСкачать

Сложение, вычитание и умножение на скаляр.

Смысл операции сложения можно описать как «смесь» вращений, т.е. мы получим вращение, которое находится между q и q’.

Что-то подобное сложению кватернионов выполнялось при неудачной попытке объединить 3 этапа Axis Angle представления.

Умножение на скаляр на вращении не отражается. Кватернион, умноженный на скаляр, представляет то же самое вращение, кроме случая умножения на 0. При умножении на 0 мы получим «неопределенное» вращение.

Пример сложения 2-х кватернионов:

Видео:18+ Математика без Ху!ни. Скалярное произведение векторов. Угол между векторами.Скачать

Норма и модуль

Следует различать (а путают их часто) эти две операции:

Модуль (magnitude), или как иногда говорят «длина» кватерниона:

Через модуль кватернион можно нормализовать. Нормализация кватерниона — это приведение к длине = 1 (так же как и в векторах):

Видео:§35 Формулы поворота координатных осейСкачать

Обратный кватернион или сопряжение ( conjugate )

Обратный кватернион задает вращение, обратное данному. Чтобы получить обратный кватернион достаточно развернуть вектор оси в другую сторону и при необходимости нормализовать кватернион.

Например, если разворот вокруг оси Y на 90 градусов = (w=0,707; x = 0; y = 0,707; z=0), то обратный = (w=0,707; x = 0; y = -0,707; z=0).

Казалось бы, можно инвертировать только компоненту W, но при поворотах на 180 кватернион представляется как (w=1; x = 0; y = 0; z=0), то есть, у него длина вектора оси = 0.

Фрагмент программной реализации:

Видео:А.7.19 Поворот в трехмерном пространствеСкачать

Инверсный (inverse) кватернион

Существует такой кватернион, при умножении на который произведение дает нулевое вращение и соответствующее тождественному кватерниону (identity quaternion), и определяется как:

Видео:Геометрия 9 класс (Урок№7 - Разложение вектора по двум неколлинеарным векторам. Координаты вектора.)Скачать

Тождественный кватернион

Записывается как q[0, 0, 0, 1]. Он описывает нулевой поворот (по аналогии с единичной матрицей), и не изменяет другой кватернион при умножении.

Видео:Разложение вектора по двум неколлинеарным векторам - 1 часть. Геометрия 9Скачать

Скалярное произведение

Скалярное произведение полезно тем, что дает косинус половины угла между двумя кватернионами, умноженный на их длину. Соответственно, скалярное произведение двух единичных кватернионов даст косинус половины угла между двумя ориентациями. Угол между кватернионами — это угол поворота из q в q’ (по кратчайшей дуге).

Видео:Урок 3. Произведение векторов и загадочный угол между векторами. Высшая математика | TutorOnlineСкачать

Вращение 3d вектора

Вращение 3d вектора v кватернионом q определяется как

причем вектор конвертируется в кватернион как

и кватернион обратно в вектор как

Видео:Трехмерные линейные трансформации | Сущность Линейной Алгебры, примечаниеСкачать

Умножение кватернионов

Одна из самых полезных операций, она аналогична умножению двух матриц поворота. Итоговый кватернион представляет собой комбинацию вращений — сначала объект повернули на q, а затем на q’ (если смотреть из глобальной системы координат).

Примеры векторного и скалярного перемножения 2-х векторов векторное произведение — вектор: Скалярное произведение — число:

Пример умножения 2-х кватернионов:

Видео:#225. КВАТЕРНИОНЫ и углы ЭйлераСкачать

Конвертирование между кватернионом и Axis Angle представлением

В разделе Axis Angle представление вращения была сделана неудачная попытка объединить 3 Axis Angle представления в одно . Это можно сделать опосредовано. Сначала Axis Angle представления конвертируются в кватернионы, затем кватернионы перемножаются и результат конвертируется в Axis Angle представление.

Пример конвертирования произведения 2-х кватернионов в Axis Angle представление:

Фрагмент программы на C:

Видео:А.7.18 Вот: это поворот!!! (+ДЗ)Скачать

Конвертирование кватерниона в матрицу поворота

Матрица поворота выражается через компоненты кватерниона следующим способом:

где

Проверим формулы конвертирования на примере конвертирования произведения 2-х кватернионов в матрицу поворотов:

Определяем элемент матрицы m[0][0] через параметры кватерниона:

Соответствующее произведению кватернионов (q1 и q2) произведение матриц поворотов было получено ранее (см. Матрицы поворота и углы Эйлера):

Как видим, результат m[0][0], полученный через конвертирование, совпал с значением в матрице поворота.

Фрагмент программного кода на С для конвертирования кватерниона в матрицу поворота:

При конвертировании используется только умножения и сложения, что является несомненным преимуществом на современных процессорах.

Часто для задания вращений используют только кватернионы единичной длины, но это не обязательно и иногда даже не эффективно. Разница между конвертированием единичного и неединичного кватернионов составляет около 6-ти умножений и 3-х сложений, зато избавит во многих случаях от необходимости нормировать (приводить длину к 1) кватернион. Если кусок кода критичен по скорости и вы пользуетесь только кватернионами единичной длины тогда можно воспользоваться фактом что норма его равна 1.

Видео:Видеоурок "Преобразование координат"Скачать

Конвертирование матрицы поворота в кватернион

Конвертирование матрицы в кватернион выполняется не менее эффективно, чем кватерниона в матрицу, но в итоге мы получим кватернион неединичной длины. Его можно нормализовать.

Фрагмент программного кода конвертирования матрицы поворота в кватернион:

Видео:Разложение вектора по двум неколлинеарным векторам. Урок 4. Геометрия 9 классСкачать

Заметки о вращении вектора кватернионом

Структура публикации

• Получение кватерниона из вектора и величины угла разворота
• Обратный кватернион
• Умножение кватернионов
• Поворот вектора
• Рысканье, тангаж, крен
• Серия поворотов

Получение кватерниона из вектора и величины угла разворота

Ещё раз – что такое кватернион? Для разработчика – это прежде всего инструмент, описывающий действие – поворот вокруг оси на заданный угол:

где v – ось, выраженная вектором;
w – компонента, описывающая поворот (косинус половины угла).

Положительное значение угла разворота означает поворот вдоль вектора по часовой стрелке, если смотреть с конца вектора в его начало.

Например, кватернион поворота вдоль оси Х на 90 градусов имеет следующие значения своих компонент: w = 0,7071; x = 0,7071; y = 0; z = 0. Левая или правая система координат, разницы нет – главное, чтобы все операции выполнялись в одинаковых системах координат, или все в левых или все в правых.

С помощью следующего кода (под рукой был Visual Basic), мы можем получить кватернион из вектора и угла разворота вокруг него:

В коде rotate_vector – это вектор, описывающий ось разворота, а rotate_angle – это угол разворота в радианах. Вектор должен быть нормализован. То есть его длина должа быть равна 1.

Не забывайте про ситуацию, когда длина может быть 0. Вместо ошибки вам может понадобиться обработать эту ситуацию индивидуально.

Обратный кватернион

Для поворота вектора кватернионом требуется уметь делать обратный разворот и правильно выполнять операцию умножения кватернионов. Под обратным разворотом я имею ввиду обратный кватернион, т. е. тот, который вращает в обратную сторону.

Чтобы получить обратный кватернион от заданного, достаточно развернуть вектор оси в другую сторону и при необходимости нормализовать кватернион. Нормализация кватерниона так же как и в векторах, это просто приведение к длине = 1.

Например, если разворот вокруг оси Y на 90 градусов = (w=0,707; x = 0; y = 0,707; z=0), то обратный = (w=0,707; x = 0; y = -0,707; z=0). Казалось бы, можно инвертировать только компоненту W, но при поворотах на 180 градусов она = 0. Кватернион, который означает «нет разворота» = (w=1; x = 0; y = 0; z=0), то есть у него длина вектора оси = 0.

Умножение кватернионов

Умножение кватернионов крайне полезная штука. Результатом умножения является кватернион, который после поворота даёт такой же результат, если последовательно выполнить развороты умножаемыми кватернионами. Причём разворот будет происходить в локальной для поворачиваемого вектора системе отчёта, т. е. система отчёта поворачиваемого вектора также двигается.

Умножение кватернионов выполняется следующим образом:

Для того, чтобы умножить кватернион на 3D вектор, нужно вектор преобразовать в кватернион присвоив компоненте W = 0 и умножить кватернион на кватернион. Или подставить ноль и выразить это в виде функции:

Поворот вектора

Теперь, собственно, поворот вектора кватернионом:

Вектор описывающий ось (x=1; y=0; z=1). Угол поворота 180 градусов.
Поворачиваемый вектор (x=0; y=0; z=1). Результат равен (x=1; y=0; z=0).

Рысканье, тангаж, крен

Рассмотрим инструмент формирования кватерниона с помощью поворотов вокруг одной из осей:
Рысканье = heading = yaw = вокруг оси Z; тангаж = altitude = pitch = вокруг оси Y; крен = bank = roll = вокруг оси X.

И в обратную сторону, из кватерниона:

Формулы преобразования зависят от принятой системы координат.

Серия поворотов

Рассмотрим пример:
1. Первый поворот – рысканье (вокруг Z) 90 градусов по часовой;
2. Второй поворот – тангаж (вокруг Y) 90 градусов по часовой;
3. Третий поворот – крен (вокруг X) 90 градусов по часовой.

Рисунки, изображающие поворот и подписанные как «global» демонстрируют повороты относительно неподвижных осей XYZ. Такой результат мы получим, если будем использовать кватернионы разворота по отдельности. Четвёртый рисунок демонстрирует, где окажется вектор, если начальные координаты у него были X=1; Y=0; Z=0.

Рисунки, подписанные как «local» демонстрируют вращение осей вместе с самолетом. То есть все вращения происходят относительно пилота, а не относительно неподвижной системы координат. Четвёртый рисунок показывает, где окажется тот же самый вектор (1; 0; 0) в итоге всех трёх поворотов. Такой результат мы получим, перемножив кватернионы разворота и применив полученный кватернион.

Видео:A.7.28 Описание поворотов кватернионамиСкачать

Поворот вектора на углы

Видео:Разложение вектора по базису. 9 класс.Скачать

Вращение и кватернионы. Сборник рецептов.

Давайте коротко определимся с терминологией. Каждый представляет себе, что такое ориентация объекта. Термин «ориентация» подразумевает, что мы находимся в некоторой заданной системе отсчета. Например, фраза «он повернул голову влево» осмыслена только тогда, когда мы представляем, где находится «лево» и где находилась до этого голова. Это важный для понимания момент, ведь если бы это был монстр с головой на животе макушкой вниз то фраза «он повернул голову влево» уже не покажется такой однозначной.

Трансформацию, которая определенным образом вращает из одной ориентации в другую, назовем поворотом. С помощью поворота можно описать и ориентацию объекта, если ввести некую ориентацию по умолчанию как точку отсчета. Например, любой объект, описанный с помощью набора треугольников, уже имеет ориентацию по умолчанию. Координаты его вершин описываются в локальной системе координат этого объекта. Произвольную ориентацию этого объекта можно описать матрицей поворота относительно его локальной системы координат. Также можно выделить такое понятие как «вращение». Под вращением будем понимать изменение ориентации объекта заданным образом во времени. Чтобы однозначно задать вращение, надо, чтобы в любой момент времени мы могли определить точную ориентацию вращаемого объекта. Другими словами вращение задает «путь», пройденный объектом при изменении ориентации. В такой терминологии поворот не задает однозначного вращения объекта. Важно понимать что, к примеру, матрица не задает однозначного вращения тела, одну и ту же матрицу поворота можно получить, повернув объект на 180 градусов вокруг фиксированной оси и на 180 + 360 или 180 — 360. Эти термины я применяю для демонстрации различий в понятиях, и ни в коей мере не настаиваю на использовании. В дальнейшем оставлю за собой право говорить «матрицы вращения».

При слове ориентация часто возникают ассоциация с направлением. Часто можно услышать фразы подобные «он повернул голову в сторону приближающегося локомотива». Например, ориентацию автомобиля можно было бы описать направлением, в котором смотрят его фары. Однако направление задается двумя параметрами (например, как в сферической системе координат), а объекты в трехмерном пространстве имеют три степени свободы (вращения). В случае с автомобилем он может смотреть в одном направлении как стоя на колесах, так и лежа на боку или на крыше. Ориентацию действительно можно задать направлением, но их потребуется два. Давайте рассмотрим ориентацию на простом примере головы человека.

Договоримся про исходное положение, в котором голова ориентирована по умолчанию (без вращения). За исходное примем положение, в котором голова смотрит лицом по направлению оси «z», а вверх (макушкой) смотрит по направлению оси «y». Назовем направление, в котором повернуто лицо «dir» (без вращения совпадает с «z»), а направление, куда смотрит макушка «up» (без вращения совпадает с «y»). Теперь у нас есть точка отсчета, есть локальная координатная система головы «dir», «up» и глобальная с осями x, y, z. Произвольно повернем голову и отметим, куда смотрит лицо. Глядя в этом же направлении можно вращать голову вокруг оси, совпадающей с направлением взгляда «dir». Например, наклонив голову на бок (прижавшись щекой к плечу) мы будем смотреть в том же направлении, но ориентация головы поменяется. Чтобы зафиксировать поворот вокруг направления взгляда, используем еще и направление «up» (направленно к макушке). В этом случае мы однозначно описали ориентацию головы и не сможем ее повернуть, не изменив направления осей «dir» и «up».

Мы рассмотрели достаточно естественный и простой способ задания ориентации с помощью двух направлений. Как же описать наши направления в программе, чтобы ими было удобно пользоваться? Простой и привычный способ хранить эти направления в виде векторов. Опишем направления с помощью векторов длиной в единицу (единичных векторов) в нашей глобальной системе координат xyz. Первый важный вопрос, как бы наши направления передать в понятном виде графическому API? Графические API работают в основном с матрицами. Нам бы хотелось получить матрицу поворота из имеющихся векторов. Два вектора описывающие направление «dir» и «up» и есть та самая матрица поворота, а точнее два компонента матрицы поворота 3×3. Третий компонент матрицы мы можем получить из векторного произведения векторов «dir» и «up» (назовем его «side»). В примере с головой вектор «side» будет смотреть в направлении одного из ушей. Матрица поворота это и есть координаты трех векторов «dir», «up» и «side» после поворота. Эти вектора до поворота совпадали с осями глобальной системы координат xyz. Именно в виде матрицы поворота очень часто и хранят ориентацию объектов (иногда матрицу хранят в виде трех векторов). Матрицей можно задать ориентацию (если известна ориентация по умолчанию) и поворот.

Похожий способ представления ориентации, называется углы Эйлера (Euler Angles), с тем лишь отличием, что направление «dir» задается в сферических координатах, а «up» описывается одним углом поворота вокруг «dir». В итоге получим три угла вращения вокруг взаимно перпендикулярных осей. В аэродинамике их называют Крен, Тангаж, Рысканье (Roll, Pitch, Yaw или Bank, Heading, Attitude). Крен (Roll) — это наклон головы вправо или влево (к плечам), поворот вокруг оси проходящей через нос и затылок. Тангаж (Pitch) — это наклон головы вверх и вниз, вокруг оси проходящей через уши. И Рысканье (Yaw) — это повороты головы вокруг шеи. Надо помнить, что повороты в трехмерном пространстве не коммутативны, а значит, на результат влияет порядок поворотов. Если мы повернем на R1 а потом на R2, ориентация объекта не обязательно совпадет с ориентацией при повороте на R2 и затем на R1. Именно поэтому при использовании Углов Эйлера важен порядок поворотов вокруг осей. Обратите внимание, что математика углов Эйлера зависит от выбранных осей (мы использовали только один из возможных вариантов), от порядка поворота вокруг них, а также от того в какой системе координат совершаются повороты, в мировой или локальной объекта. В углах Эйлера можно хранить и вращение и поворот.

Огромный недостаток такого представления, отсутствие операции комбинации поворота. Не пытайтесь складывать покомпонентно углы Эйлера. Итоговый поворот не будет комбинацией исходных поворотов. Это одна из самых распространенных ошибок начинающих разработчиков. Чтобы повернуть объект, храня вращение в углах Эйлера, нам придется перевести вращение в другую форму, например в матрицу. Затем перемножить матрицы двух поворотов и из итоговой матрицы извлечь углы Эйлера. Проблема усложняется еще и тем что в частных случаях прямое сложение углов Эйлера работает. В случае комбинации вращений вокруг одной и той же оси, этот метод математически верен. Повернув на 30 градусов вокруг оси X, а затем еще раз вокруг X на 40 градусов мы получим поворот вокруг X на 70 градусов. В случае вращений по двум осям простое сложение углов может давать некий «ожидаемый» результат. Но как только появляется поворот по третьей оси, ориентация начинает вести себя непредсказуемо. Многие разработчики тратят месяцы труда чтобы заставить работать камеру «правильно». Рекомендую обратить пристальное внимание к этому недостатку, особенно если вы уже решили использовать углы Эйлера для представления вращений. Начинающим программистам кажется что, использовать углы Эйлера проще всего. Позволю себе высказать личное мнение, что математика углов Эйлера намного сложнее и коварнее чем математика кватернионов.

Углы Эйлера это комбинация (композиция) вращений вокруг базовых осей. Существует еще один, простой, способ задания вращения. Этот способ можно назвать «смесь» вращений вокруг базовых координатных осей, или просто вращение вокруг произвольной фиксированной оси. Три компоненты описывающие вращение образуют вектор, лежащий на оси, вокруг которой и поворачивается объект. Обычно хранят ось вращения в виде единичного вектора и угол поворота вокруг этой оси в радианах или градусах (Axis Angle). Выбрав подходящую ось и угол можно задать любую ориентацию объекта. В некоторых случаях удобно хранить угол вращения и ось в одном векторе. Направление вектора в этом случае совпадает с направлением оси вращения, а длина его равна углу поворота. В физике, таким образом, хранят угловую скорость. Вектор, совпадающий направлением с осью вращения и длиной представляющей скорость в радианах в секунду.

Видео:#193 ПОВОРОТЫ ВЕКТОРОВ // ПАРАЛЛЕЛОГРАММСкачать

Кватернион

После краткого обзора о представлениях ориентации можно перейти к знакомству с кватернионом.

Кватернион — это четверка чисел, которые ввел в обращение (как считают историки) Уильям Гамильтон в виде гиперкомплексного числа. В этой статье я предлагаю рассматривать кватернион как четыре действительных числа, например как 4d вектор или 3d вектор и скаляр.

Существуют и другие представления кватерниона, которые я не буду рассматривать.
Как же хранят вращение в кватернионе? Практически также как и в «Axis Angle» представлении, первые три компонента представляют вектор, лежащий на оси вращения, причем длина вектора зависит от угла поворота. Четвертый компонент зависит только от величины угла поворота. Зависимость довольно простая — если взять единичный вектор V за ось вращения и угол alpha за вращение вокруг этой оси, тогда кватернион представляющий это вращение
можно записать как:

Для понимания того, как хранит вращение кватернион, вспомним про двумерные вращения. Вращение в плоскости можно задать матрицей 2×2, в которой будут записаны косинусы и синусы угла поворота. Можно представить, что кватернион хранит комбинацию оси вращения и матрицы половины поворота вокруг этой оси.

Видео:РАЗЛОЖЕНИЕ ВЕКТОРА ПО ДВУМ неколлинеарным ВЕКТОРАМ 9 классСкачать

Матрицы поворота, углы Эйлера и кватернионы (Rotation matrices, Euler angles and quaternions)

Объект обычно определяется в удобной для его описания локальной системе координат (ЛСК), а его положение в пространстве — в глобальной системе координат (ГСК).

В трёхмерном пространстве переход из одной СК в другую описывается в общем случае системой линейных уравнений:

Уравнения могут быть записаны через матрицы аффинных преобразований в однородных координатах одним из 2-х способов:

В ортогональных СК оси X, Y и Z взаимно перпендикулярны и расположены по правилу правой руки:

На рисунке справа большой палец определяет направление оси, остальные пальцы — положительное направление вращения относительно этой оси.

Все три вектора направлений есть единичными.

Ниже приводится единичная матрица для 2-х способов записи уравнений геометрических преобразований. Такая матрица не описывает ни перемещения, ни вращения. Оси ЛСК и ГСК совпадают.

Далее рассматривается матрица для второго способа матричной записи уравнений (матрица справа). Этот способ встречается в статьях значительно чаще.

При использовании матрицы вы можете игнорировать нижнюю строку. В ней всегда хранятся одни и те же значения 0, 0, 0, 1. Она добавлена для того, чтобы мы могли перемножать матрицы (напомню правило перемножения матриц и отмечу, что всегда можно перемножать квадратные матрицы). Подробнее см. Композиция матриц. Однородные координаты.

Остальные 12 значений определяют координатную систему. Первый столбец описывает компоненты направления оси X(1,0,0). Второй столбец задает направление оси Y(0,1,0), третий – оси Z (0,0,1). Последний столбец определяет положение начала системы координат (0,0,0).

Как будет выглядеть матрица Евклидового преобразования (преобразование движения) для задания ЛСК , с началом в точке (10,5,0) и повёрнутой на 45° вокруг оси Z глобальной СК, показано на рисунке.

Рассмотрим сначала ось X. Если новая система координат повернута на 45° вокруг оси z, значит и ось x повернута относительно базовой оси X на 45° в положительном направлении отсчета углов. Таким образом, ось X направлена вдоль вектора (1, 1, 0), но поскольку вектор системы координат должен быть единичным, то результат должен выглядеть так (0.707, 0.707, 0). Соответственно, ось Y имеет отрицательную компоненту по X и положительную по Y и будет выглядеть следующим образом (-0.707, 0.707, 0). Ось Z направления не меняет (0, 0, 1). Наконец, в четвертом столбце вписываются координаты точки начала системы координат (10, 5, 0).

Частным случаем матриц геометрических преобразований есть матрицы поворота ЛСК относительно базовых осей ГСК. Вектора осей ЛСК здесь выражены через синусы и косинусы углов вращения относительно оси, перпендикулярной к плоскости вращения.

От матрицы преобразований размером 4*4 можно перейти непосредственно к матрице поворота 3*3, убрав нижний ряд и правый столбец. При этом, система линейных уравнений записывается без свободных элементов (лямда, мю, ню), которые определяют перемещение вдоль осей координат.

Путем перемножения базовых матриц можно получать комбинированные вращения. Ниже рассмотрены возможности комбинировать вращениями через матрицы поворота на примерах работы с углами Эйлера.

Матрицы поворота и углы Эйлера

От выбора осей и последовательности вращения зависит конечный результат. На рисунках отображена следующая последовательность вращения относительно осей ЛСК:

• оси Z (угол alpha);
• оси X (угол beta);
• оси Z (угол gamma).

Получил от читателя этой статьи вопрос: «Как понять, из каких углов поворота вокруг осей X,Y,Z можно получить текущее положение объекта, когда в качестве задания мы уже имеем повернутый объект, а нужно вывести его в это положение, последовательно повернув его из какого-то начального положения до полного совмещения с заданным?»

Мой ответ: «Если я правильно понял вопрос, то Вас интересует, как от начального положения перейти к заданному положению объекта, используя для этого элементарные базовые аффинные преобразования.

Начну с аналогии. Это как в шахматах. Мы знаем как ходит конь. Необходимо переместить его в результате многоходовки в нужную клетку на доске — при условии, что это возможно.

Подробно эта проблематика рассмотрена в статье Преобразование координат при калибровке роботов.

Умение правильно выбирать последовательность элементарных геометрических преобразований помогает в решении множества других задач (см. Примеры геометрических преобразований).»

Можно получить результирующую матрицу, которая определяет положение ГСК относительно ЛСК. Для этого необходимо перемножить матрицы с отрицательными углами в последовательности выполнения поворотов:

Почему знак угла поворота меняется на противоположный? Объяснение этому простое. Движение относительно. Абстрагируемся и представим, что ГСК меняет положение относительно неподвижной ЛСК. При этом направление вращения меняется на противоположное.

Перемножение матриц даст следующий результат:

Результирующую матрицу можно использовать для пересчета координат из ГСК в ЛСК:

Для пересчета координат из ЛСК в ГСК используется результирующая обратная матрица.

В обратной матрице последовательность поворота и знаки углов меняются на противоположные (в рассматриваемом примере снова на положительные) по сравнению с матрицей определения положения ГСК относительно ЛСК.

Перемножение матриц даст следующий результат:

Выше был рассмотрен случай определения углов Эйлера через вращение относительно осей ЛСК. То же взаимное положение СК можно получить, выполняя вращение относительно осей ГСК:

• оси z (угол (gamma+pi/2));
• оси y (угол угол beta);
• оси z (угол (-alpha)).

Определение углов Эйлера через вращение относительно осей ГСК позволяет также просто получить зависимости для пересчета координат из ЛСК в ГСК через перемножение матриц поворота.

В рамках рассматриваемой задачи вместо угла gamma в матрицe Az используем угол gamma+pi/2.

Также легко можно перейти к зависимостям для пересчета координат из ГСК в ЛСК.

Обратная матрица получается перемножением обратных матриц в обратном порядке по сравнению с прямым преобразованием. При этом каждая из обратных матриц вращения может быть получена заменой знака угла на противоположный.

Детально с теоретическими основами аффинных преобразований (включая и вращение) можно ознакомиться в статье Геометрические преобразования в графических приложениях

Примеры преобразований рассмотрены в статьях:

Axis Angle представление вращения

Выбрав подходящую ось (англ. rotation axis) и угол (англ. rotation angle) можно задать любую ориентацию объекта.

Обычно хранят ось вращения в виде единичного вектора и угол поворота вокруг этой оси в радианах или градусах.

q = [ x, y, z, w ] = [ v, w ]

В некоторых случаях удобно хранить угол вращения и ось в одном векторе. Направление вектора при этом совпадает с направлением оси вращения, а его длина равна углу поворота:

q = [ x, y, z]; w=sqrt (x*x +y*y +z*z)

В физике, таким образом хранят угловую скорость. Направление вектора совпадает с направлением оси вращения, а длина вектора равна скорости (в радианах в секунду).

Можно описать рассмотренные выше углы Эйлера через Axis Angle представление в 3 этапа:

q1 = [ 0, 0, 1, alpha]; q2 = [ 1, 0, 0, beta]; q3 = [ 0, 0, 1, gamma ]

Здесь каждое вращение выполняется относительно осей текущего положения ЛСК. Такое преобразование равнозначно рассмотренному выше преобразованию через матрицы поворота:

Возникает вопрос, а можно ли 3 этапа Axis Angle представления объединить в одно, подобно матрицам поворота? Попробуем решить геометрическую задачу по определению координат последнего вектора вращения в последовательности преобразований через Axis Angle представления:

q = [ x, y, z, gamma ]

Есть ли представление q= [x, y, z, gamma] композицией последовательности из 3-х этапов преобразований? Нет! Координаты x, y, z определяют всего лишь положение оси Z ЛСК после первого и второго этапов преобразований:

При этом ось Z, отнюдь, не есть вектор вращения для Axis Angle представления, которое могло бы заменить рассмотренные 3-х этапа преобразований.

Еще раз сформулирую задачу, которая математически пока не решена: «Необходимо найти значение угла (rotation angle) и положение оси (rotation axis), вращением относительно которой на этот угол можно заменить комбинацию из 3-х поворотов Эйлера вокруг осей координат».

К сожалению, никакие операции (типа объединения нескольких преобразований в одно) с Axis Angle представлениями нельзя выполнить. Не будем расстраиваться. Это можно сделать через кватернионы, которые также определяют вращение через параметры оси и угол.

Кватернионы

Кватернион (как это и видно по названию) представляет собой набор из четырёх параметров, которые определяют вектор и угол вращения вокруг этого вектора. По сути такое определение ничем не отличается от Axis Angle представления вращения. Отличия лишь в способе представления. Как же хранят вращение в кватернионе?

q = [ V*sin(alpha/2), cos(alpha/2) ]

В кватернионе параметры единичного вектора умножается на синус половины угла поворота. Четвертый компонент — косинус половины угла поворота.

Таблица с примерами значений кватернионов:

Представление вращения кватернионом кажется необычным по сравнению с Axis Angle представлением. Почему параметры вектора умножаются на синус половины угла вращения, четвертый параметр — косинус половины угла вращения, а не просто угол?

Откуда получено такое необычное представление кватерниона детально можно ознакомиться в статье Доступно о кватернионах и их преимуществах. Хотя программисту не обязательно знать эти детали, точно также как и знать, каким образом получены матрицы преобразования пространства. Достаточно лишь знать основные операции с кватернионами, их смысл и правила применения.

Основные операции над кватернионами

Кватернион удобно рассматривать как 4d вектор, и некоторые операции с ним выполняются как над векторами.

Сложение, вычитание и умножение на скаляр.

Смысл операции сложения можно описать как «смесь» вращений, т.е. мы получим вращение, которое находится между q и q’.

Что-то подобное сложению кватернионов выполнялось при неудачной попытке объединить 3 этапа Axis Angle представления.

Умножение на скаляр на вращении не отражается. Кватернион, умноженный на скаляр, представляет то же самое вращение, кроме случая умножения на 0. При умножении на 0 мы получим «неопределенное» вращение.

Пример сложения 2-х кватернионов:

Норма и модуль

Следует различать (а путают их часто) эти две операции:

Модуль (magnitude), или как иногда говорят «длина» кватерниона:

Через модуль кватернион можно нормализовать. Нормализация кватерниона — это приведение к длине = 1 (так же как и в векторах):

Обратный кватернион или сопряжение ( conjugate )

Обратный кватернион задает вращение, обратное данному. Чтобы получить обратный кватернион достаточно развернуть вектор оси в другую сторону и при необходимости нормализовать кватернион.

Например, если разворот вокруг оси Y на 90 градусов = (w=0,707; x = 0; y = 0,707; z=0), то обратный = (w=0,707; x = 0; y = -0,707; z=0).

Казалось бы, можно инвертировать только компоненту W, но при поворотах на 180 кватернион представляется как (w=1; x = 0; y = 0; z=0), то есть, у него длина вектора оси = 0.

Фрагмент программной реализации:

Инверсный (inverse) кватернион

Существует такой кватернион, при умножении на который произведение дает нулевое вращение и соответствующее тождественному кватерниону (identity quaternion), и определяется как:

Тождественный кватернион

Записывается как q[0, 0, 0, 1]. Он описывает нулевой поворот (по аналогии с единичной матрицей), и не изменяет другой кватернион при умножении.

Скалярное произведение

Скалярное произведение полезно тем, что дает косинус половины угла между двумя кватернионами, умноженный на их длину. Соответственно, скалярное произведение двух единичных кватернионов даст косинус половины угла между двумя ориентациями. Угол между кватернионами — это угол поворота из q в q’ (по кратчайшей дуге).

Вращение 3d вектора

Вращение 3d вектора v кватернионом q определяется как

причем вектор конвертируется в кватернион как

и кватернион обратно в вектор как

Умножение кватернионов

Одна из самых полезных операций, она аналогична умножению двух матриц поворота. Итоговый кватернион представляет собой комбинацию вращений — сначала объект повернули на q, а затем на q’ (если смотреть из глобальной системы координат).

Примеры векторного и скалярного перемножения 2-х векторов векторное произведение — вектор: Скалярное произведение — число:

Пример умножения 2-х кватернионов:

Конвертирование между кватернионом и Axis Angle представлением

В разделе Axis Angle представление вращения была сделана неудачная попытка объединить 3 Axis Angle представления в одно . Это можно сделать опосредовано. Сначала Axis Angle представления конвертируются в кватернионы, затем кватернионы перемножаются и результат конвертируется в Axis Angle представление.

Пример конвертирования произведения 2-х кватернионов в Axis Angle представление:

Фрагмент программы на C:

Конвертирование кватерниона в матрицу поворота

Матрица поворота выражается через компоненты кватерниона следующим способом:

где

Проверим формулы конвертирования на примере конвертирования произведения 2-х кватернионов в матрицу поворотов:

Определяем элемент матрицы m[0][0] через параметры кватерниона:

Соответствующее произведению кватернионов (q1 и q2) произведение матриц поворотов было получено ранее (см. Матрицы поворота и углы Эйлера):

Как видим, результат m[0][0], полученный через конвертирование, совпал с значением в матрице поворота.

Фрагмент программного кода на С для конвертирования кватерниона в матрицу поворота:

При конвертировании используется только умножения и сложения, что является несомненным преимуществом на современных процессорах.

Часто для задания вращений используют только кватернионы единичной длины, но это не обязательно и иногда даже не эффективно. Разница между конвертированием единичного и неединичного кватернионов составляет около 6-ти умножений и 3-х сложений, зато избавит во многих случаях от необходимости нормировать (приводить длину к 1) кватернион. Если кусок кода критичен по скорости и вы пользуетесь только кватернионами единичной длины тогда можно воспользоваться фактом что норма его равна 1.

Конвертирование матрицы поворота в кватернион

Конвертирование матрицы в кватернион выполняется не менее эффективно, чем кватерниона в матрицу, но в итоге мы получим кватернион неединичной длины. Его можно нормализовать.

Фрагмент программного кода конвертирования матрицы поворота в кватернион:

Основы компьютерной геометрии. Написание простого 3D-рендера

Привет меня зовут Давид, а вот я собственной персоной отрендеренный своим самописным рендером:

С развитием шейдерных языков и увеличением мощностей GPU все больше людей заинтересовались программированием графики. Появились новые направления, такие как например Ray marching со стремительным ростом своей популярности.

В преддверии выхода нового монстра от NVidia я решил написать свою (ламповую и олдскульную) статью про основы рендеринга на CPU. Она является отражением моего личного опыта написания рендера, и в ней я попытаюсь довести понятия и алгоритмы с которыми я столкнулся в процессе кодинга. Стоит понимать, что производительность данного софта будет весьма низкая в силу непригодности процессора для выполнения подобных задач.

Выбор языка изначально падал на c++ или rust, но я остановился на c# из-за простоты написания кода и широких возможностей для оптимизации. Итоговым продуктом данной статьи будет рендер, способный выдавать подобные картинки:

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

Математика

Само собой куда же писать рендеры без понимания их математических основ. В этом разделе я изложу только те концепции, которые я использовал в коде. Тем кто не уверен в своих знаниях пропускать данный раздел не советую, без понимания этих основ трудно будет понять дальнейшее изложение. Так же я рассчитываю, что тот кто решил изучать computation geometry будет иметь базовые знания в линейной алгебре, геометрии, а так же тригонометрии(углы, вектора, матрицы, скалярное произведение). Для тех кто хочет понять вычислительную геометрию глубже, могу порекомендовать книгу Е. Никулина «Компьютерная геометрия и алгоритмы машинной графики».

Повороты вектора. Матрица поворота

Поворот — это одно из основных линейных преобразований векторного пространства. Так же оно является еще и ортогональным преобразованием, так как сохраняет длины преобразованных векторов. В двумерном пространстве существует два типа поворотов:

• Поворот относительно начала координат
• Поворот относительно некоторой точки

Здесь я рассмотрю только первый тип, т.к. второй является производным от первого и отличается лишь сменой системы координат вращения (системы координат мы разберем далее).

Давайте выведем формулы для вращения вектора в двумерном пространстве. Обозначим координаты исходного вектора — . Координаты нового вектора, повернутого на угол f, обозначим как .

Мы знаем, что длина у этих векторов общая и поэтому можем использовать понятия косинуса и синуса для того, чтобы выразить эти вектора через длину и угол относительно оси OX:

Заметьте, что мы можем использовать формулы косинуса и синуса суммы для того, чтобы разложить значения x’ и y’. Для тех, кто подзабыл я напомню эти формулы:

Разложив координаты повернутого вектора через них получим:

Здесь нетрудно заметить, что множители l * cos a и l * sin a – это координаты исходного вектора: x = l * cos a, y = l * sin a. Заменим их на x и y:

Таким образом мы выразили повернутый вектор через координаты исходного вектора и угол его поворота. В виде матрицы это выражение будет выглядеть так:

Умножьте и проверьте что результат эквивалентен тому, что мы вывели.

Поворот в трехмерном пространстве

Мы рассмотрели поворот в двумерном пространстве, а так же вывели матрицу для него. Теперь возникает вопрос, а как получить подобные преобразования для трех измерений? В двумерном случае мы вращали вектора на плоскости, здесь же бесконечное количество плоскостей относительно которых мы можем это сделать. Однако существует три базовых типа вращений, при помощи которых можно выразить любой поворот вектора в трехмерном пространстве — это XY, XZ, YZ вращения.

При таком повороте мы вращаем вектор относительно оси OZ координатной системы. Представьте, что вектора — это вертолётные лопасти, а ось OZ — это мачта на которой они держаться. При XY вращении вектора будут поворачиваться относительно оси OZ, как лопасти вертолета относительно мачты.

Заметьте, что при таком вращении z координаты векторов не меняются, а меняются x и x координаты — поэтому это и называется XY вращением.

Нетрудно вывести и формулы для такого вращения: z — координата остается прежней, а x и y изменяются по тем же принципам, что и в 2д вращении.

То же в виде матрицы:

Для XZ и YZ вращений все аналогично:

Проекция

Понятие проекции может варьироваться в зависимости от контекста в котором его используют. Многие, наверное, слышали про такие понятия, как проекция на плоскость или проекция на координатную ось.

В том понимании которое мы используем здесь проекция на вектор — это тоже вектор. Его координаты – точка пересечения перпендикуляра опущенного из вектора a на b с вектором b.

Для задания такого вектора нам нужно знать его длину и направление. Как мы знаем прилегающий катет и гипотенуза в прямоугольном треугольнике связаны отношением косинуса, поэтому используем его, чтобы выразить длину вектора проекции:

Направление вектора проекции по определению совпадает с вектором b, значит проекция определяется формулой:

Здесь мы получаем направление проекции в виде единичного вектора и умножаем его на длину проекции. Несложно понять, что результатом будет как раз-таки то, что мы ищем.

Теперь представим все через скалярное произведение:

Получаем удобную формулу для нахождения проекции:

Системы координат. Базисы

Многие привыкли работать в стандартной системе координат XYZ, в ней любые 2 оси будут перпендикулярны друг другу, а координатные оси можно представить в виде единичных векторов:

На деле же систем координат бесконечное множество, каждая из них является базисом. Базис n-мерного пространства является набором векторов через которые представляются все вектора этого пространства. При этом ни один вектор из базиса нельзя представить через другие его вектора. По сути каждый базис является отдельной системой координат, в которой вектора будут иметь свои, уникальные координаты.

Давайте разберем, что из себя представляет базис для двумерного пространства. Возьмём для примера всем знакомую декартову систему координат из векторов X , Y , которая является одним из базисов для двумерного пространства:

Любой вектор на плоскости можно представить в виде суммы векторов этого базиса с некими коэффициентами или же в виде линейной комбинации. Вспомните, что вы делаете когда записываете координаты вектора — вы пишете x — координату, а далее — y. Таким образом вы на самом деле определяете коэффициенты разложения по векторам базиса.

Теперь возьмём другой базис:

Через его вектора также можно представить любой 2д вектор:

А вот такой набор векторов не является базисом двухмерного пространства:

В нем два вектора и лежат на одной прямой. Какие бы их комбинации вы не брали получать будете только вектора, лежащие на общей прямой y = x. Для наших целей такие дефектные не пригодятся, однако, понимать разницу, я считаю, стоит. По определению все базисы объединяет одно свойство – ни один из векторов базиса нельзя представить в виде суммы других векторов базиса с коэффициентами или же ни один вектор базиса не является линейной комбинацией других. Вот пример набора из 3-х векторов который так же не является базисом:

Через него можно выразить любой вектор двумерной плоскости, однако вектор в нем является лишним так как сам может быть выражен через вектора и как + .

Вообще любой базис n-мерного пространства будет содержать ровно n векторов, для 2д это n соответственно равно 2.

Перейдем к 3д. Трехмерный базис будет содержать в себе 3 вектора:

Если для двумерного базиса достаточно было двух векторов не лежащих на одной прямой, то в трехмерном пространстве набор векторов будет базисом если:

• 1)2 вектора не лежат на одной прямой
• 2)3-й не лежит на плоскости образованной двумя другими.

С данного момента базисы, с которыми мы работаем будут ортогональными (любые их вектора перпендикулярны) и нормированными (длина любого вектора базиса — 1). Другие нам просто не понадобятся. К примеру стандартный базис

удовлетворяет этим критериям.

Переход в другой базис

До сих пор мы записывали разложение вектора как сумму векторов базиса с коэффициентами:

Снова рассмотрим стандартный базис – вектор в нем можно записать так:

Как видите коэффициенты разложения вектора в базисе являются его координатами в этом базисе. Разберем следующий пример:

Этот базис получен из стандартного применением к нему XY вращения на 45 градусов. Возьмем вектор a в стандартной системе имеющий координаты

Через вектора нового базиса его можно разложить таким образом:

Если вы посчитаете эту сумму, то получите – вектор а в стандартном базисе. Исходя из этого выражения в новом базисе вектор а имеет координаты – коэффициенты разложения. Это будет виднее если взглянуть с другого ракурса:

Но как находить эти коэффициенты? Вообще универсальный метод — это решение довольно сложной системы линейных уравнений. Однако как я сказал ранее использовать мы будем только ортогональные и нормированные базисы, а для них есть весьма читерский способ. Заключается он в нахождении проекций на вектора базиса. Давайте с его помощью найдем разложение вектора a в базисе X Y Z

Для начала найдем коэффициент для y’. Первым шагом мы находим проекцию вектора a на вектор y’ (как это делать я разбирал выше):

Второй шаг: делим длину найденной проекции на длину вектора y’, тем самым мы узнаем “сколько векторов y’ помещается в векторе проекции” – это число и будет коэффициентом для y’, а также y — координатой вектора a в новом базисе! Для x’ и z’ повторим аналогичные операции:

Теперь мы имеем формулы для перехода из стандартного базиса в новый:

Ну а так как мы используем только нормированные базисы и длины их векторов равны 1 отпадет необходимость делить на длину вектора в формуле перехода:

Раскроем x-координату через формулу проекции:

Заметьте, что знаменатель (x’, x’) и вектор x’ в случае нормированного базиса так же равен 1 и их можно отбросить. Получим:

Мы видим, что координата x базисе выражается как скалярное произведение (a, x’), координата y соответственно – как (a, y’), координата z – (a, z’). Теперь можно составить матрицу перехода к новым координатам:

Системы координат со смещенным центром

У всех систем координат которые мы рассмотрели выше началом координат была точка . Помимо этого существуют еще системы со смещенной точкой начала координат:

Для того, чтобы перевести вектор в такую систему нужно сначала выразить его относительно нового центра координат. Сделать это просто — вычесть из вектора этот центр. Таким образом вы как бы «передвигаете» саму систему координат к новому центу, при этом вектор остается на месте. Далее можно использовать уже знакомую нам матрицу перехода.

Пишем геометрический движок. Создание проволочного рендера.

Ну вот, думаю тому кто прошел раздел с математикой и не закрыл статью можно промывать мозги более интересными вещами! В этом разделе мы начнем писать основы 3д движка и рендеринга. Вообще рендеринг — это довольно сложная процедура, которая включает в себя много разных операций: отсечение невидимых граней, растеризация, расчет света, обработку различных эффектов, материалов(иногда даже физику). Все это мы частично разберем в дальнейшем, а сейчас мы займемся более простыми вещами — напишем проволочный рендер. Суть его в том, что он рисует объект в виде линий, соединяющих его вершины, поэтому результат выглядит похожим на сеть из проволок:

Полигональная графика

Традиционно в компьютерной графике используется полигональное представление данных трехмерных объектов. Таким образом представляются данные в форматах OBJ, 3DS, FBX и многих других. В компьютере такие данные хранятся в виде двух множеств: множество вершин и множество граней(полигонов). Каждая вершина объекта представлена своей позицией в пространстве — вектором, а каждая грань(полигон) представлена тройкой целых чисел которые являются индексами вершин данного объекта. Простейшие объекты(кубы, сферы и т.д.) состоят из таких полигонов и называются примитивами.

В нашем движке примитив будет основным объектом трехмерной геометрии — все остальные объекты будут наследоваться от него. Опишем класс примитива:

Пока все просто — есть вершины примитива и есть индексы для формирования полигонов. Теперь можно использовать этот класс чтобы создать куб:

Реализуем системы координат

Мало задать объект набором полигонов, для планирования и создания сложных сцен необходимо расположить объекты в разных местах, поворачивать их, уменьшать или увеличивать их в размере. Для удобства этих операций используются так называемые локальные и глобальная системы координат. Каждый объект на сцене имеет свои свою собственную систему координат — локальную, а так же собственную точку центра.

Представление объекта в локальных координатах позволяет легко производить любые операции с ним. Например, для перемещения объекта на вектор a достаточно будет сдвинуть центр его системы координат на этот вектор, для вращения объекта — повернуть его локальные координаты.

При работе с объектом мы будем производить операции с его вершинами в локальной системе координат, при рендеринге будем предварительно переводить все объекты сцены в единую систему координат — глобальную. Добавим системы координат в код. Для этого создадим объект класса Pivot (стержень, точка опоры) который будет представлять локальный базис объекта и его центральную точку. Перевод точки в систему координат представленную Pivot будет производиться в 2 шага:

• 1)Представление точки относительно центра новых координат
• 2)Разложение по векторам нового базиса

Наоборот же, чтобы представить локальную вершину объекта в глобальных координатах необходимо выполнить эти действия в обратном порядке:

• 1)Разложение по векторам глобального базиса
• 2)Представление относительно глобального центра

Напишем класс для представления систем координат:

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

Вращение и перемещение объекта с помощью локальных координат

Рисование полигонов. Камера

Основным объектом сцены будет камера — с помощью нее объекты будут рисоваться на экране. Камера, как и все объекты сцены, будет иметь локальные координаты в виде объекта класса Pivot — через него мы будем двигать и вращать камеру:

Для отображения объекта на экране будем использовать немудреный способ перспективной проекции. Принцип на котором основан этом метод заключается в том, что чем дальше от нас расположен объект тем меньше он будет казаться. Наверное многие решали когда-то в школе задачу про измерение высоты дерева находящимся на некотором расстоянии от наблюдателя:

Представьте, что луч от верхней точки дерева падает на некую проекционную плоскость находящуюся на расстоянии C1 от наблюдателя и рисует на ней точку. Наблюдатель видит эту точку и хочет по ней определить высоту дерева. Как вы могли заметить высота дерева и высота точки на проекционной плоскости связанны отношением подобных треугольников. Тогда наблюдатель может определить высоту точки используя это отношение:

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

Теперь вернемся к нашей камере. Представьте, что к оси z координат камеры прикреплена проекционная плоскость на расстоянии z’ от начала координат. Формула такой плоскости z = z’, ее можно задать одним числом — z’. На эту плоскость падают лучи от вершин различных объектов. Попадая на плоскость луч будет оставлять на ней точку. Соединяя такие точки можно нарисовать объект.

Такая плоскость будет представлять экран. Координату проекции вершины объекта на экран будем находить в 2 этапа:

• 1)Переводим вершину в локальные координаты камеры
• 2)Находим проекцию точки через отношение подобных треугольников

Проекция будет 2-мерным вектором, ее координаты x’ и y’ и будут определять позицию точки на экране компьютера.

Данный код имеет несколько ошибок, о исправлении которых мы поговорим далее.

Отсекаем невидимые полигоны

Спроецировав таким образом на экран три точки полигона мы получим координаты треугольника который соответствует отображению полигона на экране. Но таким образом камера будет обрабатывать любые вершины, включая те, чьи проекции выходят за область экрана, если попытаться нарисовать такую вершину велика вероятность словить ошибок. Камера так же будет обрабатывать полигоны которые находятся позади нее (координаты z их точек в локальном базисе камеры меньше z’) — такое «затылковое» зрение нам тоже ни к чему.

Для отсечения невидимых вершин в open gl используются метод усекающей пирамиды. Заключается он в задании двух плоскостей — ближней(near plane) и дальней(far plane). Все, что лежит между этими двумя плоскостями будет подлежать дальнейшей обработке. Я же использую упрощенный вариант с одной усекающей плоскостью — z’. Все вершины, лежащие позади нее будут невидимыми.

Добавим в камеру два новых поля — ширину и высоту экрана.
Теперь каждую спроецированную точку будем проверять на попадание в область экрана. Так же отсечем точки позади камеры. Если точка лежит сзади или ее проекция не попадает на экран то метод вернет точку .

Переводим в экранные координаты

Здесь я разъясню некоторый момент. Cвязан он с тем, что во многих графических библиотеках рисование происходит в экранной системе координат, в таких координатах начало — это верхняя левая точка экрана, x увеличивается при движении вправо, а y — при движении вниз. В нашей проекционной плоскости точки представлены в обычных декартовых координатах и перед отрисовкой необходимо переводить эти координаты в экранные. Сделать это нетрудно, нужно только сместить начало координат в верхний левый угол и инвертировать y:

Корректируем размер спроецированного изображения

Если вы используете предыдущий код для того, чтобы нарисовать объект то получите что-то вроде этого:

Почему — то все объекты рисуются очень маленькими. Для того, чтобы понять причину вспомните как мы вычисляли проекцию — умножали x и y координаты на дельту отношения z’ / z. Это значит, что размер объекта на экране зависит от расстояния до проекционной плоскости z’. А ведь z’ мы можем задать сколь угодно маленьким значением. Значит нам нужно корректировать размер проекции в зависимости от текущего значения z’. Для этого добавим в камеру еще одно поле — угол ее обзора.

Он нам нужен для сопоставления углового размера экрана с его шириной. Угол будет сопоставлен с шириной экрана таким образом: максимальный угол в пределах которого смотрит камера — это левый или правый край экрана. Тогда максимальный угол от оси z камеры составляет o / 2. Проекция, которая попала на правый край экрана должна иметь координату x = width / 2, а на левый: x = -width / 2. Зная это выведем формулу для нахождения коэффициента растяжения проекции:

Вот такой простой код отрисовки я использовал для теста:

Давайте проверим рендер на сцене и кубов:

И да, все прекрасно работает. Для тех, кому разноцветные кубики не кажутся пафосными я написал функцию парсинга моделей формата OBJ в объекты типа Primitive, залил фон черным и отрисовал несколько моделей:

Растеризация полигонов. Наводим красоту.

В прошлом разделе мы написали проволочный рендер. Теперь мы займемся его модернизацией — реализуем растеризацию полигонов.

По простому растеризировать полигон — это значит закрасить его. Казалось бы зачем писать велосипед, когда есть уже готовые функции растеризации треугольника. Вот что будет если нарисовать все дефолтными инструментами:

Современное искусство, полигоны сзади нарисовались поверх передних, одним словом — каша. К тому же как таким образом текстурировать объекты? Да, никак. Значит нам нужно написать свой имба-растерайзер, который будет уметь в отсечение невидимых точек, текстуры и даже в шейдеры! Но для того чтобы это сделать стоит понять как вообще красить треугольники.

Алгоритм Брезенхема для рисования линии.

Начнем с линий. Если кто не знал алгоритм Брезенхема — это основной алгоритм рисования прямых в компьютерной графике. Он или его модификации используется буквально везде: рисование прямых, отрезков, окружностей и т.п. Кому интересно более подробное описание — читайте вики. Алгоритм Брезенхема

Имеется отрезок соединяющий точки и . Чтобы нарисовать отрезок между ними нужно закрасить все пиксели которые попадают на него. Для двух точек отрезка можно найти x-координаты пикселей в которых они лежат: нужно лишь взять целые части от координат x1 и x2. Чтобы закрасить пиксели на отрезке запускаем цикл от x1 до x2 и на каждой итерации вычисляем y — координату пикселя который попадает на прямую. Вот код:

Картинка из вики

Растеризация треугольника. Алгоритм заливки

Линии рисовать мы умеем, а вот с треугольниками будет чуть посложнее(не намного)! Задача рисования треугольника сводится к нескольким задачам рисования линий. Для начала разобьем треугольник на две части предварительно отсортировав точки в порядке возрастания x:

Заметьте — теперь у нас есть две части в которых явно выражены нижняя и верхняя границы. все что осталось — это залить все пиксели находящиеся между ними! Сделать это можно в 2 цикла: от x1 до x2 и от x3 до x2.

Несомненно этот код можно отрефакторить и не дублировать цикл:

Отсечение невидимых точек.

Для начала подумайте каким образом вы видите. Сейчас перед вами экран, а то что находится позади него скрыто от ваших глаз. В рендеринге работает примерно такой же механизм — если один полигон перекрывает другой рендер нарисует его поверх перекрытого. Наоборот же, закрытую часть полигона рисовать он не будет:

Для того, чтобы понять видима точки или нет, в рендеринге применяют механизм zbuffer-а(буфера глубины). zbuffer можно представить как двумерный массив (можно сжать в одномерный) с размерностью width * height. Для каждого пикселя на экране он хранит значение z — координаты на исходном полигоне откуда эта точка была спроецирована. Соответственно чем ближе точка к наблюдателю, тем меньше ее z — координата. В конечном итоге если проекции нескольких точек совпадают растеризировать нужно точку с минимальной z — координатой:

Теперь возникает вопрос — как находить z-координаты точек на исходном полигоне? Это можно сделать несколькими способами. Например можно пускать луч из начала координат камеры, проходящий через точку на проекционной плоскости , и находить его пересечение с полигоном. Но искать пересечения крайне затратная операция, поэтому будем использовать другой способ. Для рисования треугольника мы интерполировали координаты его проекций, теперь, помимо этого, мы будем интерполировать также и координаты исходного полигона. Для отсечения невидимых точек будем использовать в методе растеризации состояние zbuffer-а для текущего фрейма.

Мой zbuffer будет иметь вид Vector3[] — он будет содержать не только z — координаты, но и интерполированные значения точек полигона(фрагменты) для каждого пикселя экрана. Это сделано в целях экономии памяти так как в дальнейшем нам все равно пригодятся эти значения для написания шейдеров! А пока что имеем следующий код для определения видимых вершин(фрагментов):

Анимация шагов растеризатора(при перезаписи глубины в zbuffer-е пиксель выделяется красным):

Для удобства я вынес весь код в отдельный модуль Rasterizer:

Теперь проверим работу рендера. Для этого я использую модель Сильваны из известной RPG «WOW»:

Не очень понятно, правда? А все потому что здесь нет ни текстур ни освещения. Но вскоре мы это исправим.

Текстуры! Нормали! Освещение! Мотор!

Почему я объединил все это в один раздел? А потому что по своей сути текстуризация и расчет нормалей абсолютно идентичны и скоро вы это поймете.

Для начала рассмотрим задачу текстуризации для одного полигона. Теперь помимо обычных координат вершин полигона мы будем хранить еще и его текстурные координаты. Текстурная координата вершины представляется двумерным вектором и указывает на пиксель изображения текстуры. В интернете я нашел хорошую картинку чтобы показать это:

Заметьте, что начало текстуры (левый нижний пиксель) в текстурных координатах имеет значение , конец (правый верхний пиксель) — . Учитывайте систему координат текстуры и возможность выхода за границы картинки когда текстурная координата равна 1.

Сразу создадим класс для представления данных вершины:

Зачем нужны нормали я объясню позже, пока что просто будем знать, что у вершин они могут быть. Теперь для текстуризации полигона нам необходимо каким-то образом сопоставить значение цвета из текстуры конкретному пикселю. Помните как мы интерполировали вершины? Здесь нужно сделать то же самое! Я не буду еще раз переписывать код растеризации, а предлагаю вам самим реализовать текстурирование в вашем рендере. Результатом должно быть корректное отображение текстур на модели. Вот, что получилось у меня:

Вся информация о текстурных координатах модели находятся в файле OBJ. Для того, чтобы использовать это изучите формат: Формат OBJ.

Освещение

С текстурами все стало гораздо веселее, но по настоящему весело будет когда мы реализуем освещение для сцены. Для имитации «дешевого» освещения я буду использовать модель Фонга.

Модель Фонга

В общем случае этот метод имитирует наличие 3х составляющих освещения: фоновая(ambient), рассеянная(diffuse) и зеркальная(reflect). Сумма этих трех компонент в итоге даст имитацию физического поведения света.

Для расчета освещения по Фонгу нам будут нужны нормали к поверхностям, для этого я и добавил их в классе Vertex. Где же брать значения этих нормалей? Нет, ничего вычислять нам не нужно. Дело в том, что великодушные 3д редакторы часто сами считают их и предоставляют вместе с данными модели в контексте формата OBJ. Распарсив файл модели мы получаем значение нормалей для 3х вершин каждого полигона.

Картинка из вики

Для того, чтобы посчитать нормаль в каждой точке на полигоне нужно интерполировать эти значения, мы уже умеем делать это. Теперь разберем все составляющие для вычисления освещения Фонга.

Фоновый свет (Ambient)

Изначально мы задаем постоянное фоновое освещение, для нетекстурированных объектов можно выбрать любой цвет, для объектов с текстурами я делю каждую из компонент RGB на некий коэффициент базового затенения (baseShading).

Рассеянный свет (Diffuse)

Когда свет падает на поверхность полигона он равномерно рассеивается. Для расчета diffuse значения на конкретном пикселе учитывается угол под которым свет падает на поверхность. Чтобы рассчитать этот угол можно применить скалярное произведение падающего луча и нормали(само собой вектора перед этим нужно нормализировать). Этот угол будет умножаться на некий коэффициент интенсивности света. Если скалярное произведение отрицательно — это значит, что угол между векторами больше 90 градусов. В этом случае мы начнем рассчитывать уже не осветление, а, наоборот, затенение. Стоит избегать этого момента, сделать это можно с помощью функции max.

Давайте применим рассеянный свет и рассеем тьму:

Зеркальный свет (Reflect)

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

Найти луч от наблюдателя к поверхности легко — это будет просто позиция обрабатываемой вершины в локальных координатах. Для того, чтобы найти отраженный луч я использовал следующий способ. Падающий луч можно разложить на 2 вектора: его проекцию на нормаль и второй вектор который можно найти вычитанием из падающего луча этой проекции. Чтобы найти отраженный луч нужно из проекции на нормаль вычесть значение второго вектора.

Теперь картинка выглядит следующим образом:

Конечной точкой моего изложения будет реализация теней для рендера. Первая тупиковая идея которая зародилась у меня в черепушке — для каждой точки проверять не лежит ли между ней и светом какой-нибудь полигон. Если лежит — значит не нужно освещать пиксель. Модель Сильваны содержит 220к с лихвой полигонов. Если так для каждой точки проверять пересечение со всеми этими полигонами, то нужно сделать максимум 220000 * 1920 * 1080 * 219999 вызовов метода пересечения! За 10 минут мой компьютер смог осилить 10-у часть всех вычислений (2600 полигонов из 220000), после чего у меня случился сдвиг и я отправился на поиски нового метода.

В интернете мне попался очень простой и красивый способ, который выполняет те же вычисления в тысячи раз быстрее. Называется он Shadow mapping(построение карты теней). Вспомните как мы определяли видимые наблюдателю точки — использовали zbuffer. Shadow mapping делает тоже самое! В первом проходе наша камера будет находиться в позиции света и смотреть на объект. Таким образом мы сформируем карту глубин для источника света. Карта глубин — это знакомый нам zbuffer. Во втором проходе мы используем эту карту, чтобы определять вершины которые должны освещаться. Сейчас я нарушу правила хорошего кода и пойду читерским путем — просто передам шейдеру новый объект растеризатора и он используя его создаст нам карту глубин.

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

Многие из вас наверное заметили артефакты данного шейдера(необработанные светом черные точки). Опять же обратившись в всезнающую сеть я нашел описание этого эффекта с противным названием «shadow acne»(да простят меня люди с комплексом внешности). Суть таких «зазоров» заключается в том, что для определения тени мы используем ограниченное разрешение карты глубин. Это значит, что несколько вершин при рендеринге получают одно значение из карты глубин. Такому артефакту наиболее подвержены поверхности на которые свет падает под пологим углом. Эффект можно исправить, увеличив разрешение рендера для света, однако существует более элегантный способ. Заключается он в том, чтобы добавлять определенный сдвиг для глубины в зависимости от угла между лучом света и поверхностью. Это можно сделать при помощи скалярного произведения.

Играем с нормалями

Я подумал, стоит ли интерполировать значения нормалей, если можно посчитать среднее между 3мя нормалями полигона и использовать для каждой его точки. Оказывается, что интерполяция дает куда более естественный и гладкий материал картинки.

Двигаем свет

Реализовав простой цикл получим набор отрендеренных картинок с разными позициями света на сцене:

Производительность

Для теста использовалась следующие конфигурации:

• Модель Сильваны: 220к полигонов.
• Разрешение экрана: 1920×1080.
• Шейдеры: Phong model shader
• Конфигурация компьютера: cpu — core i7 4790, 8 gb ram

FPS рендеринга составлял 1-2 кадр/сек. Это далеко не realtime. Однако стоит все же учитывать, что вся обработка происходила без использования многопоточности, т.е. на одном ядре cpu.