Эффективный 4x4 матричная инверсия (аффинное преобразование)
Я надеялся, что кто-то может указать на эффективную формулу для 4x4 аффинное матричное преобразование. В настоящее время мой код использует расширение кофактора, и это выделяет временный массив для каждого кофактора. Легко читать, но это медленнее, чем это должно быть.
Отметьте, это не домашняя работа, и я знаю, как разработать его вручную использующий 4x4 расширение кофактора, это - просто боль и не действительно интересная проблема для меня. Также я погуглил и придумал несколько сайтов, которые уже дают Вам формулу (http://www.euclideanspace.com/maths/algebra/matrix/functions/inverse/fourD/index.htm). Однако этот мог, вероятно, быть оптимизирован далее путем предварительных вычислений некоторых продуктов. Я уверен, что кто-то придумал "лучшую" формулу для этого однажды или другого?
3 ответа
Вы должны быть в состоянии использовать тот факт, что матрица является аффинной, чтобы ускорить процесс по сравнению с полным инверсом. А именно, если ваша матрица выглядит следующим образом
A = [ M b ]
[ 0 1 ]
где A - 4x4, M - 3x3, b - 3x1, а нижняя строка - (0,0,0,0,1), то
inv(A) = [ inv(M) -inv(M) * b ]
[ 0 1 ]
В зависимости от ситуации, может оказаться быстрее вычислить результат inv(A) * x вместо того, чтобы формировать inv(A). В этом случае все упрощается до
inv(A) * [x] = [ inv(M) * (x - b) ]
[1] = [ 1 ]
где x - вектор 3x1 (обычно трехмерная точка).
Наконец, если M представляет собой вращение (т.е. его столбцы ортонормальны), то можно использовать тот факт, что inv(M) = transpose(M). Тогда вычисление обратной величины A сводится к вычитанию компонента перевода и умножению на транспонирование части 3x3.
Заметим, что то, является ли матрица ортонормированной, можно узнать из анализа задачи. Проверять это во время выполнения будет довольно дорого; хотя вы можете захотеть сделать это в отладочных сборках, чтобы убедиться, что ваши предположения верны.
Надеюсь, все это понятно...
IIRC, вы можете значительно сократить код и время, предварительно вычислив группу (12?) Определителей 2x2. Разделите матрицу пополам по вертикали и вычислите каждые 2x2 как в верхней, так и в нижней половине. Один из этих меньших определителей используется в каждом термине, который вам понадобится для более крупных вычислений, и каждый из них используется повторно.
Кроме того, не используйте отдельную функцию-определитель - повторно используйте под-определители, которые вы вычислили для сопряженного, чтобы получить определитель.
О, только что нашел это.
Есть некоторые улучшения, которые вы можете внести, зная, что это тоже определенный вид трансформации.
Я считаю, что единственный способ вычислить обратное - это решить n раз уравнение: A x = y, где y охватывает единичные векторы, т.е. первый равен (1,0,0,0), второй равно (0,1,0,0) и т. д.
(Использование кофакторов (правило Крамера) - плохая идея, если вам не нужна символьная формула для обратного.)
Большинство библиотек линейной алгебры позволят вам для решения этих линейных систем и даже для вычисления обратного. Пример на python (с использованием numpy):
from numpy.linalg import inv
inv(A) # here you go