nabbla (nabbla1) wrote,
nabbla
nabbla1

Categories:

Алг. ближней дистанции, "случай Берегового"

Осталось определить, где же у этой мишени "верх",а где "низ"! Увы, она слишком симметрична, чтобы это можно было указать в самом начале работы. Мы начали с нахождения двух наиболее отдалённых точек, но какая из них на самом деле "левая", а какая - "правая" - мы до сих пор не знали.
FullImageAfterCenterPoints.png

И только выделив "центральные точки" (которые могли "гулять" относительно всех остальных в широких пределах и запутывать дело), мы наконец-то можем это сообразить.

Хитрость в том, что "верхние точки" мишени расположены чуть ближе к центру, а "нижние точки" - врастопырку. Поэтому точки с индексами 0 и 5 у нас всегда будут "нижними", а с индексами 2 и 3 - "верхними".

На самом деле проблема даже не сколько "вверх-вниз", сколько в наличии зеркального отражения. То есть, в зависимости от начального порядка точек, мы можем с тем же успехом пронумеровать их вот так:


Мы должны научиться в любой ситуации выбирать ОДНУ И ТУ ЖЕ нумерацию, которую мы и обзовём верной.

Достаточно, к примеру, взять точку 0 и найти её проекцию на ось, перпендикулярную к оси "6-7", ну посмотреть знак этой проекции. Мы уже строили вектор V (Vx; Vy), ведущий из точки 6 в точку 7. Из него можно построить вектор (-Vy; Vx), который будет повёрнут на 90° против часовой стрелки. Если найти проекцию точки 0 на него, то при первом варианте нумерации, знак проекции будет отрицательным, а при втором варианте - положительным.

Промелькнула нехорошая мысль: если этот знак "неправильный", то можно вернуться в начало процедуры SortByProjection, тем самым повторив 3 этапа (сортировку точек "слева направо", теперь уже правильно, нахождение центральных точек и проверку на "верх тормашками"). Это позволило бы упростить код: вместо того, чтобы "ручками" менять точки местами, мы запустим уже имеющийся код, который сделает это за нас. Ну ещё 100 микросекунд потеряем, ну и что!? На фоне 40 мс, которые уходят просто на считывание кадра, это 0,25%, никто не заметит :)

Но пожалуй, делать так не стоит по другой причине: есть опасность, при поступлении "мусора" на вход получить полное зависание программы!


У моих алгоритмов захвата (и дальней, и ближней дистанции) "философия" такова: мы не пытаемся отбраковать заведомо неверные данные, т.к это автоматом сделает алгоритм сопровождения. Но произвольные неверные данные ни при каких условиях не должны нам навредить! Под "навредить" как раз и имеется в виду ввести программу в бесконечный цикл, либо заставить её затереть нужные данные (что-то наподобие "переполнения стека").

Хороший рецепт избежать таких вещей - делать алгоритмы максимально детерминированными. К примеру, все наши итеративные вычисления имели фиксированное количество итераций, поэтому если сходимости не будет (ненормированные "синус" и "косинус" окажутся оба нулевыми, после чего нормировать их можно до второго пришествия), мы хотя бы не зависнем.

Но этот наш финт ушами может привести к нехорошим последствиям, и для этого достаточно дать алгоритму мишень с "нечётной симметрией", вроде такого:


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

На самом деле, если просто генерить 8 случайных точек и давать их в качестве входных данных, я подозреваю, что вероятность "налететь" на такое - 50%. Всегда из этих точек две будут "самые отдалённые", и весь вопрос, как будут стоять две точки близкие к ним - "по одну сторону" или "по разную". Если "по разную" - нам кранты.

Так что не будем очередной раз жадничать - и зеркально отразим точки отдельным небольшим кусочком кода.

Но сначала надо написать определение знака проекции.

И тут мы, пожалуй, чуть подправим процедуру FindCentralPoint, а именно, выберем ей другое место для хранения координат центров. Они нам затирали ранее найденный вектор, фу такими быть! Добавим в её начале строку:

    Y         a22


И сразу напишем "рыбу" нашей очередной процедуры:
;содержание регистров и стека к этому моменту:
;i неизвестно (от 5 до 7)
;j = 3
;k = 0
;C, Acc неизвестны
;X = Points2D
;Y = a22 (временное хранилище)
;Z = Fx1 (сдвинуто на 1 точку отн. X)
;[SP], [SP+1] - неизвестны
CheckUpsideDown proc
;на самом деле, проблема не в том, что "вверх ногами", а в возможном зеркальном отражении


CheckUpsideDown endp


"неизвестно" - немножко не так. Можно довольно точно сказать, что там лежит, но не так уж важно.


Дальше, по ходу разработки, пришла в голову ещё более бредовая мысль.

Мы сейчас в качестве временного хранилища используем треугольную матрицу 6х6, которую будем "собирать" только на этапе сопровождения. Она содержит 6*7/2 = 21 элемент:

a11   a12   a13   a14   a15   a16
      a22   a23   a24   a25   a26
            a33   a34   a35   a36
                  a44   a45   a46
                        a55   a56
                              a66


но почему-то в памяти я их размещал "столбец за столбцом", т.е a11, a12, a22, a13, a23 и т.д. Вообще матрица А симметричная, поэтому с тем же успехом можно назвать элементы a11, a21, a22, a31, a32 и т.д. Тогда они будут размещаться как раз "строка за строкой".

В общем, речь о том, что места у нас дохрена! Хочу сохранить вектор не в a11, a12, как изначально задумывалось, а в a14, a24, т.е с отступом в 6 элементов. Затем, при поиске центральных точек задействовать a11, a12. И потом при проверке будем использовать хитрючую адресацию [Y+i^j], где i идёт от 1 до 0, а j=6. Нам нужно j=6, чтобы получить доступ к точкам 6 и 7. XOR (исключающее ИЛИ, оно же ^) нужен, чтобы "на лету" поменять местами значения X и Y, чтобы вместо скалярного произведения получилось "векторное на плоскости", результатом которого становится 1 число. В итоге, при i=1, j=6, по [Y+i^j] мы получим 7-й элемент, a24, где лежит Vy. А при i=0, j=6, получим 6-й элемент, a14, где лежит Vx.

Если так сделать, получим весьма компактный код:
;		i	1
;		j	6		;или всё это одной командой ijk
		ijk	0x0026		;{Inv,k,i,j}
		[SP]	0
@@i_loop:	Acc	[X+i]		;Fy0 на первой итерации, Fx0 на второй
		SUB	[Z+2j+i]	;вычесть Fy7 на первой итерации, Fx7 на второй
		C	[Y+i^j]		;i^j = 7 на первой итерации, 6 на второй. Должным выбором Y можно это устроить...
		MUL	Acc		;(Fy0-Fy7) * Vx на первой итерации,  (Fx0-Fx7) * Vy на второй
		SUB	[SP]		;вычитаем 0 на первой итерации, получая (Fy0-Fy7) * Vx.  Вычитаем (Fy0-Fy7) * Vx на второй, получая (Fy0-Fy7) * (-Vx) + (Fx0-Fx7) * Vy
		[SP]	Acc
		iLOOP	@@i_loop
;по завершении, флаг знака обозначает знак проекции на "вертикальную" ось (перпендикулярную к отрезку, соед. точки 6-7)


Всего 9 строк (т.е 18 байт) - и получаем флаг знака, по которому мы примем решение, делать ли "зеркальное отражение", в смысле, переупорядочивание точек в обратную сторону.

Осталось сообразить, как его лучше всего провернуть. Нужны следующие перестановки:
0 ↔ 5
1 ↔ 4
2 ↔ 3
6 ↔ 7


Ну, как-то так:
		JGE	@@skip
;7 <-> 6		
;0 <-> 5
;1 <-> 4
;2 <-> 3

;i=0, j=6, k=0, но могли бы k поставить какой хотим.
;Swap меняет (X,i)  с (Z,j) в смысле нумерация i от нулевой точки, j - от первой.
		i	6
		[SP]	Call(SwapPoints)	;поменяли 6 и 7
		ijk	0x0042	;i=2, j=2, k=0, Inv=0, последнее вообще необязательно
@@reverse:	[SP]	Call(SwapPoints)
		j++	0
		iLOOP	@@reverse


Ещё 7 строчек, жить можно.

И под самый конец этой весёлой процедуры, мы хотим поменять местами точки 1 и 6, а также 4 и 7. То есть, запихнуть "центральные" точки в самый конец массива! Дело в том, что при нахождении матрицы аффинного преобразования мы их использовать не хотим, они в эту логику не вписываются. Так что ещё 4 дурацких строки:

@@skip:	ijk	0x0025	;Inv=0, k=0, i=1, j=5
	[SP]	Call(SwapPoints)
	ijk	0x0086	;Inv=0, k=0, i=4, j=6
	[SP]	Call(SwapPoints)



На этом всё! Эта процедура занимает ещё 20 строк (40 байт), а всего алгоритм ближней дистанции пока упихивается в 103 слова, или 206 байт.

Надо проверить всё это дело, а потом ещё переписать умножение матриц, чтобы можно было ему "скормить" либо умножение матрицы 3х4 на 4х2 (как для дальней дистанции), либо 3х6 на 6х2 (как сейчас). А дальше нахождение крена менять не надо, нахождение масштаба тоже. Разве что вектору другую "экспоненту" приписать...
Tags: ПЛИС, программки, работа, странные девайсы
Subscribe

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 19 comments