Свещеният сметач - списание за компютърна графика...
БРОЙ - 24 (юни 2003)
Брой 24  Свещеният сметач
 
   
Тодор "Тош" Арнаудов
Как се чертае отсечка
Описание на алгоритъм с целочислена аритметика - без умножение и деление - за изчертаване на отсечка, изведен от автора. Негово изпълнение с единични процедури за Паскал и Асемблер за x86 в режим $13. Споменават се, като сравнение, още - според цитирания източник - "най-известният" такъв алгоритъм - на Breshenham от 1965 г. и изчертаване на отсечка, изпълнено от друг програмист в няколко процедури на Асемблер и Паскал.

 

Как се чертае отсечка?

 

Забележка:

"Омесване на понятията" - Линия и отсечка по-долу означават едно и също нещо, за разнообразие и защото, от гледна точка на "рисуването им", са едно и също нещо на платното. "Безкрайната линия" се чертае като крайна отсечка.

Думи на юнашки и др., използвани в изследването:

Ябълка, Маце - Apple-2, IBM-PC
стъкло, стъклария - силиций, интегрални схеми
глаголица - Асемблер
стих и производните му - програма на машинен език
стихотворец, поет и подобни - програмист на машинен език
решетка - матрица, координатна система
казба - инструкция
точка - клетка от решетка; област със свойства различни от свойствата на обграждащото я пространство


Отсечка

На мен самият ми стана съвсем ясно как се чертае линия, - т.е. най-накрая написах работещо за всички случаи предписание - докато си играех на философ преди около година. (Разбира се, става въпрос за решение на целочислен Асемблер, защото делението на отсечката на части с плаваща запетая е твърде "близко до ума".) Този алгоритъм е много съществен в "рисуването" с по-стари сметачета, като Правчото, с който си играех едно време, затова съм си блъскал, плахо и без успех, главата върху този алгоритъм още когато минавах прав под рекламите на поникналите като гъби "Интернет-клубове" и когато на озадачените посетители, учудени от нелепото откритие, че в клуб с надпис "Интернет" няма достъп до Интернет, администраторите отвръщаха: "Прекарай ни телефон и ще има!"...

Философският "двубой", наречен Схващане за всеобщата предопределеност 2, беше между млад "субективен идеалист", "детерминист" и "неопозитивист", смятащ че истината е това, което можеш да пресъздадеш в предписание, и то да работи, и опитен метафизичен идеалист и "свободолюбец".

Не бях съгласен с "метафизичното твърдение", че "разсъдъкът ни не може да схване, изрази и опише дори най-простото движение, да речем преместването на една точка по права линия(...)" и си спомних, че се бях заел с въпросния алгоритъм, на осем-шестак, преди време, но го бях зарязал, щото това, което бях измислил, не работеше за всички случаи - едни линии излизаха както трябва, други - не. (С разни знаци май че се балтаех...)

Впрочем, не мога да се сдържа да не вмъкна какво мисли Дружество "Разум": http://eim.hit.bg/razum/ за "истината" и "смисъла" (понятия с допирни точки в същността си), защото тази статия, алгоритъмът от нея, би трябвало да бъде част от "любителското изследване", наречено "Основи на разпознаването на образи", което предстои да бъде издадено.

Истината според мен:

Колкото повече входният къс знание, чиято "истинност" се проверява, съвпада с къс знание от спомените на разума, толкова по-"истинен" и "действителен" е той според разума. Т.е. определянето на "истинност" е определяне на разлика между минало и настояще.

Смисълът според Илиян Георгиев:

Смисъл на едно изречение (мисъл) е функция, която търси противоречие между базата знания на мислещия и самата мисъл, която се анализира. Т.е. всички елементи от базата знания и техните връзки се съпоставят с "новата" мисъл, която се анализира и ако някой от елементите на мисълта има връзка с друг елемент, и връзката не се намира в базата данни, то изречението се счита за безсмислено (имащо грешка).

...Спомних си за старата започната, но недовършена работа, и като прегледах отново какво съм бил зарязал, същината на алгоритъма ми се изясни напълно, и разбрах къде бях грешал (но после забравих ;-).

Първо да видим как би могла да се реши задачата:

Последователността от действия се схваща по-лесно, ако си начертаем двумерен масив (решетка), през който прокарваме отсечки и квадратчетата, които те пресичат, запълваме, т.е. си правим "пикселизирано" изображение на отсечка. Изобщо, разглеждането на образите по този начин улеснява изследването на разпознаването на образи.

Какви входни данни имаме и какви изходни трябва да получим, или как бих могъл да оправдая описания под "решението-оправдание" ;-) алгоритъм

Като вход имаме:
- координати на началото и края - (x,y),(x1,y1)
Като изход:
- изображението, което сме начертали

В него можем да забележим, че:
- отсечката е съставена от съседни точки (т.е. все намиращи се сред "осморката" около дадена централна точка; за "осморката", съседството и свързаността в "Основи на разпознаването на образи"), следователно някъде ще се използва стъпка единица
- понякога се срещат две и повече съседни точки, които не са диагонални, следователно ще има стъпка, която в общия случай не е единица

Открихме, че едната стъпка на обхождане е единица. Числата, от които се налага да построим зависимост, са 4 - x,y,x1,y1 и зависимостта на стъпката, с която се покачва втората координата, трябва да бъде получена като уравнение от четирите променливи. Можем да забележим, обаче, че като местим отсечката по координатната система (направена, както отбелязахме, като матрица, за да изпъква по-ясно границата между точките), разликите във взаимното разположение между точките в отсечката не се променят. Следователно важно е отношението между началните и крайните координати, а не абсолютната им стойност. Отношението между координатите е разликата между началото и края по двете оси - така опростяваме търсенето, до зависимост между 2 входни стойности.

Спомняме си, че промяната на координатата нявсякъде, включително в частите на отсечката, където има поредица от съседни точки, образуващи хоризонтала, става с единица. Следователно двете променливи определят периода, през който ще се извършва промяна на стойност с единица.

Алгоритъмът трябва да е прост - да използваме само събиране и изваждане. Забелязваме, че колкото е по-голямо отношението между разликите по двете оси, толкова е по-полегата отсечката, т.е. промяната на едната от координатите с единица става по-рядко, следователно периодът е по-голям. Разбира се - трябва да разделим едната разлика на другата. Делението чрез събиране става, като натрупваме делителя в първоначално нулирана променлива и броим колко пъти са нужни да го съберем, за да получим число, равно или по-голямо от делимото. (Разбира се, за чисто изчислителни задачи и големи отношения делимо/делител могат да се използват хитрости, като запомняне на получения сбор след втората стъпка, чрез което пресмятаме резултата направо след осмата, после след шестнайстата и т.н.). Полученото частно е стъпката, през която става промяна на втората координата. След пресмятане на първото частно не трябва да нулираме променливата, защото така ще загубим остатъка. Вместо това изваждаме от натрупания сбор стойността на делимото - остатъкът остава да се помни в променливата, в която натрупваме делителя.

По този начин задачата е решена.

 
Изчертаване на отсечка

1. Взимаме началните координати x,y и крайните x1,y1 в решетката, в която ще преместваме точката.
2. Пресмятаме разликите: dx = x1 - x; dy = y1 - y.
3. Ако (dx >= dy) -> (4) иначе (10)

"По-широка, отколкото висока"

4. (dx >= dy), т.е. ъгълът, който сключват двете точки спрямо "водоравната ос" X на координатната система е между 0 и 45 градуса включително, отсечката е по-"широка", отколкото "висока".
5. Определяме броя на стъпките: (st = dx).
6. Настоящото положение на точката се записва в променливи (tx, ty). На всяка стъпка, tx се увеличава с единица - по оста Х точката се премества с една клетка.
7. В променлива, в началото със стойност нула - да я наречем "n", след всяка стъпка прибавяме dy. Когато "n" стане по-голямо от dx, преместваме точката и по оста y с една стъпка, след което изваждаме от натрупаната в n стойност dx.
8. Дали я преместваме "нагоре" или "надолу" зависи от избора на посоки: ако нарастването на y означава "надолу", то ако (y1 > y), точката ще се "спуска" надолу (++) след всяко преминаване на "n" над dx; ако (y1 < y), точката ще се "издига" нагоре (--); ако пък (y1 == y), точката ще се "плъзга" на едно и също равнище.
9. Повтаряме действията от 4 до 8, докато tx се изравни с x1.

"По-висока, отколкото широка"

10. (dx < dy), т.е. ъгълът спрямо водоравната ос е между 45 и 90 градуса. Тогава стъпките (st = dy). Използваме същата последователност, с промените:
- преместваме с една клетка на всяка стъпка по Y (ty++), вместо X (tx)
- в n се прибавя dx (вместо dy), която щом надмине dy (вместо dx) кара точката да се измести и по оста X и предизвиква изваждане на dy от n.

...

Горд от откритието си ;-), реших да потърся какво пише из Мрежата за чертаенето на отсечка. Намерих нещо само на едно място (но не помня дали мързелът се върна твърде бързо или Интернет излезе "празен" откъм такава информация), което цитирам.

  http://www.rulabinsy.com/cavd/text/chap09-2.html
"The solution to drawing lines without complex arithmetic is to use scaled-integer values for the determination of pixel increments. The most popular technique also does all initial calculations in terms of these scaled integers [Breshenham 65]. The algorithm makes use of an indicator that initially has the value D = 2dy - dx (where dy = y2 - y1 and dx = x2 - x1), and a current point (x, y), which initially is (x1, y1). After plotting this point, x is incremented by 1, and y increments by 1 only if D > 0. If y increments, then D has the value 2(dy - dx) added to it; otherwise, it has the value 2y added to it. This continues until (x, y) reaches (x2, y2).

The Breshenham algorithm is very fast because the terms can be precomputed and all of them require only addition and subtraction. The version described is, of course, for lines with a slope of less than one because x increments smoothly. For other lines, the coordinate terms are simply reversed."


  В приблизителен превод:

"...Алоритъмът използва указател, в който първоначално е записана стойност (D = 2dy - dx), където (dy = y2 - y1) и (dx = x2 - x1), и настояща точка (x, y), която в началото е (x1, y1). След изчертаването на първата точка, x се увеличава с единица, а към y се добавя единица, само ако (D > 0). Ако y нараства, тогава към D се добавя стойността 2(dy-dx); в противен случай, се добавя 2y. Това продължава, докато (x, y) достигне (x2, y2).

Алгоритъмът на Брешънъм (?) е много бърз, защото стойностите могат да бъдат предварително изчислени, и то само със събиране и изваждане. Описаната тук разновидност е, разбира се, за отсечки с наклон по-малък от едно, защото x нараства плавно. За другите отсечки, променливите за координатите просто се обръщат.

 

Изпълнение на алгоритъма на Тош от Тош

Прилагам изпълнение на предложения от мен алгоритъм, "подкарано" на "Турбо Паскал 7" и на глаголица за 8086. Имам "програмисткото чувство", че за режими с последователно разположение на точките и кодиране на цветовете с байт, както е в използвания по-долу, чертането може да се насече на допълнителни стъпки с размер 2 и 4 (за 32-битов вършач), за да се използва пълния размер на регистрите. Конкретно за използвания режим "$13" - при чертаенето на "по-широки, отколкото високи линии", може би може да се напише стъпка, която запълва местата от отсечката, в които има поредица от 4 съседни точки без промяна на "Y" с 32-битов регистър; във втората стъпка запълва по 16-бита и чак на третата, като вършаче от 70-те, се "мъчи" с 8-битови регистри. Сигурно може...

Изпълнението по-долу е също и сравнение с набора процедури на Алексей Фрунзе от графичната му библиотека "grafix.pas". http://alexfru.chat.ru/
Аз самият не съм много добър (и мотивиран) в разчитането на поезия от десетки казби на глаголица без бележки и обяснения. (Благодарение на това "съвестта ми е чиста", че не съм "крал" от процедурата "line" (само от "putpixel" ;-)) Ако на някого му се разчита, може да разкаже и на другите на http://bgit.net

  Изтегли: lina_sam.pas

----------lina_sam.pas-----------
(* 10.11.2002

Примерни алгоритми за:
-------------------------------------------
ИЗЧЕРТАВАНЕ НА ЛИНИЯ ПРИ 320x200x256 ($13)
--------------------------------------------
Сравнение между набор процедури на ниско и високо ниво,
част от универсална графична библиотека, писана
от Алексей Фрунзе: http://alex.chat.ru
и "LINA" - единствена процедура на Тодор Арнаудов, изцяло
на ниско равнище.
"LI" показва разписан алгоритъма на "LINA" на високо ранище.
*)



program lina_lina;

var vsega:word;  {сегмент на графичната страница}
    i,j,k:word;

procedure init;assembler;
asm
  mov vsega, $A000      {адрес на графичната страница}
  mov   ax, $13
  int   10H
  mov   ah, $0F
  int   10H
end;

(*-----------------------------------------------*)
(*------------Alexei Frunze----------------------*)

Procedure PutPixel(X, Y : Word; C : Byte); Assembler;
Asm
  Mov   AX, VSegA
  Mov   ES, AX
  Mov   DI, X
  Mov   BX, Y
  ShL   BX, 6
  Add   DI, BX
  ShL   BX, 2
  Add   DI, BX
  Mov   AL, C
  mov es:[di],al {променено от Тош; в оригинала на
		     {Алексей е "STOSB"}
End;

Function Sgn (I : Integer) : Integer; Assembler; 
Asm
  Mov   AX, I
  Or    AX, AX
  JZ    @end
  ShL   AX, 1
  JC    @1
  Mov   AX, 1
  Jmp   @end
@1:
  Mov   AX, -1
@end:
End;

Function _Abs (I : Integer) : Integer; Assembler;
Asm
  Mov   AX, I
  Test  AX, 8000h
  JZ    @end
  Neg   AX
@end:
End;

Procedure Line (X1, Y1, X2, Y2 : Word; C : Byte);
{от "grafix" на Alexei Frunze, http://alex.chat.ru }
Var
  SX, SY, M, N,
  DX1, DY1, DX2, DY2 : Integer;
Begin
  SX := X2-X1;
  SY := Y2-Y1;
  DX1 := Sgn (SX);
  DY1 := Sgn (SY);
  M := _Abs (SX);
  N := _Abs (SY);
  DX2 := DX1;
  DY2 := 0;
  If M < N then
    Begin
      M := _Abs (SY);
      N := _Abs (SX);
      DX2 := 0;
      DY2 := DY1
    End;
  Asm
    Mov   AX, VSegA
    Mov   ES, AX
    Mov   DI, X1
    Mov   BX, Y1
    ShL   BX, 6
    Add   DI, BX
    ShL   BX, 2
    Add   DI, BX                              

    Mov   AX, DY1
    Test  AX, 8000h
    JZ    @lb0
    Neg   AX
    ShL   AX, 6
    Mov   BX, AX
    ShL   AX, 2
    Add   BX, AX
    Neg   BX
    Jmp   @lb1
@lb0:
    ShL   AX, 6
    Mov   BX, AX
    ShL   AX, 2
    Add   BX, AX
@lb1:
    Add   BX, DX1

    Mov   AX, DY2
    Test  AX, 8000h
    JZ    @lb2
    Neg   AX
    ShL   AX, 6
    Mov   DX, AX
    ShL   AX, 2
    Add   DX, AX
    Neg   DX
    Jmp   @lb3
@lb2:
    ShL   AX, 6
    Mov   DX, AX
    ShL   AX, 2
    Add   DX, AX
@lb3:
    Add   DX, DX2

    Mov   AL, C
    Xor   SI, SI
    Mov   CX, M
    Inc   CX
@cycle:
    Mov   ES:[DI],AL { AX - razmazvane }
    Add   SI, N
    Cmp   SI, M
    JC    @cl1
    Sub   SI, M
    Add   DI, BX                                
    Loop  @cycle
    Jmp   @end
@cl1:
    Add   DI, DX                                
    Loop  @cycle
@end:
  End
End;

(*-----====================================================------*)
(*  Тодор Арнаудов (TodProg, Tosh)                               *)

procedure li(x,y,x1,y1:word;c:byte);   {скелет на високо ниво}
var ym,xm:word;
    dx,dy:integer;
    dxa,dya:word;      {абсолюттни}
    dxaa,dyaa:word;
    a,b  :word; {текущи координати}
    q:boolean;
    sx,sy:shortint;
 begin

dx:=x1-x;       {x1>x !}
dy:=y1-y;       {y1>y !}

if (dx>=0) then sx:=1 else sx:=-1;
if (dy>=0) then sy:=1 else sy:=-1;

a:=x;
b:=y;

dxa:=abs(dx);
dya:=abs(dy);
dxaa:=dxa;
dyaa:=dya;

if dxa >= dya then
   begin
ym:=0;
 putpixel(a,b,c);

 while (dxaa>0) do
       begin
            a:=a+sx;
            ym:=ym+dya;
            if (ym > dxa) then begin
                                   b:=b+sy;
                                   ym:=ym-dxa;
                              end;
           putpixel(a,b,c);
           dec(dxaa);
      end;
   end

else
 begin
  xm:=0;
  putpixel(a,b,c);
 while (dyaa>0) do
       begin
            b:=b+sy;
            xm:=xm+dxa;
            if (xm > dya) then begin
                                   a:=a+sx;
                                   xm:=xm-dya;
                              end;
           putpixel(a,b,c);
           dec(dyaa);
      end;
   end;
 end;

{lina - 8.9.2002, използва знаци}
procedure lina(x,y,x1,y1:word;c:byte);
(*
- Изисква само сегмента на графичната страница
- Ицяло на Асемблер
- Около 75 казби
*)
var dex,dey:integer;
    dexx,deyy:word;
    xm, ym:word;
    a,b  :word;
    buf  :word;
    sx,sy:integer; {1,-1 , 320,-320}
 begin
asm
   mov ax,x1
   cmp ax,x
   jb  @sxminus
   mov sx,1
   jmp @sxsled
@sxminus:
   mov sx,-1
@sxsled:
   mov bx,y1
   cmp bx,y
   jb  @syminus
   mov sy,320
   jmp @sysled
@syminus:
   mov sy,-320    {sx,sy - стъпки на преместването}
@sysled:
   mov dx,vsega   {точки}
   mov es,dx
   sub ax,x
   cmp ax,$F000   {ако разликата DX<0, обърни абс. стойн.}
   jb @sledsrav
   not ax         {-100 = +100}
   inc ax
@sledsrav:
   mov dex,ax
   mov dexx,ax
@smetdey:
   sub bx,y
   cmp bx,$F000
   jb @sledsravdey
   not bx
   inc bx
@sledsravdey:
   mov dey,bx
   mov deyy,bx                  {dexx,deyy - abs}
{===============================================}

@sravnixy:
  cmp ax,bx
  ja  @linx     {dex > dey}
  jmp @liny     {dey = < dex}

@linx:
  mov ax,x      {проверка за край на линията}
  mov dx,y      {Първа точка}
  mov di,ax
  shl dx,6
  add di,dx
  shl dx,2
  add di,dx
  mov dl,c

  xor bx,bx      {ym = 0 - проверка за увеличение на y}
  mov ax,dex
{==================================}
@sledplus:
  mov es:[di], dl       {точка}
@sledpix:
  dec ax                {брояч ax}
  cmp ax,0
  je @kra
  add di,sx             {Увеличава X}
  add bx,dey
  cmp bx,dex
  jnb @plusy
  jmp @sledplus
@plusy:
  add di,sy
  sub bx,dex
  jmp @sledplus

@liny:
  mov ax,x     
  mov dx,y      {Първа точка}
  mov di,ax
  shl dx,6
  add di,dx
  shl dx,2
  add di,dx
  mov dl,c

  xor bx,bx      {ym(bx) = 0 - проверка за покачване на y}
  mov ax,dey
{==================================}
@sledplusy:
  mov es:[di], dl       {точка}
@sledpixy:
  dec ax                {брояч dec/jz е по-бавно?}
  cmp ax,0
  je @kra
  add di,sy                {Увеличава X}
  add bx,dex
  cmp bx,dey
  jnb @plusx
  jmp @sledplusy
@plusx:
  add di,sx
  sub bx,dey
  jmp @sledplusy
@kra:
     end;
end;

begin
 init;
(*
Тук се вписват цикли, с които се изследва
бързината на различните процедури.
*)
end.

------------lina_sam.pas----------------
Според изпитанията, "line" изпреварва "lina" само с няколко процента при
завъртане на въртележка на най-дългите за използвания режим отсечки - 0,0,319,199 или 319,199,0,0.
Колкото по-къси са отсечките, толкова повече "незамърсеността" на "lina" с високо равнище изпъква и при отсечки с дължина десетина точки "lina" е до няколко пъти по-бърза от "line".



© Тодор Илиев Арнаудов (Тош), юни 2003 г.
Българска компютърна история от Българските сметачи
Дружество "Разум"
Пиши на Тош: dzbe@mail.bg, todprog@yahoo.com
Прочети още статии от Тош и други автори: http://bgit.net