nabbla (nabbla1) wrote,
nabbla
nabbla1

Categories:

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

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

Пока что у нас был алгоритм для дальней дистанции, где мы видим 4 пятна: мишени дальней дистанции 1-3 (МДД1-МДД3) и мишень ближней дистанции (МБД), отдельные элементы которой с такого расстояния сливаются в одно пятно.
TestFrameEnlarged.png

По счастью, часть этапов будут общими для обоих алгоритмов. Алгоритм дальней дистанции состоял из 6 этапов:
1. Нахождение самого отдалённого пятна на изображении (это будет МДД3),
2. Сортировка оставшихся пятен против часовой стрелки, относительно МДД3,
3. Нахождение матрицы аффинного преобразования путём умножения матрицы 3х4 на матрицу 4х2, образованную четырьмя точками - центрами наших пятен.
4. Нахождение крена и выражение его в виде кватерниона, компенсация крена в матрице аффинного преобразования.
5. Нахождение масштаба
6. Нахождение вектора параллельного переноса.

Матрицу аффинного преобразования в алгоритме ближней дистанции будем находить, умножая матрицу 3х6 на матрицу 6х2, т.е из 8 обнаруженных пятен возьмём только "задние" 6, лежащие в одной плоскости. Два вынесенных вперёд нарушают все условия аффинного преобразования, и к тому же одно из них мы можем "потерять", т.к оно перегородит собой одно из 6 при взгляде с экстремального ракурса, неудобно!

Ну а вместо первых 2 пунктов у нас, увы, появляется целых 5:


1. Нахождение ДВУХ самых отдалённых друг от друга точек,
2. Сортировку остальных точек по величине проекции на ось, образованную самыми отдалёнными точками,
3. Нахождение "границы водораздела" (только если обнаружено 7 точек. Если их 8, то всё понятно, 4 слева и 4 справа),
4. Нахождение вынесенных вперёд мишеней (они могут "гулять" в очень широких пределах при изменении ракурсов),
5. Проверка разворота на 180 градусов.

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

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

У нас в памяти уже был сделан "задел" в своё время:

Points2D:
;дистанция 300 метров, все углы нулевые
Fx0	Int16	53	
Fy0	Int16	-7
Fx1	Int16	480	
Fy1	Int16	-30
Fx2	Int16	-539	
Fy2	Int16	-302
Fx3	Int16	400	
Fy3	Int16	-997
Fx4	Int16	-32768
Fy4	Int16	?
Fx5	Int16	-32768
Fy5	Int16	?
Fx6	Int16	-32768
Fy6	Int16	?
Fx7	Int16	-32768
Fy7	Int16	?


Давайте сразу поставим сюда реалистичные числа. Здесь формат представления Q10.6, то есть от -512 до ≈512, 10 целочисленных бит и 6 дробных, что позволяет указывать координаты с точностью до 1/64 пикселя:

;дистанция 0,5 метра, самое мясо
Fx0	Int16	14528	
Fy0	Int16	-2944
Fx1	Int16	-14016	
Fy1	Int16	-7872
Fx2	Int16	29376	
Fy2	Int16	-11456
Fx3	Int16	22720	
Fy3	Int16	-13568
Fx4	Int16	-18752
Fy4	Int16	-20736
Fx5	Int16	-25664
Fy5	Int16	-20800
Fx6	Int16	14848
Fy6	Int16	-23488
Fx7	Int16	-9408
Fy7	Int16	-27648


Точки приведены по мере прохождения списка, получается от конца к началу:


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

Ну ладно, а для начала мы ищем две наиболее отдалённые точки, т.е два индекса, а затем переносим их в конец списка.

Как ни странно, найти ДВЕ наиболее отдалённые точки - вычислительно проще, чем одну!

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

- будет 3 вложенных цикла. Регистр j будет перебирать первую точку (от 1 до 7), регистр i - вторую точку (от 0 до 6), регистр k - выбирать между координатой X и Y (т.е от 0 до 1).
- Для доступа к памяти точек, Points2D, придётся задействовать два регистра, например, X и Y. Они будут сдвинуты на 2, это сильно упростит индексацию и возню с регистрами.
- Нужно держать в памяти самую большую пока что достигнутую дистанцию, и два индекса, при которых она получилась. Для этого мы могли бы использовать регистр Z, а также "локальные переменные" [SP] и [SP+1].
- Где-то нужно хранить промежуточные вычисления для выражения (Yj-Yi)2 + (Xj-Xi)2. Скажем, мы загрузим в аккумулятор Yj, вычтем Yi, результат возведём в квадрат - и куда-то его нужно сунуть. Так-то у нас вроде есть регистр C, но следующее возведение в квадрат сотрёт его содержимое!

По такому случаю можно "реанимировать" команду ijk, которая упихивает три 5-битных регистра i,j,k и однобитный Inv в 16 бит на шину, либо из шины раскидывает биты по этим 4 регистрам. Основным назначением предполагалось быстрое занесение регистров в стек во время вызова процедуры, но и тут оно пригодится.

Давайте быстренько глянем, что там с таймингами, если ijkEnabled = 1.


Боль... Но это мы в своё время исправим. Не хочу уродовать код лишь потому, что сходу тайминги не выполнились.

В общем, вот наш код:

Find2Points proc
		X		Points2D	;используется с индексом i, чтобы выбрать точки 0..6
		Z		Fx1		;используется с индексом j, чтобы выбрать точки 1..7
		;в Y будем хранить индексы, сразу оба (для этого нужно хотя бы 8 бит).
		;в [SP] будем хранить текущую сумму,
		;в [SP+1] максимальную отдалённость на данный момент
			
		j		6		;в дальнейшем будет выбор между 5 и 6 (если рассматривать 7 найденных точек вместо 8)
		[SP+1]		0		;обнуляем. А "X" (индексы) можно не обнулять, заведомо будут занесены на первой же итерации		
@@j_loop:	i		j		;сравниваем точку под индексом j+1 со всеми остальными, чей индекс меньше j+1
@@i_loop:	k		1
		[SP]		0		;сравниваем с точкой i. Начинаем считать квадрат расстояния
@@k_loop:	Acc		[Z+2j+k]	;это Fy[j+1], если k=1, или Fx[j+1], если k=0
		SUB		[X+2i+k]	;это Fy[i], если k=1, или Fx[i], если k=0
		SQRD2		Acc		;разность возвести в квадрат
		ADD		[SP]
		[SP]		Acc
		kLOOP		@@k_loop
		;здесь у нас есть квадрат дистанции, лежит и в [SP], и в Acc. Это удобно :)
		SUB		[SP+1]	;сравниваем с самой большим квадратом дистанции на данный момент
		JL		@@skip	;меньше, не интересно
		;обновим значение дальности и индексов, при которых она достигается
		[SP+1]		[SP]		;программисты на ассемблерах x86, AVR и ARM должны завидовать, что у нас такое можно!
		Y		ijk		;и такому
@@skip:		iLOOP		@@i_loop
		jLOOP		@@j_loop
		
		;индексы найдены, теперь нужно переместить эти точки куда положено
		ijk		Y
		;начнём с индекса j, с ним правильное смещение даёт Z. А для X поставим i = 7 (запихаем в самую последнюю, это ПРИНЦИПИАЛЬНО)
		i		7
		[SP]		Call(SwapPoints)
		;теперь нужно вытащить индекс i
		ijk		Y
		;с ним правильное смещение даёт X. А чтобы [Z+2i] указывало на точку с индексом 6, нужно выставить j = 5 (Z сдвинуто на 1 вперёд)
		j		5
		[SP]		Call(SwapPoints)
		
Find2Points endp


;используется для алгоритмов и ближней, и дальней дистанций

;меняет местами точку с базой Z, инд. j  и базой X, инд. i
;изменяет регистр k (по окончании выходит 0), и C
;вызов через [SP]  Call(SwapPoints), т.е без инкремента стека
SwapPoints	proc
	k		1
	NOP		0	;хотим избежать warning'ов
@@swap:	C		[Z+2j+k]
	[Z+2j+k]	[X+2i+k]
	[X+2i+k]	C
	kLOOP		@@swap
	JMP		[SP]
SwapPoints	endp	


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

Он компилируется, но выползает один Hazard:

Конфликт (Hazard) между командами [SP] и [Z+2j+k], файл ShortRangeAffine.asm, процедура Find2Points, строки:
		[SP]		0		;сравниваем с точкой i. Начинаем считать квадрат расстояния
@@k_loop:	Acc		[Z+2j+k]	;это Fy[j+1], если k=1, или Fx[j+1], если k=0
Вставляем NOP


Всё из-за нашего нежелания поставить два формирователя эффективного адреса. Увы, если мы поменяем "[SP] 0" с "k 1", то Hazard всё равно останется, только в этот раз Read-After-Write по регистру k, т.е первый раз [Z+2j+k] применит старое значение k, не успеет его вовремя выставить.


Проверять будем уже в понедельник. Я уже смирился, что к 12-му у меня макет ещё не заработает, да и дурное это дело поспевать к определённым датам.

На выходных, если получится, попробую доделать "мобильную" мишень дальней дистанции.
Tags: ПЛИС, программки, работа, странные девайсы
Subscribe

Recent Posts from This Journal

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 0 comments