Kurs Assemblera cz. 8
- TeBe / MadTeam
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.
