Know-how, előadás, poligonok és területek kitöltése
Hagyja, hogy a poligon kontúrja raszterezve legyen és megjelenjen. Ezután a töltés a raszter minden egyes sorának a [x2i-1. X2I]. ahol xk az ebben a sorban szereplő "beillesztett" pixelek x koordinátáit mutatja, növekvő sorrendben rendezve (lásd a 6.4a. ábrát).
A (x, y) értékkel jelöljük a pixel állapotát a koordinátákkal (x, y). I (x, y) = 1. ha a pixel "on", és I (x, y) = 0 egyébként. Könnyű látni a művelet sorozatos végrehajtását
x = 1, 2, 3. X - 1 (ahol X - vízszintes méretét a raszter) vezet a kívánt eredményt - az egyetlen különbség az, hogy az utolsó pixel mindegyik intervallum nem festette át (lásd 6,4 B ..). Ez a kis pontatlanság a legtöbb esetben kritikátlan és vizuálisan láthatatlan. Formálisan az algoritmus így írt:
Lista 6.3. XOR raszterizálás
Ha meg kell szerezni az 1. ábra szerinti eredményt. 6.4a. akkor a poligon vázlatát ismét festeni lehet, vagy a fenti algoritmus következő módosításával (ún. "XOR a zászlóval"):
Lista 6.4. XOR Raszterezés zászlóval
A XOR algoritmusok előnye a rendkívüli egyszerűség. A hátrány az, hogy lehetetlen a külföldi képekkel együtt dolgozni a képernyőn.
Kivételes esetek
Most helyezzük el a 2. ábrán bemutatott esetek megszüntetésére szolgáló módszereket. 6.1. A vízszintes perem esetében nyilvánvalóan elegendő csak a végét visszahúzni, ha ezt a szélességet raszterezik.
A fennmaradó esetek kizárásához az alábbiak szerint járjon el. Amikor egy poligon minden szélét raszterezik, nem adjuk ki az alsó végét (x2. Y2). és levezetni a felső végén a művelet I (x1. y1) = I (x2. y2) XOR 1. Ennek hatására, hogy a felső (alsó) végződik a bordák, hogy esik az azonos képpont, azokat vissza nem vonják, és így , a rasztervonalak "egyetlen" pontjai kizárásra kerülnek.
Ábra. 6.5. A poligon festésének lépései.
Algoritmus XOR művelettel partícióval
Az algoritmus áll fordítja a színe az összes pixel jobbra található az i-edik borda és egymás után az i = 1, 2 N (a számozás bordák nem számít). A vízszintes élek figyelmen kívül maradnak. Amint az 1. ábrából látható. 6.5. Ennek eredményeképpen a sokszög belső pixelei feltöltődnek.
Ennek az algoritmusnak az érdemei közé tartozik az egyszerűség és az eredetiség, valamint a további adatszerkezetek hiánya. A hátrány az, hogy nagyszámú műveletet kell végrehajtani képpontokkal (legfeljebb N műveletekkel minden egyes képpontnál), beleértve a sokszögön kívüli műveleteket is. Különösen, minél nagyobb a távolság a sokszög és a képernyő jobb szélénél, annál több "felesleges" műveletet hajtanak végre.
Ebből a hátrányból az algoritmus szabad módosítása - "XOR-2 partícióval". Az az elképzelés, hogy megfordítja a régió nem széle közötti és a jobb a képernyő szélén, és a között a borda és a függőleges vonal ( „fal”), mentálisan végzett bármilyen erre alkalmas helyen - mint például a átkelés egy sokszög (lásd 6.6 ábra ..).
Ábra. 6.6. Raszterezés XOR művelettel partícióval.