mapa stránky tlačiť stránku slovensky | english

• Úvodná stránka
• Testy
• Java applety
• CG na webe
• O autoroch
• Kontakt

Oblasti

Vypĺňanie oblasti

    Oblasťou rozumieme množinu rastrových bodov, ktoré sú vzájomne súvislo pospájané. Zadefinujme si pojem susednosti pre bod. Každému rastrovému bod P prislúcha v rastrovom obraze osem susedných, označme ich 0,...,7. Susedov 0, 2, 4 a 6 nazývame priamymi susedmi bodu P, pretože nimi reprezentované obdĺžniky majú s ním spoločnú hranu. Susedov 1, 3, 5 a 7 nazývame nepriamymi susedmi bodu P. Oblasti poznáme 4-súvislé a 8-súvislé. Pri 4-súvislej oblasti (resp. 8-súvislej) môžeme každé dva body spojiť postupnosťou 4-susedných (resp. 8-susedných) bodov z tejto oblasti. Oblasť zadaná svojimi vnútornými bodmi sa nazýva vnútorné definovaná. Oblasť zadaná hranicou sa nazýva hranične definovaná.

$$$APPLET

Applet 4 a 8 susednosť bodu P

$$$APPLET

Applet 4-connectivity 8-connectivity. Select first point with mouse. You can change raster size on left side. Author Michal Švirec

Source code

Jednoduché rekurzívne algoritmy vypĺňania oblasti.

Vlnový algoritmus

    Tento algoritmus rekurzívne priradí bodom 4 - súvislej oblasti novú farbu, ak daný bod spĺňa podmienku, že je vo vnútri vyplňovanej oblasti.

$$$APPLET

Applet Vypĺňanie oblasti. Zadaj začiatočný bod.

// Algoritmus vlnového vypĺňania: void Vypln (int x,int y,Color stara_farba,Color nova_farba) { if (read_pixel (x,y) == stara_farba) // test farby pixlu  { write_pixel (x, y, nova_farba); // zafarbí pixel novou farbou Vypln (x, y-1, stara_farba, nova_farba); // rekurzivne vola sam seba Vypln (x, y+1, stara_farba, nova_farba); Vypln (x-1, y, stara_farba, nova_farba); Vypln (x+1, y, stara_farba, nova_farba); } }

FloodFill algorithm

$$$APPLET

Applet FloodFill algorithm Author: Bezak Martin

Algorithm source:
public void flood(int x, int y){ if(obr[x][y] == 0 ){ obr[x][y] = 2; flood(x+1,y); flood(x,y+1); flood(x-1,y); flood(x,y-1); } }

Source code

FloodFill algorithm applet 2

$$$APPLET

Applet FloodFill algorithm Author: Peter Kan

Algorithm source:
public void flood(int x, int y){ if(obr[x][y] == 0 ){ obr[x][y] = 2; flood(x+1,y); flood(x,y+1); flood(x-1,y); flood(x,y-1); } }

Boundary Fill Algorithm:

• Choosing a specific interior point [x,y]- which will be a start point for filling.
• I will use a 4-connected approach to visualize the functionality of the algorithm.

$$$APPLET

Applet algorithm is designed as real boundary fill alg., but for visibility, it is drawing not only single pixels, but 10x10px squares. By clicking on the canvas, you specify starting point where algorithm is started... That�s why white spaces are creating near borders of other colors...

Author Martin Pullmann

Source code

Vypĺňanie podľa parity

    Jedným zo základných postupov počítačovej grafiky je určenie vnútorného bodu mnohouholníka. Bod je vnútorný ak polpriamka rovnobežná s osou x vychádzajúca z tohto bodu pretne mnohouholník nepárnym počtom prienikov (priesečníkov) hrán. Toto môžeme pretransformovať aj na využitie pre vypĺňanie mnohouholníka. Popis je v [1].

Zmenšenie hĺbky rekurzie

    Jednou z nevýhod predchádzajúcich algoritmov je skutočnosť, že algoritmus je rekurzívny, čo nie je vždy vhodné. Preto vzniklo niekoľko efektívnych algoritmov, ktoré zmenšujú hĺbku rekurzie. Jedným z príkladov je algoritmus vypĺňania oblasti po riadkoch.

Rastrový rozklad mnohouholníka

    Rastrovým rozkladom mnohouholníka rozumieme vyplnenie oblasti, ktorej hranicu tvorí mnohouholník. Najčastejšie postupujeme tak, že urobíme rozklad mnohouholníka do riadkov, a potom použijeme riadkový skanovací algoritmus.

Riadkový rozklad (skanovací algoritmus)

    Každým riadkom rastra vedieme skanovaciu priamku, pričom testujeme jej prienik s hranicou mnohouholníka (tj. jednotlivými hranami). Priesečníky potom zoradíme podľa osi x. Dvojica priesečníkov dáva úsečku, ktorá leží vo vnútri mnohouholníka. Tú potom nakreslíme príslušnou farbou.

    Pri takomto usporiadaný nám môže vzniknúť problém s hraničnými bodmi mnohouholníka, ktorých obidva susedné body sú buď nad alebo pod skanovaciou priamkou. Tieto body musíme započítavať do množiny priesečníkov dvakrát.

    Pri teste prieniku so skanovaciou priamkou je dobré mať všetky hrany mnohouholníka v  dátovej štruktúre, aby sme nemuseli testovať prienik zo všetkými hranami mnohouholníka. Neskôr si takúto tabuľku vytvoríme a nazveme ju tabuľka aktívnych hrán (TAH). Pri jej vytváraní môžeme využiť to, že ak priamka v i-tom riadku pretína danú hranu, tak ju obvykle pretína aj v i+1 riadku. 

Dátová štruktúra na reprezentáciu hrán 

    Najprv si zoradíme všetky hrany (hrana je vlastne úsečka s dvoma bodmi) podľa hornej súradnice y (väčšia y hodnota z tých dvoch bodov). Hrany orientujeme vždy podľa hornej súradnice y, pričom hrana je orientovaná zhora nadol. Môžeme použiť hašovaciu tabuľku napr. pomocou usporiadaných zoznamov. Takúto dátovú štruktúru nazývame tabuľkou hrán (TH). Pre každý skanovací riadok si vytvoríme zoznam tých hrán, ktoré majú minimálnu súradnicu y práve v tomto riadku. Pre každú hranu uložíme do TH:

1. maximálnu y-súradnicu hrany
2. x-súradnicu, pre bod s minimálnou y-súradnicou hrany
3. prevrátenú hodnotu smernice (1/m).
$$$APPLET

Applet Tabuľky hrán (napravo zoznam hrán, ktore pretina skanovací riadok)

    V tabuľke hrán máme zadefinované všetky potrebné informácie o hrane. Podľa riadku, v ktorom skanujeme vieme y-súradnicu horného (začiatočného) bodu orientovanej hrany, prvá položka je y-súradnica koncového bodu hrany, druhá položka je aktuálna súradnica x priesečníka hrany s skanovacou priamkou, tretia vyjadruje prírastok x pri prechode na ďalší skanovací riadok.

Ďalšou dátovou štruktúrou je tabuľka aktívnych hrán (TAH), do ktorej ukladáme len tie hrany, ktoré pri spracovávaní skanovacia priamka práve pretína. Hrany v tabuľke udržujeme usporiadané podľa x-súradnice, preto pri zmene hrán v tabuľke ich utriedime napr. bublinkovým triedením.

Scan_Line algoritmus [1]:

1. Vytvoríme usporiadanú tabuľku  všetkých hrán mnohouholníka (TH).
2. Vytvoríme prázdnu tabuľku aktívnych hrán TAH.
3. Nastav y na prvú súradnicu y v TH.
4. Rob pokiaľ TH a TAH nebudú prázdne
   1. Pre danú hodnotu y pridáme do TAH zodpovedajúce hrany z TH usporiadané podľa x-súradníc.
   2. Zoberieme z tabuľky TAH súradnice x dvoch za sebou nasledujúcich v zozname a medzi nimi vypĺňame úseky odpovedajúcich bodov pre dané x.
   3. Z TAH vylúčime hrany. pre ktoré nastane rovnosť y = ymax.
   4. Pre všetky hodnoty x, y tabuľky TAH musíme vypočítať nové hodnoty x, tj. nové x = x + 1/m.
   5. Usporiadame TAH podľa x, pretože v predchádzajúcom bode došlo k zmene x hodnôt súradníc nachádzajúcich sa v tabuľke TAH.
   6. Usporiadame TAH podľa x, pretože v predchádzajúcom bode došlo k zmene x hodnôt súradníc nachádzajúcich sa v tabuľke TAH.
   7. y = y +1

$$$APPLET

Applet Scan-Line algoritmus mnohouholníka, vyber riadok na scan-line vpravo od zvislej úsečky

Fill polygon

$$$APPLET

Fill pogygon. Set points for polygon. You can set color for each new point. After finish press button "vykresli". You get colored polygon created with scan-line alghoritm. Press "zmaz" button for clear scene. Author Dzurec Jan

Source code

Scan line polygon clipping

$$$APPLET

Applet Scan line polygon clipping. Set polygon type from 3 to 6 points, then you can move these points. Press mouse on right side of vertical line for points from scan-line alghoritm. Author Ľuboš Ľahký

Source code