Permiteți rasterizarea și afișarea conturului poligonului. Apoi, umplerea sa este redusă la umplerea în fiecare rând al raster a tuturor intervalelor formei [x2i-1. x2i]. unde xk reprezintă coordonatele x ale pixelilor "inclusi" din acest rând, aranjate în ordine ascendentă (a se vedea figura 6.4a).
Denumim prin I (x, y) starea pixelului cu coordonatele (x, y). I (x, y) = 1. dacă pixelul este "pornit" și I (x, y) = 0 în caz contrar. Este ușor să vedem execuția secvențială a operației
pentru x = 1, 2, 3. X - 1 (în care X - dimensiune orizontală a unui raster) va conduce la rezultatul dorit - cu singura diferență fiind că ultimul pixel din fiecare interval nu este vopsită (vezi Figura 6.4b ..). Această mică inexactitate în majoritatea cazurilor este necritică și invizibilă vizual. Formal, algoritmul este scris astfel:
Listing 6.3. XOR Rasterizare
Dacă este necesar să se obțină rezultatul corespunzător Fig. 6.4a. sau după ce este posibil să se re-vopsea circuitul de afișare al poligonului, sau utilizați următoarea modificare a algoritmului (numit „XOR cu steag“):
Listing 6.4. XOR Rasterizare cu pavilion
Avantajul algoritmilor XOR este simplitatea lor extremă. Dezavantajul este că este imposibil să lucrați cu imagini străine pe ecran.
Cazuri excepționale
Să abordăm acum metodele de eliminare a cazurilor prezentate în Fig. 6.1. În cazul unei muchii orizontale, evident, este suficient să se retragă numai capetele sale atunci când rasterizarea acestei margini.
Pentru a exclude cazurile rămase, puteți proceda după cum urmează. Când rasterizarea de fiecare margine a poligonului nu va transmite capătul inferior (x2. Y2). și derivă capătul superior prin operația I (x1. y1) = I (x2. y2) XOR 1. Aceasta va determina ca partea superioara (inferior) capetele nervurilor care se încadrează în același pixel, acestea sunt retrase și, prin urmare, , punctele "unice" din liniile raster vor fi excluse.
Fig. 6.5. Pași pentru pictura poligonului.
Algoritm cu operare XOR cu partiție
Algoritmul constă în inversarea culoarea tuturor pixelilor localizate la dreapta nervurii i-lea și secvențial pentru i = 1, 2. N (numerotarea nervurilor nu contează). Marginile orizontale sunt ignorate. Așa cum se poate vedea din fig. 6.5. ca rezultat, toți pixelii interni ai poligonului și numai aceștia vor fi umpluți.
Meritele acestui algoritm includ simplitatea și originalitatea acestuia, precum și lipsa unor structuri de date suplimentare. Dezavantajul este necesitatea de a efectua un număr mare de operațiuni cu pixeli (până la N operații cu fiecare pixel), inclusiv în afara poligonului. În special, cu cât este mai mare distanța dintre poligon și marginea din dreapta a ecranului, vor fi efectuate mai multe operații "redundante".
Din acest dezavantaj este modificarea liberă a acestui algoritm - "XOR-2 cu o partiție". Ideea este de a inversa regiunea nu este între margine și marginea din dreapta a ecranului, și între coaste și linia verticală ( „perete“), realizat mental la orice locație convenabilă - cum ar fi traversarea unui poligon (vezi Figura 6.6 ..).
Fig. 6.6. Rasterizarea cu funcționarea XOR cu o partiție.
Articole similare
Trimiteți-le prietenilor: