Rastrování

Při rastrování vektorové grafiky , v tomto příkladu ve formátu SVG , musí být určeny hodnoty barevných pixelů výsledné rastrové grafiky .

Ve 2D počítačové grafice označuje rasterizace (z „rastru“: pravidelné vzory rozložené po povrchu), nazývaná také rendrování nebo skenování , převod vektoru na rastrovou grafiku .

Postup

Renderovač PDF, který převádí vektorová písma na pixelovou grafiku . Nad PDF Sumatra , pod Adobe Reader .

Existuje řada algoritmů pro rastrování grafických primitiv , jako jsou čáry, mnohoúhelníky , kruhy a další geometrické tvary, viz:

• Rastrování linek
• Rastrování polygonů
• Mřížka kruhů

Známým problémem screeningu je efekt schodiště . Pokud barevná hloubka větší než 1 bit na pixel je k dispozici pro tyto rastrový být generován , tento účinek může být snížen pomocí anti-aliasing . Existuje několik metod, z nichž některé fungují nevážené a některé používají speciální rekonstrukční filtr. Při rastrování textu existují speciální problémy, kterým lze zabránit pomocí nápovědy .

Screening tlustých primitiv

Při skríningu grafických primitiv určité tloušťky existuje několik možností , pokud již nejsou použity algoritmem vyhlazování - aliasing . V případě polygonů je třeba zohlednit také spojovací body mezi jednotlivými úsečkami, viz Rastrování polygonů .

Opakování pixelů

Jednou z metod je při rastrování nakreslit několik pixelů svisle nebo vodorovně namísto jednoho . Jedním z problémů je, že konce křivek se na silných křivkách objevují „odříznuté“. Kromě toho mohou být v místech, kde přepínáte z horizontálního na vertikální opakování nebo naopak, patrné mezery. Kromě toho , podobně jako tenké čáry, mají takové rastrované křivky jinou tloušťku v závislosti na místním sklonu .

štětec

Určitá rastrová grafika se přesune po křivce jako „štětec“, v nejjednodušším případě čtverec s požadovanou délkou hrany . I zde se tloušťka liší v závislosti na přechodu, ale na rozdíl od opakování pixelů je čára nejsilnější s úhlopříčnými kroky. Řešením je otočit čtverec podle místního sklonu křivky, ale je jednodušší použít kruh jako štětec. Nevýhodou metody je, že při rasterizaci narazíte na velké množství pixelů , které již byly vybarveny v předchozích krocích . Čím silnější je křivka, tím větší je tento efekt. Mnohoúhelníkové kartáče lze použít k vyřešení problému měnící se tloušťky křivky.

Vyplňte mezi hranami

Dalším způsobem, jak rastrovat silnou křivku, je nakreslit její dva okraje v určité vzdálenosti od sebe a vyplnit mezeru mezi nimi. Nevýhodou je, že u dvoubarevného rastru může křivka vypadat mírně posunutá kvůli chybám zaokrouhlování. V případě elips je třeba poznamenat, že mřížka nakreslením dvou konfokálních elips s poloosami různých délek není geometricky správná.

Čáry

Nakonec existuje možnost kreslení silných křivek spojováním krátkých úseček. Stejné speciální funkce jako při rastrování polygonů je třeba dodržovat, aby byly úsečky navzájem správně spojeny.

Vypuštění primitiv

Obrázky, které již byly nakresleny, lze selektivně odstranit opětovným nakreslením s barvou pozadí. To však nefunguje, pokud se překrývají s jinými čísly, protože lze také odstranit nechtěné části obrazu. Účinným způsobem, jak se tomu vyhnout, je testování minimaxem nebo boxem. Zde se nejprve zkontroluje, zda jsou v obdélníku překlenutém obrázkem, který má být odstraněn, další postavy. Pouze v tomto případě musíte otestovat křižovatky a v případě potřeby překreslit celou oblast.

3D projekce

Trasování paprsků a rastrování jsou dva zásadně odlišné přístupy k vykreslování obrázků ze 3D scén, i když pro primární paprsky počítají stejné výsledky. Rastrování promítá každý trojúhelník na rovinu obrazu a uvádí všechny pokryté pixely ve 2D , zatímco sledování paprsků se provádí ve 3D generováním paprsků přes každý pixel a následným nalezením nejbližšího průsečíku s trojúhelníkem.

Jeden se může vyhnout použití modelu nebo zobrazit transformaci tím, že místo toho transformuje generátor vzorkovače. Zatímco čísla s plovoucí desetinnou čárkou se obvykle používají při sledování paprsku, s jejich numerickými problémy lze 3D screening implementovat se stejnými pravidly konzistence jako 2D screening. Ve 3D rastrování jsou jedinými zbývajícími rozdíly mezi těmito dvěma přístupy křížení scén a výčet potenciálně pokrytých vzorků v rovině obrazu (viz binning ).

Výpočty

Obrázek 2: Normální vektor je kolmý k trojúhelníku .${\ displaystyle {\ vec {n_ {2}}}}$ ${\ displaystyle ({\ vec {e}}, {\ vec {p_ {1}}}, {\ vec {p_ {0}}})}$

Obrázek 1: Projekce střed jako původu trojrozměrné souřadnicové systému s pixelu , který leží v rovině obrazu a trojúhelníku .${\ displaystyle {\ vec {e}}}$ ${\ displaystyle {\ vec {d}}}$ ${\ displaystyle ({\ vec {p_ {0}}}, {\ vec {p_ {1}}}, {\ vec {p_ {2}}})}$

Obrázek 3: pixely musí být určena trojúhelníky , a definované Poloprostor se nacházejí.${\ displaystyle {\ vec {d}}}$ ${\ displaystyle ({\ vec {e}}, {\ vec {p_ {1}}}, {\ vec {p_ {0}}})}$${\ displaystyle ({\ vec {e}}, {\ vec {p_ {2}}}, {\ vec {p_ {1}}})}$${\ displaystyle ({\ vec {e}}, {\ vec {p_ {0}}}, {\ vec {p_ {2}}})}$

Obrázek 4: Poloha průsečíku v trojúhelníku .${\ displaystyle {\ vec {e}} + t \ cdot {\ vec {d}}}$ ${\ displaystyle ({\ vec {p_ {0}}}, {\ vec {p_ {1}}}, {\ vec {p_ {2}}})}$

Chcete-li zjistit, zda je pixel v obrazové rovině je pokryta pomocí trojúhelníku , postačí ověřit, zda výstupek nosník (viz centrální výstupek ), který prochází protíná pixel trojúhelník.

Za předpokladu, že střed projekce na původu v trojrozměrném systému kartézských souřadnic , a odkazuje na rohy promítaného trojúhelníku , , (obrázek 1), pak se tyto podmínky za následek pro pixel v promítnuté trojúhelníku je umístěn (obrázek 3): ${\ displaystyle {\ vec {e}}}$ ${\ displaystyle {\ vec {p_ {0}}}}$${\ displaystyle {\ vec {p_ {1}}}}$${\ displaystyle {\ vec {p_ {2}}}}$${\ displaystyle {\ vec {d}}}$

• Rovina, která prochází trojúhelníkem, rozděluje trojrozměrný prostor na dva poloprostory . Pixel obrazové roviny musí ležet v poloprostoru, ve kterém je bod umístěn. Také Pixel${\ displaystyle ({\ vec {e}}, {\ vec {p_ {1}}}, {\ vec {p_ {0}}})}$ ${\ displaystyle {\ vec {p_ {2}}}}$
• leží v poloprostoru definovaném trojúhelníkem, ve kterém je bod umístěn a${\ displaystyle ({\ vec {e}}, {\ vec {p_ {2}}}, {\ vec {p_ {1}}})}$${\ displaystyle {\ vec {p_ {0}}}}$
• leží v poloprostoru definovaném trojúhelníkem, ve kterém je bod umístěn.${\ displaystyle ({\ vec {e}}, {\ vec {p_ {0}}}, {\ vec {p_ {2}}})}$${\ displaystyle {\ vec {p_ {1}}}}$

Následující funkci lze použít ke kontrole, zda je bod umístěn v poloprostoru definovaném body , a : ${\ displaystyle {\ vec {p}}}$${\ displaystyle {\ vec {a}}}$${\ displaystyle {\ vec {b}}}$${\ displaystyle {\ vec {c}}}$

${\ displaystyle V ({\ vec {p}}): = {\ vec {n}} \ cdot {\ vec {p}} = (({\ vec {b}} - {\ vec {a}}) \ times ({\ vec {c}} - {\ vec {b}})) \ cdot {\ vec {p}}}$

kde je skalární součin z vektorů a . Normálový vektor je přes součin${\ displaystyle {\ vec {n}} \ cdot {\ vec {p}}}$ ${\ displaystyle {\ vec {n}}}$${\ displaystyle {\ vec {p}}}$ ${\ displaystyle {\ vec {n}}}$

${\ displaystyle {\ vec {n}}: = ({\ vec {b}} - {\ vec {a}}) \ krát ({\ vec {c}} - {\ vec {b}})}$

definované a je kolmé k trojúhelníku . Tato funkce počítá objem o Tetra z S s rohy , , , . Pokud je bod nad trojúhelníkem , znaménko je kladné, pokud je níže, znaménko je záporné. Pokud leží v rovině trojúhelníku , je objem 0. ${\ displaystyle ({\ vec {a}}, {\ vec {b}}, {\ vec {c}})}$ ${\ displaystyle {\ vec {a}}}$${\ displaystyle {\ vec {b}}}$${\ displaystyle {\ vec {c}}}$${\ displaystyle {\ vec {p}}}$${\ displaystyle {\ vec {p}}}$${\ displaystyle ({\ vec {a}}, {\ vec {b}}, {\ vec {c}})}$${\ displaystyle {\ vec {p}}}$${\ displaystyle {\ vec {p}}}$${\ displaystyle ({\ vec {a}}, {\ vec {b}}, {\ vec {c}})}$

S funkcemi

${\ displaystyle V_ {0} ({\ vec {d}}): = ({\ vec {p_ {2}}} - {\ vec {e}}) \ krát ({\ vec {p_ {1}} } - {\ vec {p_ {2}}})}$

${\ displaystyle V_ {1} ({\ vec {d}}): = ({\ vec {p_ {0}}} - {\ vec {e}}) \ krát ({\ vec {p_ {2}} } - {\ vec {p_ {0}}})}$

${\ displaystyle V_ {2} ({\ vec {d}}): = ({\ vec {p_ {1}}} - {\ vec {e}}) \ krát ({\ vec {p_ {0}} } - {\ vec {p_ {1}}})}$

lze formulovat následující prohlášení:

• Pixelové spočívá v promítá trojúhelník, pokud a i je.${\ displaystyle {\ vec {d}}}$${\ displaystyle V_ {0} ({\ vec {d}})> 0}$${\ displaystyle V_ {1} ({\ vec {d}})> 0}$${\ displaystyle V_ {2} ({\ vec {d}})> 0}$

Průsečík pixelu s původním trojúhelníku může také barycentrický souřadnice jednotlivých bodů , , jsou vyjádřeny (obrázek 4). Pak: ${\ displaystyle {\ vec {e}} + t \ cdot {\ vec {d}}}$${\ displaystyle {\ vec {d}}}$${\ displaystyle ({\ vec {p_ {0}}}, {\ vec {p_ {1}}}, {\ vec {p_ {2}}})}$${\ displaystyle {\ vec {p_ {0}}}}$${\ displaystyle {\ vec {p_ {1}}}}$${\ displaystyle {\ vec {p_ {2}}}}$

${\ displaystyle {\ vec {e}} + t \ cdot {\ vec {d}} = t \ cdot {\ vec {d}} = \ lambda _ {0} \ cdot {\ vec {p_ {0}} } + \ lambda _ {1} \ cdot {\ vec {p_ {1}}} + \ lambda _ {2} \ cdot {\ vec {p_ {2}}}}$ S ${\ displaystyle \ lambda _ {i} = {\ frac {V_ {i} ({\ vec {d}})} {V_ {0} ({\ vec {d}}) + V_ {1} ({\ vec {d}}) + V_ {2} ({\ vec {d}})}}}$

kde a jsou reálná čísla . Barycentrické souřadnice jsou označeny.${\ displaystyle t}$${\ displaystyle \ lambda _ {i}}$ ${\ displaystyle {\ vec {e}} + t \ cdot {\ vec {d}} = (\ lambda _ {0}: \ lambda _ {1}: \ lambda _ {2})}$

Algoritmy

Jakmile je k vykreslení vybrán trojúhelník , je důležité efektivně identifikovat paprsky, které pokrývá. U tradičního trasování paprsků jsou uvedeny pouze trojúhelníky, u nichž je pravděpodobné, že budou protínány průchodem. U větších částí obrazu však trojúhelník může pokrýt pouze malou část pixelů a může být výhodné použít binning k urychlení hledání pokrytých pixelů. Ze stejného důvodu se při rasterizaci vždy používalo binování, aby se rychle zobrazily pokryté pixely na obrazovce .

Obecná formulace kombinovaného procházení a binování ukazuje následující rekurzivní funkci , která je reprezentována v pseudokódu :

funktion durchlaufen(bildausschnitt F, knoten N)
    falls istVerdeckt oder istAuszerhalb dann stop
    falls bildausschnittTeilen dann
        teile F in teilausschnitte F[i]
        für jeden teilausschnitt F[i]
            durchlaufen(F[i], N)
    ende
    sonst falls pixelErzeugen dann rastern(N, binning)
        sonst
            für jeden nachfolger_von_N
                durchlaufen(F, nachfolger_von_N)
    ende
ende
                durchlaufen(F, nachfolger_von_N)

Zde F je obrazová část a N je uzel struktury prostorového indexu , který obvykle začíná celým výřezem nebo kořenovým uzlem. Psané kurzivou slova istVerdeckt, istAuszerhalb, bildausschnitt akcií , pixel generovat istAuszerhalb a Binning testovací funkce pro volání, chování algoritmu kontroly a nám umožňují vyrábět výše uvedených zobrazovacích algoritmů a objevovat nové cesty.

literatura

• James D. Foley et al: Počítačová grafika: Principy a praxe. Addison-Wesley, Reading 1995, ISBN 0-201-84840-6
• David F. Rogers: Procedurální prvky pro počítačovou grafiku. WCB / McGraw-Hill, Boston 1998, ISBN 0-07-053548-5

webové odkazy

• Základy počítačové grafiky - rasterizace. Archivovány od originálu 6. srpna 2016 ; Citováno 9. listopadu 2017 . 

Individuální důkazy

1. ^ Hans F. Ebel , Claus Bliefert : Přednášky z přírodních věd, technologií a medicíny. 1991; 2., upravené vydání 1994, VCH, Weinheim ISBN 3-527-30047-3 , s. 302.
2. ^ John D. Hobby: Digitalizované stopy kartáčů. Dizertační práce, Stanford University, 1985 ( PDF, 30 MB ( Memento ze dne 26. října 2006 v internetovém archivu ))
3. ↑ ^{a b c} 3D Rasterization: Most mezi Rasterization a Ray Casting