(Elemi grafikai algoritmusok)
Megjegyzés: minden algoritmusnál normál koordináta-rendszert tételezünk fel, ezért a 'Rajzol' eljárásnak kell még gondoskodnia a képre transzformálásról.
1. szakasz rajzolás:
A.: egyszerû algoritmus:
A szakasz végpontjai legyenek (X1,Y1), illetve (X2,Y2)! Tegyük fel, hogy X2>X1! A két ponton át húzható egyenes egyenlete ekkor: Y=(X-X1)/(X2-X1)*(Y2-Y1)+Y1
Rajzolás:
SZ:=(Y2-Y1)/(X2-X1) [X1=X2 esetén]
Ciklus X=X1-tõl X2-ig
Y:=(X-X1)*SZ+Y1
Rajzol(X,Y)
Ciklus vége
Eljárás vége.
Ekkor az az alapvetõ probléma, hogy ha Y2-Y1 nagyobb, mint X2-X1, akkor a vonal nem lesz folytonos.
B.: folytonos vonallal:
Rajzolás:
HX:=X2-X1: HY:=Y2-Y1
Ha abs(HX)>abs(HY) akkor H:=abs(HX) különben H:=abs(HY)
Ha H=0 akkor
Rajzol(X1,Y1)
különben
LX:=HX/H: LY:=HY/H
X:=X1: Y:=Y1
Ciklus K=1-tõl H+1-ig
Rajzol(X,Y)
X:=X+LX : Y:=Y+LY
Ciklus vége
Elágazás vége
Eljárás vége.
2. kör rajzolás
Mielõtt a kör rajzolást elkezdenénk, egy egyszerû észrevételt tehetünk: Ha egy origó középpontú kört rajzolunk, akkor abból, hogy az (x,y) pont pontja a körvonalnak, követ¡kezik, hogy az (x,-y), a (-x,y) és a (-x,-y) is az, hiszen a kör egy szimmetrikus alakzat.
A.: a körvonal pontjai: x, sqr(r*r-x*x)
Egy origó középpontú, r sugarú kör pontjaira a következõ azonosság igaz: x*x+y*y=r*r! Ezt felhasználva készíthetjük el az elsõ megoldást!
Rajzolás:
Ciklus X=0-tól R-ig
Y:=gyök(R*R-X*X)
Rajzol(X,Y): Rajzol(X,-Y)
Rajzol(-X,Y): Rajzol(-X,-Y)
Ciklus vége
Eljárás vége.
B.: a körvonal pontjai: r*cos(alfa),r*sin(alfa)
A körvonal azon pontjának koordinátái, amely az x-tengellyel alfa szöget zár be, a kö¡vetkezõ azonossággal számolhatók: x=r*cos(alfa), y=r*sin(alfa)
Rajzolás:
Ciklus ALFA=0-tól pi/2-ig .01-esével
X:=R*cos(ALFA): Y:=R*sin(ALFA)
Rajzol(X,Y): Rajzol(X,-Y)
Rajzol(-X,Y): Rajzol(-X,-Y)
Ciklus vége
Eljárás vége.
A megoldás problémája olyan lépésköz meghatározása, amelynél a körvonal még összefüggõ, de nem kell túl sok pontot rajzolni (elég gyors a megoldás). A negyedkör kerülete r*pi/2, így akkor érnek össze a körvonal pontjai, ha a lépésköz 1/r.
C.: a körvonal pontjai: x,sqr((x+r)*(r-x))
Ha a kör átmérõjének két végpontját összekötjük a körvonal egy tetszõleges pontjával, akkor egy derékszögû háromszöget kapunk. Ennek a derékszögû háromszögnek a magassága adja meg az x koordinátához az y koordinátát. A derékszögû há¡romszög magasságára az alábbi ábra alapján a következõ kép¡let adható: y*y=(r+x)*(r-x)
Rajzolás:
Ciklus X=0-tól R-ig
Y:=gyök((R+X)*(R-X))
Rajzol(X,Y): Rajzol(X,-Y): Rajzol(-X,Y): Rajzol(-X,-Y)
Ciklus vége
Eljárás vége.
Mindhárom megoldás esetén az az alapvetõ probléma, hogy nem biztos, hogy a kör¡vonal folytonos vonal lesz, illetve elképzelhetõ, hogy nagyon sok pontot rajzolunk egy¡másra.
D.: folytonos vonallal:
Ebben a megoldásban kiindulunk abból, hogy a (0,r) pont pontja a körvonalnak. Ha az I. síknegyedbe esõ körvonalat rajzoljuk, akkor egy tetszõleges körvonalra esõ pont után a következõ pont vagy tõle jobbra található, vagy jobbra és lefele, vagy pedig lefele. Pró¡báljuk ki ?ilyen sorrendben?, hogy melyik nem lép ki a körvonalon kívülre!
Rajzolás:
X:=0: Y:=R: RR:=R*R
Ciklus amíg Y>=0
Rajzol(X,Y): Rajzol(X,-Y): Rajzol(-X,Y): Rajzol(-X,-Y)
Ha (X+1)*(X+1)+Y*Y<=RR akkor X:=X+1
különben Y:=Y-1
Ha (X+1)*(X+1)+Y*Y<=RR akkor X:=X+1
[különben le]
Elágazások vége
Ciklus vége
Eljárás vége.
Megjegyzés: Ez az algoritmus használható tetszõleges konvex alakzat rajzolásához is.
E.: A körvonal követésével:
Körvonalpont(x,y):
Rajzol(x,y): Rajzol(-x,y): Rajzol(-x,-y ): Rajzol(x,-y )
Rajzol(y,x ): Rajzol(-y,x ): Rajzol(-y,-x ): Rajzol(y,-x)
Eljárás vége.
Körrajz(r):
x:=0: y:=r [a tetején kezdjük, Kelet felé egy nyolcadot]
d:=1-r: dE:=3: dSE:=-2*r+5
Körvonalpont(x,y)
Ciklus amíg y>x
Ha d<0 akkor [Keletre lépés]
d:=d+dE: dE:=dE+2: dSE:=dSE+2
x:=x+1 [ y:=y ]
különben [Délkeletre lépés]
d:=d+dSE: dE:=dE+2: dSE:=dSE+4
x:=x+1: y:=y-1
Körvonalpont(x,y)
Ciklus vége
Eljárás vége.
3. Pont rajzoló eljárás:
Tegyük fel, hogy a képernyõ sorainak számát az SS, oszlopainak számát az OS változó tartalmazza, a képernyõ origója a bal felsõ sarokban van, a koordináták jobbra, illetve lefelé növekszenek. Legyen a valódi koordinátatengely origója a képernyõ KS. sor KO. oszlopában és irányítása legyen a szokásos! A rajzoló eljárás a paraméterként kapott valós koordináta értékeket kerekítse egészre, s a pontot csak akkor ábrázolja, ha a képernyõn van. Ebben a megoldásban a valós koordinátarendszer és a képernyõ¡koordinátarendszer léptéke azonos. (Ha nem azonos lenne, akkor X-et és Y-t meg kell szorozni a megfelelõ léptékkel.)
Rajzol(X,Y):
S:=Kerekít(KS-Y): O:=Kerekít(KO+X)
Ha S>=0 és S<SS és O>=0 és O<OS akkor Pontrajzolás(O,S)
Eljárás vége.
Alakzatok színezése:
A.: Rekurzív festés pontonként:
Ez az eljárás egy belsõ pontból kiindulva festi be az alakzatot. A rekurzió miatt nagy alakzatokhoz túl nagy a memóriaigénye.
Festés(X,Y):
Pontrajzolás(X,Y)
Ha üres(X-1,Y) akkor Festés(X-1,Y)
Ha üres(X,Y-1) akkor Festés(X,Y-1)
Ha üres(X+1,Y) akkor Festés(X+1,Y)
Ha üres(X,Y+1) akkor Festés(X,Y+1)
Eljárás vége.
B.: Sort alkalmazó festés pontonként:
Ez az eljárás az elõzõ egy gazdaságosabb változata, egy hullámfrontot ábrázol sor adatszerkezetben..
Festés(X,Y):
Pontrajzolás(X,Y): Sorba(X,Y)
Ciklus amíg a sor nem üres
Sorból(X,Y)
Ha üres(X-1,Y) akkor Pontrajzolás(X-1,Y): Sorba(X-1,Y)
Ha üres(X,Y-1) akkor Pontrajzolás(X,Y-1): Sorba(X,Y-1)
Ha üres(X+1,Y) akkor Pontrajzolás(X+1,Y): Sorba(X+1,Y)
Ha üres(X,Y+1) akkor Pontrajzolás(X,Y+1): Sorba(X,Y+1)
Ciklus vége
Eljárás vége.
D.: Vermet alkalmazó festés pontonként:
Ez az eljárás az elõzõ egy másik változata, vermet használ a még feldolgozandó belsõ pontok ábrázolására.
Festés(X,Y):
Pontrajzolás(X,Y): Verembe(X,Y)
Ciklus amíg a verem nem üres
Verembõl(X,Y)
Ha üres(X-1,Y) akkor Pontrajzolás(X-1,Y): Verembe(X-1,Y)
Ha üres(X,Y-1) akkor Pontrajzolás(X,Y-1): Verembe(X,Y-1)
Ha üres(X+1,Y) akkor Pontrajzolás(X+1,Y): Verembe(X+1,Y)
Ha üres(X,Y+1) akkor Pontrajzolás(X,Y+1): Verembe(X,Y+1)
Ciklus vége
Eljárás vége.
E.: Háromszögfestés:
Egy háromszöget könnyû festeni, ha megadjuk azokat a vízszintes szakaszokat, ame¡lyekkel teljesen befesthetõ. Ezen szakaszok végpontjai az oldalegyenesek egyenleteibõl számolhatók, azaz nincs szükség a képmemória leolvasására.
Háromszögfestés(A,B,C):
Ciklus S=C.Y-tól A.Y-ig
O1:=(A-C egyenes) az S. sorban
O2:=(B-C egyenes) az S. sorban
Vonal(O1,S,O2,S)
Ciklus vége
Ciklus S=A.Y+1-tõl B.Y-ig
O1:=(A-B egyenes) az S. sorban
O2:=(B-C egyenes) az S. sorban
Vonal(O1,S,O2,S)
Ciklus vége
Eljárás vége.
F.: Rekurzív festés szakaszonként:
Egy alakzat kiszínezéséhez meg kell adni egy belsõ pontját. Ekkora színezést a kö¡vetkezõképpen végezzük el. Húzzuk meg azt a függõleges vonalat, amely ezen a pon¡ton keresztül halad, s a kiszínezendõ ábra legközelebbi határvonaláig tart. Ez a vonal a kiszínezendõ ábrát (legalább) 2 részre vágja: a vonaltól balra, illetve jobbra levõ részre. (Kettõnél több részrõl akkor van szó, ha a vonal érintette valahol a kiszínezendõ áb¡rát.) A feladat ezek után e két rész kiszínezése. Ezt úgy oldjuk meg, hogy végigme¡gyünk a vonal mindkét oldalán, s ha belsõ, még kiszínezetlen pontot találunk, akkor a fenti eljárás végrehajtjuk ebbõl a pontból kiindulva.
Festés(X,Y):
Vonalvég(-1,X,Y,Y1): Vonalvég(1,X,Y,Y2)
Vonalrajzolás(X,Y1,X,Y2)
Ciklus I=Y1-tõl Y2-ig
Ha üres(X-1,I) akkor Festés(X-1,I)
Ha üres(X+1,I) akkor Festés(X+1,I)
Ciklus vége
Eljárás vége.
Vonalvég(I,X,Y,Z): [Z a vonal végpontja - belsõ pont]
Z:=Y
Ciklus amíg üres(X,Z+I)
Z:=Z+I
Ciklus vége
Eljárás vége.
A feladat nemrekurzív változata ennél jóval bonyolultabb lesz. Itt verembe tesszük a megrajzolandó vonal végpontjai koordinátáit, miközben az elõbb megrajzolt szakasz oldalait járjuk be, s csak ezután fogunk hozzá a verem tetején levõ szakasz tényleges feldolgozásához.
Festés(X,Y):
Vonalvég(-1,X,Y,Y1): Vonalvég(1,X,Y,Y2)
Verembe(X,Y1,Y2)
Ciklus amíg a verem nem üres
Verembõl(X,Y1,Y2)
Vonalrajzolás(X,Y1,X,Y2)
Szomszéd oszlop(X-1,Y1,Y2) [bal szomszéd]
Szomszéd oszlop(X+1,Y1,Y2) [jobb szomszéd]
Ciklus vége
Eljárás vége.
Szomszéd oszlop(X,Yk,Yv):
I:=Yk
Ciklus amíg I<=Yv
Ha üres(X,I) akkor Vonalvég(-1,X,I,Y3): Vonalvég(1,X,I,Y4)
Verembe(X,Y3,Y4): I:=Y4+1
különben I:=I+1
Elágazás vége
Ciklus vége
Eljárás vége.
G.: Sokszög festés háromszögenként:
Konvex sokszög mindig felbontható háromszögekre egy tetszõleges csúcsából kiin¡dulva, így alkalmazható rá a felbontás (1., i-edik és i+1-edik csúcs), majd a háromszög¡festés.
Konkáv sokszög esetén is alkalmazható a fenti eljárás, de ekkor a sokszögön kívüli területeket is befest ez az eljárás. Megállapíthatjuk ugyanakkor, hogy a sokszögön kívüli területeket mindig páros sokszor, a belülieket pedig páratlan sokszor festi. Ekkor XOR mûveletet alkalmazva a festéskor, végeredményként éppen a befestett alakzatot kapjuk.
H.: Sokszög festés metszõ vonalakkal:
A képernyõ szélérõl a másik széle felé haladva számoljuk, hogy hány határoló szaka¡szon haladunk át! A belsõ pontokban ez a szám mindig páros, a külsõ pontokban pedig páratlan. Kivételt jelentenek sajnos a vízszintes szakaszokat, illetve alsó vagy felsõ csúcs¡pontokat tartalmazó sorok. A megoldás: ne a képponotokon, hanem ponotsan két kép¡pont között húzzuk a képzeletbeli vonalat, s ez alapján figyeljünk a párosságra, páratlan¡ságra!
Egy másik megoldásnál szûmoljuk ki az összes (nem vízszintes) határoló szakasz és képernyõ vízszintes szakaszai metszéspontjait, majd ezeket képernyõ soronként ren¡dezzük sorba! Ekkor minden esetben páratlan sorszámú ponttól a következõ páros sor¡számúig kell egy vízszintes szakaszt rajzolni a képernyõre.
5. Vágás (Cohen-Sutherland):
Ha az alakzat nagyobb, mint a képernyõ, akkor az alakzat képernyõn kívüli részét le kell vágni. Az alakzat és a képernyõ viszonya a következõ lehet [kép].
Az ábrán az A szakasz teljes egészében látszik a képen, a B-nek csak az egyik része látható, a C-nek csak egy középsõ darabja látszik, a D pedig egyáltalán nem látszik. Ez a négy eset sokféle¡képpen fordulhat elõ. A felada¡tunk ezek vizsgálata, s a szüksé¡ges vágások elvégzése lesz.
Egészítsük ki a képet az egész képmezõre, s rendeljünk egy négy bites kódot minden mezõhöz: [kép]
A kódolás célja az, hogy elkerüljük nagyon sok logikai feltétel vizsgálatát.
Ha egy szakasz mindkét végpontjának kódja 0000, akkor a teljes szakasz látszik, ha a végpon¡tok kódjával végrehajtott logikai ÉS mûvelet eredménye nem 0, akkor a szakasz biztosan nem látszik (a kódokat ezért választottuk ilyennek). Ha nem ezek az esetek állnak fenn, akkor a szakaszt a képernyõ egyik élével alkotott metszéspontjánál kettévágjuk. Az így kapott egyik szakasz biztosan a képernyõn kívül lesz, a másikra pedig újra el kell végezni a fenti eljárást (ugyanis a 0001-bõl 1000-ba húzott szakasz vagy metszi a képernyõ egyik élét, vagy nem).
Megjegyzés: A nagybetûs logikai mûveletek egész számokra vonatkozó bitenkénti mûveleteket jelentenek.
Legyen a képernyõ felsõ sorának y-koordinátája KF, alsó sorának pedig KA, a baloldali szél x-koordinátája KB, a jobboldalié pedig KJ!
Vágóalgoritmus(X1,Y1,X2,Y2):
Végpontok kódjának elõállítása(C1,C2)
Ciklus amíg nem ( (C1=0 és C2=0) vagy (C1 ÉS C2)=0 )
Ha C1=0 akkor Csere(C1,X1,Y1,C2,X2,Y2)
Ha (C1 ÉS 1)=1 akkor Vágás a felsõ szélen
Ha (C1 ÉS 2)=1 akkor Vágás a jobbszélen
Ha (C1 ÉS 4)=1 akkor Vágás az alsó szélen
Ha (C1 ÉS 8)=1 akkor Vágás a balszélen
Végpontok kódjának elõállítása(C1,C2)
Ciklus vége
Ha C1=0 és C2=0 akkor Szakasz rajzolás(X1,Y1,X2,Y2)
Eljárás vége.
Végpontok kódjának elõállítása(C1,C2):
C1:=0 : C2:=0
Ha Y1>KF akkor C1:=C1 VAGY 1
Ha Y2>KF akkor C2:=C2 VAGY 1
Ha X1>KJ akkor C1:=C1 VAGY 2
Ha X2>KJ akkor C2:=C2 VAGY 2
Ha Y1<KA akkor C1:=C1 VAGY 4
Ha Y2<KA akkor C2:=C2 VAGY 4
Ha X1<KB akkor C1:=C1 VAGY 8
Ha X2<KB akkor C2:=C2 VAGY 8
Eljárás vége.
A vágáshoz mindig két szakasz metszéspontjának koordinátáit kell kiszámítani.
Vágás a felsõ szélen:
X1:=X1+(X2-X1)*(KF-Y1)/(Y2-Y1) : Y1:=KF
Eljárás vége.
Vágás az alsó szélen:
X1:=X1+(X2-X1)*(KA-Y1)/(Y2-Y1) : Y1:=KA
Eljárás vége.
Vágás a jobbszélen:
X1:=KJ : Y1:=Y1+(Y2-Y1)*(KJ-X1)/(X2-X1)
Eljárás vége.
Vágás a balszélen:
X1:=KB : Y1:=Y1+(Y2-Y1)*(KB-X1)/(X2-X1)
Eljárás vége.
* * * * *