Rasterizacijos algoritmai PDF

Rasterizacijos algoritmai Kompiuterinė grafika – 11 paskaita Doc. dr. Kęstutis Jankauskas KTU. IF. Multimedijos inžinerijos katedra © 2024 Šiandien paskaitoje Linijinių primityvų rasterizacija Apskritimo rasterizacij...

Rasterizacijos algoritmai Kompiuterinė grafika – 11 paskaita Doc. dr. Kęstutis Jankauskas KTU. IF. Multimedijos inžinerijos katedra © 2024 Šiandien paskaitoje Linijinių primityvų rasterizacija Apskritimo rasterizacija vidurio taško algoritmu Daugiakampių užpildymo būdai Daugiakampio vidinio taško nustatymo būdai Vaizdo kraštų netolydumo mažinimo būdai 2 Problema Prieš vaizduojant, vektorinius vaizdus reikia rasterizuoti Išvedimo įrenginio koordinatės – sveikieji skaičiai Realiųjų skaičių koordinačių perskaičiavimas į įrenginio kordinates 3 Rasterizacijos uždaviniai Kontūrai: Tiesės (atkarpos) Apskritimai Elipsės Kreivės Storos linijos Uždaros sritys (daugiakampiai) Vienos spalvos užpildas Tekstūros užpildas 4 Reikalavimai rasterizuotai atkarpai Vaizdas turi būti be trūkių Rastro taško atstumas iki realios atkarpos turi būti minimalus Rasterizacijos procesas turi būti spartus ir tikslus Atkarpų galai turi būti nurodytuose rastro taškuose Atkarpos turi atrodyti tiesios Rastro spalva turi atrodyti vienoda Vienodoms atkarpoms visada parenkami tie patys pikseliai 5 Tiesės lygtys 1. Neišreikštinė: 𝑎𝑥 + 𝑏𝑦 + 𝑐 = 0 𝑎2 + 𝑏 2 ≠ 0 𝑦2 − 𝑦1 2. Kryptinė: 𝑦 = 𝑘𝑥 + 𝑝 𝑘= 𝑥2 − 𝑥1 3. Parametrinė: 𝑥 = 𝑓𝑥 (𝑡) 𝑦 = 𝑓𝑦 (𝑡) 𝑥 𝑦 4. Ašinė: + =1 y 𝑚 𝑛 n 𝑥 − 𝑥1 𝑦 − 𝑦1 𝑧 − 𝑧1 5. Per 2 taškus: = = 𝑥2 − 𝑥1 𝑦2 − 𝑦1 𝑧2 − 𝑧1 0 m x 6 Rasterizacijos algoritmai Tiesių (atkarpų) rasterizavimas 1. Naivaus požiūrio (naive approach) 2. Plono stačiakampio (lines as thin rectangle) 3. Storų linijų 4. Tiesioginio koordinačių skaičiavimo 5. Skaitinis diferencialinis analizatorius (DDA - Digital Differential Analyzer) 6. Bresenhamo (angl. Bresenham) arba vidurio taško algoritmas Apskritimų, elipsių: Vidurio taško Uždarų sričių (daugiakampių): 1. Užliejimo (food fill) 2. Eilučių skenavimo (scan-line fill) 7 Naivaus požiūrio algoritmas Principas Nustatomas kiekvienas pikselis, kurį kerta atkarpa Formuojama 1 pikselio storio linija Trūkumai Darbas su realiais skaičiais Papildomas darbas pertvarkyti į 1 pikselio storio liniją 8 Plono stačiakampio algoritmas Principas Pildomi pikseliai, kurių centrai patenka į stačiakampį Užpildomi neužpildyti tarpai Trūkumai: Darbas su realiais skaičiais Papildomas darbas užpildant tarpus 9 Storų linijų rasterizacijos algoritmas Principas Plonų linijų algoritmų pagrindu, vietoje atskiro pikselio rasterizuojama plunksnos formą atitinkanti pikselių aibė Atmetami persidengiantys pikseliai 10 Tiesioginio koordinačių skaičiavimo algoritmas Principas Naudojama kryptinė lygtis 𝑦 = 𝑘𝑥 + 𝑝 x kinta vienodu žingsniu Trūkumai: Trupmeninių skaičių operacijos sąlygoja mažą skaičiavimų spartą Problemos su žingsnio parinkimu, kai tiesės krypties koeficientas > 1 11 Skaitinio diferencialinio analizatoriaus algoritmas Principas Naudojama kryptinė lygtis Kiekvienam žingsnyje 𝑦𝑘+1 = 𝑦𝑘 + 𝑚∆𝑥 Gautas y apvalinamas Trūkumai Kaupiasi skaičiavimų paklaida Iškraipomas vaizdas, kai didelis tiesės krypties koeficientas Trupmeniniai skaičiai ir apvalinimas mažina spartą 12 Bresenhamo (vidurio taško) algoritmas Principas Tiesė rasterizuojama naudojant tik sveikų skaičių sumavimą Privalumai: Sudėtis vykdoma sparčiau nei daugyba, daugyba vykdoma sparčiau nei dalyba Jack Elton Bresenham Sveikų skaičių operacijos spartesnės už slankaus kablelio (Nereikia padengti ypatingų atvejų) Pritaikomas apskritimams, elipsėms ir kreivėms 13 Bresenhamo (vidurio taško) algoritmo idėja Naudojama kryptinė lygtis x arba y koordinatė didinama +1 žingsniu Kita koordinatė didinama +0 arba +1 žingsniu 14 k-tasis žingsnis Reikia nustatyti +0 arba +1 y koordinatei yk+3 (xk, yk)  (xk+1,yk) yk+2 y = mx + b (xk, yk)  (xk+1,yk+1) yk+1 yk Vidurio taško sąvoka xk xk+1 xk+2 x k+3 𝑦 = 𝑚𝑥 + 𝑏 15 Parametras p Parametro p skaičiavimas Įvedami pradžios ir pabaigos tašką y Kiekvienoje iteracijoje 𝑥𝑘+1 = 𝑥𝑘 + 1 k+3 Baigiama, kai pasiekiamas pabaigos taškas y y = mx + b k+2 𝐷𝑥 = 𝑥2 − 𝑥1 𝐷𝑦 = 𝑦2 − 𝑦1 y 𝑝0 = 2𝐷𝑦 − 𝐷𝑥 k+1 y 𝑝𝑘 + 2𝐷𝑦, 𝑗𝑒𝑖_𝑝𝑘 < 0 𝑝𝑘+1 =ቊ k 𝑝𝑘 + 2𝐷𝑦 − 2𝐷𝑥, 𝑘𝑖𝑡𝑢 𝑎𝑡𝑣𝑒𝑗𝑢 x x x x 𝑦𝑘 , 𝑗𝑒𝑖_𝑝𝑘 < 0 k k+1 k+2 k+3 𝑦𝑘+1 =ቊ 𝑦𝑘 + 1, 𝑘𝑖𝑡𝑢 𝑎𝑡𝑣𝑒𝑗𝑢 16 Brensenhamo algoritmo pavyzdys Pradžia = (1, 1) pabaiga = (10, 7) Dx = 9, Dy = 6 p0 = 2*6-9 = 3 Iteracijos: p0 > 0 → p1=3+2*6-2*9=-3 (10,7) p1 < 0 → p2=-3+2*6=9 p2 > 0 → p3=9+2*6-2*9=3 p3 > 0 → p4=3+2*6-2*9=-3 p4 < 0 → p5=-3+2*6=9 (1,1) p5 > 0 → p6=9+2*6-2*9=3 p6 > 0 → p7=3+2*6-2*9=-3 p7 < 0 → p8=-3+2*6=9 p8 > 0 → p9=9+2*6-2*9=3 17 Apskritimo rasterizacija Apskritimo lygtis (𝑥 − 𝑥𝑐 )2 +(𝑦 − 𝑦𝑐 )2 = 𝑅2 𝑦 = 𝑦𝑐 ± 𝑅2 − 𝑥𝑐 − 𝑥 2 Trūkumai Reikia atlikti labai daug veiksmų su realiaisiais skaičiais Kvadratinės šaknies skaičiavimai ir apvalinimas mažina spartą x keičiant vienodu žingsniu y reikšmės išsidėstę labai nevienodais intervalais 18 Apskritimo rasterizacija Vienodo intervalo išraiška 𝑥 = 𝑥𝑐 + 𝑅cos𝜃 𝑦 = 𝑦𝑐 + 𝑅cos𝜃 xc,yc Trūkumas Trigonometrinės funkcijos imlios laikui Galimybė Simetrija centrinio taško atžvilgiu 19 Vidurio taško algoritmas apskritimui rasterizuoti Principas Rasterizuojamas tik vienas aštuntadalis Kiti pikseliai kopijuojami į likusius aštuntadalius Kiekvienam žingsniui 𝑥𝑘+1 = 𝑥𝑘 + 1 Kiekvienam žingsniui 𝑦𝑘+1 = 𝑦𝑘 arba 𝑦𝑘+1 = 𝑦𝑘 − 1 5 𝑝0 = −𝑅 ≈1−𝑅 4 𝑝𝑘 + 2𝑥𝑘+1 + 1, 𝑘𝑎𝑖 𝑝𝑘 < 0 𝑝𝑘+1 = ቊ 𝑝𝑘 + 2𝑥𝑘+1 + 1 − 2𝑦𝑘+1 , 𝑘𝑖𝑡𝑢 𝑎𝑡𝑣𝑒𝑗𝑢 𝑦𝑘 , 𝑘𝑎𝑖 𝑝𝑘 < 0 𝑦𝑘+1 = ቊ 𝑦𝑘 − 1, 𝑘𝑖𝑡𝑢 𝑎𝑡𝑣𝑒𝑗𝑢 20 Vidurio taško algoritmas apskritimui rasterizuoti 1. Įvedamas spindulys R bei apskritimo centras (xc,yc) ir nustatomas apskritimo, kurio centras koordinačių pradžioje, pirmasis taškas (x0,y0) = (0, R). 2. Apskaičiuojama taško parinkimo parametro pradinė reikšmė: p0 = 1 – R. 3. Kiekvienas stulpelis xk, pradedant k=0, tikrinamas ir parenkamas taškas: Jei pk < 0, pasirinkti (xk+1, yk) 𝑝𝑘 + 2𝑥𝑘+1 + 1, 𝑘𝑎𝑖 𝑝𝑘 < 0 𝑝𝑘+1 =ቊ 𝑝𝑘 + 2𝑥𝑘+1 + 1 − 2𝑦𝑘+1 , 𝑘𝑖𝑡𝑢 𝑎𝑡𝑣𝑒𝑗𝑢 Jei pk  0, pasirinkti (xk+1, yk-1) 4. Pirmo aštuntadalio pikselis kopijuojamas 7 kartus 5. Kiekvienas pikselis perkeliamas per (xc,yc) 21 Daugiakampių ir kitų plokščiųjų figūrų užpildymas 1. Užliejimo (flood fill) 2. Eilučių skenavimo (scan-line fill) 22 Daugiakampio užpildymo, skleidžiant bangą, algoritmas Užpildymas pradedamas nuo daugiakampio vidinio taško iki kontūro ribos 4 krypčių banga 8 krypčių banga 4 krypčių problema 23 Daugiakampio vidinių taškų nustatymas 1. Pagal nelygiškumo porų taisyklę 2. Trikampio vidinio taško 3. Iškiliojo daugiakampio vidinio taško pagal trikampio taisyklę 24 Nelygiškumo porų taisyklė Kontūro kirtimų skaičius lyginis – taškas daugiakampio išorėje Kontūro kirtimų skaičius nelyginis – taškas daugiakampio viduje 25 Trikampio vidinio taško nustatymas Trikampio kraštinės orientuotos kryptimi prieš laikrodžio rodyklę Taškas yra kiekvienos kraštinės kairėje, apeinant kraštines kryptimi prieš laikrodžio rodyklę Daugiakampio vidinio taško nustatymas pagal trikampio taisyklę (tik iškiliesiems daugiakampiams) 26 Eilučių skenavimo algoritmas Vidiniai daugiakampio taškai ant jį kertančios skleistinės Skenuojant linijomis nustatomas daugiakampio ir jį kertančios skleistinės sanklotos intervalas 27 Eilučių skenavimo algoritmas 1. Rasti darbinės skleistinės sankirtas su visomis daugiakampio kraštinėmis 2. Surikiuoti sankirtas x koordinatės didėjimo tvarka 3. Užpildyti vidinius daugiakampio taškus, esančius tarp sankirtų taškų porų Ypatingi atvejai: Sankirtos su daugiakampio viršūnėmis sveikaskaitinėse koordinatėse Bendros viršūnės Horizontalios briaunos. 28 Teksto rasterizavimas Binarinė matrica Vektorinė grafika 1 1 1 1 1 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 1 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 a) b) 29 Vaizdo kraštų glotninimas 30 Spalva pagal linijos plotą daugiakampio viduje S – visas spalvinamas plotas Sx – spalvinamas plotas, kurį dengia kontūras C – objekto spalva Cfono – fono spalva Cx – ieškoma spalva C  S x + C fono  ( S − S x ) Cx = S 31 Apibendrinimas Bresenhemo algoritmas yra vienas efektyviausiu rasterizuojant atkarpas Atkarpų rasterizacija užliejimo ir eilučių skenavimo Daugiakampio vidinio taško nustatymo būdai: interaktyvus, pagal nelygiškumo porų taisyklę ir orienuotas kraštines Vaizdo kraštų glotninimas leidžia vizualiai spręsti mažos raiškos problemą 32 Literatūra 1. A. Lenkevičius. Kompiuterinė grafika ir vizualizacija. E. mokomoji knyga. TEV, 2011. 1.4 skirsnis. http://www.ebooks.ktu.lt/eb/230/kompiuterine_grafika_ir_vizualizacija/ 2. Edward Angel, David Shreiner. Interactive computer graphics: a top-down approach with shader-based OpenGL. 2012. 6th edition. 6.8-6.10 sk. 3. Peter Shirley. Fundamentals of Computer Graphics. 4th edition. 2002. 3.5-3.7 sk. 33