Artykuły

    Kurs Assemblera cz. 8

    PLOT, DRAWTO, CIRCLE, FILL POLYGON

    Wstęp

    Kto by pomyślał, ósma część Waszego ulubionego kursu :) W tym odcinku zajmę się bardzo praktycznym zastosowaniem asemblera 6502 w rysowaniu po ekranie. Nareszcie coś co będzie można zastosować w zrealizowaniu jakiegoś projektu na malucha. Zamiast bawić się w Basic'u w rysowanie kresek, kółek itp. tutaj zrobimy to znacznie szybciej i efektywniej.

    Procedury rysujące linie, okręgi czy stawiające pojedyńcze pixle to podstawa każdej podręcznej biblioteki programisty. Oglądając jednak ostatnio niektóre produkcje scenowe, można dojść do wniosku, że nie każdy ma w swoich zbiorach te podstawowe procedurki. Być może także osoby, które uważają że wszystko już wiedzą natrafią tutaj na interesujący wątek. W końcu dobrze jest się przekonać, że inni też robią to w ten sposób i że szybciej się nie da :) Sam się ostatnio zdziwiłem, gdy odkryłem znacznie szybszy sposób wyznaczania krawędzi wielokąta niż "czysty" Bresenham. No ale pewnie już o tym wszyscy wiedzą, tylko ja dowiaduje się o tym na końcu ;)

    O tematach tutaj poruszanych można poczytać po polsku m.in. tu http://www.republika.pl/wmula/prog/bresenham.html#4. Znajdziecie tam wzory matematyczne i rysunki. W samym kursie nie będę tak dokładnie tłumaczył rysowania linii czy okręgu, skupie się na implementacji algorytmów w asemblerze.

    1. Pamięć obrazu Atari.

    Na początek małe przypomnienie, tego co każdy już wie, a co było we wcześniejszych kursach. Aby zacząć stawiać pixle, rysować linie itp. musimy wiedzieć po czym rysujemy i jaki jest najmniejszy nośnik informacji,który pozwala zaprezentować na ekranie pixel i jego kolor.

    Na Atari nie ma trybów "chunky" jak na PC, gdzie jeden bajt to jeden pixel. Nie ma tak prosto :) Na Atari jeden bajt to od 2 do 8 pixli, w zależności od użytego trybu graficznego, tzn. w jednym bajcie konkretna kombinacja bitów odpowiada za kolor i szerokość pixla. Dlatego np. w trybie 9OS mamy tak szerokie pixele, mamy tam dostępnych 16 odcieni jednego koloru, więc jeden pixel to 4 bity.

    Oprócz wybranego trybu graficznego, który determinuje liczbę dostępnych kolorów, oraz szerokość pixla czyli proporcje obrazu, mamy jeszcze możliwość wybrania szerokości obrazu. Dostępne są trzy szerokości: wąski, normalny i szeroki. Odpowiada za nie rejestr DMACTL ($D400) i dwa jego najmłodsze bity (cień tego rejestru DMACTLS znajduje się pod adresem $22F):

         000000xx
         76543210 - numer bitu
         
     bity 0-1  00 - brak obrazu
               01 - obraz wąski, jedna linia obrazu liczy wtedy 32 bajty
               10 - obraz normalny, jedna linia obrazu liczy wtedy 40 bajtów
               11 - obraz szeroki, jedna linia obrazu liczy wtedy 48 bajtów 
    
     bit 2     DMA dla pocisków (1 = włączony)
     bit 3     DMA dla graczy (1 = włączony)
     bit 4     rozdzielczość PMG (0 = dwu-, 1 = jednoliniowa)
     bit 5     DMA dla programu ANTIC-a (1 = włączony)
     bity 6-7  niewykorzystane
    

    Im obraz mniejszy tym mniej miejsca zajmie w pamięci RAM, a ANTIC zostawi więcej wolnych cykli dla CPU.

    Podsumowując pamięć obrazu ANTIC'a składa się z bajtów, ułożonych liniowo. Jedna linia obrazu to 32 lub 40 lub 48 bajty. Pamięć ograniczona jest do 4kB, czyli maksymalny ciągły obszar liczy sobie 4096 bajtów, potem musimy znowu załadować nowy adres do licznika pamięci ANTIC'a. Te adresy nie są zbyt dowolne, najlepiej aby zawsze mieściły się w granicy 4kB bloku pamięci.

    W przypadku obrazu wąskiego uda nam się zmieścić 4096/32=128 linii, dla obrazu o szerokości normalnej będzie tych linii już tylko 102, dla najszerszego 85.

    Adres (WORD) programu dla ANTIC'a umieszczamy w cieniu rejestru DLPTRS $230..$231, a jeśli OS jest wyłączony to bezpośrednio w DLPTR $d402..$d403, np.

    Przykład: ANTIC_1.ASM
    
          org $0600
          
    main  mwa #antic $230
          lda #%00100001     ; obraz wąski
          sta $22f
    
    loop  jmp loop
    
    antic dta d'ppppppp'     ; 7 x 8 pustych linii = 56 pustych linii
          dta $4f,a($2000)   ; licznik pamięci obrazu = $2000, tryb 8OS
          :128 dta $0f
          dta $41,a(antic)   ; czekaj ramkę i zaczynaj tworzyć obraz ANTIC
          
          run main
    

    I tak powstał wąski ekran z wycentrowanym na środku obszarem w trybie 8 OS.

    A jeśli chcemy zmieścić więcej grafiki, więcej niż 4kB, a znacznym ułatwieniem jest ciągłość takiego obszaru, to będziemy musieli "skleić" dwa obszary po 4kB każdy. Jeśli mamy wąski ekran, to nie ma problemu, w każdych 4kB mieści się równo 128 linii, w pozostałych szerokościach trzeba będzie pierwszy obszar przesunąć tak, aby jego koniec pokrywał się w początkiem drugiego obszaru.

    Przykład: ANTIC_2.ASM
    
          org $0600
    
    gfx1  equ $2010
    gfx2  equ $3000
          
    main  mwa #antic $230
          lda #%00100010     ; obraz normalny, o szerokości 40 bajtów
          sta $22f
    
    loop  jmp loop
    
    antic dta d'ppp'         ; 3 x 8 pustych linii = 24 puste linie
          dta $4e,a(gfx1)    ; licznik pamięci obrazu = gfx1, tryb 15OS
          :101 dta $0e
          dta $4e,a(gfx2)    ; licznik pamięci obrazu = gfx2, tryb 15OS
          :89 dta $0e
          dta $41,a(antic)   ; czekaj ramkę i zaczynaj tworzyć obraz ANTIC
          
          run main
    

    Otrzymaliśmy ekran o wysokości 192 linii, o szerokości normalnej w trybie 15OS. Dzięki temu, że adres GFX1 przesunięty jest o 16 bajtów i mamy 102 linie (102*40=4080) obszar styka się bezpośrednio z GFX2. W ten sposób najwyżej dwa obszary możemy ze sobą scalić (dla szerokości obrazu <> 32), w pozostałych przypadkach nie pozostaje nic innego jak przemieszczenie grafiki na początek bloku 4kB i liczenie się z tym że będą "dziury".

    2. PLOT

    PLOT to nic innego jak kasowanie i ustawianie odpowiednich bitów w bajcie.

        00000000  - bajt w którym wszystkie bity są skasowany
        00010000  - bajt w którym 4 bit jest ustawiony
        11000000  - bajt w którym dwa najstarsze bity są ustawione (bit 6..7)
    

    Jak ustawić bity ?

        lda #%00000000
        ora #%00010000   ; bit 4-y ustawiony
        
        lda #%00000000
        ora #%00001111   ; bity 0..3 ustawione
       
        lda #%00000000
        ora #%11000000   ; bity 6..7 ustawione
    

    Jak skasować bity ?

        lda #%10010000
        and #%11101111   ; bit 4-y skasowany, bit 7 zostal zachowany
        
        lda #%00001111
        and #%11110000   ; bity 0..3 skasowane
    
        lda #%11000000
        and #%00111111   ; bity 6..7 skasowane
    

    Innymi słowy dokonaliśmy operacji OR i AND na bitach. OR ustawia, AND kasuje. Dokonaliśmy tych operacji za pomocą masek ANDowania i ORowania. Maski te będą nam potrzebne aby móc zapalać i kasować konkretne pixle w konkretnym trybie graficznym. Koloru 0 nie będziemy brać pod uwagę, w końcu nie interesuje nas stawianie niewidocznych pixli, czy też kasowanie uprzednio postawionych, bo kasować to można szybciej.

    8 OS:
    and_mask dta %01111111,%10111111,%11011111,%11101111
             dta %11110111,%11111011,%11111101,%11111110
    ora_mask dta %10000000,%01000000,%00100000,%00010000
             dta %00001000,%00000100,%00000010,%00000001
    
    15 OS:
    and_mask dta %00111111,%11001111,%11110011,%11111100
    ora_mask dta %01000000,%00010000,%00000100,%00000001  ; kolor 1
             dta %10000000,%00100000,%00001000,%00000010  ; kolor 2
             dta %11000000,%00110000,%00001100,%00000011  ; kolor 3
    
    9 OS:
    and_mask dta %00001111,%%11110000
    

    Przykładowo stawiamy pixel na ekranie o zadnym kolorze. Jeśli tryb grafiki to HiRes, będziemy mieli do dyspozycji tylko dwa kolory, czyli bit w bajcie zapalony lub bit skasowany, np. PLOT 14,5 (X=14, Y=5), czyli mamy zapalić 14 pixel w 5-ej linii.

    Jak znaleźć bajt w linii, w którym znajduje się 14 pixel ?

    Dzielimy pozycję X przez liczbę pixli na bajt, dla HiRes będzie to wartość 8 (w jednym bajcie znajduje się 8 pixli). Na szczęście CPU6502 ma dzielenie przez potęgę dwójki (2^3=8), więc nie jest źle.

         ldx #14
         ldy #5
         jsr plot
         ...
    
    plot txa
         :3 lsr @      ; dzielimy przez 8 czyli przesuwamy o 3 bity w prawo
         tay
    

    Mamy teraz w rejestrze Y numer bajtu, w którym znajduje się pixel, który mamy zapalić. Ogólnie dokonaliśmy dzielenia pozycji X przez 8 bez reszty, czyli regY=regX div 8.

    Ale który pixel w bajcie mamy zapalić ?

    Teraz przydałaby się reszta z dzielenia regX=regX mod 8.

         txa
         and #7     ; andujemy 3 najmłodsze bity (%00000111)
         tax
    

    Mamy już w regY ofset do bajtu, w regX ofset do bitu, ale zapomnieliśmy o pozycji Y, nie mamy adresu 5-ej linii (Y=5). Aby otrzymać adres 5-ej linii, musimy pomnożyc pozycję Y przez szerokość obrazu (5*40) i dodać otrzymaną wartość do adresu początkowego obrazu.

    Tutaj nie pomnożymy już przez potęgę dwójki (5*40), ale zamiast pisać procedurę do mnożenia wartości jedno bajtowych, użyjemy dopalacza w postaci tablicy. Aby wygenerować taką tablicę nie trzeba mnożenia, bo wiemy że mnożenie możemy zastąpić dodawaniem, np. 7*5=(7+7+7+7+7).

    init  mwa #gfx adres   ; adres pamięci obrazu do zmiennej ADRES (WORD)
    
          ldy #0           ; inicjowanie licznika pętli regY=0
    in_0  lda adres        ; przepisanie młodszego bajtu do tablicy 'l_line'
          sta l_line,y
          lda adres+1      ; przepisanie starszego bajtu do tablicy 'h_line'
          sta h_line,y
          
          lda adres        ; zwiekszenie zmiennej ADRES o szerokość obrazu (32)
          clc              ; ADRES = ADRES + 32
          adc #32
          sta adres
          bcc *+4
          inc adres+1
          
          iny              ; zwiekszenie licznika petli
          cpy #128         ; wartosc maksymalna petli
          bne in_0         ; jesli nie osiagnął wartości maksymalnej to skacz pod 'in_0'
    

    Mamy teraz tablice z początkowymi adresami linii obrazu, młodszy bajt adresu w tablicy L_LINE, starszy w H_LINE. Teraz bez większych problemów możemy odczytać adres konkretnej linii obrazu na początku procedury PLOT, oraz postawić pixel.

    Przykład: PLOT_1.ASM
    
    plot lda l_line,y     ; odczytujemy z tablic adres linii
         sta adres
         lda h_line,y
         sta adres+1
         
         txa              ; DIV
         :3 lsr @         ; dzielimy przez 8 czyli przesuwamy o 3 bity w prawo
         tay
    
         txa              ; MOD
         and #7           ; ANDujemy 3 najmłodsze bity (%00000111)
         tax
         
         lda (adres),y    ; pobieramy bajt z pamięci obrazu
         ora ora_mask,x   ; stawiamy pixel
         sta (adres),y    ; z powrotem stawiamy bajt w pamięci obrazu
         rts
    

    W końcu postawiliśmy pixel na ekranie, jednak ta procedura nie jest jeszcze najszybsza. Możemy przecież zastąpić operacje DIV i MOD dodatkowymi tablicami. Dopiszemy w podprogramie inicjalizacyjnym:

          ldy #0
    in_1  tya
          :3 lsr @
          sta tab_div,y
          iny
          bne in_1
    

    Następnie zamiast obliczać MODulo, powtórzymy 32 razy tablice ORA_MASK, dzięki czemu będziemy odczytywali konkretna wartość maski ORA o indeksie równym pozycji X stawianego pixla.

    ora_mask :32 dta $80,$40,$20,$10,8,4,2,1
    
    Przykład: PLOT_2.ASM
    
    plot lda l_line,y     ; odczytujemy z tablic adres linii
         sta adres
         lda h_line,y
         sta adres+1
         
         ldy tab_div,x    ; dzielimy pozycje X przez 8 dzieki tablicy TAB_DIV
    
         lda (adres),y
         ora ora_mask,x   ; ustawiamy pixel dzieki rozpisanej tablicy ORA_MASK
         sta (adres),y
         rts
    

    Czy jest to najszybsza możliwa procedura stawiająca pixel ? Otóż nie. Dla większego przyspieszenia stawiania pixla można inaczej zorganizować pamięć obrazu, co 256 bajtów.

    antic dta d'ppppppp'     ; 7 x 8 pustych linii = 56 pustych linii
          dta $4f,a(gfx)
          dta $4f,a(gfx+$100)
          dta $4f,a(gfx+$200)
          dta $4f,a(gfx+$300)
          ...
          dta $41,a(antic)
    

    Dzięki takiej organizacji pamięci, młodszy bajt adresu linii obrazu zawsze jest równy 0 (lub innej stałej wartości) i będziemy używać tylko tablicy ze starszymi bajtami adresu linii obrazu H_LINE lub wcale jeśli umieścimy pamięć obrazu od strony zerowej. Bez obaw nie zajmiemy całej strony pamięci tylko jej wybrana cześć, stos też będzie działał, zostanie też miejsce na stronie zerowej. W końcu przy takiej organizacji pamięci obrazu potrzeba nam tylko od 32 do 48 bajtów na każdej ze stron pamięci, lub od 64 do 96 jeśli użyjemy dwubuforowania.

    plot sty adres+1      ; wartość z regY jest starszym adresem linii obrazu
     
         ldy tab_div,x    ; dzielimy pozycje X przez 8 dzieki tablicy TAB_DIV
    
         lda (adres),y
         ora ora_mask,x   ; ustawiamy pixel dzieki rozpisanej tablicy ORA_MASK
         sta (adres),y
         rts
    

    Dodatkowo umieścimy PLOT'a na stronie zerowej, dzięki czemu powstanie najszybsza możliwa procedura stawiająca pixel dla Atari 8-bit :) Wypadałoby też zrezygnować z wywołania procedury przez JSR i powrót przez RTS, gdyż zabiera to razem 12 cykli CPU. Trzeba po prostu PLOT'a wpleść w kod programu.

    Przykład: PLOT_3.ASM
    
         org zero_page
     
    plot dta {sty 0},adres+1 ; rozkaz STY($84) strony zerowej, tutaj kompilator
                             ; mysli ze ADRES jest dwubajtowy
                             ; wiec musimy wyprowadzic go z bledu "ręcznie"
         
         ldy tab_div,x       ; dzielimy pozycje X przez 8 dzieki tablicy TAB_DIV
                             ; czyli wczytujemy do regY wartosc z TAB_DIV
                             ; o indeksie w regX
    
         lda $ff00,y         ; tutaj mamy 4cyklowa komende LDA $FF00,Y której
                             ; adres modyfikujemy dzieki takiej
    adres equ *-2            ; deklaracji adresu ADRES (2 bajty wstecz *-2)
    
         ora ora_mask,x      ; ustawiamy pixel dzieki rozpisanej tablicy ORA_MASK
         sta (adres),y       ; 5cyklowa komenda STA (ADRES),Y dziala tylko dlatego
                             ; ze nasz PLOT jest na ztronie zerowej
    

    W stosunku do wcześniejszej wersji PLOT'a jest to jedno cyklowa oszczędnośc, zawsze to coś :) W sumie postawienie jednego pixla zajmie nam 20 cykli CPU.

    3. DRAWTO - BRESENHAM

    W Basic'u komenda DRAWTO odpowiada za rysowanie linii, od pozycji początkowej jaka została wskazana wcześniej przez PLOT, czyli ogólnie rzecz biorąc zajmiemy się tutaj rysowaniem linii.

    Naszą linię charakteryzować będą dwie pary współrzędnych (x1,y1)(x2,y2) oraz kąt nachylenia 'm'.

        (x1,y1)
           *--------                           
                    ---------                dy=(y2-y1)
                             ---------*      
                                    (x2,y2)
                     dx=(x2-x1)
                     
         m=dy/dx  ->  kąt nachylenia
    

    Pozycja X zwiększana będzie zawsze o 1, natomiast pozycja Y o 'm'. Algorytm takiego postępowania nazywamy przyrostowym. W pseudo kodzie Pascala taki program rysujący linie mógłby wyglądać następująco:

     Y=Y1;
     DX=X2-X1; DY=Y2-Y1;
     M=DY/DX;
     
     for X=X1 to X2 do
      begin
       plot(X,Y); Y=Y+M
      end
    

    Zadziała to dla tego konkretnego nachylenia linii, dla pozostalych trzech możliwości będzie trzeba zmodyfikować tylko w/w schemat postępowania. Proste i przyjemne :), no może nie zupełnie bo operacja dzielenia nie jest naturalna dla CPU6502. Można stablicować wszystkie możliwe dzielenia dla konkretnego zakresu wartości, np. dla wartości 0..127 tablica zajmie nam jedyne 128x128=16384 bajtów, czyli bank pamięci, będzie to jednobajtowa precyzja, dwubajtowa zajmie dwukrotnie więcej.

    Bez przesady, żartowałem, nie będziemy nic tablicować. Pan Bresenham nas wyręczył, wymyślił algorytm z punktem środkowym, można poczytać o nim m.in. tutaj http://www.republika.pl/wmula/prog/bresenham.html#4

    Algorytm z punktem środkowym zaproponowany przez Bresenhama służy rasteryzacji krzywych 2D. Jego implementacja jest bardzo prosta i jednocześnie efektywna. W głównej pętli algorytmu wykorzystywane są zaledwie dwie operacje: porównania i dodawania; algorytm może działać zarówno na liczbach zmiennoprzecinkowych, jak i całkowitych.

    Zamiast jednak przytaczać tutaj wzory funkcji, schematy itp. podam gotowy, sprawdzony w działaniu program w Pascalu, rysujący linię wg. algorytmu Bresenhama. W sieci można znaleźć sporo informacji na ten temat, także gotowe programy, które dziwnym trafem nie zawsze rysują to co powinny.

    Przykład: BRESENHAM.PAS
    
    procedure Line (x1, y1, x2, y2, color : byte);
    { d : shortint; }
    { dinc2 : byte; }
    { dla takiej deklaracji zmiennych d oraz dinc2 odcinki }
    { mialyby ograniczona dlugosc do abs(x2-x1)=<0..64> }
    
    var d:integer;
        dinc2 : word;
        xinc1, xinc2, yinc1, yinc2, dinc1, i, npix, dx, dy, x, y : byte;
    begin
    
     { obliczenie 'dx' i 'dy' }
      dx := abs(x2 - x1);
      dy := abs(y2 - y1);
    
     { inicjalizujemy zmienne, w zależności od tego czy pozycja }
     { pozioma X będzie zwiększana, czy też pozycja pionowa Y}
      if dx >= dy then
        begin
    
     { X jest tutaj zwiększaną zmienną }
          npix := dx;
          dinc1 := dy Shl 1;
          d := dinc1 - dx;
          dinc2 := (dy - dx) shl 1;
          xinc1 := 1;
          xinc2 := 1;
          yinc1 := 0;
          yinc2 := 1;
        end
      else
        begin
    
     { Y jest tutaj zwiększaną zmienną }
          npix := dy;
          dinc1 := dx Shl 1;
          d := dinc1 - dy;
          dinc2 := (dx - dy) shl 1;
          xinc1 := 0;
          xinc2 := 1;
          yinc1 := 1;
          yinc2 := 1;
        end;
    
     { upewniamy się, że pozycje X,Y są skierowane w prawą stronę }
      if x1 >= x2 then
        begin
          xinc1 := - xinc1;
          xinc2 := - xinc2;
        end;
    
      if y1 >= y2 then
        begin
          yinc1 := - yinc1;
          yinc2 := - yinc2;
        end;
    
     { zaczynamy rysowanie linii, od pozycji (x1,y1) } 
      x := x1;
      y := y1;
    
     { główna pętla wyznaczająca punkty linii }
      for i := 0 to npix do begin
    
          PutPixel(x, y, color);
    
          if d < 0 then
            begin
              d := d + dinc1;
              x := x + xinc1;
              y := y + yinc1;
            end
          else
            begin
              d := d + dinc2;
              x := x + xinc2;
              y := y + yinc2;
            end;
        end;
    end;
    

    Mamy gotowy program w Pascalu, wszystkie zmienne sprowadzone zostały do najprostszej postaci typu BYTE, WORD, INTEGER, teraz tylko przepisać to na asembler.

    Na początek musimy zaimplementować funkcję ABS, aby obliczyć DX oraz DY. Funkcja ABS zwraca wartość bez znaku, np.

       abs(-2) = 2
       abs(-9) = 9
       abs(5) = 5
    

    Jak to zapisać w asemblerze ? Najprościej sprawdzić która z dwóch wartości jest największa i od niej odjąć mniejszą, wtedy na pewno wynik zawsze będzie dodatni :)

        lda x2
        cmp x1
        bcs gt   ; jeśli x2 >= x1 to skocz do 'gt'
    
        lda x1   ; tutaj x2 < x1, wiec  
        sec      ; dx=x1-x2
        sbc x2
        jmp skp
                   
    gt  lda x2   ; dx=x2-x1
        sec
        sbc x1
    
    skp sta dx
    

    Tragicznie dużo tego kodu, jak na biedne ABS, a przecież można szybciej i krócej. Odejmujemy wartości typu BYTE i wynik odejmowania też będzie typu BYTE, jeśli w BYTE ma być jeszcze informacja o znaku + -, to w takiej zmiennej przechowamy wartości z zakresu -128..127 (będzie to odpowiednik Pascal'owego typu SHORTINT). Wartości 0..127 będą miały skasowany bit7 w bajcie, wartości -128..-1 ustawiony bit7. I tak możemy rozpoznać czy wartośc jest dodatnia czy ujemna.

        lda x2
        sec
        sbc x1
        bpl _ok   ; wartość dodatnia, więc kończ
    
        eor #$ff  ; tutaj wartość ujemna
        adc #1    ; musimy zmienić znak
    	  
    _ok sta dx
    

    Zmiana znaku to operacja uzupełnienie do dwóch (albo zapis w odwrotnej notacji polskiej, o ile mnie pamięć nie myli). W szczegóły wdawać się nie będę, ogólnie polega to na odwróceniu wszystkich bitów (eor #$ff) i zwiększenie wyniku o jeden (adc #1).

    Chcesz poznać zapis liczby -37 w uzupełnieniu do dwóch ?

        lda #37
        eor #$ff
        adc #1
    

    I w regA mamy wartość -37 ;), a raczej $db, tak więc $db oznacza -37.

    W dalszej części programu ciekawe wartości przyjmują zmienne xinc1, xinc2, yinc1, yinc2, bo z zakresu -1..1. Skoro 1 oznacza zwiększanie o jeden, -1 zmniejszanie o jeden, a asembler daje do dyspozycji odpowiedniki takich operacji 'inx', 'dex', 'iny', 'dey' to aż prosi się aby to wykorzystać. Będziemy musieli dokonywać modyfikacji programu w "locie", dodatkowo musimy znać kody mnemoników wymienionych wcześniej. Jeśli jednak używamy XASM'a kompilator nas wyręczy gdy umieścimy mnemonik w nawiasie klamrowym {}.

            lda #{inx}   ; xinc2=1
            sta xinc2
            
            lda #{iny}   ; yinc1=1
            sta yinc1
            sta yinc2    ; yinc2=1
            
            lda #{nop}   ; xinc1=0
            sta xinc1
    

    Dalej w programie dokonywana jest zmiana znaku zmiennych xinc1, xinc2, yinc1, yinc2.

          xinc1 := - xinc1;
          xinc2 := - xinc2;
          ...
          yinc1 := - yinc1;
          yinc2 := - yinc2;
    

    Jak to zrealizować w asemblerze ?

    Zastąpiliśmy już te zmienne odpowiednimi mnemonikami typu: inx, dex, iny, dey. Wystarczy teraz dokonać zamiany inx<>dex, iny<>dey, a nop<>nop za pomocą operacji EOR i będziemy mieli zmieniony kierunek działania. Analizujac kod programu w Pascalu można zauważyć, że tylko xinc1 i yinc1 przyjmują wartość '0', a '0' to u nas nic nie robiący 'NOP'. 'NOP' nie może być eor-owany, w końcu zero nie ma znaku plus ani minus. Tak więc, eorować będziemy tylko xinc2 i yinc2, pozostałe zmienne musimy załatwić inaczej.

      lda xinc2
      eor #[{inx}^{dex}]  ; znak ^ oznacza operacje EOR
      sta xinc2
      ...
      lda yinc2
      eor #[{iny}^{dey}]
      sta yinc2
    

    Dla xinc1, yinc1 wymyśliłem sobie tablice ZMIANA_ZNAKU. Odczytając z tej tablicy wartość o indeksie równym kodowi mnemonika otrzymamy nowy kod mnemonika o działaniu przeciwnym, lub ten sam kod w przypadku 'NOP'. Stworzenie tej tablicy polegać będzie na kilku operacjach zapisu do pamięci, pamięci czyli tablicy ZMIANA_ZNAKU:

          ldy #{inx}
          lda #{dex}
          sta zmiana_znaku,y
    
          ldy #{dex}
          lda #{inx}
          sta zmiana_znaku,y
    
          ldy #{iny}
          lda #{dey}
          sta zmiana_znaku,y
    
          ldy #{dey}
          lda #{iny}
          sta zmiana_znaku,y
    
          ldy #{nop}
          lda #{nop}
          sta zmiana_znaku,y
    

    Proste i skuteczne, teraz zmiana znaku zmiennych polega tylko na:

          ldy xinc1
          lda zmiana_znaku,y
          sta xinc1
          ...
          ldy yinc1
          lda zmiana_znaku,y
          sta yinc1
    

    Reszta operacji w programie to dodawanie i odejmowanie, nie powinno być z tym problemów. W przypadku sumowania lub odejmowania wartości 8 bitowych, w wyniku którego ma powstać wartość 16 bitowa, musimy zadbać o najstarszy bajt takiego wyniku.

          d := dinc1 - dx;
    

    W asemblerze zrobimy to tak:

          lda dinc1
          sec
          sbc dx
          sta d
          lda #0      ; tutaj zgarniemy nadmiarowy bit, który
          sbc #0      ; mógł powstać przy odejmowaniu młodszych bajtów
          sta d+1
    

    To byłby już koniec dla tych którzy nie analizowali przykładowego programu BRESENHAM.PAS. Ci którzy sie mu przyjrzeli zauważyli pewnie, że można jeszcze szybciej narysować linię i to bez tablicy ZMIANA_ZNAKU.

    OPTYMALIZACJA

    Na pierwszy ogień pójdzie fragment, w którym inicjalizowane są zmienne dinc1, d, dinc2 w zależności od tego czy zwiększana jest pozycja X czy Y.

          dinc1 := dy Shl 1;
          d := dinc1 - dx;
          dinc2 := (dy - dx) shl 1;
    

    Gdy rozpiszemy dinc2, otrzymamy:

          dinc2 := dy shl 1 - dx shl 1;
    

    Widzimy, że 'dy shl 1' to wcześniej obliczone dinc1. Z kolei zmienna d to 'dinc1 - dx', więc wystarczy jeszcze raz odjąć dx i otrzymamy 'dinc1 - dx - dx' czyli 'dinc1 - dx shl 1'. Podsumowując, otrzymujemy:

          dinc1 := dy Shl 1;
          d := dinc1 - dx;
          dinc2 := d - dx;
    

    W dwóch miejscach programu będziemy mogli zastosować tą optymalizację.

    Następnie przyjrzymy się zmiennym xinc1, yinc1, xinc2, yinc2. Widać, że xinc2, yinc2 przyjmują na początku zawsze wartość '1', skoro tak to nie musimy zmieniać ich znaku przez 'xinc2 = -xinc2', tylko wpiszemy go na sztywno 'xinc2 = -1'.

    Pozatym możemy fragment programu sprawdzający czy współrzędne (x1,y1)..(x2,y2) są skierowane w prawo, umieścić obok inicjalizacji zmiennych w zależności od tego czy zwiększamy X czy Y. Dzięki temu będziemy znali wartości xinc1, yinc1, xinc2, yinc2, i przez to zmiana znaku polegać będzie tylko na wpisaniu "na sztywno" konkretnej wartości do zmiennej.

    Przykład programu w Pascalu, po optymalizacji:

    Przykład: BRES_2.PAS
    
    procedure Line(x1, y1, x2, y2, color : byte);
    { d : shortint; }
    { dinc2 : byte; }
    { dla takiej deklaracji zmiennych d oraz dinc2 odcinki }
    { mialyby ograniczona dlugosc do abs(x2-x1)=<0..64> }
    
    var d:integer;
        dinc2 : word;
        xinc1, xinc2, yinc1, yinc2, dinc1, i, npix, dx, dy, x, y : byte;
    begin
    
     { Calculate dx and dy for initialisation }
      dx := abs(x2 - x1);
      dy := abs(y2 - y1);
    
      xinc2 := 1;
      yinc2 := 1;
    
     { Initialize all vars based on which is the independent variable }
      if dx >= dy then
        begin
    
     { x is independent variable }
          npix := dx;
          dinc1 := dy Shl 1;
          d := dinc1 - dx;
          dinc2 := d - dx;
          xinc1 := 1;
          yinc1 := 0;
    
     { Make sure x and y move in the right directions }
          if x1 >= x2 then
           begin
            xinc1 := $ff;   { $ff oznacza -1 }
            xinc2 := $ff;
          end;
    
          if y1 >= y2 then yinc2 := $ff;
    
        end
      else
        begin
    
     { y is independent variable }
          npix := dy;
          dinc1 := dx Shl 1;
          d := dinc1 - dy;
          dinc2 := d - dy;
          xinc1 := 0;
          yinc1 := 1;
    
     { Make sure x and y move in the right directions }
          if x1 >= x2 then xinc2 := $ff;
    
          if y1 >= y2 then
           begin
            yinc1 := $ff;   { $ff oznacza -1 }
            yinc2 := $ff;
          end;
    
        end;
    
     { Start drawing at (x1, y1) }
      x := x1;
      y := y1;
    
     { Draw the pixels }
      for i := 0 to npix do begin
    
          PutPixel(x, y, color);
    
          if d < 0 then
            begin
              d := d + dinc1;
              x := x + xinc1;
              y := y + yinc1;
            end
          else
            begin
              d := d + dinc2;
              x := x + xinc2;
              y := y + yinc2;
            end;
        end;
    end;
    

    To tyle jeśli chodzi o DRAWTO i rysowanie wg BRESENHAMA

    4. CIRCLE - BRESENHAM

    Okrąg, wg. Bresenhama z ośmio krotną symetrią. Gotowy, działający program w Pascalu poniżej:

    Przykład: CIRCLE.PAS
    
    { ks - pozycja pozioma srodka okregu }
    { ws - pozycja pionowa srodka okregu }
    { r  - promien okregu }
    
    procedure Circle(ks, ws, r: byte);
    var x, y, mo, og, ou:byte;
    begin
    
    y := 0;
    x := r;
    mo := 0;
    
    while x >= y do begin
    
    plot(ks+x, ws+y);
    plot(ks-x, ws+y);
    plot(ks+x, ws-y);
    plot(ks-x, ws-y);
    plot(ks+y, ws+x);
    plot(ks+y, ws-x);
    plot(ks-y, ws+x);
    plot(ks-y, ws-x);
    
    og := mo + y + y + 1;
    ou := og - x - x + 1;
    
    y := y + 1;
    mo := og;
    
      if ou < og then
      begin
       x := x - 1;
       mo := ou;
      end;
    
    end;
    
    end;
    

    Wszystkie zmienne są typu BYTE (ograniczy to promień naszego okręgu do r=95), więc przełożenie programu na asembler nie będzie skomplikowane.

    Z ciekawszych sztuczek jakie można tu zastosować, jest zwiększenie wartości o 1 przy dodawaniu lub odejmowaniu za pomocą znacznika przeniesienia C. Mam tu na myśli ten fragment programu:

    og := mo + y + y + 1;
    ou := og - x - x + 1;
    

    Ustawiony znacznik przeniesienia (SEC) podczas dodawania w naturalny sposób zwiększy nam wynik dodawania o 1, natomiast skasowany znacznik przeniesienia (CLC) podczas odejmowania zwiększy wynik odejmowania o 1.

            lda mo
            sec     ; znacznik przeniesienia C ustawiony (set C)
            adc y
            adc y
            sta og
            
            clc     ; znacznik przeniesienia C skasowany (clear C)
            sbc x
            sbc x
            sta ou
    

    5. FILL POLYGON

    Wielokąt (polygon) tym różni się od lini ciągłych (line), że jest figurą zamkniętą. Ostatni punkt figury automatycznie łączy się z pierwszym tworząc całość, czyli wielokąt (wielobok). Najprostszym polygonem jest trójkąt, który powstaje z połączenie trzech punktów. A jeśli połączymy cztery punkty powstanie czworokąt :) i takimi polygonami tutaj będziemy się zajmować. Zresztą bez większych problemów można przerobić procedurę wypełniającą czworokąt na wypełniającą trójkąt (czwarty wierzchołek pokrywa się z trzecim).

    Co jest nam potrzebne ?

    Do pełni szczęścia potrzebna jest nam informacja o współrzędnych poziomych lewej i prawej krawędzi. Jeśli już je zdobędziemy, wystarczy je tylko połączyć poziomym odcinkiem.

    Oto przykładowy czworokąt, w tragicznej rozdzielczości ASCII :). Na szczęście widać jak łączone są poszczególne punkty. Kolejność ich łączenia nie jest przypadkowa, wszystko odbywa się zgodnie z ruchem wskazówek zegara, czyli w prawą stronę. Dzięki temu, że wielokąt jest prawoskrętny możemy jednoznacznie określić która krawędź jest prawa, a która lewa np. jeśli odcinek jest rysowany w dół (x1,y1)-(x2,y2) to jest krawędzią prawą, jeśli w górę (x3,y3)-(x4,y4) to krawędzią lewą.

                    
                        (x1,y1)
                          / \
                      /      \
                  /           \
              /                \ 
     (x4,y4) \                  \
              \                  / (x2,y2)
               \               /
                \            /
                 \         /
                  \      /
                   \   /
                    \/ 
                  (x3,y3)
    

    Teraz wystarczy tylko współrzędne poziome X umieszczać w odpowiedniej tablicy, odpowiedniej ze względu na prawą i lewą stronę. Dzięki takiej organizacji będziemy zawsze łączyć mniejszą wartość X z większą.

    6. BRESENHAM RUN-LENGTH SLICE

    Tutaj opisze algorytm, którego głównym zadaniem jest wyznaczenie pierwszych punktów krawędzi linii, czyli taki który przyda się gdy będziemy wypełniać polygon w postaci czworokąta, czy też innego wielokąta. Przy jego pomocy można także narysować linię, trzeba tylko napisać szybką procedurę rysującą poziome odcinki o zadanej długości, bowiem istotą tego algorytmu jest właśnie rysowanie linii w poziomie.

          (x1,y1)
             #----
                  #-----
                        #------
                               #-----
                                   (x2,y2)
                                   
      # oznacza pierwszy pixel na danej pozycji Y                              
    

    Ogólnie rzecz biorąc, poruszamy się w pionie, w przedziale Y=Y1..Y2, dla każdej nowej pozycji Y wyznaczana jest nowa pozycja X, czyli pierwszy punkt odcinka i jego długość. To wszystko, proste i diabelnie szybkie. Jest jednak małe ale, rysując linie tym algorytmem możemy narysować jej za dużo, dlatego najlepiej używać go tylko do wyznaczania punktów krawędzi linii. Pozatym występuje tu operacja dzielenia, której stablicowanie zajmie 32 kB pamięci (dla zakresu wartości 0..127).

    Przykład działającego programu w Pascalu poniżej.

    Przykład: BRES_RLS.PAS
    
    var miny, cnt: byte;
    
    procedure Line(x1, y1, x2, y2: byte);
    var x, m: word;
        adx, ady, rlen, y, dx, dy, npix: byte;
    begin
    
     npix := y2;      { wartość końcowa głównej pętli }
    
     dx := abs(x2 - x1);
     dy := abs(y2 - y1);
    
     { ustawiamy zmienna 'adx' na '$ff' jesli }
     { pozycja pozioma ma byc zmniejszana, a na '1' }
     { jesli ma byc zwiekszana }
     if x2-x1 < 0 then adx := $ff else adx := 1;
    
     { tutaj sprawdzamy czy rysowana jest prawa }
     { czy lewa strona wielokąta }
     { jesli lewa to indeks 'edge=0' do tablicy 'tedge' }
     { jesli prawa to indeks 'edge=128' do tablicy 'tedge' }
     { zmienna 'ady' okresla czy pozycja pionowa Y bedzie }
     { zmniejszana 'ady=$ff', czy zwiekszana 'ady=1' }
     if y2-y1 < 0 then begin
       edge := 0; ady := $ff; cnt := cnt + dy;
       
     { obliczenie minimalnej pozycji pionowej Y }
     { testujemy 'miny' gdy rysujemy lewa krawedz }
     { poniewaz lewa krawedz rysujemy od dolu do gory }
     { wiec wystarczy tylko tutaj sprawdzac minimum 'miny' }
     
       if y2 < miny then miny := y2;
       
      end else begin
       edge := 128; ady := 1
     end;
    
     x := x1;         { wartość początkowa X }
    
     { stała 'm' odczytana z tablicy 'tab_div' }
     { stała 'm' jest typu WORD }
     m:=tab_div[dx,dy];
    
     { główna pętla wyznaczająca punkty krawedzi }
     while y1<>npix do begin
    
      x := lo(x);     { mlodszy bajt zmiennej X }
    
      if adx=1 then x := x + m else x := x - m;
    
     { 'rlen' to wartość o jaka nalezy }
     { zwiekszyc pozycje pozioma }
     { 'hi(x)' oznacza starszy bajt zmiennej X }
      rlen := hi(x);
    
     { wpółrzędna pozioma 'x1' do tablicy krawedzi 'tedge' }
      tedge[edge+y1] := x1;
    
     { zwieksz pozycje pozioma 'x1' o 'rlen' }
      x1 := x1 + rlen;
      
     { zwieksz lub zmniejsz pozycje pionowa 'y1' }
     { 'ady=$ff' zmniejsza, 'ady=1' zwieksza }
      y1 := y1 + ady;
    
     end;
    
     { ostatnia wartosc 'x1' do tablicy krawedzi 'tedge' }
      tedge[edge+y1] := x1;
    end;
    

    Przed wywołaniem rysowania czterech odcinków określających polygon, zmienne 'miny', 'cnt' powinny przyjąć wartości domyślne:

     miny := $ff;
     cnt := 0;
    

    Tablice TAB_DIV wypełniamy wartościami, w sposób następujący:

    var tab_div:array [0..16383] of word;    { deklaracja tablicy }
    
    fillchar(tab_div,sizeof(tab_div),0);     { czyścimy obszar tablicy }
    
    for i:=1 to 127 do                       { zapisujemy wartości }
     for j:=0 to 127 do begin
      tab_div[j+i*128]:=trunc((j shl 8)/i);
     end;
    

    Teraz wypada przełożyć to na asembler. Na początek musimy umieścić w pamięci tablicę TAB_DIV, np. w dwóch dodatkowych bankach. W pierwszych 128 bajtach tablicy będą młodsze bajty wyniku dzielenia, w ostatnich 128 bajtach starsze bajty wyniku dzielenia. Aby odczytać wynik dzielenia z tak zorganizowanej tablicy wystarczy:

        ldy dy         ; na podstawie 'dy' znajdujemy kod banku pamieci
        lda _bank,y
        sta $d301
        tya
        lsr @
        ora >$4000
        sta low+2      ; oraz starszy bajt adresu w banku (dy=<0..127>)
        sta hig+2
        
        ldx dx
    low lda $ff00,x    ; mlodszy bajt wyniku dzielenia
        sta m
    hig lda $ff80,x    ; starszy bajt wyniku dzielenia
        sta m+1
        
    _bank :64 dta bank1                ;dla dy=<0..63> bank1
          :64 dta bank2                ;dla dy=<64..127> bank2
    

    Cała reszta to już ostra optymalizacja kodu, dzięki czemu staje się mało zrozumiały :), ale szybki, może nawet szybszy niż wersja Pascalowa :)

    Jeśli ktoś zna szybszy sposób na wypełnianie polygonów chętnie posłucham.

    Komentarze gości atari.area

    Momencik, uaktualniam...  

    Nie jesteś zalogowany. Tylko zarejestrowani i zalogowani użytkownicy mog± dodawać komentarze.

Lotharek.pl
Retronics
Sikor Soft

Szukaj

Wyszukiwarka przeszukuje zasoby atari.area, atariki oraz forum.

Twoliner

Momencik, uaktualniam...  .

Pamiętaj, żeby linki do Twolinera dodawać wyłącznie po skróceniu za pomocą serwisu tiny.pl. Jeśli coś Ciebie ominęło - skorzystaj z archiwum.

Network

konto

Nie jesteś zalogowany. Zaloguj się lub załóż konto

forum

Artykuły

Wywiady

Allegro

Jako, że Allegro.pl jest bardzo często odwiedzanym serwisem przez Atarowców, umiejscowiłem poniżej wyszukiwarkę produktów związanych z naszym kochanym Atari. Chcesz coś kupić - wystarczy wpisać w okienko poniżej.


Wystarczy wpisac czego szukamy i po chwili znajdujemy sie juz na Allegro.pl.