Pull to refresh

Comments 27

… более эффективной в вычислительном плане, так как все операции работы с бикватернионами после раскрытия выражений являются линейными.

И где видно что количество операций сложения, умножения и обращений к памяти уменьшилось или хотя бы сравнение по производительности на тестовых примерах.
Чем бикватернион лучше, просто вектора и кватерниона?
Или в случае кораблей 2d вектора и одного угла?

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

В статье это не показано, так как это отдельная тема, но у меня есть публикация где такой подробный анализ проводится.
Я привел ссылку на видео где показано сравнение моделирования 3D-графики между обычными методами и методами с использованием бикватернионов.
Из своего опыта скажу, что при использовании бикватернионов вы убираете всю тригонометрию. Тригонометрические функции используются только для задания начальных условий, ну и для вывода отладочной информации в человекопонятном виде.
Возможно стоит подробно раскрыть тему операции бикватернионного умножения в отдельной статье.


Чем бикватернион лучше, просто вектора и кватерниона?
Или в случае кораблей 2d вектора и одного угла?

Да, в статье приведен пример в 2D, хотя весь код в библиотеки можно применять для вычислений в трехмерном пространстве. Сделано это лишь для того чтобы и так не перегружать пример еще большим кодом.
Бикватернион лучше тем, что он в себе содержит полную информацию об ориентации и положении в пространстве объекта в одном числе, пусть и в сложном гиперкомплексном.
Используя этот математический аппарат можно, например, применять различные методы управления объектами, там обнаруживаются иногда очень интересные случаи.


Приведу пример такого случая.
При синтезе оптимального управления квадракоптером по высоте стояла задача: с высоты 100 м опуститься на 10 м.
С использованием математического аппарата векторов и углов ориентации квадракоптер просто уменьшал тягу винтов и опускался до нужной высоты.
При использовании бикватернионов квадракоптер повел себя иначе, он перевернулся винтами вниз, увеличил тягу и при прилете до требуемой высоты перевернулся обратно винтами вверх.


ps: Еще такой вопрос чем отличаются норма и модуль бикватерниона и почему они содержат символ Клиффорда?

Бикватернион, по сути своей — дуальный кватернион = q1 + εq2.
Но часто его представляют в виде двух кватернионов, как это сделано в статье, поэтому здесь символ Клиффорда опущен, хотя его наличие надо всегда подразумевать у дуальной части q2.


Если совсем утрировать, то норма — это сумма квадратов компонентов бикватерниона, а модуль — корень квадратный из суммы квадратов компонентов бикватерниона.
Эти величины используются в других операциях, например, в операции вычисления обратного бикватерниона (в коде dual_quaternion.js в методе inverse как раз реализована операция деления бикватерниона на дуальное число), или при использовании численных методов интегрирования бикватерниона приходится его нормировать.

В статье норма, модуль и остальное берутся с потолка, это не очень классно (тем более при их размере). Думаю, что, зная норму и модуль обычных кватернионов и что бикватернион — дуальный кватернион, можно их вывести, но лучше было бы, если бы этот вывод был в статье.
Я старался не делать громоздких выводов. Но, раскрытие этих формул есть в коде javascript-библиотеки, методы «norm» и «mod».
И где видно что количество операций сложения, умножения и обращений к памяти уменьшилось или хотя бы сравнение по производительности на тестовых примерах.

На самом деле — дуальные кватернионы немного "дороже" по операциям, чем просто пара "вектор переноса + обычный кватернион". Главное их преимущество — почти полное отсутствие артефактов при скиннинге в местах, где на вершины влияет более одной кости. В видео приведенном в статье про это рассказывается с 0:55. И там кстати видно, что интерполяция на дуальных кватернионов работает чуть медленнее (~200 FPS) чем "обычный" метод (~270 FPS)

Октонион — это другое. Эта штука в статье — дуальный кватернион.
Да, вы правы. Просто в статьях иногда эти понятия путают (из статьи убрал).
Также неверно называть его «комплексный кватернион».
Большое спасибо за обзор. Он очень полезен.

У меня такой вопрос:
Есть ли преимущество в использовании бикватерниона перед преобразованием, описываемым кватернионом (для ориентации) и 3-вектором (для трансляции). Есть ли преимущество по скорости вычисления комбинированного перемещения?

P.S. А, хотя вижу комментарий выше.
Я выложил статью на github в которой проведено такое исследование.
Ben Kenwright — A Beginners Guide to Dual-Quaternions.pdf
Примерный перевод главы «11. Результаты»:
Бикватернион объединяет перемещение и вращение в одну переменную состояния. Это переменная состояния предлагает надежный, однозначный, вычислительно эффективный способ представления преобразования твердого тела.
Вычислительные затраты различных матриц и бикватерниона:
Матрица4х4: 64 умножений + 48 сложений.
Матрица4х3: 48 умножений + 32 сложений.
Бикватернион: 42 умножений + 38 сложений.

В наших тестах мы обнаружили, что метод умножения бикватернионных преобразований в среднем на 10% быстрее по сравнению с умножением матриц. Мы не использовали преимущества архитектуры ЦП, используя параллельные методы, такие как SIMD, которые могут еще больше улучшить скорость вычислений, как продемонстрировал Паллави [MEHU10] (как для матриц, так и для умножения кватернионов).

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

Ну пусть мы комбинируем две пары (поворот, вектор) (q1,r1) и (q2, r2).
В результате получится что-то вроде (q2 * q1, r1 + q1 * r2 * q1^{-1}) (я мог местами перепутать индексы, но на рассуждения это не влияет.)


  1. перемножение кватернионов: вроде бы 16 умножений и 12 сложений.
  2. поворот вектора кватернионом можно реализовать как два умножения кватернионов. Там одна из координат будет 0, можно это использовать и не делать лишних умножнений. (https://habr.com/en/post/255005/) Получается, первое "умножение " можно сделать за 12 умножений и 8 сложений, инвертирование кватерниона 3 или даже 1 одно вычитание (сложение), смотря как инвертировать. При перемножении от результата нам вроде бы нужны только три компоненты (это же повернутый вектор будет), поэтому 12 умножений и 9 сложений. Сложение с вектором — ещё 3 сложения.

Итого, если я не ошибаюсь, получается 40 умножений и 33 сложения. Хм. Капельку меньше, чем для бикватернионов.


P.S. Вообще говоря, такие оценки не несут большой ценности, но мне самому было интересно. Важно насколько хорошо происходящее сочетается с инструкциями процессора, которые, например, позволяют вектор из четырёх чисел складывать с другим вектором или поточечно умножать — и тогда те же матрицы 4*4 могут оказаться не хуже чем 4*3 или бикватернионы.

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

(q0*q1, r0*q1+q0*r1) — бикватернионы — 48 умножений, 40 сложений.
(q0*q1, r0+qrot(r1, q0)) — кватернион + вектор — 41 умножение, 35 сложений.
(M0*M1, r0 + M0*r1) -> 36 умножений, 27 сложений…

!!!
Оказывается, расчет в матрицах — самый быстрый… То ли я где-то накосячил в расчете, то ли… вся картина мира едет.
А что за операция рассмотрена? Преобразование точки или комбинация?
Надо будет почитать статью.

P.S. Если преобразование точки, то 3вектор+кватернион однозначно медленнее матрицы 3х4.
Смущают цифры
Вычислительные затраты различных матриц и бикватерниона:
Матрица4х4: 64 умножений + 48 сложений.
Матрица4х3: 48 умножений + 32 сложений.
Бикватернион: 42 умножений + 38 сложений.

У меня получается примерно так:
Умножение вектора на матрицу 3*4 = 9 умножений + 9 сложений
Умножение матрицы на матрицу 3*4 = 36 умножений + 27 сложений
Умножение кватерниона на кватернион = 10 умножений + 6 сложений
Поворот вектора кватернионом = 15 умножений + 9 сложений
Преобразование с поворотом и сдвигом через кватернион => 15 умножений + 15 сложений

Учитывать ориентацию кватернионом быстрее и точнее, плюс интерполяция поворота.
Но преобразование векторов матрицами требуют меньше операций.
Повертели и потом в матрицу и перемножаем толпу векторов.
А тут утверждается обратное.

Может я где-то не прав?
R'=A*R

x'=A00*x+A01*y+A02*z+A03
y'=A10*x+A11*y+A12*z+A13
z'=A20*x+A21*y+A22*z+A23

=> *9 +9

C=A*B

| C00 C01 C02 C03 |   | A00 A01 A02 A03 |   | B00 B01 B02 B03 |
| C10 C11 C12 C13 | = | A10 A11 A12 A13 | * | B10 B11 B12 B13 |
| C20 C21 C22 C23 |   | A20 A21 A22 A23 |   | B20 B21 B22 B23 |
| 0   0   0     1 |   | 0   0   0     1 |   | 0   0   0     1 |

C00 = A00*B00 + A01*B10 + A02*B20
C01 = A00*B01 + A01*B11 + A02*B21
C02 = A00*B02 + A01*B12 + A02*B22
C03 = A00*B03 + A01*B13 + A02*B23 + A03

C10 = A10*B00 + A11*B10 + A12*B20
C11 = A10*B01 + A11*B11 + A12*B21
C12 = A10*B02 + A11*B12 + A12*B22
C13 = A10*B03 + A11*B13 + A12*B23 + A03

C20 = A20*B00 + A21*B10 + A22*B20
C21 = A20*B01 + A21*B11 + A22*B21
C22 = A20*B02 + A21*B12 + A22*B22
C23 = A20*B03 + A21*B13 + A22*B23 + A03

=> *36 +27

R'=q*R/q

Rx'=(1-q1*q1)*Rx-q1*q2*Ry-q1*q3*Rz
Ry'=-q1*q2*Rx+(1-q2*q2)*Ry-q2*q3*Rz
Rz'=-q1*q3*Rx-q2*q3*Ry+(1-q3*q3)*Rz

=> *15 +9

R'=R1+q*(R-R0)/q
=> *15 +15

Там речь судя по всему о комбинировании пребразований (умножение матриц / кватернионов / etc) а не о применении преобразования к вектору / векторам. Правда я как-то с трудом себе представляю где вопрос производительности комбинирования преобразований имел бы какое-то практическое значение.

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

В геймдеве, например.
Сколько там матриц надо перемножить чтобы посчитать финальную? Десяток? Ну и на что ускорение подобного преобразования на 10% повлияет? Вот к миллионам векторов потом эту матрицу применять — там да, нужно время. Но как раз там-то как верно заметил kovserg быстрее матриц ничего нет. И по числу операций и по удобству приложения к современным вычислительным платформам.
Видел применение дуальных чисел для расчёта производных. Интересно, можно ли тут это использовать и быстро считать производные по компонентам кватернионов.
Рискну предположить. Взятие производной с помощью дуальных чисел само по себе вычислительно избыточно, а значит, никак не может быть использовано для «быстрого» вычисления компонент кватернионной производной.

нет, там ничего избыточного не производится.
(f, f') * (g, g') = (f * g, f * g' + f' * g)
Умножением для дуальных чисел будет обычное умножение и сразу же вычисление производной от произведения. Если в будущем планируется использовать и то и другое, то этот способ оптимальнее некуда.

Если посчитать количество операций на расчет функции + производной и на расчет функции в дуальных числах, окажется, что второе вычислительно тяжелее

Можно пример? Мне кажется, что будет то же самое.

Возьмём функцию (x^2)*(x+3). Вычислим ее производную в точке 'a' в дуальных числах.
x->(a,1)
x^2 -> (a,1)*(a,1) -> (a*a, a*1 + a*1) -> (b, bi)
x+3 -> (a,1) + (3,0) -> (a+3, 1+0) -> (c, ci)
x^2 * (x+3) -> (b,bi)*(c,ci) -> (b*c, b*ci + c*bi) -> (d, di)
result: (d, di).imag -> di
Итого: 6 умножений, 4 сложения.

Вычисляем предберя производную: 2x*(x+3) + x^2 = 3*x*x + 6*x = 3*x*(x+2)
Итого: 1 сложение, 2 умножения. (и столько же, если мы хотим и значение функции тоже (Итого: 2 сложения, 4 умножения))

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

А если сделать "дуальные-дуальные-кватернионы"? Ну просто смотреть на дуальные кватернионы как на один объект, задающий ориентацию в пространстве, и поверх прикрутить дуальность для производных. Мне кажется, что такое может работать.

Это будет работать, но, как я пишу выше, это огроменный оверхед по производительности. Это вдвойне излишне, учитывая, что обычно в контексте задач кинематики (для которых обычно применяются кватернионы и бикватернионы)
g'(M*x) == M*g'(x) — производная трансформированного вектора равна трансформированной производной вектора (хотя, это, конечно… не всегда)…
Sign up to leave a comment.

Articles