Рисование линий на экране

Тема в разделе "WASM.DOS/BIOS/Vesa/ports", создана пользователем Mikl___, 24 дек 2016.

  1. Mikl___

    Mikl___ Супермодератор Команда форума

    Публикаций:
    14
    Регистрация:
    25 июн 2008
    Сообщения:
    3.708

    Рисование линий на экране

    Проведение линий подразумевает установку на экране всех точек, принадлежащих отрезку. Сложность при рисовании линии в том, что точки из которых мы ее строим создавали иллюзию прямой. На экране абсолютно точно можно нарисовать только вертикальные, горизонтальные и 1:1 диагональные линии.
    Если у нас установлен 13h графический режим (320x200x256), то горизонтальную линию рисуют следующими командами
    Код (ASM):
    1.  
    2. ;предварительные установки
    3. PUSH 0A000h
    4. POP ES; позиционируем ES на область видеопамяти
    5. MOV DI,X ; в DI координаты начальной точки по X
    6. MOV AX,320; длина строки экрана
    7. MUL Y; умножаем на Y
    8. ADD DI,AX; и складываем с X
    9. MOV AL,COLOR; цвет линии
    10. ; рисуем горизонтальную линию
    11. MOV CX,N; длина линии
    12. REP STOSB
    13.  
    Вертикальную линию обычно рисуют циклом
    Код (ASM):
    1.  
    2. MOV CX,N; длина линии
    3. A1: MOV ES:[DI],AL; рисуем точку на строке
    4. ADD DI,320; переход на следующую строку
    5. LOOP A1
    6.  
    диагональную линию с наклоном влево можно нарисовать циклом
    Код (ASM):
    1.  
    2. MOV CX,N; длина линии
    3. A1: MOV ES:[DI],AL; рисуем точку на строке
    4. ADD DI,319; переход на следующую строку
    5. LOOP A1
    6.  
    диагональную линию с наклоном вправо — циклом
    Код (ASM):
    1.  
    2. MOV CX,N; длина линии
    3. A1: MOV ES:[DI],AL; рисуем точку на строке
    4. ADD DI,321; переход на следующую строку
    5. LOOP A1
    6.  
    Первое, все остальные линии рисуются только приближенно. Второе, что бы быть полезной, функция рисования линии должна работать быстро.
    Давайте рассмотрим случай, когда горизонтальная проекция линии длиннее вертикальной и угол наклона линии отрицательный. Например, нарисуем линию направленную из точки (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):
    1. .286
    2. .model tiny
    3. .code
    4. org 100h
    5. start:
    6. SCREEN_WIDTH equ 320;ширина экрана в режиме 13h
    7. SCREEN_SEGMENT equ 0A000h
    8. parms struc
    9. dw ? ; сохраненный в стеке ВР
    10. dw ? ; сохраненный в стеке адрес возврата
    11. XStart dw ? ; начальная координата Х линии
    12. YStart dw ? ; начальная координата Y линии
    13. XEnd dw ? ; конечная координата Х линии
    14. YEnd dw ? ; конечная координата Y линии
    15. Color db ? ;цвет линии, рядом с ним пустой байт,
    16. db ? ;потому что Color в стеке длиной в слово
    17. parms ends
    18. ; Локальные переменные.
    19. AdjUp equ -2;ошибку накопления подправляем на каждом шаге
    20. AdjDown equ -4;ошибку накопления уменьшаем, когда превышен порог
    21. WholeStep equ -6 ; минимальная длина прогона
    22. XAdvance equ -8 ;1 или -1, направление, в котором идем по оси Х
    23. LOCAL_SIZE equ 8
    24. mov ah,0Fh ;запомнить видеорежим
    25. int 10h
    26. mov videor,al
    27. mov ax,13h
    28. int 10h;установили видеорежим 256x320x200
    29. push 5 ;Color
    30. push 12 ;YEnd
    31. push 55 ;XEnd
    32. push 0 ;YStart
    33. push 0 ;XStart
    34. call LineDraw ;рисуем линию
    35. mov ah,0 ;ждем нажатия на клавишу
    36. int 16h
    37. mov ax,word ptr videor ;восстановить видеорежим
    38. int 10h
    39. int 20h ;выход из программы
    40. videor db 0,0
    41. LineDraw proc near;универсальная процедура для рисования линий
    42. push bp ; сохраним стек вызывающей программы
    43. mov bp,sp ;спозиционируемся на стек
    44. sub sp,LOCAL_SIZE ; выделим место для локальных переменных
    45. push si ; сохраним регистровые переменные
    46. push di
    47. push ds ; сохраним DS
    48. ;Рисуем сверху вниз,чтобы уменьшить число сравнений и
    49. ;чтобы получить одни и те же точки линий с
    50. ;одинаковыми координатами.
    51. mov ax,[bp].YStart
    52. cmp ax,[bp].YEnd
    53. jle LineIsTopToBottom
    54. xchg [bp].YEnd,ax;поменяем местами координаты линии
    55. mov [bp].YStart,ax
    56. mov bx,[bp].XStart
    57. xchg [bp].XEnd,bx
    58. mov [bp].XStart,bx
    59. LineIsTopToBottom:
    60. mov dx,SCREEN_WIDTH ;Установим DI на первый пиксель
    61. mul dx ;для отображения.YStart*SCREEN_WIDTH
    62. mov si,[bp].XStart
    63. mov di,si ; DI=YStart*SCREEN_WIDTH+XStart
    64. add di,ax ; в DI смещение первого пикселя
    65. ; Определим, до каких пор идти по вертикали.
    66. mov cx,[bp].YEnd
    67. sub cx,[bp].YStart ;СХ = YDelta
    68. ;Определим, идти влево или вправо и до каких пор идти
    69. ;по горизонтали. По ходу дела выделим рисование
    70. ;вертикальных линий в целях ускорения, а также во
    71. ;избежание предельных случаев и деления на 0.
    72.  mov dx,[bp].XEnd
    73.  sub dx,si ;XDelta
    74.  jnz NotVerticalLine;XDelta = 0 означает
    75. ;вертикальную линию
    76.  push SCREEN_SEGMENT;установим DS:DI на первый
    77.  pop ds ;байт для отображения
    78.  mov al,[bp].Color
    79. VLoop: mov [di],al
    80.  add di,SCREEN_WIDTH
    81.  loop VLoop
    82.  jmp Done
     
    Последнее редактирование: 24 дек 2016
    >Quiet Snow< нравится это.
  2. Mikl___

    Mikl___ Супермодератор Команда форума

    Публикаций:
    14
    Регистрация:
    25 июн 2008
    Сообщения:
    3.708
    Код (ASM):
    1. ; Обработка горизонтальных линий.
    2. IsHorizontalLine: push SCREEN_SEGMENT;установим
    3. pop es ;ES:DI на первый байт для отображения
    4. mov al,[bp].Color; сдублируем старший байт
    5. mov ah,al ;для пословного вывода
    6. and bx,bx ; слева направо?
    7. jns DirSet ;да
    8. sub di,dx ; обработка движения справа налево,
    9. ; спозиционируемся на левый край линии
    10. DirSet: mov cx,dx
    11. inc cx ; число пикселей для отображения
    12. shr cx,1 ;число слов для отображения
    13. rep stosw ; обработаем как можно больше слов
    14. adc cx,cx
    15. rep stosb; обработаем нечетный байт, если
    16. jmp Done; таковой имеется
    17. ; Обработка диагональных линий.
    18. IsDiagonalLine:
    19. push SCREEN_SEGMENT;установим DS:DI на первый
    20. pop ds ;байт для отображения
    21. mov al,[bp].Color
    22. add bx,SCREEN_WIDTH ;пройдем расстояние от
    23. ; одного пикселя до следующего
    24. DLoop: mov [di],al
    25. add di,bx
    26. loop DLoop
    27. jmp Done
    28. NotVerticalLine: mov bx,1;начинаем слева направо,
    29. ; так что XAdvance=1 флаги не изменяются
    30. jns LeftToRight ; проход слева направо
    31. neg bx;проход справа налево, так что
    32. ;XAdvance = -1
    33. neg dx ; модуль XDelta
    34. LeftToRight: ; Обработка горизонтальных линий.
    35. jcxz IsHorizontalLine ;YDelta = 0? да
    36. ; Обработка горизонтальных линий.
    37.    cmp cx,dx ; YDelta = XDelta?
    38.    jz IsDiagonalLine ;да
    39. ;Определим, какая из осей основная, а какая вспомогательная.
    40.    cmp dx,cx
    41.    jb YMajor;Линия с основной осью Х (горизонтальная проекция больше вертикальной).
    42. XMajor: push SCREEN_SEGMENT; установим ES:DI на
    43.    pop es ;первый байт для отображений
    44.    and bx,bx ;слева направо?
    45.    jns DFSet ;да, CLD уже установлен
    46.    std ;справа налево, так что рисуем в обратном направлении
    47. DFSet: mov ax,dx ;XDelta
    48.    sub dx,dx; подготовим для деления
    49.    div cx ;AX = XDelta/YDelta;(минимальное число пикселей в прогоне этой линии) ;DX=XDelta%YDelta
    50.    mov bx,dx;ошибку накопления подправляем при каждом шаге по оси Y
    51.    add bx,bx ;используется для индикации, не нужен ли дополнительный пиксель в прогоне, чтобы округлить
    52.    mov [bp].AdjUp,bx;нецелые шаги вдоль оси Х при 1-пиксельных шагах вдоль оси Y
    53.    mov si,cx;ошибку накопления подправляем, когда ее
    54.    add si,si ;значение превышает допустимый порог
    55. ;используем это для определения, необходимо ли сделать шаг по оси Х
    56.    mov [bp].AdjDown,si ;Начальная ошибка накопления отражает начальный шаг 0,5 вдоль оси Y.
    57.    sub dx,si ;(XDelta % YDelta) - (YDelta * 2), DX - начальная ошибка накопления
    58. ;Первый и последний прогоны являются неполными, потому что перемещение по оси Y идет на 0,5,а не
    59. ;на 1.Разделим один полный прогон плюс начальный пиксель между первым и последним прогонами.
    60.    mov si,cx ;SI = YDelta
    61.    mov cx,ax ;шаг (минимальная длина прогона)
    62.    shr cx,1
    63.    inc cx ;счетчик начального пикселя=(шаг/2)+1 (подправим позже).
    64. ;Это также счетчик пикселей в последнем прогоне
    65.    push cx;запомним счетчик пикселей в последнем прогоне. Если основная длина прогона четная, а
    66. ;дробная часть отсутствует, то у нас есть бесхозный пиксель, который можно определять либо
    67. ;в первый, либо в последний прогон, вот давайте и определим этот пиксель в последний прогон. Если
    68. ;число пикселей в прогоне нечетно, то у нас есть пиксель, который нельзя определить ни в первый,
    69. ;ни в последний прогон, так что добавим, 0,5 к ошибке накопления чтобы текущий пиксель
    70. ;обрабатывался стандартным циклом рисования прогона.
    71.    add dx,si ;положим нечетную длину, добавим
    72. ;YDelta к ошибке накопления (добавим 0,5 пикселя к ошибке накопления)
    73.    test al,1 ; четна ли длина прогона?
    74.    jnz XMajorAdjustDone;нет, и тогда все уже готово
    75.    sub dx,si ; длина четна поэтому проверим ошибку,.
    76.    and bx,bx ; 0 или нет?
    77.    jnz XMajorAdjustDone ;нет (проверять длину на четность смысла нет, так как только что это уже
    78.    dec cx; было проделано) оба условия удовлетворены, делаем прогон 1 короче
    79. XMajorAdjustDone:
    80.    mov [bp].WholeStep,ax ;шаг (минимальная длина прогона)
    81.    mov al,[bp].Color;AL – цвет, рисуем первый прогон пикселей.
    82.    rep stosb ; рисуем последний прогон
    83.    add di,SCREEN_WIDTH;перейдем вдоль неосновной оси (Y)
    84. ; Рисуем все прогоны.
    85.    cmp si,1 ;есть ли более чем 2 сканирования,
    86. ; т.е. нет ли заполненных прогонов? (SI = число сканирований - 1)
    87. jna XMajorDrawLast ;заполненных прогонов нет
    88.    dec dx ;подправим ошибку накопления на -1,
    89. ; чтобы использовать проверку флага переноса
    90.    shr si,1
    91. jnc XMajorFullRunsOddEntry ;если число
    92. ;сканирований, нечетное -- выполняем нечетное сканирование
    93. XMajorFullRunsLoop:
    94.    mov cx,[bp].WholeStep;прогон не может быть короче этой величины
    95.    add dx,bx ;обновим ошибку накопления и добавим
    96.    jnc XMajorNoExtra;дополнительный пиксель, если требуется
    97.    inc cx
    98.    sub dx,[bp].AdjDown;сбросим ошибку накопления
    99. XMajorNoExtra: rep stosb;рисуем прогон этой линии сканирования
    100.    add di,SCREEN_WIDTH ;перейдем вдоль неосновной оси (Y)
    101. XMajorFullRunsOddEntry: ;если число нечетно, войдем в цикл заполнения прогонов
    102.    mov cx,[bp].WholeStep ;прогон не может быть короче этой величины
    103.    add dx,bx ; обновим ошибку накопления и добавим
    104.    jnc XMajorNoExtra2 ; дополнительный пиксель, если того требует ситуация
    105.    inc cx
    106.    sub dx,[bp].AdjDown ;сбросим ошибку накопления
    107. XMajorNoExtra2: rep stosb ; рисуем прогон этой линии сканирования
    108.    add di,SCREEN_WIDTH;перейдем вдоль неосновной оси (Y)
    109.    dec si
    110.    jnz XMajorFullRunsLoop
    111. ; Рисуем последний прогон пикселей.
    112. XMajorDrawLast: pop cx ;возьмем длину последнего прогона
    113.    rep stosb ;рисуем последний прогон
    114.    cld ;восстановим флаг нормального направления
    115.    jmp Done
    116. ;Y - основная ось (вертикальная проекция больше
    117. ;горизонтальной).
    118. YMajor: mov [bp].XAdvance,bx ;запомним, в какую
    119. ; сторону идти по оси Х
    120.    push SCREEN_SEGMENT;установим DS:DI на
    121.    pop ds ;первый байт для отображения
    122.    mov ax,cx ; YDelta
    123.    mov cx,dx ; XDelta
    124.    sub dx,dx ;подготовим для деления
    125.    div cx ;AX = YDelta/XDelta
    126. ;(минимальное число пикселей в прогоне этой линии) DX = YDelta % XDelta
    127.    mov bx,dx ;ошибку накопления подправляем
    128. ; каждый раз при шаге вдоль оси X
    129. add bx,bx ;ошибку накопления используем для
    130. mov [bp].AdjUp,bx ; индикации не пора ли
    131. ; добавить еще пиксель к базовой длине прогона?
    132. ;чтобы округлить ошибку отклонения при шагах
    133. mov si,cx ; вдоль оси Y,ошибку накопления
    134. add si,si ; подправим, когда она переполнится
    135. ;и скажет,что пора сделать шаг по Y
    136. mov [bp].AdjDown,si ;Начальная ошибка
    137. ;накопления, отражает начальный шаг величиной 0,5
    138. ;вдоль оси X.
    139. sub dx,si ;DX=(YDelta%XDelta)-(XDelta*2)
    140. ; - начальная ошибка накопления Первый и
    141. ; последний прогоны являются неполными, потому
    142. ;что для них ось Х изменяется только на 0,5, а
    143. ;не на 1. Разделим один полный прогон плюс
    144. ;начальный пиксель между первым и последний
    145. ;прогонами.
    146. mov si,cx ;SI = XDelta
    147. mov cx,ax ;шаг (минимальная длина прогона)
    148. shr cx,1
    149. inc cx ;счетчик начального пикселя
    150. ; =(whоlеstер/2)+1 (подправин позже)
    151. push cx ;запомним счетчик пикселей в
    152. ; последнем прогоне. Если основная длина прогона
    153. ; четная, а дробная часть отсутствует, у нас есть
    154. ;пиксель, который нужно отправить либо в первый,
    155. ; либо в последний прогон, поэтому отправим его в
    156. ; последний прогон. Если число пикселей в прогоне
    157. ; ненечетно, то один пиксель нельзя добавить ни к
    158. ;первому, им к последнему прогону, так что
    159. ; добавим 0,5 к ошибке накопления, чтобы текущий
    160. ;пиксель обрабатывался стандартным циклом
    161. ;рисования прогона.
    162. add dx,si ;положим, что длина нечетная,
    163. ; добавим Xdelta к ошибке накопления
    164. test al,1 ;длина прогона четная?
    165. jnz YMajorAdjustDone ;нет. а значит, все уже
    166. ;сделано
    167. sub dx,si ;длина четная, сделаем все заново
    168. and bx,bx ; ошибка накопления равка О?
    169. jnz YMajorAdjustDone ;нет (не нужно проверять
    170. ; длину на четность, потому что это уже
    171. dec cx ; проделано)оба условия удовлетворены;
    172. ; сделаем первый прогон на 1 короче
    173. YMajorAdjustDone: mov [bp].WholeStep,ax
    174. ;полный шаг (минимальная длина прогона)
    175. mov al,[bp].Color ;AL - цвет
    176. mov bx,[bp].XAdvance;направление движения вдоль оси Х
    177. ;Рисуем первый, неполный прогон пикселей.
    178. YMajorFirstLoop: mov [di],al ; рисуем пиксель
    179. add di,SCREEN_WIDTH ;перейдем по основной оси (Y)
    180. loop YMajorFirstLoop
    181. add di,bx ; перейдем вдоль неосновной оси (X)
    182. ;Рисуем все прогоны.
    183. cmp si,1;число полных прогонов.Если всего
    184. ;прогонов более двух, значит, имеются полные
    185. ;прогоны? (SI = число прогонов - 1)
    186. jna YMajorDrawLast ; полных прогонов нет
    187. dec dx ;подправим ошибку накопления на -1,
    188. ; чтобы использовать проверку флага переноса.
    189. shr si,1;считаем пары прогонов на основе
    190. ; пройденных единичных прогонов. если число
    191. ; прогонов нечетно, обрабатываем
    192. jnc YMajorFullRunsOddEntry ;сейчас нечетный прогон
    193. YMajorFullRunsLoop: mov cx,[bp].WholeStep ;прогон не
    194. ;может быть короче этой величины обновим ошибку
    195. ;накопления и добавим
    196. add dx,[bp].AdjUp ;дополнительный пиксель,
    197. jnc YMajorNoExtra ;если ошибка накопления
    198. ;просит об этом
    199. inc cx ; дополнительный пиксель в прогоне
    200. sub dx,[bp].AdjDown;сбросим омибку накопления
    201. YMajorNoExtra: ;Рисуем
    202. YMajorRunLoop: mov [di],al ;рисуен пиксель
    203. add di,SCREEN_WIDTH;перейдем по основной оси (Y)
    204. loop YMajorRunLoop
    205. add di,bx ;перейдем вдоль неосновной оси (X)
    206. YMajorFullRunsOddEntry: ;войдем здесь в цикл.Если
    207. mov cx,[bp].WholeStep ;число прогонов
    208. ;нечетно, прогон не может быть короче этой
    209. ;величины.
    210. add dx,[bp].AdjUp ;обновим ошибку накопления
    211. jnc YMajorNoExtra2; и добавим дополнительный
    212. ;пиксель, если ошибка накопления просит об этом
    213. inc cx ;дополнительный пиксель в прогоне.
    214. sub dx,[bp].AdjDown;с6росим ошибку накопления
    215. YMajorNoExtra2: ; Рисуем
    216. YMajorRunLoop2: mov [di],al ;рисуем пиксель
    217. add di,SCREEN_WIDTH;перейдем по основной оси (Y)
    218. loop YMajorRunLoop2
    219. add di,bx ;перейдем вдоль неосновной оси (X)
    220. dec si
    221. jnz YMajorFullRunsLoop
    222. ; Рисуем последний прогон пикселей.
    223. YMajorDrawLast:
    224. pop cx ;возьмем длину последнего прогона пикселей
    225. YMajorLastLoop: mov [di],al ;рисуем пиксель
    226. add di,SCREEN_WIDTH ;перейдем по основной оси (Y)
    227. loop YMajorLastLoop
    228. Done: pop ds ;восстановим DS
    229. pop di
    230. pop si ;восстановим регистровые переменные
    231. mov sp,bp ;освободим локальные переменные
    232. pop bp;восстановим стек вызывающей программы
    233. ret
    234. LineDraw endp
    235. end start
    236.  
     
    Мановар и rococo795 нравится это.