Vydělávej až 160.000 Kč měsíčně! Akreditované rekvalifikační kurzy s garancí práce od 0 Kč. Více informací.
Hledáme nové posily do ITnetwork týmu. Podívej se na volné pozice a přidej se do nejagilnější firmy na trhu - Více informací.

Lekce 2 - Plechovka aneb Flood fill či seed seed

V minulé lekci, Rasterizace úsečky, jsme si ukázali základní algoritmy pro vykreslování úseček. Probereme si algoritmy DDA, Error control DDA a Bresenhamův algoritmus.

Jak to udělat, aby se barva rozlila od zadaného bodu na obrazovce (nebo obecně v nějakém čtverečkovém rastru) do všech stran a souvisle vyplnila celou libovolně složitou oblast stejné barvy jako měl zadaný bod? Ukážeme si ten asi nejjednodušší způsob, který je sice pomalý a náročný na paměť, ale spolehlivě funguje. Ještě jednodušší by sice bylo použití rekurze, ale ta funguje jen na velmi malé plochy kvůli malé kapacitě systémového zásobníku, proto ji tu uvádět nebudu. Budeme potřebovat nějaký hodně velký zásobník, do kterého budeme ukládat souřadnice pixelů, které chceme vybarvit. Nejvhodnější konstrukce je pro tento případ asi pole:

array[0..co nejvíc] of record x,y:integer; {nebo jiný typ podle potřeby} end;

Pak si deklarujeme ukazatel na něj a vytvoříme ho jako dynamickou proměnnou (New), aby nám nezabírala místo v data segmentu.

Když zásobník, tak potřebujeme ještě procedury pro vkládání a vyjímání dat:

procedure Push(x,y:integer);
procedure Pop(var x,y:integer);

První uloží danou dvojici souřadnic na vrchol zásobníku, druhá vyjme souřadnice z vrcholu zásobníku a předá nám je přes parametry. Do procedury Push je potřeba zabudovat kontrolu přetečení: když je zásobník plný, aby už se do něj nepokoušela nacpat nic dalšího, nebo ještě lépe, aby vytvořila další zásobník a uložila to do něj (jestli chcete tímto způsobem vyplnit celou obrazovku 640x480, nic jiného vám nezbyde). Procedura Pop pak nesmí způsobit problémy, pokud se snažíme tahat data z prázdného zásobníku. V takovém případě by měla vrátit nějakou bezpečnou hodnotu (třeba původní zadané výchozí souřadnice) nebo ještě lépe zrušit aktuální prázdný zásobník a pokud existuje nějaký před ním, načíst data z něj. Ale to už nechám na vás.

Máme tedy fungující zásobník, jdeme na vlastní vyplňování:

  • Někam si uložíme barvu výchozího bodu (dejme tomu do proměnné "Výchozí barva").
  • Pokud je tato barva rovna barvě, jakou chceme oblast vybarvit, končíme, protože už je hotovo (pokud bychom začali vybarvovat, skončilo by to nekonečnou smyčkou).
  • Uložíme na zásobník (Push) souřadnice výchozího bodu.

Cyklus:

  • Vyjmeme ze zásobníku jedny souřadnice (Pop).
  • Vybarvíme bod na těchto souřadnicích zvolenou barvou.
  • Podíváme se na body vlevo, vpravo, nahoře a dole od tohoto bodu. Pokud se nacházejí uvnitř rastru (tedy např. neleží mimo obrazovku) a mají barvu rovnou Výchozí barvě (jsou ještě uvnitř zadané souvislé jednobarevné oblasti => mají se vybarvit), uložíme jejich souřadnice na zásobník (Push). Nic jiného s nimi neděláme.
  • To celé opakujeme tak dlouho, dokud není zásobník úplně prázdný.

Na začátku jsme tedy uložili jedny souřadnice. Pak jsme je v prvním průchodu cyklem načetli (zásobník byl tedy na chvíli prázdný), ale hned jsme uložili souřadnice čtyř (možná méně, to je jedno) políček okolo něj. V příštím cyklu jsme přečetli souřadnice jednoho z těchto uložených políček a zase jsme uložili políčka okolo. Tady vidíte, jak rychle se zásobník plní. Plnit se přestane, až dosáhneme hranic oblasti. To se moc políček z okolí vybarvených pixelů neuloží, protože z jedné strany je hranice (barva <> Výchozí barva) a z druhé vybarvená oblast (taky barva <> Výchozí barva). Tak zásobník postupně splaskává a na konci, kdy jsme vyjmuli poslední souřadnice a nevložili jsme žádné, je prázdný, cyklus končí a oblast je v tu chvíli kompletně vyplněna.

Určitě vás praštilo do očí, jak je tenhle algoritmus neefektivní: do zásobníku se dostává spousta duplicitních políček, které pak většinu času jenom kontrolujeme a vyhazujeme. Spotřeba paměti je taky větší, než bychom rádi. V dalším článku si plechovku optimalizujeme.

V další lekci, Mandelbrotova množina, si ukážeme algoritmus pro vykreslení nejznámějšího fraktálu Mandelbrotovy množiny včetně popisu, aplikace a zdrojových kódů.


 

Předchozí článek
Rasterizace úsečky
Všechny články v sekci
Grafické algoritmy
Přeskočit článek
(nedoporučujeme)
Mandelbrotova množina
Článek pro vás napsal Mircosoft
Avatar
Uživatelské hodnocení:
8 hlasů
Autor je amatérský pascalista, assemblerista a bastlíř. Profesionálně psal nebo píše v HLASM, Rexxu, Cobolu, ST, LAD, FBD, PHP, SQL, JS, Basicu a pár dalších jazycích, které kupodivu stále existují a používají se :-).
Aktivity