Иногда в программировании возникает задача - найти такую матрицу линейного преобразования, которая один меш(или просто множество точек) как можно ближе переводит к другому. Например, при моделировании деформаций иногда требуется найти такую матрицу трансформации, которая переводит тело из известного недеформированного состояния как можно ближе к также известному деформированному.
Давайте формализуем задачу. Пусть x0i - множество из N "исходных" точек. x1i - множество из N "конечных" точек. Будем полагать, что центры масс обоих множеств уже перенесены в начало координат. Таком образом, требуется найти такую матрицу A, которая минимизирует функцию
F(A) = sum[i = 0..N](A * x0i - x1i)2.
Смысл "на пальцах" - сумма разниц между "преобразованными" точками A * x0i и их целевыми положениями x1i должна быть минимальна.
F(A) - квадратична функция, у неё единственный минимум, который можно найти, приравняв dF(A)/dAi,j к нулю. Чтобы это проделать, придётся вспомнить немного тензорного анализа, хотя ответ достаточно прост и чтобы его перенести в код, ничего вспоминать не надо. Тем не менее, интересующиеся могут взглянуть под спойлер:
Таким образом, искомую матрицу A можно расписать так:
A = sum[i = 0..N](x1i * x0iT) * sum[i = 0..N](x0i * x0iT)-1
Напомню, что под выражением a * bT понимается такая матрица:
a.x*b.x a.x*b.y a.x*b.z a.y*b.x a.y*b.y a.y*b.z a.z*b.x a.z*b.y a.z*b.z
Обратную матрицу sum[i = 0..N](x0i * x0iT)-1 можно взять практически всегда и на этапе препроцесса меша, так как она зависит только от изначальных координат. Нельзя её взять в случае, если, например, все точки меша лежат в одной плоскости, что на практике встречается достаточно редко.
Сложность алгоритма - O(N), что на самом деле очень быстро и позволяет в реальном времени считать сотни тысяч точек. В добавок суммирование большого количества матриц можно легко распараллелить на произвольное количество процессоров а само получение матриц - на SSE.