Vyplňování souvislé oblasti

1.

Které z následujících tvrzení není pravdivé: a) Princip interpolace je určení souřadnic pixelů a jejich barevné hloubky, které reprezentují tvar základních grafických prvků b) Princip interpolace využívá souřadnic pixelů a barvy pixelů k vyjádření rastrových dat vektorovým způsobem c) Princip interpolace je stanovení polohy a hodnoty pixelů, které nejlépe nahradí zadanou křivku d) Princip interpolace využívá souřadnic pixelů a barevné hloubky k vyjádření vektorových dat rastrovým způsobem

2.

Jedním z algoritmů, který se používá při vykreslování úsečky na monitoru je: a) Digitální diferenciální analyzátor (algoritmus DDA) b) Algoritmus nejkratších polocest c) Šifrovací algoritmus RSA d) Algoritmus slepé koleje

3.

Pro kresbu celé kružnice stačí vypočítat souřadnice bodů: a) Jednoho kvadrantu b) Dvou kvadrantů c) Jednoho oktantu d) Dvou oktantů

4.

Pro počítačovou grafiku má největší význam křivka zadaná: a) Implicitně b) Parametricky c) Explicitně d) Ve tvaru spojité funkce

5.

Stav, kdy vzdálenost uzlů nemusí být např. u křivek NURBS konstantní, vyjadřujeme slovem: a) nespojitý b) nehomogenní c) neuniformní d) neracionální

Počítačová grafika

Vyplňování souvislé oblasti Jana Dannhoferová

([email protected])

Ústav informatiky, PEF MZLU

Metody vyplňování podle reprezentace hranice

Oblast • obecný prvek pro kreslení plošných obrazců (vždy uzavřená) • definice oblasti souvisí s popisem její hranice: • geometricky určená hranice • je zadána pomocí posloupnosti bodů definujících mnohoúhelník nebo pomocí jedné či více navazujících křivek (příp. jako průnik poloprostorů) • základní metodou je řádkové vyplňování • hranice nakreslená v rastru (v obrazové paměti) • tvar hranice může být libovolný • nutno znát buď barvu hranice nebo barvu vnitřní oblasti

a) řádkové vyplňování

b) semínkové vyplňování

(příp. barvu vně oblasti)

• základní metodou je semínkové vyplňování © J. Dannhoferová, Počítačová grafika

3

4

A) Vyplňování geometricky určené hranice

Úloha vyplňování oblasti • je rozdělena na dvě části: 1) nalezení vnitřních bodů • algoritmicky složitější 2) obarvení vnitřních bodů • použito může být: • prázdná oblast (empty, void, hollow) • jedna barva (solid fill) • šrafování (hatch fill) • opakovaně nanášený vzorek (pattern tilling) • interpolace barvy

© J. Dannhoferová, Počítačová grafika


• geometricky zadaná hranice se může protínat (které body budou vnitřní?)

a) paritní vyplňování

5

b) vnitřní c) obtočení bodu d) více hranic vyplňování hranicí


6

1

Paritní vyplňování polygonální oblasti

Paritní řádkové vyplňování

• je přirozené, nejjednodušší a nejběžnější

• nebo tzv. vyplňování rozkladovými řádky

• odpovídá intuitivnímu pohledu na hranici jako entitu oddělující vyplněný a nevyplněný prostor

• každým řádkem rastru je vedena pomyslná vodorovná čára a jsou hledány její průsečíky s hranicemi oblasti

• pro vnitřní bod platí, že libovolná polopřímka z něj vedená protne lichý počet hran oblasti (lichá x sudá parita)

• nalezené průsečíky na jedné čáře se seřadí dle souřadnic x • dvojice těchto průsečíků definují úsečky ležící uvnitř oblasti

• základní metody: • paritní řádkové vyplňování • rozklad na trojúhelníky

7


Metoda řádkového vyplňování Pro každý řádek y: 1. vytvoř seznam průsečíků xi řádku y se všemi hraničními úsečkami ui 2. uspořádej seznam průsečíků podle souřadnic xi 3. vykresli vodorovné úseky mezi lichými a sudými průsečíky v seznamu 4. zruš seznam průsečíků y 1 2 3 B 4 5 6

C

F D

E

G

A 2

BC BC BC AB AB AB

4

6

8

Metoda řádkového vyplňování • nutnost předzpracování jednotlivých hraničních úseček • vynechání vodorovných hraničních úseček • systematické zkrácení všech hran (vede ke snížení počtu průsečíků, funkčnost zůstane zachována) y

y

6 5 4 B 3 2 1

– CD, EF – FG – CD, EF – FG – CD, (DE), EF – FG ? BC – FG – FG – (GA) - FG

C

9

Paritní řádkové vyplňování

F D

G 4

6

8

C

6 5 B’ 4 B 3 2 A’ 1

E

A 2

x


8


x

F D’

E’

G’

2

4

6

8


x 10

Inverzní vyplňování

• celkový postup:

• nevyžaduje řazení průsečíků

1) Pro všechny hraniční úsečky ověř: a) je-li vodorovná, vynech ji (případně vykresli) b) uprav orientaci shora dolů a zkrať ji o 1 ve směru y c) aktualizuj mezní souřadnice celé hranice ymax a ymin 2) Pro y od ymin do ymax proveď: a) nalezni průsečíky hran s řádkem y b) uspořádej všechny průsečíky podle souřadnice x c) vykresli úseky mezi lichými a sudými průsečíky 3) Vykresli hranici oblasti (je-li třeba)

• šablona • univerzální pomocná paměť (stencil buffer) • vhodná pro ukládání dočasných hodnot pro různé algoritmy • stala se běžnou součástí grafických akcelerátorů (rozměry mívá totožné s velikostí obrazovky)

• část paměti, ve které je prováděno vyplňování oblasti (inverováním/negací hodnot v šabloně)

• 1 pixel obrazové paměti = 1 bit v šabloně (vyplněno/nevyplněno)


11


13

2

Inverzní vyplňování

Inverzní vyplňování 1) Vyčisti šablonu

• každá hraniční úsečka je zpracována samostatně

(pro každou souřadnici y hraniční úsečky je vykreslena vodorovná čára vedoucí od bodu na úsečce s odpovídající souřadnicí x k bodu s maximální souřadnicí x celé hranice, příp. celé obrazovky)

2) Pro každou nevodorovnou hranu: a) zkrať hranu o jeden pixel zdola a rasterizuj hranu b) nalezni řádkovým rozkladem její pixely [x,y]

• po zpracování první úsečky je takto vyplněn lichoběžník (zleva omezený touto úsečkou a zprava svislou čárou o souřadnici x = xmax)

c) invertuj pixely ve vodorovném úseku [x,y] – [xmax,y]

• další hraniční úsečky způsobí smazání části tohoto lichoběžníku, případně jeho doplnění o nové vyplněné oblasti

14


Plotové vyplňování


15

Plotové vyplňování

• časově úspornější • plot – myšlená svislá čára, která může protínat i vnitřek oblasti • výsledkem je obecně nižší počet pixelů, které je třeba invertovat Pro všechny hrany dělej: Pro každou horizontální řádku, která protíná hranu v bodě [x1,y1]: • jestliže průsečík je vlevo od plotu, pak komplementuj vš. pixely, jejichž střed leží vpravo od [x1,y1] a vlevo od plotu • jinak komplementuj všechny pixely, jejichž středy leží vpravo od plotu a vlevo od [x1,y1]

16



17

Šrafování

Šrafování pomocí přerušovaných čar

• rozšířeno především v technických aplikacích • v praxi se uplatňuje šrafování pod určitým úhlem  (např. 45°)

• při šrafování přerušovanými čárami může dojít k nežádoucímu optickému jevu

(vodorovné šrafování + transformace otáčení)

• • • •

otočení všech hraničních úseček oblasti o úhel - aplikování algoritmu vodorovného šrafování vykreslení každého k-tého řádku před vykreslením vypočítané vodorovné úseky otočíme zpátky o úhel  a teprve pak zobrazíme • kreslení zahájené od levého okraje vodorovného úseku vytváří při pohledu z dálky siluetu (kopíruje levou hranici oblasti) • odstranění: úprava algoritmu (šrafování nezávislé na tvaru a umístění oblasti)


18


19

3

Vyplňování vzorem

Pinedův algoritmus • příklad vyplnění trojúhelníku definovaného pomocí 3 orientovaných přímek (průnik 3 polorovin) • hranová funkce: E(x,y) = (x – X).dY – (y – Y).dX • E(x,y)>0, pak (x,y) je vpravo • E(x,y)=0, pak (x,y) leží na hraně • E(x,y)<0, pak (x,y) je vlevo

• opakované šrafování téže oblasti pod různými úhly • vzor je umístěn nezávisle na poloze hranice • oblast je považována za výřez, kterým uživatel nahlíží na nekonečný vzor v pozadí

• někdy je žádoucí, aby se vzor pohyboval spolu s oblastí

20



21

B) Vyplňování hranice nakreslené v rastru

Pinedův algoritmus

• hranice není geometricky jasně určena

• příklady strategií procházení rovinnou oblastí

(všechny informace se získávají čtením z obrazové/rastrové paměti)

• metody jsou obecně nazývány semínkové vyplňování (seed fill) • semínko • vybraný vnitřní bod oblasti • od semínka se rozšiřuje prohledávání obrazové paměti a nalezeným vnitřním bodům se nastaví nová barva • směr prohledávání a vyplňování úzce souvisí s charakterem hranice a s tím, co považujeme za její vnitřek min/max

obrat na hranici

• rozlišujeme tyto vnitřní oblasti: • 4-spojitá (4-souvislá) oblast • 8-spojitá (8-souvislá) oblast

plot/paralelní vyhodnocení 22


Semínkové vyplňování

(většina systémů zpracovává 8-spojitou hranici a 4-spojitou oblast) 23


Semínkové vyplňování

• každému typu oblasti odpovídá jiný typ hranice

• při semínkovém vyplňování postupujeme od zadaného semínka a zkoumáme, zda jeho sousední body patří k vnitřku oblasti

• pro ohraničení 8-spojité oblasti musíme použít 4-spojitou hranici (problém vyplnění bodů i za touto hranicí)

• příslušnost je ovlivněna testovanou vlastností • 2 základní varianty: • hraniční vyplňování

(testovaný bod je vnitřní, má-li jinou barvu, než je zadaná barva hranice)

• záplavové vyplňování (lavinové) a) 4-spojitá oblast ohraničená 8-spojitou hranicí © J. Dannhoferová, Počítačová grafika

(testovaný bod je vnitřní, má-li stejnou barvu jako zadané semínko – tzv. přebarvování)

b) 8-spojitá oblast ohraničená 4-spojitou hranicí 24


25

4

Semínkové hraniční vyplňování

Semínkové záplavové vyplňování

• vyplnění až k hranici dané barvy


• přebarvení pixelů dané barvy

26


27


4-souvislá oblast



8-souvislá oblast

28

Řádkové semínkové vyplňování


29

Řádkové semínkové vyplňování

• metoda, která snižuje počet přístupů do obrazové paměti • používá zásobník, ve kterém jsou uchovány souřadnice jen několika vnitřních bodů vyplňované oblasti 1) Vlož uživatelem zadané semínko do zásobníku 2) Dokud není zásobník prázdný: a) vyjmi semínko o souřadnicích [x,y] ze zásobníku b) nalezni hranici xL a xR na řádku y v nejbližším okolí bodu [x,y] c) nakresli úsečku [xL,y] – [xR,y] d) na (vyšší) úsečce [xL,y + 1] – [xR,y + 1] hledej souvislé vnitřní úseky a pro každý z nich vlož do zásobníku souřadnice jednoho vnitřního bodu e) na (nižší) úsečce [xL,y – 1] – [xR,y – 1] hledej souvislé vnitřní úseky a pro každý z nich vlož do zásobníku souřadnice jednoho vnitřního bodu 30



31

5

Ořezávání 2D objektů • ořezávací algoritmy jsou specializovány na: • test polohy bodu • ořezání úsečky • ořezání oblasti – speciální postupy • osově orientované okno umožňuje použít jednoduché testy porovnáváním příslušné souřadnice s hraniční hodnotou • u obecně orientované hranice je vhodné použít rovnici hraniční přímky: F(x,y) = a * x + b * y + c = 0 a testovat pozici bodu P=[xp,yp] pomocí testu F(xp,yp) > 0 (leží uvnitř) F(xp,yp) = 0 (leží na hranici) F(xp,yp) < 0 (leží mimo)

Ořezávání v rovině Jana Dannhoferová

([email protected])

Ústav informatiky, PEF MZLU © J. Dannhoferová, Počítačová grafika

33

Ořezávání polygonů

Cohen-Sutherland • metoda ořezávání úsečky obdélníkovým oknem • algoritmus označuje krajní body úseček pomocí hraničních kódů • 3 možné polohy úsečky vůči oknu:

• zahrnuje v sobě úlohu ořezání úseček podle hranice

(chceme-li pouze obrys n-úhelníku, pak stačí ořezávat hrany samostatně jako úsečky)

• kód(P)  kód(Q) =  - celá úsečka leží uvnitř • kód(P)  kód(Q)   - celá úsečka leží mimo okno • kód(P)  kód(Q) =  - úsečku je třeba oříznout

• pro ořezání polygonů podle okna se používají: • Cohen-Sutherland

(ořezání každé hrany polygonu podle celého okna)

• Sutherland-Hodgman

(postupně ořezává polygon podle jednotlivých hranic)


34


35

Literatura

Sutherland-Hodgman • používá se pro ořezání vyplněných polygonů

• Beneš, B., Felkel, P., Sochor, J., Žára, J. Moderní počítačová grafika. Computer Press: Brno, 2004.

• ořezává postupně podle každé hrany pravoúhlého okna • pro zjednodušení se ořezává pořád podle stejné hrany a polygon se po každém ořezu otočí o 90°

• Beneš, B., Sochor, J., Žára, J. Algoritmy počítačové grafiky. ČVUT: Praha, 1996. • Sochor, J.: Základy počítačové grafiky. FI MU: Brno, 2001.


36


37

6

Vyplňování souvislé oblasti

Recommend Documents