Kitöltött sokszögek és árnyékolás területén
A legtöbb alkalmazás használja egyik jelentős előnye raszter eszközök - a lehetőséget, hogy kitöltse a képernyőt.
Kétféle töltési:
· Először is, mindkét kapcsolódó interaktív működés, és programozni a szintézis a kép, arra szolgál, hogy kitöltse a belső része a sokszög koordinátái által meghatározott csúcsához.
· Másodszor, amelyek elsősorban az interaktív működés, arra szolgál, hogy töltse amely terület határolja határ pixel kóddal eltérő kódokat minden pixel a régión belüli vagy pixel festett egy előre meghatározott kóddal;
Ebben a részben, úgy véljük, töltés algoritmus sokszög. A következő szakaszban lesz szó algoritmusok töltse ki a mezőt.
A legegyszerűbb módszer a töltés egy sokszög által meghatározott vertex koordinátákat, annak meghatározása, hogy az aktuális képpont tartozik, hogy a belsejében a sokszög. Ha tartozik, a pixel van tárolva.
Határozzuk meg a sokszög pixel tartozik lehet, például, számítva a teljes szöget csúcspontot pixel, amikor áthalad a poligon kontúrt. Ha a pixel belül van a szög 360 °. ha van - 0 ° (ábra.).
Ábra. 0.4.1. A meghatározás a sokszög pixel
Kiszámítása a tartozék kell végezni minden pixel a képernyőn, mint a legtöbb pixel valószínűleg sokszög, akkor a folyamat túl pazarló. A kötet a felesleges számítások bizonyos esetekben lehetőség van arra, hogy csökkentsék a téglalap héj - minimum körülvevő négyszöget az objektum az érdeklődés, de mindegy számítások lesz sok. Egy másik módszer meghatározására tagság belső pontja a sokszög lesz szó az alábbiakban a tanulmány a nyírás darab algoritmus szerint Cyrus-Beck.
fokozatos feltöltésének algoritmusok ténylegesen használják, azon a tényen alapul, hogy a szomszédos pixel egy sorban valószínűleg ugyanaz, és változhat csak ott, ahol a vonal metszi a sokszög szélét. Ez a koherencia nevezik raszter vonalak (Yi szkennelési vonal. Yi + 1 + 2 Yi látható.). Ez elegendő ahhoz, hogy meghatározza az X-koordinátákat a kereszteződések letapogatott sorok bordákkal. Párok rendezve metszéspontjai határozzák meg a szakadó időközönként.
Ábra. 0.4.2. Progresszív sokszög árnyékolás
Ezen túlmenően, ha az éleket metszik az i-edik sorban, akkor nagy valószínűséggel akkor is metszi a vonal i + 1. (A szkennelési vonal Yi és Yi + 1 ábrán látható. 0,2). Ezt nevezik a koherencia a bordák. Az átmenet egy új vonal könnyen kiszámítható az új X-koordinátája metszéspontja a bordák, az X-koordinátája metszéspontja a régi és az szög tangense a bordák:
(Tangense a dőlésszög a bordák - k = dy / dx, mivel dy = 1, akkor a 1 / k = dx).
Mennyiségének változtatásával bányásszák időközönként fordul elő, ha a csúcs jelenik meg a szkennelési vonal.
Számviteli vonalak és élek koherenciáját teszi kitöltési sokszögek építeni a különböző algoritmusok igen progresszív scan. Csak azokat az éleket tartják minden szkennelési vonal metszi vonalon. Ezeket adott egy listát az aktív élek (ATS). Amikor elhaladnak a következő sort kell keresztbe bordák újratervezi X koordinátája kereszteződéseket. Amikor egy szkennelési vonalat előállított csúcsot átrendeződést ATS. A bordák, amelyek már nem metszik egymást, eltávolítjuk a KAP és az összes új élek, átlépte a vonalat kell beírni azt.
Általános diagram dinamikusan létrehoz egy listát az aktív élek, és a poligon töltse alulról felfelé, az alábbiak szerint:Minden él a listán az aktív élek megadva:
Ha ezután úgy találják, hogy a lista az aktív élek üres, a töltés befejeződött.
5. függelék mutatja két szubrutin kitöltött sokszögek - V_FP0 és V_FP1. Első végrehajtja az aktív (a legegyszerűbb) algoritmus. Ez a program nagyon hatékony, de generál kétszer vagy háromszor a bejegyzést a pixel. Ez elfogadható, kis kimeneti eszközök, például a mátrix vagy a tintasugaras nyomtatók.
Ellentétben V_FP0, a V_FP1 program használ egy bonyolultabb algoritmust képező listán az aktív éle, amely gyakorlatilag teljes hiánya párhuzamos (ábra.).
Ábra. 0.4.3. Összehasonlítás sokszög kitöltési algoritmusok
0.4.2 Sorting adagoló számlálási mód
Mint már említettük, az alkalmazások, főként az interaktív munka algoritmusok segítségével töltse le a területet primer.
Ezen a módon, vagy egy másik meghatározott öntjük (recolorable) régió, egy pixel kódot, ami fut kitölti és a kiindulási pont a területen, ahonnan indul kitöltésével.
Referenciaként területek két csoportba sorolhatjuk:
· Határ-biztos felkérte (zárt) határt, hogy a határ a pixel kódok eltérnek belső kódok recolorable a terület. Kódok a képpontok belül a terület kiszabott két feltétel - ezek nem lehetnek azonosak a kódot hozása újrafestés pixelkód. Ha egy bizonyos határ-régió létezik egy másik által rajzolt határ pixelek ugyanazzal a kóddal, mint a külső határán, a megfelelő része a régió nem kell festeni;
· Belső definiált, húzott egy adott pixel kódot. Amikor betöltötte a kód helyébe egy új kódot árnyékolástechnika.
Ez az alapvető különbség terület kitöltéséhez beoltott kitöltésével a sokszög. Az utóbbi esetben, azonnal az összes információt korlátozza a méret a képernyő által elfoglalt sokszög. Ezért a meghatározást a sokszög pixel kiegészítők alapuló gyors munka algoritmusokat koherens vonalak és szélek (lásd. Az előző rész). Az algoritmusok is töltenek ki egy területet a mag, akkor először meg kell olvasni a pixel, majd meghatározza, hogy ez területéhez tartozik, és ha tartozik, majd átfestés.
Töltsük meg a területen, vagy annak határán - a csatlakoztatott set pixel. A hozzáférési eszközökkel, hogy a szomszédos pixel területek vannak osztva 4-bites és 8-csatlakoztatva. A 4-kapcsolt régiók hozzáférést szomszédos pixelek végezzük a négy irányba - bal és jobb vízszintesen és függőlegesen felfelé és lefelé. A 8-csatlakoztatott régiók ezeken a területeken hozzáadunk további 4 átlós. A kapcsolat tudjuk, mozog a kiindulási pont, hogy elérje, és festeni az összes képpont területen.
Fontos megjegyezni, hogy a határ 8 csatlakozik (ábra. A) és a fordítva 8-csatlakoztatva régió 4. határvonal van csatlakoztatva (lásd. Ábra. B) 4-x összekapcsolt téglalap alakú terület. Ezért, kitöltése 4-csatlakoztatott régió csatlakoztatott 8 algoritmus vezethet „szivárgás” a határon, és kitölti a képpont egy szomszédos területen.
Általában a 4-kapcsolt régió tudjuk tölteni mind a 4. és 8. kapcsolt algoritmus. Az ellenkezője nem igaz. Mivel a terület látható. és mi lehet tölteni bármilyen algoritmussal, és a régió látható. alkalmazzuk, amely két szomszédos 4-csatlakoztatott régiók lehet tölteni csak 8-koherens algoritmus.
Ábra. 0.5.1. Kapcsolódás területek és határok
A kapcsolat-nak és verem lehet építeni egyszerű algoritmusokkal töltse mind belsőleg, mind határ körülhatárolt területen. A [] tartják nagyon rövid rekurzív kitöltés rutinok. A [] - valamivel hosszabb iteratív rutinok.
0.5.1 Egyszerű töltési algoritmus
Ez a függelék három öntési eljárások határ-specifikus területen kiemelt.
Az első eljárás - V_FAB4R valósít rekurzív algoritmus kitöltésére 4-csatlakoztatott megfelelő régióban algoritmust helyezzük [4].
A második eljárás - V_FAB4 valósít egy iteratív algoritmust kitöltésére 4-csatlakoztatva régióba, közel az algoritmus helyezzük [3].
A jellemző ezen algoritmusok - nagyon magas költsége memória a folyamat verem és többszörös párhuzamos bejegyzés pixel. Jellemző értékei a verem mérete (lásd. MAX_STK állandók azt alább definiált) mintegy tízezer bájt, ha a méret a sorrendben 70 × 70 pixel, és nagyon erősen függ a méret a megtöltött terület, a konfiguráció és a kezdeti pontot. Például, hogy töltse ki egy négyzet oldalsó egyenlő, mint 65 diszkrét, és megkezdődik az öntés pont (20,20) képest egy négyzet szögben igényel 7938 bájt, hogy a köteget.
A harmadik eljárás - V_FAST algoritmus végrehajtja fokozatos feltöltésének beoltjuk határ-meghatározott területen, közel a megfelelő algoritmus [3]. A megkülönböztető jegye ezen algoritmusok - nagy mennyiségű kódot, kis költség memória a verem és a munka gyakorlatilag nem párhuzamos bejegyzés pixel. Jellemző értékei a verem mérete (lásd. MAX_STK állandókat alább definiált) mintegy száz bájt.
0.17.1 V_FAB4R - rekurzív kitöltés 4-x összekapcsolt régió