Algoritmy rovinne grafiky Obrazek vytvareny na obrazovce se sklada z ruznych elementarnich objektu: bodu, usecek, kruhu, elips atd. Zobrazeni techto objektu je ruzne slozite. Bodu odpovida jeden bit obrazove pameti, zde neni zadny problem. U slozitejsich objektu (cara, kruh) je situace ponekud slozitejsi. Z ciste matematickeho hlediska jsou tyto objekty slozeny z nekonecneho poctu bodu. Obrazovka samozrejme nemuze zobrazit tak velky pocet nekonecne malych bodu a tak musi byt provedena urcita aproximace, kdy se vykresli pixely lezici nejblize skutecnemu umisteni krivky. Algoritmy pro rovinou grafiku maji za ukol, co nejrychleji a nejjednoduseji, urcit polohu aproximovanych pixelu. Z techto algoritmu je nejjednodussi algoritmus pro kresleni usecek. Rozebereme ho zde tedy ponekud podrobneji. Bresenhamuv algoritmus pro kresbu usecky Z matematiky si jeste mozna pamatujete, ze rovnici primky lze zapsat ve tvaru: y = mx + b, ( 1 ) kde m je smernice a b posun na ose y. Je-li usecka urcena pocatecnim a koncovym bodem (souradnicmi bodu [x1,y1] a [x2,y2]), muzeme smernici a posunuti vyjadrit nasledujicimi vztahy: y2-y1 ëy m = ------- = ---- x2-x1 ëx ( 2 ) x2y1-x1y2 x2y1-x1y2 b = ----------- = -----------. x2-x1 ëx Algoritmy pro zobrazeni usecky vychazeji z rovnic 1 a 2. Na nejakem intervalu ëx se souradnice y zmeni o hodnotu ëy podle nasledujiciho vztahu: ëy = m ëx. J.E.Bresenham vymyslel algoritmus, ktery pri generovani usecky vystaci s celociselnou aritmetikou. Na obrazku 10 je nakreslena cast obrazovky, na ktere maji byt zobrazeny pixely usecky. Po nakresleni leveho koncoveho bodu usecky mame rozhodnout, zda nasledujici bod bude vykreslen na pozici se souradnici y stejnou jako predchozi bod nebo o jedna vetsi. Z techto dvou moznosti umisteni nasledujiciho pixelu vybereme tu, ktera lezi blize skutecne poloze bodu usecky. Popiseme si zde zpusob, jak pomoci Bresenhamova algoritmu vykreslit usecku s kladnou smernici mensi nez 1. Ostatni smery jsou pouze obmenou dale uvdedneho postupu. V pripade, ze usecka ma kladnou smernici mensi nez jedna je ridici osou osa x. Znamena to, ze postupne pro vsechny souradnice x menene o jednicku, urcime jim odpovidajici souradnice y. Predpokokladejme, ze pixel o souradnicich [xi,yi] jiz byl nakreslen a my mame rozhodnou o poloze nasledujiciho. Na vyber mame ze dvou moznosti [xi+1,yi] a [xi+1,yi+1]. Vzdalenost techto dvou bodu od skutecneho bodu usecky je na obraazku 10 vyznacena jako d1 a d2. Pro skutecnou souradnci y plati: y = m (xi + 1) + b. Pak plati: d1 = y - yi = m (xi + 1) + b - yi d2 = yi + 1 - y = yi + 1 - m (xi + 1) - b Rozdil techto dvou vzdalenosti je: ëd = d1 - d2 = 2m (xi + 1) - 2yi + 2b - 1 ( 3 ) Podle promene ëd muzeme urcit, ktery ze dvou pixelu lezi blize skutecnemu umisteni usecky. Kladna hodnota ëd, znamena ze d1 > d2 a tudiz blizsi je pixel o souradnicich [xi+1,yi+1]. Naopak zaporna hodnota ëd (d1 < d2) vybere pixel o souradnicich [xi+1,yi]. Neni tedy dulezita hodnota ëd, ale jeji znamenko. Bohuzel ëd neni diky m celocislena. Celou rovnici 3 vsak muzeme vynasobit ëx a dostavame: pi = ëd ëx = 2 ëy xi - 2 ëx yi + 2 ëy + ëx (2b - 1), ( 4 ) kde 2 ëy + ëx (2b - 1) je konstanta, ktera bude pri nasledujicich upravach vyloucena. Hodnotu p, podle jejihoz znamenka urcujeme polohu nasledujicich pixelu nazveme predikci. Predikci nasledujciho bodu pi+1 muzeme zapsat jako: pi+1 = 2 ëy xi+1 - 2 ëx yi+1 + konstanta ( 5 ) Rovnice 4 a 5 muzeme odecist, vyjadrime tak pi+1 pomoci pi: pi+1 = pi + 2 ëy - 2 ëx (yi+1 - yi), ( 6 ) za predpokladu, ze xi+1 = xi + 1. Nasledujici vztahy vyjadruji zavislost hodnoty pi+1 na hodnote pi: /---------------------------------------------\ | pi < 0 => pi+1 = pi + 2 ëy | |---------------------------------------------| | pi n 0 => pi+1 = pi + 2 ëy - 2 ëx | \---------------------------------------------/ Prvni hodnota predikce p1 se ziska dosazenim pocatecniho bodu usecky do rovnice 4. Dostaneme p1 = 2 ëy - ëx. Predikce tvori zakladni kriterium pro vyber pixelu tvoricich rastrovy obraz usecky. Hodnotu pi pro kazdy pixel postupne aktualizujeme podle jednoduchych vztahu v tabulce. Znamenko predikce urcuje polohu nasledujiciho pixelu. Pokud je predikce zaporna, y souradnice nasledujiciho pixelu se nemeni. Pokud je kladna, zvetsi se o jedna. V pripade, kdy je smernice vetsi nez jedna zamenime souradnice x a y a algoritmus zustane stejny. Pokud je smernice usecky zaporna, jedna ze souradnic se zmensuje a zbytek postupu je shodny. Priklad na zaver Nektere zde uvedene poznatky shrneme do ukazkoveho programu. Je jim jednoducha graficka knihovna, ktera dovede pouze kreslit cary ruznymi barvami a ruznym zpusobem je kombinovat s jiz nakreslenymi objekty. Knihovna je ve tvaru unity pro Turbo Pascal, coz je pro vetsinu z vas asi nejdostupnejsi a nejsrozumitelnejsi programovaci jazyk. Pro dosazeni vysoke rychlosti jsou jeji klicove casti napsane v assembleru. Unit SGraph; interface Const { Konstanty pro typ kresleni } NormalPut = 0; { Prepisovani } ANDPut = 8; { Logicke AND } ORPut = 16; { Logicke OR } XORPut = 24; { Logicke XOR } { Hlavicky exportovanych procedur } procedure Line( X1, Y1, X2, Y2: word); { Kresleni cary } procedure InitGraph; { Inicializace grafiky } procedure CloseGraph; { Obnoveni puvodniho videomodu } procedure SetColor( Color: byte); { Nastaveni barvy pro kresleni car } procedure SetWriteMode( Mode: byte); { Volba druhu kombinace kreslenych a jiz zobrazenych dat } implementation Const ActColor: byte = 15; { Promena slouzici k ulozeni aktualni barvy Standardne je nastavena bila barva } WriteMode: byte = 0; { Zapisovaci rezim 0 = prepisovani 8 = AND 16 = OR 24 = XOR } BytesPerRow = 80; { Pocet byte v jedne radce (640/8 = 80) } IsGraphicsMode: boolean = false; { Indikace zda jsme v grafice } PixelsPerByte = 3; { Pocet bodu v jednom bite udany v bitovych posuvech } ModMask = 7; { Bitova maska pro ziskani MOD 8 (zbytku po deleni osmi } BMask = 128; { Bitova maska pro kresleni bodu } VRAMSegment = $a000; { Segment pocatku obrazove pameti } GraphicsAR = $3ce; { Port Graphics 1 and 2 Address Register } ModeRegister = 5; { Index registru zapisovaciho modu } DataRotate = 3; { Index registru pro rotaci a kombinaci dat } BitMask = 8; { Index registru bitove masky } var OldVMode: byte; { Promena slouzici pro uchovani cisla zobrazovaciho rezimu } delta: word; { Pomocne promene pro uchovani 2dx nebo 2dy} procedure Line( X1, Y1, X2, Y2: word); assembler; { Kresli caru z X1, Y1 do X2, Y2 } const neg_dx = 2; { Znamenko od delta x } neg_dy = 4; { Znamenko od delta y } asm push BP { Uchovani registru BP } push DS { a DS } mov AX, X1 { Nacteni souradnic do registru procesoru } mov BX, Y1 mov CX, X2 mov DX, Y2 xor BP, BP { Smazani registru BP } mov DI, CX { Spocitani hodnoty deltax } sub DI, AX jg @p_dx { Je deltax kladne ? } or BP, neg_dx { ne => uloz znamenko do BP } neg DI { absolutni hodnota DI tj. deltax } @p_dx: mov SI, DX { Urceni hodnoty deltay } sub SI, BX jg @p_dy { Je deltay kladne ? } or BP, neg_dy { ne => uloz znamenko do BP } neg SI { absolutni hodnota delaty } @p_dy: cmp DI, SI { Porovnani deltax a deltay } jb @vertical_dir { deltax > deltay <=> absolutni hodnota smernice > 1 => vertikalni smer deltax <= deltay <=> absolutni hodnota smernice <= 1 => horizontalni smer } @horizontal_dir: test BP, neg_dx { Porovnani X1 a X2 } jz @hor_init { Je smer zprava doleva ? } xchg AX, CX { ne => vymen souradnice pocatku a konce cary } xchg BX, DX xor BP, neg_dy { uprav znamenko deltay } @hor_init: { Vypocet adresy prvniho bodu } mov CX, AX { Do CX X1 } xchg AX, BX { BX = X1, AX = X2 } mov DX, BytesPerRow { DX = Pocet byte na jedne radce (80) } mul DX { AX:DX = Y1 * 80 } shr BX, PixelsPerByte { BX = BX div 8 } add BX, AX { V BX je offset prvniho bodu cary } mov AX, DS { Do ES presuneme DS } mov ES, AX mov AX, VRAMSegment { Segment obrazove pameti do DS } mov DS, AX mov DX, GraphicsAR { Port adresoveho registru grafickeho kontroleru } mov AX, ModeRegister + $0200 { Nastavi zapisovaci mod 2 } out DX, AX mov AL, DataRotate { Nastavi zpusob kombinace dat z CPU } mov AH, ES: WriteMode { s latch-registry } out DX, AX and CX, ModMask { CX = X1 and 7 } mov AH, BMask { AH = 80h, tj. nastaven je levy pixel } shr AH, CL { Rotace AH. Po rotaci je v AH bitova maska bodu } mov DX, BP { Uchova znamenka deltax a deltay v DX } mov CX, DI { CX = deltax } inc CX { CX = deltax - 1, tj. pocet bodu na care } { Vypocet predikce do BP: } shl SI, 1 { SI = 2*deltay } mov BP, SI { BP = 2*deltay } sub BP, DI { BP = 2*deltax - deltay } shl DI, 1 { DI = 2*deltax } mov ES: delta, DI { Ulozeni hodnoty 2*deltax } mov DI, BX { Do DI offset adresy 1. bodu } test DX, neg_dy { Urceni smeru } pushf { Uchovani flagu } mov DX, GraphicsAR { Nastavi index graf. kontroleru na Bit mask reg. } mov AL, BitMask out DX, AL inc DX { DX = datovy port graf. kontroleru } popf { Obnovi flagy s vysledkem testu smeru } jnz @hor_neg_dy_init { Rozskok, podle znamenka smernice } @hor_pos_dy_init: { Kladna smernice, y souradnice je zvysovana } mov BL, ES: ActColor { BL = Barva cary } mov BH, BL { BH = Barva cary } mov AL, AH { AL = Bitova maska prvniho bodu } @hor_pos_dy: cmp BP, 0 { Test predikce } jng @hor_pos_dy_L1 out DX, AL { predikce >= 0 } mov BL, BH { BL = Barva bodu } xchg [DI], BL { Nakresli bod } xor AL, AL { Vynuluje stradanou masku } sub BP, ES: delta { Upravi predikaci P = P - 2*deltax } add DI, BytesPerRow { Zvetseni y souradnice } @hor_pos_dy_L1: add BP, SI { Uprava predikce P = P + 2*deltay } ror AH, 1 { Zvetseni x souradnice } jc @hor_pos_dy_L2 { Presahli jsme jeden byte ? } or AL, AH { Uprav masku byte } loop @hor_pos_dy { Dalsi bod } jmp @hor_pos_dy_lastbyte { Dosli jsme do koncoveho bodu } @hor_pos_dy_L2: out DX, AL { Nastavi novou bitovou masku } mov BL, BH xchg [DI], BL { Nakresli body jednoho byte } mov AL, AH { Inicializuje bitovou masku } inc DI { Zvetsi x souradnici } loop @hor_pos_dy { Byl to posledni bod ? } jmp @l_done { => konec kresleni cary } @hor_pos_dy_lastbyte: xor AL, AH { Posledni bit je neplatny, odstranit } out DX, AL { Nastaveni bitove masky } mov BL, BH { BL = Barva cary } xchg [DI], BL { Nakresleni bodu } jmp @l_done { Ukonceni kresleni cary } @hor_neg_dy_init: { Zaporna smernice, y souradnice je zmensovana } mov BL, ES: ActColor { BL = Barva cary } mov BH, BL { BH = Barva cary } mov AL, AH { AL = Bitova maska prvniho bodu } @hor_neg_dy: cmp BP, 0 { Test predikce } jng @hor_neg_dy_L1 out DX, AL { predikce >= 0 } mov BL, BH { BL = Barva bodu } xchg [DI], BL { Nakresli bod } xor AL, AL { Vynuluje stradanou masku } sub BP, ES: delta { Upravi predikaci P = P - 2*deltax } sub DI, BytesPerRow { Zmenseni y souradnice } @hor_neg_dy_L1: add BP, SI { Uprava predikce P = P + 2*deltay } ror AH, 1 { Zvetseni x souradnice } jc @hor_neg_dy_L2 { Presahli jsme jeden byte ? } or AL, AH { Uprav masku byte } loop @hor_neg_dy { Dalsi bod } jmp @hor_neg_dy_lastbyte { Dosli jsme do koncoveho bodu } @hor_neg_dy_L2: out DX, AL { Nastavi novou bitovou masku } mov BL, BH xchg [DI], BL { Nakresli body jednoho byte } mov AL, AH { Inicializuje bitovou masku } inc DI { Zvetsi x souradnici } loop @hor_neg_dy { Byl to posledni bod ? } jmp @l_done { => konec kresleni cary } @hor_neg_dy_lastbyte: xor AL, AH { Posledni bit je neplatny, odstranit } out DX, AL { Nastaveni bitove masky } mov BL, BH { BL = Barva cary } xchg [DI], BL { Nakresleni bodu } jmp @l_done { Ukonceni kresleni cary } @vertical_dir: { Vypocet adresy 1. bodu } test BP, neg_dy { Kreslime shora dolu ? } jz @vert_init xchg AX, CX { Prohozeni souradnic } xchg BX, DX xor BP, neg_dx { Uprava znamenka } @vert_init: mov CX, AX { CX = X1 } xchg AX, BX { AX = Y1, BX = X1 } mov DX, BytesPerRow { DX = Pocet byte na radku (80) } mul DX { AX:DX = Y1 * 80 } shr BX, PixelsPerByte { BX = X1 div 8 } add BX, AX { BX = Offset adresy 1. bodu } mov AX, DS { Ulozi datovy segment do ES } mov ES, AX mov AX, VRAMSegment { DS = Segment obrazove pameti } mov DS, AX mov DX, GraphicsAR { Port adresoveho registru graf. kontroleru } mov AX, ModeRegister + $0200 { Nastavi zapisovaci mod 2 } out DX, AX mov AL, DataRotate { Nastaveni zpusobu kombinovani dat z CPU } mov AH, ES: WriteMode { s latch-registry } out DX, AX and CX, ModMask { CX = X1 and 7 } mov AH, BMask { Bitova maska pro levy bod (80h) } shr AH, CL { Rotaci vytvori spravnou masku } mov DX, BP { Ulozi znamenka do DX } mov CX, SI { CX = Delka cary } inc CX { Urceni predikace } shl DI, 1 { DI = 2*deltax } add BP, DI { BP = 2*deltax } sub BP, SI { BP = 2*deltax - deltay } shl SI, 1 { SI = 2*deltay } mov ES: delta, SI { ulozi 2*deltay } mov SI, DI { SI = 2*deltax } mov DI, BX { DI = Offset adresy 1. bodu } test DX, neg_dx { Zjisteni smeru } mov DX, GraphicsAR { DX = adresovy port graf. kontroleru } jnz @vert_neg_dx_init { Rozskok podle znamenka smernice } @vert_pos_dx_init: { Kladna smernice } mov BL, ES: ActColor { BL = Barva cary } mov BH, BL { BH = Barva cary } mov AL, BitMask { Index Bit mask registru } out DX, AX inc DX { DX = datovy registr graf. kontroleru } mov AL, AH { AL = Bitova maska } @vert_pos_dx: mov BL, BH { BL = Barva cary } xchg [DI], BL { Nakresli bod } cmp BP, 0 { Test predikce } jng @vert_pos_dx_L1 sub BP, ES: delta { P >= 0, P = P - 2*deltay } ror AL, 1 { Zvys souradnici x } adc DI, 0 { Presun do dalsiho byte } out DX, AL { Nastav novou bitovou masku } @vert_pos_dx_L1: add BP, SI { P = P + 2*deltax } add DI, BytesPerRow { Zvys souradnici y } loop @vert_pos_dx { Dalsi bod } jmp @l_done { Konec cary } @vert_neg_dx_init: { Zaporna smernice } mov BL, ES: ActColor { BL = Barva cary } mov BH, BL { BH = Barva cary } mov AL, BitMask { Index Bit mask registru } out DX, AX inc DX { DX = datovy registr graf. kontroleru } mov AL, AH { AL = Bitova maska } @vert_neg_dx: mov BL, BH { BL = Barva cary } xchg [DI], BL { Nakresli bod } cmp BP, 0 { Test predikce } jng @vert_neg_dx_L1 sub BP, ES: delta { P >= 0, P = P - 2*deltay } rol AL, 1 { Zmensi souradnici x } sbb DI, 0 { Presun do dalsiho byte } out DX, AL { Nastav novou bitovou masku } @vert_neg_dx_L1: add BP, SI { P = P + 2*deltax } add DI, BytesPerRow { Zvys souradnici y } loop @vert_neg_dx { Dalsi bod } jmp @l_done { Konec cary } @l_done: mov DX, GraphicsAR { Smazani bitove masky } mov AX, BitMask out DX, AX mov AX, ModeRegister out DX, AX { Nastavi zapisovaci mod 0 } mov AX, DataRotate out DX, AX { Vypne rotyci dat, standardni kombinovani dat } @exit: pop DS { Obnovi obsah registru DS } pop BP { BP } end; procedure SetMode( Mode: byte); assembler; { Nastavi aktualni zobrazovaci rezim pomoci sluzby 00h BIOS } asm mov AH, 00h mov AL, Mode int 10h end; function GetMode: byte; assembler; { Sluzbou BIOS zjisti zobrazovaci rezim } asm mov AH, 0fh int 10h end; procedure InitGraph; { Inicializace grafiky } begin if not IsGraphicsMode then OldVMode := GetMode; { Ulozi cislo aktivniho zobrazovaciho rezimu } SetMode( $12); { Nastavi zobrazovaci rezim 640 x 480, 16 barev } IsGraphicsMode := True; { Nastavi priznak prepnuti do grafiky } end; procedure CloseGraph; { Ukonci graficky rezim } begin if IsGraphicsMode then SetMode( OldVMode); { Obnovi puvodni zobr. rezim } IsGraphicsMode := False; end; procedure SetColor( Color: byte); { Nastavi barvu pouzitou pro kresleni } begin ActColor := Color; end; procedure SetWriteMode( Mode: byte); { Nastavi zapisovaci rezim pro kresleni } begin WriteMode := Mode; end; begin end. Pouziti graficke knihovny demonstruje nasledujici kratky program, ktery navic vyuziva nektere z registru karty VGA k snadne implementaci vertikalniho scrolovani dvema smery zaroven. Vsimnete si, ze scrolovani bude stejne rychle na vsech pocitacich, bez ohledu na jejich rychlost. Je to zpusobeno tim, ze jednotlive animacni kroky jsou oddeleny cekanim na vertikalni zpetny chod, ktery je v tomto zobrazovacim rezimu generovan s frekvenci priblizne 60 Hz. Program pro svoji spravnou cinnost potrebuje kartu VGA. Uses Sgraph, { Pouzva jednotku SGraph } Crt; { a Crt } procedure SetStartAdr( Adr: word); assembler; { Procedura nastavujici registry CRTC pocatecni adresa index 0ch a 0dh } asm mov DX, 3dah { Vstupni stavovy registr 1 } @wait_retrace: in AL, DX and AL, 8 jz @wait_retrace { Cekani na vertikalni zpetny chod } @wait_display: in AL, DX and AL, 8 jnz @wait_display { Cekani na aktivni zobrazovaci signal } mov cx, Adr mov dx, 03d4h { CRTC adresovy registr } mov al, 0ch { index pocatecni adresa - vyssi byte } mov ah, ch out dx, ax inc al { index pocatecni adresa - nizsi byte } mov ah, cl { nizsi byte adresy } out dx, ax end; procedure SetLineComp( Line: word); assembler; { Nastavi registr CRTC porovnani radky vcetne 9. a 10. bitu } asm mov DX, 03d4h { CRTC adresovy registr } mov AL, 18h { index registru porovnani radky } out DX, AL mov CX, Line mov AL, CL inc DX out DX, AL { zapis 8 nizsich byte cisla radky } dec DX mov AL, 07h { index registru preteceni } out DX, AL inc DX in AL, DX { cte nastaveni registru preteceni } mov CL, CH and CL, 1 shl CL, 4 and AL, 11101111b { smaze 9. bit cisla radky pro porovnani } or AL, CL { nastavi 9. bit } out DX, AL { zapise registr } dec DX mov AL, 09h { registr pocet radek na znak - obsahuje 10. bit } out DX, AL inc DX in AL, DX shr CH, 1 and CH, 1 shl CH, 6 and AL, 10111111b { smazani stare hodnoty 10. bitu } or AL, CH { nova hodnota 10. bitu } out DX, AL { zapsani registru } end; const MaxX = 639; { Maximalni hodnota souradnice x } MaxY = 479; { Maximalni hodnota souradnice y } var i: word; { Pomocne promenne } x: word; begin InitGraph; { Inicializace grafiky } SetWriteMode( XORPut); { Nastaveni zapisovaciho zpusobu } { Nakresleni jednoducheho obrazce pres celou obrazovku } for x := 0 to MaxX do Line( MaxX div 2, MaxY div 2, x, 0); for x := 0 to MaxY do Line( MaxX div 2, MaxY div 2, MaxX, x); for x := MaxX downto 0 do Line( MaxX div 2, MaxY div 2, x, MaxY); for x := MaxY downto 0 do Line( MaxX div 2, MaxY div 2, 0, x); { Jednoducha animace } for i := 0 to MaxY div 2 do begin SetLineComp( i); { Scrolovani dolu pomoci porovnani radky } SetStartAdr( i* 80); { Zaroven scrolovani nahoru pomoci pocatecni adresy } end; { Obraceny smer animace } for i := MaxY div 2 downto 0 do begin SetLineComp( i); SetStartAdr( i* 80); end; Delay( 300); { Mala pauza nakonec } SetLineComp( 1023); { Nastaveni standardni hodnoty } CloseGraph; { Ukonceni grafiky, predchozi zobr. rezim } end. Literatura: [1] Kliewer, B.D. - EGA/VGA A programmer's reference guide 371 stran, McGraw-Hill Publishing Company, 1990 [2] Zara, J. - Pocitacova grafika - principy a algoritmy 472 stran, Grada a.s., 1992 [3] Brown, R. - Interrupt List - freewarova el. prirucka 1993
Copyright © Jiri Kosek