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