Публикации Проекты Форум Работа
Войти
ПрограммированиеПодсказкиОбщее

Матрица перехода от одного множества точек к другому

Автор:

Иногда в программировании возникает задача - найти такую матрицу линейного преобразования, которая один меш(или просто множество точек) как можно ближе переводит к другому. Например, при моделировании деформаций иногда требуется найти такую матрицу трансформации, которая переводит тело из известного недеформированного состояния как можно ближе к также известному деформированному.

Давайте формализуем задачу. Пусть 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.

#графика, #программирование, #математика

11 сентября 2013 (Обновление: 15 окт 2013)

Комментарии [13]

Контакт Сообщества Участники Каталог сайтов Категории Архив новостей
GameDev.ru — Разработка игр
©2001—2023