-
В процессе размышления о рисовании линии пришёл к мысли, что вычисление ошибки это затратная и не особо полезная работа в том смысле, что это не точки которые нужно записать в память. Если достаточно длинную линию нарисованную алгоритмом Брезенхема поделить на кусочки по 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. В общем для быстрого рисования нужно для каждой линии компилировать свой алгоритм.
-
Как-то я пропустил. Круто, но даже вариант с группировкой по 2 все не соберусь реализовать, хотя уже все придумано/продумано. Причем я созрел только на "тупую" группировку - расчет группируется по 2 и рисование по 2, но рисование каждой точки отдельно с декрементом счетчика и проверкой окончания. В итоге экономия только на пересылках ошибки в A и обратно. Можно еще подумать и сделать рисование линий четной длины + (если нужно) еще одной точки. Но настолько громоздко, что нет никакого желания реализовать это.
-
Не знаю, насколько это может быть полезно для реального кода, но есть мысль, что всю линию можно нарисовать имея код для рисования двух небольших отрезков. Совсем в тривиальном случае мы это делаем рисуя единичные отрезки по горизонтали или диагонали, но такие отрезки можно и укрупнить. Например линию 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
-
Теория ушла далеко вперед, практика сильно отстает.
-
Вложений: 1
Какбыдизерингом легко получить 7 довольно убедительных (особенно на реальном элт тв) оттенков синего вместо штатных 4. Причем с разрешением до 256x256.
-
ivagor, даешь clrs в котором 8 синих строк!
-
https://youtu.be/wdYbeqP5KPs вот типо последние достижения многоцветного zx... интересно потянет ли Вектор эту игру даже просто используя штатные режимы? Что интесно наложения предметов нету вообще, все в своих знакоместах, по идее годится для перевода даже на чисто vt52 терминал
-
bigral, все "нештатные" режимы для игр не годятся, они слишком эзотеричны для нормального использования.
В спектрумовских играх есть чему поучиться. Например, как отбросить несущественные аспекты представления ради достижения цели. Атрибуты-клёш? Сотрем фон, оказывается это смотрится совсем неплохо. У Вектора нет атрибутов, но вычисление наложения спрайта на фон невыносимо медленно и можно было бы хорошо сэкономить, просто стирая фон. Не знаю, сколько игр осталось несделанными просто из-за того, что авторы слишком рано и слишком глубоко закопались в рисование спрайтов.
Что до этой игры и игр вообще, по-моему тут вопрос дизайна в первую очередь: кто-то должен такое придумать. Сделать — это уже вторично. Технически ничего архисложного для Вектора тут не видно. Но если и найдется проблема, всегда же можно найти компромисс, чем-то несущественным пожертвовать ради общего дела.
-
Вложений: 1
Сделал таки вращение проволочного кубика. Хотя строго говоря на экране отображается параллелепипед, т.к. нет коррекции соотношения сторон.
14-14.5 FPS
Самая долгая операция - собственно рисование кубика. Использовал процедуру рисования линии по заветам blackmirrora.
- - - Добавлено - - -
Забыл написать клавиши управления: курсор+F1/F2. TAB - исходное положение.
-
Красота! А отсечение тыльных сторон + модели посложнее планируешь сделать?
