Рисование линий на экранеПроведение линий подразумевает установку на экране всех точек, принадлежащих отрезку. Сложность при рисовании линии в том, что точки из которых мы ее строим создавали иллюзию прямой. На экране абсолютно точно можно нарисовать только вертикальные, горизонтальные и 1:1 диагональные линии. Если у нас установлен 13h графический режим (320x200x256), то горизонтальную линию рисуют следующими командами Код (ASM): ;предварительные установки PUSH 0A000h POP ES; позиционируем ES на область видеопамяти MOV DI,X ; в DI координаты начальной точки по X MOV AX,320; длина строки экрана MUL Y; умножаем на Y ADD DI,AX; и складываем с X MOV AL,COLOR; цвет линии ; рисуем горизонтальную линию MOV CX,N; длина линии REP STOSB Вертикальную линию обычно рисуют циклом Код (ASM): MOV CX,N; длина линии A1: MOV ES:[DI],AL; рисуем точку на строке ADD DI,320; переход на следующую строку LOOP A1 диагональную линию с наклоном влево можно нарисовать циклом Код (ASM): MOV CX,N; длина линии A1: MOV ES:[DI],AL; рисуем точку на строке ADD DI,319; переход на следующую строку LOOP A1 диагональную линию с наклоном вправо — циклом Код (ASM): MOV CX,N; длина линии A1: MOV ES:[DI],AL; рисуем точку на строке ADD DI,321; переход на следующую строку LOOP A1 Первое, все остальные линии рисуются только приближенно. Второе, что бы быть полезной, функция рисования линии должна работать быстро. Давайте рассмотрим случай, когда горизонтальная проекция линии длиннее вертикальной и угол наклона линии отрицательный. Например, нарисуем линию направленную из точки (0, 0) в точку (55, 12). Программа должна провести линию в 55 пикселя по горизонтали и 12 пикселей по вертикали. Поскольку наклон линии находится в пределах 55/12=4,5833…, то можно точно сказать что линия будет состоять из чередующихся рядов точек (прогонов) из 4 (минимальный прогон) и 5 точек (максимальный прогон). Как разместить прогоны с минимальной и максимальной длиной? Остаток деления 55 на 12 равен 7, равномерно раскидаем эти дополнительные 7 точек. На каждый шаг по оси Y мы ставим, по меньшей мере, 4 пикселя вдоль оси X. После этого нам нужно решить, ставить ли пятый или переходить на следующую координату по оси Y. Если мы подсчитаем, какую ошибку отклонения мы накопили, и если ошибка накопления превышает 0,5 пикселя — тогда нам нужен в отрезке дополнительный пиксель. Длина минимального отрезка по оси X на один шаг по оси Y составляет XDelta/YDelta=4,5833… Обозначим XDelta%YDelta получение остатка от деления XDelta на YDelta, ошибка накопления в каждом прогоне составляет (XDelta%YDelta)/YDelta=7/12=0,5833… дополнительный пиксел потребуется если (XDelta%YDelta)/YDelta — ½ > 0 (XDelta%YDelta) — YDelta /2 > 0 (XDelta%YDelta)х2 — YDelta > 0 то есть, на каждом шаге по оси Y накапливается ошибка (XDelta %YDelta)x2. Если ошибка достигнет одного пикселя или больше, то мы добавим к прогону дополнительный пиксель и вычтем из значения ошибки YDelta*2 Теперь попробуем нарисовать линию — на каждый шаг по оси Y будем ставить по 4 или 5 точек по оси X. Если соединить центры наших прогонов, то окажется, что наша линия смещена на 2 или 3 точки от идеальной линии. Чтобы точки максимально близко ложились к идеальной линии применяется балансировка прогонов. Для этого берут один максимальный прогон и распределяют его равномерно между первым и последним отрезком, чтобы концы линии стали симметричными. Ниже приводится листинг программы реализующее построение линии по алгоритму Брезенхейма с переменной длиной отрезков. Код (ASM): .286 .model tiny .code org 100h start: SCREEN_WIDTH equ 320;ширина экрана в режиме 13h SCREEN_SEGMENT equ 0A000h parms struc dw ? ; сохраненный в стеке ВР dw ? ; сохраненный в стеке адрес возврата XStart dw ? ; начальная координата Х линии YStart dw ? ; начальная координата Y линии XEnd dw ? ; конечная координата Х линии YEnd dw ? ; конечная координата Y линии Color db ? ;цвет линии, рядом с ним пустой байт, db ? ;потому что Color в стеке длиной в слово parms ends ; Локальные переменные. AdjUp equ -2;ошибку накопления подправляем на каждом шаге AdjDown equ -4;ошибку накопления уменьшаем, когда превышен порог WholeStep equ -6 ; минимальная длина прогона XAdvance equ -8 ;1 или -1, направление, в котором идем по оси Х LOCAL_SIZE equ 8 mov ah,0Fh ;запомнить видеорежим int 10h mov videor,al mov ax,13h int 10h;установили видеорежим 256x320x200 push 5 ;Color push 12 ;YEnd push 55 ;XEnd push 0 ;YStart push 0 ;XStart call LineDraw ;рисуем линию mov ah,0 ;ждем нажатия на клавишу int 16h mov ax,word ptr videor ;восстановить видеорежим int 10h int 20h ;выход из программы videor db 0,0 LineDraw proc near;универсальная процедура для рисования линий push bp ; сохраним стек вызывающей программы mov bp,sp ;спозиционируемся на стек sub sp,LOCAL_SIZE ; выделим место для локальных переменных push si ; сохраним регистровые переменные push di push ds ; сохраним DS ;Рисуем сверху вниз,чтобы уменьшить число сравнений и ;чтобы получить одни и те же точки линий с ;одинаковыми координатами. mov ax,[bp].YStart cmp ax,[bp].YEnd jle LineIsTopToBottom xchg [bp].YEnd,ax;поменяем местами координаты линии mov [bp].YStart,ax mov bx,[bp].XStart xchg [bp].XEnd,bx mov [bp].XStart,bx LineIsTopToBottom: mov dx,SCREEN_WIDTH ;Установим DI на первый пиксель mul dx ;для отображения.YStart*SCREEN_WIDTH mov si,[bp].XStart mov di,si ; DI=YStart*SCREEN_WIDTH+XStart add di,ax ; в DI смещение первого пикселя ; Определим, до каких пор идти по вертикали. mov cx,[bp].YEnd sub cx,[bp].YStart ;СХ = YDelta ;Определим, идти влево или вправо и до каких пор идти ;по горизонтали. По ходу дела выделим рисование ;вертикальных линий в целях ускорения, а также во ;избежание предельных случаев и деления на 0. mov dx,[bp].XEnd sub dx,si ;XDelta jnz NotVerticalLine;XDelta = 0 означает ;вертикальную линию push SCREEN_SEGMENT;установим DS:DI на первый pop ds ;байт для отображения mov al,[bp].Color VLoop: mov [di],al add di,SCREEN_WIDTH loop VLoop jmp Done
Код (ASM): ; Обработка горизонтальных линий. IsHorizontalLine: push SCREEN_SEGMENT;установим pop es ;ES:DI на первый байт для отображения mov al,[bp].Color; сдублируем старший байт mov ah,al ;для пословного вывода and bx,bx ; слева направо? jns DirSet ;да sub di,dx ; обработка движения справа налево, ; спозиционируемся на левый край линии DirSet: mov cx,dx inc cx ; число пикселей для отображения shr cx,1 ;число слов для отображения rep stosw ; обработаем как можно больше слов adc cx,cx rep stosb; обработаем нечетный байт, если jmp Done; таковой имеется ; Обработка диагональных линий. IsDiagonalLine: push SCREEN_SEGMENT;установим DS:DI на первый pop ds ;байт для отображения mov al,[bp].Color add bx,SCREEN_WIDTH ;пройдем расстояние от ; одного пикселя до следующего DLoop: mov [di],al add di,bx loop DLoop jmp Done NotVerticalLine: mov bx,1;начинаем слева направо, ; так что XAdvance=1 флаги не изменяются jns LeftToRight ; проход слева направо neg bx;проход справа налево, так что ;XAdvance = -1 neg dx ; модуль XDelta LeftToRight: ; Обработка горизонтальных линий. jcxz IsHorizontalLine ;YDelta = 0? да ; Обработка горизонтальных линий. cmp cx,dx ; YDelta = XDelta? jz IsDiagonalLine ;да ;Определим, какая из осей основная, а какая вспомогательная. cmp dx,cx jb YMajor;Линия с основной осью Х (горизонтальная проекция больше вертикальной). XMajor: push SCREEN_SEGMENT; установим ES:DI на pop es ;первый байт для отображений and bx,bx ;слева направо? jns DFSet ;да, CLD уже установлен std ;справа налево, так что рисуем в обратном направлении DFSet: mov ax,dx ;XDelta sub dx,dx; подготовим для деления div cx ;AX = XDelta/YDelta;(минимальное число пикселей в прогоне этой линии) ;DX=XDelta%YDelta mov bx,dx;ошибку накопления подправляем при каждом шаге по оси Y add bx,bx ;используется для индикации, не нужен ли дополнительный пиксель в прогоне, чтобы округлить mov [bp].AdjUp,bx;нецелые шаги вдоль оси Х при 1-пиксельных шагах вдоль оси Y mov si,cx;ошибку накопления подправляем, когда ее add si,si ;значение превышает допустимый порог ;используем это для определения, необходимо ли сделать шаг по оси Х mov [bp].AdjDown,si ;Начальная ошибка накопления отражает начальный шаг 0,5 вдоль оси Y. sub dx,si ;(XDelta % YDelta) - (YDelta * 2), DX - начальная ошибка накопления ;Первый и последний прогоны являются неполными, потому что перемещение по оси Y идет на 0,5,а не ;на 1.Разделим один полный прогон плюс начальный пиксель между первым и последним прогонами. mov si,cx ;SI = YDelta mov cx,ax ;шаг (минимальная длина прогона) shr cx,1 inc cx ;счетчик начального пикселя=(шаг/2)+1 (подправим позже). ;Это также счетчик пикселей в последнем прогоне push cx;запомним счетчик пикселей в последнем прогоне. Если основная длина прогона четная, а ;дробная часть отсутствует, то у нас есть бесхозный пиксель, который можно определять либо ;в первый, либо в последний прогон, вот давайте и определим этот пиксель в последний прогон. Если ;число пикселей в прогоне нечетно, то у нас есть пиксель, который нельзя определить ни в первый, ;ни в последний прогон, так что добавим, 0,5 к ошибке накопления чтобы текущий пиксель ;обрабатывался стандартным циклом рисования прогона. add dx,si ;положим нечетную длину, добавим ;YDelta к ошибке накопления (добавим 0,5 пикселя к ошибке накопления) test al,1 ; четна ли длина прогона? jnz XMajorAdjustDone;нет, и тогда все уже готово sub dx,si ; длина четна поэтому проверим ошибку,. and bx,bx ; 0 или нет? jnz XMajorAdjustDone ;нет (проверять длину на четность смысла нет, так как только что это уже dec cx; было проделано) оба условия удовлетворены, делаем прогон 1 короче XMajorAdjustDone: mov [bp].WholeStep,ax ;шаг (минимальная длина прогона) mov al,[bp].Color;AL – цвет, рисуем первый прогон пикселей. rep stosb ; рисуем последний прогон add di,SCREEN_WIDTH;перейдем вдоль неосновной оси (Y) ; Рисуем все прогоны. cmp si,1 ;есть ли более чем 2 сканирования, ; т.е. нет ли заполненных прогонов? (SI = число сканирований - 1) jna XMajorDrawLast ;заполненных прогонов нет dec dx ;подправим ошибку накопления на -1, ; чтобы использовать проверку флага переноса shr si,1 jnc XMajorFullRunsOddEntry ;если число ;сканирований, нечетное -- выполняем нечетное сканирование XMajorFullRunsLoop: mov cx,[bp].WholeStep;прогон не может быть короче этой величины add dx,bx ;обновим ошибку накопления и добавим jnc XMajorNoExtra;дополнительный пиксель, если требуется inc cx sub dx,[bp].AdjDown;сбросим ошибку накопления XMajorNoExtra: rep stosb;рисуем прогон этой линии сканирования add di,SCREEN_WIDTH ;перейдем вдоль неосновной оси (Y) XMajorFullRunsOddEntry: ;если число нечетно, войдем в цикл заполнения прогонов mov cx,[bp].WholeStep ;прогон не может быть короче этой величины add dx,bx ; обновим ошибку накопления и добавим jnc XMajorNoExtra2 ; дополнительный пиксель, если того требует ситуация inc cx sub dx,[bp].AdjDown ;сбросим ошибку накопления XMajorNoExtra2: rep stosb ; рисуем прогон этой линии сканирования add di,SCREEN_WIDTH;перейдем вдоль неосновной оси (Y) dec si jnz XMajorFullRunsLoop ; Рисуем последний прогон пикселей. XMajorDrawLast: pop cx ;возьмем длину последнего прогона rep stosb ;рисуем последний прогон cld ;восстановим флаг нормального направления jmp Done ;Y - основная ось (вертикальная проекция больше ;горизонтальной). YMajor: mov [bp].XAdvance,bx ;запомним, в какую ; сторону идти по оси Х push SCREEN_SEGMENT;установим DS:DI на pop ds ;первый байт для отображения mov ax,cx ; YDelta mov cx,dx ; XDelta sub dx,dx ;подготовим для деления div cx ;AX = YDelta/XDelta ;(минимальное число пикселей в прогоне этой линии) DX = YDelta % XDelta mov bx,dx ;ошибку накопления подправляем ; каждый раз при шаге вдоль оси X add bx,bx ;ошибку накопления используем для mov [bp].AdjUp,bx ; индикации не пора ли ; добавить еще пиксель к базовой длине прогона? ;чтобы округлить ошибку отклонения при шагах mov si,cx ; вдоль оси Y,ошибку накопления add si,si ; подправим, когда она переполнится ;и скажет,что пора сделать шаг по Y mov [bp].AdjDown,si ;Начальная ошибка ;накопления, отражает начальный шаг величиной 0,5 ;вдоль оси X. sub dx,si ;DX=(YDelta%XDelta)-(XDelta*2) ; - начальная ошибка накопления Первый и ; последний прогоны являются неполными, потому ;что для них ось Х изменяется только на 0,5, а ;не на 1. Разделим один полный прогон плюс ;начальный пиксель между первым и последний ;прогонами. mov si,cx ;SI = XDelta mov cx,ax ;шаг (минимальная длина прогона) shr cx,1 inc cx ;счетчик начального пикселя ; =(whоlеstер/2)+1 (подправин позже) push cx ;запомним счетчик пикселей в ; последнем прогоне. Если основная длина прогона ; четная, а дробная часть отсутствует, у нас есть ;пиксель, который нужно отправить либо в первый, ; либо в последний прогон, поэтому отправим его в ; последний прогон. Если число пикселей в прогоне ; ненечетно, то один пиксель нельзя добавить ни к ;первому, им к последнему прогону, так что ; добавим 0,5 к ошибке накопления, чтобы текущий ;пиксель обрабатывался стандартным циклом ;рисования прогона. add dx,si ;положим, что длина нечетная, ; добавим Xdelta к ошибке накопления test al,1 ;длина прогона четная? jnz YMajorAdjustDone ;нет. а значит, все уже ;сделано sub dx,si ;длина четная, сделаем все заново and bx,bx ; ошибка накопления равка О? jnz YMajorAdjustDone ;нет (не нужно проверять ; длину на четность, потому что это уже dec cx ; проделано)оба условия удовлетворены; ; сделаем первый прогон на 1 короче YMajorAdjustDone: mov [bp].WholeStep,ax ;полный шаг (минимальная длина прогона) mov al,[bp].Color ;AL - цвет mov bx,[bp].XAdvance;направление движения вдоль оси Х ;Рисуем первый, неполный прогон пикселей. YMajorFirstLoop: mov [di],al ; рисуем пиксель add di,SCREEN_WIDTH ;перейдем по основной оси (Y) loop YMajorFirstLoop add di,bx ; перейдем вдоль неосновной оси (X) ;Рисуем все прогоны. cmp si,1;число полных прогонов.Если всего ;прогонов более двух, значит, имеются полные ;прогоны? (SI = число прогонов - 1) jna YMajorDrawLast ; полных прогонов нет dec dx ;подправим ошибку накопления на -1, ; чтобы использовать проверку флага переноса. shr si,1;считаем пары прогонов на основе ; пройденных единичных прогонов. если число ; прогонов нечетно, обрабатываем jnc YMajorFullRunsOddEntry ;сейчас нечетный прогон YMajorFullRunsLoop: mov cx,[bp].WholeStep ;прогон не ;может быть короче этой величины обновим ошибку ;накопления и добавим add dx,[bp].AdjUp ;дополнительный пиксель, jnc YMajorNoExtra ;если ошибка накопления ;просит об этом inc cx ; дополнительный пиксель в прогоне sub dx,[bp].AdjDown;сбросим омибку накопления YMajorNoExtra: ;Рисуем YMajorRunLoop: mov [di],al ;рисуен пиксель add di,SCREEN_WIDTH;перейдем по основной оси (Y) loop YMajorRunLoop add di,bx ;перейдем вдоль неосновной оси (X) YMajorFullRunsOddEntry: ;войдем здесь в цикл.Если mov cx,[bp].WholeStep ;число прогонов ;нечетно, прогон не может быть короче этой ;величины. add dx,[bp].AdjUp ;обновим ошибку накопления jnc YMajorNoExtra2; и добавим дополнительный ;пиксель, если ошибка накопления просит об этом inc cx ;дополнительный пиксель в прогоне. sub dx,[bp].AdjDown;с6росим ошибку накопления YMajorNoExtra2: ; Рисуем YMajorRunLoop2: mov [di],al ;рисуем пиксель add di,SCREEN_WIDTH;перейдем по основной оси (Y) loop YMajorRunLoop2 add di,bx ;перейдем вдоль неосновной оси (X) dec si jnz YMajorFullRunsLoop ; Рисуем последний прогон пикселей. YMajorDrawLast: pop cx ;возьмем длину последнего прогона пикселей YMajorLastLoop: mov [di],al ;рисуем пиксель add di,SCREEN_WIDTH ;перейдем по основной оси (Y) loop YMajorLastLoop Done: pop ds ;восстановим DS pop di pop si ;восстановим регистровые переменные mov sp,bp ;освободим локальные переменные pop bp;восстановим стек вызывающей программы ret LineDraw endp end start
