nabbla (nabbla1) wrote,
nabbla
nabbla1

Categories:

Аффинный алгоритм, математическая интерлюдия

Часть 1 - нахождение наиболее отдалённой точки
Часть 2 - сортировка против часовой стрелки
Комментарий об операторе упорядочивания
Часть 3 - нахождение матрицы преобразования
Часть 4 - нахождение крена
Математическая интерлюдия
Часть 5 - нахождение масштаба
Финал!

Спустя 111 слов кода (222 байта), мы правильно расставили точки, нашли матрицу аффинного преобразования и "вычленили" из неё крен. В итоге у нас осталась симметричная матрица 2х2, в которой "закодированы" масштаб (дальность) и "ракурсы" (тот факт, что мы смотрим на плоскость не под прямым углом, из-за чего картинка ужимается вокруг некоторой оси).

Вот она, эта зверюга:



Я продолжал раз за разом уверять, что s<0 ("отрицательный масштаб") соответствует подлёту "с противоположной стороны", и только сейчас осознал - это полный бред! s<0 - это всего лишь другой способ изобразить поворот на 180 градусов, "по крену". Просто мы условились включить такой поворот именно в крен, а s после этого будет заведомо больше нуля. А вот подлёт "с противоположной стороны" - это когда a<0.

В общем, неплохо бы слегка прояснить, каким образом из этой матрицы получить масштаб и затем пройти "проверку на вшивость"...


Напомним, что SA означает перемножение матриц S, scale (масштаб) и A, aspect (ракурс).
s>0 - величина масштаба,
a - величина "ужатия",
ψ - направление, в котором происходит данное "ужатие".

Поначалу кажется, что число a может принимать любое значение, и так оно и есть.

Но в разложении симметричной матрицы на масштаб и "ракурсы" существует неоднозначность, когда одно и то же преобразование может быть записано двумя разными наборами (s, a, ψ). В одном из них |a|≤1, в другом: |a|≥1.

Пусть в первом наборе |a|≤1, и ещё заданы произвольный масштаб s и угол ψ.

Тогда мы можем найти второй "набор":




Подставим эти значения вместо "исходных" в нашу матрицу, и посмотрим, что из этого выйдет:



Воспользуемся формулами приведения, а также внесём a в скобки:


Наконец, выразим квадрат косинуса через синус, и наоборот:


Если дальше раскрыть скобки, то придём в точности тому же выражению, с которого мы и начали.

Так что до сих пор мы не накладывали никаких "физических" ограничений на эти величины, то есть исходя из наших знаний, откуда мы должны выходить на цель. Требование s>0 снимало неоднозначность в опеределении угла крена, а требование |a|≤1 снимает неоднозначность в определении (s, a, ψ).

Попробуем теперь выразить масштаб через известные нам компоненты матрицы. Чтобы не мучаться, обозначаем её компоненты как X,Y,Z:


Если сложить элементы на главной диагонали, получим:



В прошлой части мы выбрали такой угол крена, что эта сумма заведомо получится положительной, и, действительно, при s>0 и |a|≤1 так всегда и будет.

Теперь вычтем Z и X:


Возведём это выражение в квадрат и прибавим (2Y)2:


Извлечём квадратный корень, зная, что s>0 и |a|≤1:


И наконец, можно выразить s:


Очень важно, что до сих пор мы не делали никаких допущений относительно диапазона измеряемых величин, типа того что "эта формула правильно посчитает масштаб, если мы смотрим "прямой наводкой", но может выдать что угодно, если мы отклонились от нормали более чем на 30 градусов" - ничего подобного!!!

Результат всегда будет правильным, и это очень радостно.

А затем, когда мы найдём s, можно поделить всю матрицу на него, и у нас останется следующая штука:


И теперь, сложив X' с Z', имеем:


откуда


замечательное выражение!

И результат заведомо будет находиться в границах [-1;1], мы такое любим, когда работаем с "фиксированной запятой" :)

(обозначив



и

,

имеем

)

Так что финальным аккордом можно будет проверить, лежит ли число a в диапазоне от cos(30°) до 1, и если да - мы именно в той зоне, в которой должны находиться. В противном случае велика вероятность, что мы всё-таки "зацепились" за какие-то неправильные точки.

В общем, специально проверять знак чисел на главной диагонали не нужно - это частный случай, который в любом случае будет рассмотрен, когда мы проверим число a.

Ну и диапазон масштаба полезно посмотреть - если он слишком мал или слишком велик - это тоже весьма подозрительно. Скорее всего, у нас будет "дополнительный канал" для измерения дальности - мы будем смотреть время экспозиции. Если оно соответствует ожидаемому на заданной дистанции - всё хорошо.

На самом деле, есть и ещё один "канал", по которому мы могли бы осуществить "проверку на вшивость". Дело в том, что мы решали оптимизационную задачу - искали 6 коэффициентов, которые наилучшим образом сопоставляли картинки из 4 точек каждая, т.е по 8 координат. Значит, можно посмотреть "невязку". Но этого мы в алгоритме захвата делать не будем, немножко не то место. Потому как наша модель не очень точна - на малых дальностях уже будет заметно, что центральная точка лежит не на той плоскости, и перспектива вступает в свои законные права (в смысле, не все дистанции уменьшаются в одинаковое число раз, как в аффинном приближении, а нужно всё честно считать в пространстве!), тут уже высокий риск перегнуть палку с проверками и отбраковать вполне себе "законную" картинку.

А самое главное: алгоритм сопровождения начнёт ровно с такой проверки "невязки", только он "спроецирует" точки на экран по всем законам перспективы. Именно так будет работать его "сопоставление" - мы будем говорить "точка под номером ноль должна быть ЗДЕСЬ. Ага, вот она, сдвинута на 1,5 пикселя, но это должна быть именно она. Точка под номером один должна быть ЗДЕСЬ. Но здесь ничего нет, что за нахрен!? Возвращаемся в режим поиска...".
Tags: tex, ПЛИС, кватернионы-это просто (том 1), математика, работа, странные девайсы
Subscribe

  • Нахождение двух самых отдалённых точек

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

  • Слишком общительный счётчик

    Вчера я чуть поторопился отсинтезировать проект,параметры не поменял: RomWidth = 8 вместо 7, RamWidth = 9 вместо 8, и ещё EnableByteAccess=1, чтобы…

  • Балансируем конвейер QuatCore

    В пятницу у нас всё замечательно сработало на симуляции, первые 16 миллисекунд полёт нормальный. А вот прошить весь проект на ПЛИС и попробовать "в…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 0 comments