Алгоритм растеризации отрезков Брезенхема на языке Ассемблера
Ассемблер. Небессмысленный, но беспощадный.
Вступление
Итак, что же такое алгоритм Брезенхема и растеризация. Как только машины начали использоваться для работы с графикой, встала проблема рисования изображений: на растровом устройстве вывода, коим является монитор, прямую нарисовать нельзя в виду его дискретности. С тех пор появилось достаточное количество соответствующих алгоритмов, из них самый интуитивный — ЦДА(DDA), цифровой дифференциальный анализатор. Но он использует в работе операции с плавающей запятой, что резко ухудшает производительность. Чуть погодя сотрудником IBM Джеком Е. Брезенхемом был предложен целочисленный алгоритм, выполняющий эту же задачу. Алгоритм решает, какой пиксель находится ближе к прямой, и какой пиксель надо засветить, корректируя себя по ошибке. Как отмечено ранее, алгоритм использует только целочисленные операции, а значит, обеспечивает выигрыш по производительности.
За более подробной информацией на этот счёт есть Википедия(Брезенхема алгоритм), ещё раз Википедия(ЦДА) и книга Д. Роджерса «Алгоритмические основы машинной графики».
Алгоритм в схемах
Схема алгоритма достаточно проста и представлена ниже:
Блок-схема:
По блок-схеме строить ассемблерный код трудновато, посему есть смысл нарисовать линейную схему:
Последняя схема даёт уже лучшее представление о том, какой код будет на выходе. По крайней мере, она выявляет положения важных опорных точек.
В обеих схемах защита от дурака некорректных действий персонала не показана, но подразумевается, что она стоит перед блоком OP0/INIT.
Реализация
Позволю себе небольшое предисловие перед тем, как будет код.
Расчитывал я это реализовать за 3 часа, но реализация растянулась на 5. В начале работы я долго бился с глупой ошибкой: не зря переменные названы dfx и dfy именно с буквой f(differential) — когда переменная приращения x звалась dx, я долго не мог понять, почему компилятору не нравится её объявление, и только спустя минут 20 вспомнил, что DX — двухбайтный кусок регистра EDX. Не считая дальнейших описок sgx/dfx[sgy/dfy], сильно тормозящих работу ошибок не было, но были трудности с арифметикой. В операциях OP4, OP5, OP7, OP8 мне пришлось вбивать костыли в код, и вручную увеличивать/уменьшать значения зависимо от определённого вручную знака sgx/sgy. В итоге так и не стало понятно, почему выходят сбои при сложении чисел, одно из которых отрицательное. Вероятно, есть более элегантный способ обойти это, нежели использованный. Но долго думать не хотелось.
Начнём с того, что C–шный прототип функции выглядит так:
extern "C" {
void rasterize_bresenham( long pt1x, long pt1y, long pt2x, long pt2y, void* bufptr, long bufwidth, long bufheight );
};
Здесь:
- pt1x, pt1y, pt2x, pt2y — абсциссы и ординаты точек начала и конца соответственно;
- bufptr — указатель на буфер байтов;
- bufwidth, bufheight — размеры буфера в длину и ширину.
Функция при работе своей записывает в буфер байты 0x1h в те места, где должны быть точки, полагая, что все остальные обнулены.
Итак, вот он — код. Дальнейшие комментарии, я думаю, излишни, в виду того, что ими тут дополнена почти каждая строка.
.model flat, c
.386
.data
SGN EQU 80000000h
NEGSGN EQU 0FFFFFFFEh
x dd 0
y dd 0
xch db 0
err dd 0
dfx dd 0
dfy dd 0
sgx dd 0
sgy dd 0
.code
rasterize_bresenham PROC USES EAX EBX ECX EDX, pt1x:dword, pt1y:dword, pt2x:dword, pt2y:dword, buf_ptr:dword, buf_wid:dword, buf_hei:dword
__CHECK:
; === проверка координат на выход за пределы буфера
; == x1
__CHECK_x1:
mov edx, pt1x ; достаём pt1x в EDX
cmp edx, 0 ; проверяем координату на знак
jge __CHECK_x1_1 ; если >= 0, то следующая проверка
ret
__CHECK_x1_1:
cmp edx, buf_wid ; сравниваем с широной буфера
jl __CHECK_x2 ; если меньше, то проверяем дальше
ret
; = x2
__CHECK_x2:
mov edx, pt2x ; достаём pt2x в EDX
cmp edx, 0 ; проверяем координату на знак
jge __CHECK_x2_1 ; если >= 0, то следующая проверка
ret
__CHECK_x2_1:
cmp edx, buf_wid ; сравниваем с широной буфера
jl __CHECK_y1 ; если меньше, то проверяем дальше
ret
; == y1
__CHECK_y1:
mov edx, pt1y ; достаём pt1y в EDX
cmp edx, 0 ; проверяем координату на знак
jge __CHECK_y1_1 ; если >= 0, то следующая проверка
ret
__CHECK_y1_1:
cmp edx, buf_hei ; сравниваем с широной буфера
jl __CHECK_y2 ; если меньше, то проверяем дальше
ret
; == y2
__CHECK_y2:
mov edx, pt2x ; достаём pt2y в EDX
cmp edx, 0 ; проверяем координату на знак
jge __CHECK_y2_1 ; если >= 0, то следующая проверка
ret
__CHECK_y2_1:
cmp edx, buf_hei ; сравниваем с широной буфера
jl __INIT ; если меньше, то переходим к инициализации
ret
__INIT:
; === сбрасываем значения переменных
mov sgx, 0
mov sgy, 0
mov xch, 0
; === достаём значения из аргументов в переменные
mov edx, pt1x ; достаём pt1x в EDX
mov x, edx ; отправляем EDX в x
mov edx, pt1y ; достаём pt1y в EDX
mov y, edx ; отправляем EDX в y
; === считаем x2 - x1
mov edx, pt2x ; достаём pt2x в EDX
sub edx, x ; вычитаем x из EDX
mov dfx, edx ; кладём результат в dfx
; === вычисляем dfx и sgx
cmp edx, 0 ; проверяем, что за число в EDX
jg __l_sgx_g ; если > 0, то переходим
jz __l_sgx_cont ; если 0, то действие не требуется
neg edx ; меняем знак
mov dfx, edx ; возвращаем полученное в dfx
mov sgx, NEGSGN ; отправляем -1 в sgx
jmp __l_sgx_cont ; уходим на продолжение
__l_sgx_g:
mov sgx, 1 ; устанавливаем sgx в 1
__l_sgx_cont:
; === считаем y2 - y1
mov edx, pt2y ; достаём pt2y в EDX
sub edx, y ; вычитаем x из EDX
mov dfy, edx ; кладём результат в dfx
; === вычисляем dfy и sgy
cmp edx, 0 ; проверяем, что за число в EDX
jg __l_sgy_g ; если > 0, то переходим
jz __l_sgy_cont ; если 0, то действие не требуется
neg edx ; меняем знак
mov dfy, edx ; возвращаем полученное в dfy
mov sgy, NEGSGN ; отправляем -1 в sgy
jmp __l_sgy_cont ; уходим на продолжение
__l_sgy_g:
mov sgy, 1 ; устанавливаем sgx в 1
__l_sgy_cont:
__IF0:
cmp edx, dfx ; сравниваем dfx и EDX(dfy)
jle __OP2 ; если dfy <= dfx, то операции не требуются
xchg dfx, edx ; обмениваем значениями EDX(dfy) и dfx
mov dfy, edx ; восстанавливаем в dfy значение из EDX(dfx)
mov xch, 1 ; запоминаем, что был перенос
__OP2:
; === вычисляем err [ err = 2*dfy - dfx ]
mov err, 0 ; сбрасываем err в 0
mov edx, dfy ; отправляем в EDX dfy
shl edx, 1 ; сдвигаем EDX влево на 1 бит(умножение на 2)
add err, edx ; прибавляем EDX(dfy*2) к err
mov edx, dfx ; отправляем в EDX dfx
sub err, edx ; вычитаем EDX(dfx) из err
; === подготовка к главному циклу
mov ecx, dfx ; устанавливаем счётчик на dfx
__IF1:
; === начало основного цикла
cmp ecx, 0 ; сравниваем ECX и 0
jle __OP11 ; если ECX < 0, то на выход
__MAINLOOP:
__OP3:
; == вычисляем требуемое положение в буфере и кладём точку
mov ebx, buf_ptr ; кладём в базовый регистр ссылку на буфер
mov eax, buf_wid ; кладём длину строки буфера в EAX
mul y ; множим на ординату
add ebx, eax ; складываем значение EBX с EAX
add ebx, x ; прибавляем абсциссу
mov byte ptr [ebx], 1 ; кладём 1 в буфер по адресу точки
__IF2:
; == циклически вычисляем значение ошибки
cmp err, 0 ; сравниваем err с 0
jl __IF4 ; если err < 0, то переходим дальше
__IF3:
cmp xch, 0 ; проверяем наличие обмена
jg __OP5 ; если был обмен, то на __OP5
__OP4:
cmp sgy, 0 ; сравниваем знак y с 0
jg __OP4_g ; если > 0, то переход
jz __OP6 ; если 0, то ничего не делать
dec y ; иначе (если < 0), уменьшаем на 1
jmp __OP6
__OP4_g:
inc y ; увеличиваем на 1
jmp __OP6
__OP5:
cmp sgx, 0 ; сравниваем знак x с 0
jg __OP5_g ; если > 0, то переход
jz __OP6 ; если 0, то ничего не делать
dec x ; иначе (если < 0), уменьшаем на 1
jmp __OP6
__OP5_g:
inc x ; увеличиваем на 1
__OP6:
; == вычисляем приращение ошибки [ err -= 2 * dfx ]
mov edx, dfx ; забираем dfx в EDX
shl edx, 1 ; сдвигаем EDX влево на 1 бит(умножение на 2)
sub err, edx ; вычитаем из err EDX(2*dfx)
jmp __IF2 ; возвращаемся обратно
; == конец цикла вычисления ошибки
__IF4:
cmp xch, 0 ; проверяем наличие обмена
jnz __OP8 ; если был обмен, то на __OP8
__OP7:
cmp sgx, 0 ; сравниваем знак x с 0
jg __OP7_g ; если > 0, то переход
jz __OP9 ; если 0, то ничего не делать
dec x ; иначе (если < 0), уменьшаем на 1
jmp __OP9
__OP7_g:
inc x ; увеличиваем на 1
jmp __OP9
__OP8:
cmp sgy, 0 ; сравниваем знак y с 0
jg __OP8_g ; если > 0, то переход
jz __OP9 ; если 0, то ничего не делать
dec y ; иначе (если < 0), уменьшаем на 1
jmp __OP9
__OP8_g:
inc y ; увеличиваем на 1
__OP9:
; == вычисляем приращение ошибки [ err += 2 * dfy ]
mov edx, dfy ; забираем dfy в EDX
shl edx, 1 ; сдвигаем EDX влево на 1 бит(умножение на 2)
add err, edx ; прибавляем к err EDX(2*dfy)
__OP10:
dec ecx ; ECX--
jmp __IF1 ; зацикливаемся
; === конец основного цикла
__OP11:
ret ; возврат
rasterize_bresenham ENDP
end
Код несколько перегружен метками, но я решил не удалять их, для сохранения единой стилизации и логики построения. На выходном результате количество меток, вообще говоря, никак не скажется.
Оговорюсь по поводу умножения: сдвиг влево на 1 бит равносилен умножению на 2.
И, наконец, результат работы этого кода:
Код написан на MASM и расчитан на подключение к программам, основной язык которых C.
Василий «DarkWolf» Юмашов, 5 X 2011