Каморка

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

Код делает следующее. Есть поворот пространства A. Есть другой поворот пространства B. Код находит их разницу, а потом со все возрастающим весом добавляет эту разницу к A, чтобы в конце получить B.

И вот тут возникает любопытный вопрос. А разница D=(B-A) это что такое? Как он должен работать (плюс означает последовательные повороты, а значок * на самом деле, означает Q*w == slerp(1,Q,w) ):

D1*w(t) + A

или

A + D2*w(t)

Повороты штука некоммутативная, так что результаты будут разные. Так что такое разница - D1 или D2?
Лично я интуитивно предположил, что D2. Потому что мы сначала делаем поворот A, а потом добавляем к нему дельту.

Но на практике получается, что так переход от A к B идет не по кратчайшему пути, а по дуге. А вот D1 делает все верно. Сижу и чешу репу. Ничего понять не могу. Почему это, сначала дельта, а потом поворот верно, а не наоборот?

Мы живем в сумасшедшем мире, друзья мои.

sz писал(а):Мы живем в сумасшедшем мире, друзья мои.

Это точно... Сидят, пространства крутят - как хотят, а потом "рубают финики лопари, и в Сахаре снега невпроворот"

Надобно отметить забористая трава у товарища sz.

-Maxim

Оба поворота A и B заранее известны, но надо показать динамику поворота - какая-то графическая программа? Потому что, по идее, использование матрицы поворота более быстрый метод, чем использование кватернионов, но кватернионы имеют простую интерполяцию между двумя поворотами (slerp) и, соответственно можно легко достигнуть "плавности" движения... Определение "плюса" тоже не совсем понятно: "плюс" - это действительно сложение матриц (кватернионов), или сложение "поворотов" (умножение матриц)?

То есть, правильно ли я понял: Есть матрицы поворотов A и B. Вектор v надо повернуть на B и получить vB. При этом, стоит задача разложить поворот B на поворот A и некий поворот D ("разница" поворотов А и B) и осуществить эти два поворота, вместо того, чтобы просто повернуть на B сразу.

Решение:
Допустим, что мы хотим повернуть v сначала на A, а затем на "разницу" D1 и получить B:
vB = B * v = D1 * vA = D1 * A * v
или
B = D1 * A
Отсюда,
D1 = B * A^(-1) - "разница" поворотов 1.

Допустим, что мы хотим повернуть v сначала на "разницу" D2, а затем на А и получить B:
vB = B * v = A * vD2 = A * D2 * v
или
B = A * D2
Отсюда,
D2 = A^(-1) * B - "разница" поворотов 2.

То есть, в общем случае, D1 != D2. Соответственно, метод нахождения "разницы" D диктует последовательность применения поворотов A и D.

С кватернионами тоже самое.

Azazello писал(а):Оба поворота A и B заранее известны, но надо показать динамику поворота - какая-то графическая программа? Потому что, по идее, использование матрицы поворота более быстрый метод, чем использование кватернионов, но кватернионы имеют простую интерполяцию между двумя поворотами (slerp) и, соответственно можно легко достигнуть "плавности" движения... Определение "плюса" тоже не совсем понятно: "плюс" - это действительно сложение матриц (кватернионов), или сложение "поворотов" (умножение матриц)?

То есть, правильно ли я понял: Есть матрицы поворотов A и B. Вектор v надо повернуть на B и получить vB. При этом, стоит задача разложить поворот B на поворот A и некий поворот D ("разница" поворотов А и B) и осуществить эти два поворота, вместо того, чтобы просто повернуть на B сразу.

Решение:
Допустим, что мы хотим повернуть v сначала на A, а затем на "разницу" D1 и получить B:
vB = B * v = D1 * vA = D1 * A * v
или
B = D1 * A
Отсюда,
D1 = B * A^(-1) - "разница" поворотов 1.

Допустим, что мы хотим повернуть v сначала на "разницу" D2, а затем на А и получить B:
vB = B * v = A * vD2 = A * D2 * v
или
B = A * D2
Отсюда,
D2 = A^(-1) * B - "разница" поворотов 2.

То есть, в общем случае, D1 != D2. Соответственно, метод нахождения "разницы" D диктует последовательность применения поворотов A и D.

С кватернионами тоже самое.

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

Это не программизм, а математика Как сказал классик, "страшно далеки они от народа"

Ranger писал(а):Это не программизм, а математика Как сказал классик, "страшно далеки они от народа"

спасибо, подбодрил. На душе заметно потеплело.

Azazello писал(а):Оба поворота A и B заранее известны, но надо показать динамику поворота - какая-то графическая программа? Потому что, по идее, использование матрицы поворота более быстрый метод, чем использование кватернионов, но кватернионы имеют простую интерполяцию между двумя поворотами (slerp) и, соответственно можно легко достигнуть "плавности" движения... Определение "плюса" тоже не совсем понятно: "плюс" - это действительно сложение матриц (кватернионов), или сложение "поворотов" (умножение матриц)?

То есть, правильно ли я понял: Есть матрицы поворотов A и B. Вектор v надо повернуть на B и получить vB. При этом, стоит задача разложить поворот B на поворот A и некий поворот D ("разница" поворотов А и B) и осуществить эти два поворота, вместо того, чтобы просто повернуть на B сразу.

Решение:
Допустим, что мы хотим повернуть v сначала на A, а затем на "разницу" D1 и получить B:
vB = B * v = D1 * vA = D1 * A * v
или
B = D1 * A
Отсюда,
D1 = B * A^(-1) - "разница" поворотов 1.

Допустим, что мы хотим повернуть v сначала на "разницу" D2, а затем на А и получить B:
vB = B * v = A * vD2 = A * D2 * v
или
B = A * D2
Отсюда,
D2 = A^(-1) * B - "разница" поворотов 2.

То есть, в общем случае, D1 != D2. Соответственно, метод нахождения "разницы" D диктует последовательность применения поворотов A и D.

С кватернионами тоже самое.

Именно так. Работаем мы, разумеется с кватернионами. С матрицами уже редко кто работает.
Плюс у меня там означал последовательные повороты, а не сложение матриц/кватернионов.

Да, методы отличаются последовательностью применения.
D1 = (A^-1)*B
D2 = B*(A^-1)

Тогда получаем две возможные траэктории:
Q1(t) = A * slerp( I, D1, t );
Q2(t) = slerp( I, D2, t ) * A;

где t меняется от 0 до 1; а I - единичный кватернион ( 1, (0, 0, 0) ).

Вопрос состоит в том, какая из траэкторий лучше?
Под словом "лучше" я, разумеется, понимаю близость к геодезической:
Q(t) = slerp( A, B, t );

Так вот, чисто практически, оказывается, что Q1(t) дает лучшие результаты. В общем, мне пока не удалось найти поворотов при которых Q(t) != Q1(t). Доказать их идентичность аналитически я не могу. Более того, я почти уверен, что они не идентичны.

Вот потому и удивляюсь. Чем, собственно Q1 лучше, чем Q2? Да ничем. Наоборот, Q2 как-то логичнее выглядит. А вот..

Есть какие-то приблизительные соображения, что slerp с единичным кватернионом на границе правильно (геодезично) проэцируется на любую другую траэкторию. А все остальные slerp-ы искажаются при проэцировании. Поэтому, чтобы получить правильную проэкцию, надо провести преобразование координат, сделать там slerp с единицей, а потом преобразовать обратно. Что, собственно случай 1 и делает. Но, честно говоря, с большой неуверенностью я все это говорю. Нету у меня точного понимания, почему. Гуглил на эту тему вчера много, но так ничего и не нашел.

Два вопроса:
1. Откуда известно, что D1 и D2 - единичные кватернионы? У меня не было времени проверять, но, по-моему, они не будут таковыми в общем случае. Если они не единичные, то Slerp(I, Di; t) не будет давать кротчайшую траекторию.
2. Даже если они и единичные, то (по прикидке), хотя углы между (I и D1) и (I и D2) равны между собой, они не равны углу между А и B. А Slerp не есть простая линейная комбинация - коэффициенты зависят от аргументов (угла). То есть, по-моему,
Slerp(A, B; t) = Slerp( A*I, A * D1; t ) != A * Slerp( I, D1; t )
Slerp(A, B; t) = Slerp( I*A, D2 * A; t ) != Slerp( I, D2; t ) * A

Единственно когда это будет работать, по-моему - это в пределе малых углов, когда мы sin можем заменить на угол - получится линейный Slerp.

Или я неправ конкретно? Честно скажу, думал по дороге в машине, времени возиться не было... Интересно было бы услышать Ваше мнение перед тем как лезть в это дело ...

Azazello писал(а):Два вопроса:
1. Откуда известно, что D1 и D2 - единичные кватернионы? У меня не было времени проверять, но, по-моему, они не будут таковыми в общем случае. Если они не единичные, то Slerp(I, Di; t) не будет давать кротчайшую траекторию.

Единичные - в смысле нормированные?
Это известно практически по определению. Повороты определяются нормированными кватернионами. Множество нормированных кватернионов образует четырехмерную гиперсферу. Которая, разумеется, один в один отображается на пространство трехмерных поворотов.
В принципе, я слышал, что иногда используют и ненормированные кватернионы для описания поворота, но, откровенно говоря, не вижу смысла.

Azazello писал(а):2. Даже если они и единичные, то (по прикидке), хотя углы между (I и D1) и (I и D2) равны между собой, они не равны углу между А и B. А Slerp не есть простая линейная комбинация - коэффициенты зависят от аргументов (угла). То есть, по-моему,
Slerp(A, B; t) = Slerp( A*I, A * D1; t ) != A * Slerp( I, D1; t )
Slerp(A, B; t) = Slerp( I*A, D2 * A; t ) != Slerp( I, D2; t ) * A

У меня в конце концов получилось доказать, что Slerp( A*I, A * D1; t ) == A * Slerp( I, D1; t ).
Да оно и интуитивно понятно, если вдуматься. A - это поворот пространства. Если мы берем две точки В и C и линейно интерполируем между ними, то получаем точку на дуге окружности между B и C. И положение этой точки не изменится от того, что мы выполним вращение пространства.
Поэтому A * Slerp( B, C; w ) == Slerp( A*B, A*C, w ).

А вот второе, вообще говоря не верно, то есть:
Slerp( B, C; w ) * A != Slerp( B*A, C*A, w )
Потому что в этом случае, мы сначала выполняем преобразование пространства, а затем делаем в этом интерполяцию от B к С. Что совсем не то же самое, что сделать интерполяцию повернутого B к повернутому C.

Ну, выкладки у меня тоже сошлись - они довольно длинные, но все получилось. Так что, все доказалось.
Правильная разница поворотов - это B*A^-1.
А A^-1*B - это неправильно.
А так сразу и не скажешь. Все таки, эти некоммутативные алгебры полны парадоксов.

Azazello писал(а):Единственно когда это будет работать, по-моему - это в пределе малых углов, когда мы sin можем заменить на угол - получится линейный Slerp.

Кстати, Slerp-ом практически никто никогда не пользуется. Nlerp на порядок эффективнее, а результаты очень похожи - он ведет по правильной дуге, но немного неравномерно по времени. В любом случае, отклонение от Slerp у Nlerp никогда не превышает 8% от длинны дуги, что практически незаметно глазу.
Вот тут есть подробнее об этом: http://number-none.com/product/Hacking% ... index.html

Ну я и балбес
Даже доказательство построил какое-то. А вся проблема из-за ошибки в тестовой программе.
На самом деле,

q1 * Slerp( I, q1^-1 * q2, t ) == Slerp( I, q2 * q1^-1, t ) * q1 == Slerp( q1, q2, t )

Все три версии производят абсолютно одинаковые результаты.

sz писал(а):...q1 * Slerp( I, q1^-1 * q2, t ) == Slerp( I, q2 * q1^-1, t ) * q1 == Slerp( q1, q2, t )

Все три версии производят абсолютно одинаковые результаты.

В общем, интуитивно было понятно, что либо оба правильны, либо оба неправильны. И скорее правильны . Первое равенство верно если q1 и q2 нормированы, потому что угол один и тот же в Slerp получается, так как Re(q1^(-1) * q2) = Re(q2 * q1^(-1)), и, соответственно, коэффициенты одни и те же - просто линейная комбинация. А вот последнее мне было не очевидно, потому что Slerp зависит от угла между кватернионами и, на вскидку, угол между q1 и q2 не равен углу Ang(I , q1^(-1) * q2 ) = Ang(I , q2 * q1^(-1)). То есть, Slerp должен меняться при выносе/вносе кватерниона (если Slerp от угла не зависит, то все три равенства очевидны автоматом) и доказательство не так тривиально. Или я просто его не вижу, что очень может быть.