Демо эффекты для Вектора

[ivagor]

У меня после разворота крутых циклов 256 линий от верхнего края до нижнего стали рисоваться за 48 кадров вместо 64, а после разворота пологих циклов, но без группировки точек 256 линий от левого края до правого стали рисоваться за 48 кадров вместо 73.

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

[Advertiser]

[blackmirror]

У меня разворот крутого цикла был сделан так:

LineYn0: SetPix 128;продолжнение цикла здесь
        IncY
        Err+=dy-dx
        jp nc,LineYn1
LineYp0: SetPix 128 ;точка входа здесь
        IncY
        Err-=dx
        jp nc,LineYp0;крутимся рисуя вертикальный отрезок
LineYn1: SetPix 64
        IncY
        Err+=dy-dx
        jp nc,LineYn2;нарисовав точку нового отрезка идём дальше или 
LineYp1: SetPix 64
        IncY	
        Err-=dx
        jp nc,LineYp1;крутимся рисуя следующий
LineYn2:
	...
LineYn8:
        IncH		;x
        Dec Cnt8 ;изначально=(x2-x1-8)/8
        Jp nz,LineYn0

[ivagor]

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

В итоге:
1. Бенч svofski
1.1. Без разворотов - 323 линии/секунду
1.2. Развернутый пологий - 355 линий/секунду (+285 байт по сравнению с 1.1)
1.3. Развернутые пологий и крутой - 369 линий/секунду (+588 байт по сравнению с 1.1)

2. По результатам рисования 256 пологих линий (x0=0, y0=0; x1=255, y1=0..255)
2.1. Без разворотов - 113 линий/секунду
2.2. Развернутый пологий - 145 линий/секунду

3. По результатам рисования 256 крутых линий (x0=0, y0=0; x1=0..255, y1=255)
3.1. Без разворотов - 126 линий/секунду
3.2. Развернутый крутой - 139 линий/секунду

[svofski]

> до 220 или 380 далеко

Уже нет!

[ivagor]

Про 380 я помню. Если с допингом (ВМ1/8085/Z80), то уже больше. А для 8080 надо реализовать оставшиеся идеи blackmirrorа, что несколько сложно.

[blackmirror]

В процессе размышления о рисовании линии пришёл к мысли, что вычисление ошибки это затратная и не особо полезная работа в том смысле, что это не точки которые нужно записать в память. Если достаточно длинную линию нарисованную алгоритмом Брезенхема поделить на кусочки по n точек, то различных кусочков для данной линии будет встречаться n+1. То есть если мы рисуем линию кусочками по 4 точки, нам нужно 5 вариантов кода для рисования кусочков данной линии, и хитрая схема переходов между ними. Схема переходов для линий скорее горизонтальных чем вертикальных (|dy|<|dx|) выглядит так:

1/8	0->01248	1248->0			
1/7	0->1248	124->0	8->01		
1/6	0->248	12->0	4->01	8->12	
1/5	0->48	1->0	2->01	4->12	8->24
1/4	1->01	2->12	4->24	8->48	0->8
2/7	1->12	9->1	2->24	4->48	8->89
1/3	2->24	1->2	4->489	9->12	8->9
3/8	2->459	5->2	4->9A	A->4	9->24
2/5	2->59	5->2	4->9A	9->24	A->45
3/7	2->9A	5->24	9->45	A->59	4->A
1/2	5->245	9->5	A->59A	24->A	
4/7	5->56A	BD->5	A->ABD	6->A	
3/5	5->6A	B->5	6->AB	A->BD	D->56
5/8	5->AB	6->BD	B->56	D->6A	A->D
2/3	6->BD	B->56	5->B	D->6AB	A->D
5/7	6->DE	7->6	B->67B	D->BD	E->D
3/4	7->67	B->7B	D->BD	E->DE	6->E
4/5	7->7B	F->7	B->BD	D->DE	E->EF
5/6	7->BD	B->DE	D->EF	F->7B	E->F
6/7	7->DE	B->EF	F->7BD	DE->F	
7/8	7->EF	F->7BDE	BDE->F		
8/8	F->7BDEF	7BDE->F

Здесь 1/8 означает что данная схема переходов работает для линий с отношением dy/dx от 0/8 до 1/8, то есть почти горизонтальных, 1/7 для линий от 1/8 до 1/7, и так далее, 8/8 для линий от 7/8 до 8/8 то если почти диагональных. Кусочек линии из 4х точек закодирован 16-ричной цифрой, где нулевой бит означает смещение вправо после рисования точки, а 1 смещение по диагонали: 0 - рисуем 4 точки по горизонтали и смещаемся вправо для следующего кусочка, 1 - рисуем 4 точки по горизонтали и смещаемся по диагонали, F - рисуем 4 точки по диагонали и смещаемся по диагонали, E - рисуем 4 точки по диагонали и смещаемся вправо, 5-рисуем две точки, смещаемся по диагонали, рисуем еще 2 точки и опять смещаемся по диагонали, ну и далее в том же духе.
Если посмотреть на строку помеченную как 1/5, то можно увидеть, что после рисования кусочка из 4 точек, нужно сделать 1 условный переход, чтобы выяснить какой из двух кусочков рисовать дальше. Есть правда и такие строки как 1/8 или 8/8 где после рисования горизонтального или диагонального кусочка есть целых 5 альтернатив, и для их выбора требуется 2-3 условных перехода, но зато только одна альтернатива после рисования любого другого кусочка, и в среднем на одну точку будет приходиться раза в два-три меньше сравнений и переходов.
Конечно такое количество вариантов закодировать нереально, меня хватило только на 1/8 и 8/8 как самые простые и понятные, и проверка показала, что данные варианты рисуют 256 почти горизонтальных линий за время от 13 до 20 кадров(против от 22 до 25), почти диагональные линии за время от 35 до 32 кадров против от 39 до 41 у кода с группировкой 4x сравнений и 4х рисований точек, не говоря уже про варианты с вращением маски, которые требуют кадров по 50. В общем для быстрого рисования нужно для каждой линии компилировать свой алгоритм.

[ivagor]

Как-то я пропустил. Круто, но даже вариант с группировкой по 2 все не соберусь реализовать, хотя уже все придумано/продумано. Причем я созрел только на "тупую" группировку - расчет группируется по 2 и рисование по 2, но рисование каждой точки отдельно с декрементом счетчика и проверкой окончания. В итоге экономия только на пересылках ошибки в A и обратно. Можно еще подумать и сделать рисование линий четной длины + (если нужно) еще одной точки. Но настолько громоздко, что нет никакого желания реализовать это.

[blackmirror]

Не знаю, насколько это может быть полезно для реального кода, но есть мысль, что всю линию можно нарисовать имея код для рисования двух небольших отрезков. Совсем в тривиальном случае мы это делаем рисуя единичные отрезки по горизонтали или диагонали, но такие отрезки можно и укрупнить. Например линию dy/dx=144/233(числа Фибоначчи) можно рисовать парой отрезков /-/ и /-/-/, здесь "-" это движение вправо, а "/" это движение по диагонали. Можно все отрезки из трёх точек прицепить к отрезкам из 5 точек и рисовать линию отрезками в 5 и 8 точек или пойти дальше и рисовать линию отрезками в 8 и 13 точек. Для других линий отрезки будут другие, например для рисования линии 92/255 можно использовать отрезки -/--/-/--/- и -/-, хотя тут тоже можно рисовать отрезками в 11 и 14 или в 11 и 25 точек. Для линии 197/252 можно использовать отрезки //-///-// и //-//. Для почти горизонтальных или почти диагональных линий базовые отрезки могут получаться слишком длинные и там могут потребоваться другие алгоритмы.
Общий алгоритм выбора отрезков пока еще не совсем ясен, но если взять целые числа, умножить на dy, вычислить остаток от деления на dx, и вычесть dx если остаток получился более dx/2, то мы получим табличку насколько изменяется ошибка при рисовании отрезка длиной n точек. Для первого отрезка нам подойдёт n1, которое даёт минимальное изменение ошибки по сравнению со всеми предыдущими, а для второго n2 которое даёт еще меньшее изменение ошибки и кроме этого в другую сторону. Для 144/233 табличка ошибок и подходящие для рисования отрезки выглядят так:

1	-89	/
2	55	/-
3	-34	/-/
4	110
5	21	/-/-/
6	-68
7	76
8	-13	/-/-//-/
9	-102
10	42
11	-47
12	97
13	8	/-/-//-//-/-/
14	-81
15	63
16	-26
17	-115
18	29
19	-60
20	84
21	-5	/-/-//-//-/-//-//-/-/
22	-94

[ivagor]

Теория ушла далеко вперед, практика сильно отстает.

[ivagor]

Какбыдизерингом легко получить 7 довольно убедительных (особенно на реальном элт тв) оттенков синего вместо штатных 4. Причем с разрешением до 256x256.