6 Algoritmy ořezávání a testování polohy

6 Algoritmy ořezávání a testování polohy Studijní cíl Tento blok je věnován problematice vzájemné polohy grafických primitiv, zejména poloze bodu vzhledem k mnohoúhelníku včetně jednotlivých specifických variant jako jsou čtyřúhelník, jehož strany jsou rovnoběžné s osami souřadnicového systému, konvexní mnohoúhelní a i varianta obecného mnohoúhelníku. Dále jsou vysvětleny případy, kdy je nutno ořezat úsečku pravoúhlou oblastí, případně konvexním nebo i obecným mnohoúhelníkem. Rovněž je ukázáno řešení situace, kdy je třeba ořezat mnohoúhelník oblastí, která je rovněž ve tvaru čtyřúhelníku nebo obecného mnohoúhelníku. Zároveň jsou vysvětleny důvody k potřebě použití těchto ořezových algoritmů.

Doba nutná k nastudování

3-4 hodiny

Průvodce studiem Při studiu tohoto bloku se předpokládá, že student je seznámen se základy analytické geometrie, zná základní vztahy pro práci s vektory a vektorovými operacemi. Rovněž je nutné, aby student ovládal základní operace booleovské matematiky.

6.1 Ořezávání a ořezávací oblast Při potřebě zobrazení jakéhokoliv objektu na zobrazovací plochu jsou zasílány požadavky na zobrazení prostřednictvím jednotlivých grafických příkazů grafickému procesoru, který vytváří jejich obraz v grafické paměti a následně jsou obsah grafické paměti přenesen na výstupní zařízení. V rámci celého procesu zobrazení jsou ty části obrazu, které přesahují skutečnou zobrazovací oblast daného zařízení odstraněny (oříznuty). Nemá totiž žádný smysl pokoušet se zobrazit části obrazu, které nemohou být díky např. velikosti zobrazovací plochy daného výstupního zařízení fyzicky zobrazeny. Tyto algoritmy jsou použity i v případě, že ořezávací oblast není limitována zobrazovací plochou fyzického zařízení, ale omezující je plocha okna aplikace, do níž výstup směřuje. Přestože dnes dokáže prakticky každé zařízení oříznout na úrovni HW KST/IPOGR Počítačová grafika

1-1

Petr Veselý KST FEI Univerzita Pardubice

nepotřebné části obrazu, aniž by došlo byť k marnému pokusu o vykreslení, dochází k případné úpravě obrazu již během jeho zpracování na úrovni grafických kreslících funkcí, případně při zpracování grafickým procesorem nebo na úrovni ovladače. Snaha o včasné použití ořezávacích algoritmů je motivována především úsporou času, neboť každé následné zpracování zbytečných údajů je naprosto zbytečné (např. rasterizace celé úsečky, pokud její velká část leží mimo zobrazovací oblast). Obvykle je viditelnou (ořezávací) oblastí osově orientovaný pravoúhelník (většinou okno souřadnicového systému zařízení). Motivací pro vlastní implementaci a použití ořezávacích algoritmů může být:  zrychlení grafického výstupu (v případě, že velké množství objektů leží mimo viditelnou oblast a zjištění této skutečnosti je rychlejší než samotné kreslení),  vykreslení obrazu pouze do určité části grafického výstupního zařízení (vykreslení více obrazů do různých částí jednoho okna),  náhrada ořezávání na úrovni grafického výstupního zařízení. Ořezávací algoritmy (clipping) je možno rozdělit na kategorie:  ořezání bodu (test polohy bodu) pro určení, zda se daný bod zobrazí nebo ne,  ořezání liniových objektů určenou oblastí,  ořezání oblasti určenou oblastí.

6.2 Testování polohy bodu 6.2.1 Poloha bodu vzhledem k pravoúhelníku se stranami rovnoběžnými s osami souřadnicového systému Tato varianta je nejběžnější vzhledem k tomu, že ořezání (test polohy) je nejčastěji používán např. vzhledem k na oblast okna, obrazovky nebo vzhledem k potisknutelné části listu papíru v tiskárně. V tomto specifickém a na výpočet velmi nenáročném případě ořezávání osově orientovaným pravoúhelníkem stačí vyhodnotit souřadnice vykreslovaného KST/IPOGR Počítačová grafika

1-2


bodu [x,y] vzhledem k hranicím pravoúhelníku. Podmínka pro určení, že bod leží v ořezávané oblasti je následující:  (x>xMin)  (x<xMax)  (y>yMin)  (y
Y

M

AX y Y

MIN

x

X

X

M

6.2.2 Test polohy bodu vzhledem ke konvexnímu mnohoúhelníku IN MA V tomto případě je nutno určit polohu bodu vůči všem hraničním úsečkám. Polohu bodu P a úsečky AB lze určit pomocí velikosti X vektorového součinu

  u ( AB ) a v (AP )

i   u  v  uX vX

j

j

k

uY uZ  bX  aX

bY  aY

0

pX  aX

pY  aY

0

vY

k vZ

i

Vzhledem k tomu, že oba vektory leží v jedné rovině, je pro další postup rozhodující pouze znaménko z-ové souřadnice výsledného vektoru. S=(bx-ax)(py-ay)-(by-ay)(px-ax) Dle znaménka je možno určit polohu bodu P vzhledem k úsečce AB následovně:  pokud S<0, potom bod P leží napravo od úsečky AB  pokud S=0, potom bod P leží na úsečce AB  pokud S>0, potom bod leží nalevo od úsečky AB Pravidlo pro určení celkové polohy bodu P k danému mnohoúhelníku KST/IPOGR Počítačová grafika

1-3


Pokud je mnohoúhelník definován posloupností vrcholových uzlů:  proti směru hodinových ručiček, potom vyšetřovaný bod A leží uvnitř právě tehdy, pokud leží vlevo od všech úseček.  po směru hodinových ručiček, potom vyšetřovaný bod leží uvnitř právě tehdy, pokud leží vpravo od všech úseček. 6.2.3 Test polohy bodu vzhledem k obecnému mnohoúhelníku Pro nekonvexní mnohoúhelník je třeba vyhodnotit počet průsečíků polopřímky vedené z vyšetřovaného bodu P libovolným směrem s hranami mnohoúhelníku.

Pravidlo pro určení polohy  Sudý počet průsečíků znamená, že bod leží vně  Lichý počet průsečíků znamená, že bod leží uvnitř Problémy nastanou, pokud paprsek prochází vrcholem nebo pokud část paprsku je totožná s některou hranou. V tomto případě je řešením stejný postup, jako u algoritmu řádkového vyplňování vektorově zadané oblasti, tj. použití vodorovného paprsku, vynechání vodorovných hran a rozpojení hran pomocí jejich zkrácení.

6.3 Ořezání úsečky Ořezání úsečky je velmi často používanou operací, proto algoritmy pro její provedení musí být maximálně efektivní a spolehlivé. Existuje mnoho různých algoritmů, které se liší jak možnostmi použití, tak i rychlostí. Obecně lze říci, že obecné metody, umožňující ořezání úsečky libovolným mnohoúhelníkem jsou pomalejší, než metody, které jsou použitelné pouze ve specifických případech (ořez pravoúhelníkem stranově rovnoběžným s osami SS nebo ořez konvexním mnohoúhelníkem). KST/IPOGR Počítačová grafika

1-4


Existují rovněž specifické metody pro ořez jiných liniových objektů než je úsečka a metody umožňující ořez jinou oblastí než je mnohoúhelník (např. kružnice), ovšem tyto metody lze vždy (téměř vždy) po příslušné aproximaci objektů naradit ořezávací metodou pro ořezávání úsečky (úseček) mnohoúhelníkem. 6.3.1 Metoda Cohen-Sutherland Metoda je použitelná pro ořezání úsečky pravoúhlou oblastí, jejíž strany jsou rovnoběžné s osami SS. Je založena na rozdělení celé plochy USS na jednotlivé oblasti. Těmto oblastem je přiřazen 4-bitový kód podle polohy vzhledem k poloze ořezávací oblasti (vlevo, vpravo, dole, nahoře) 1001

0001

0101

1000

0000

0100

1010

0010

0110

Obrázek 1: Rozdělení plochy na sektory

Pro každý počáteční (Z) a koncový (K) bod úsečky se určí kód. Následující podmínky rozhodnou o poloze úsečky vzhledem k pravoúhelníku a o následném postupu:  Pokud kód(Z)  kód(K) = 0, potom úsečka je celá uvnitř.  Pokud kód(Z)  kód(K)  0, potom úsečka je celá mimo a je možno ji celou za dalšího zpracování (např. zobrazení) vynechat  Pokud kód(Z)  kód(K) = 0, potom je zřejmé, že nastala situace, kdy úsečka prochází více oblastmi. V tomto případě je třeba ji oříznout (ořezávání se provádí dle libovolné jedničky v kódech pro Z a K) a testy s novými kódy je nutno zopakovat. KST/IPOGR Počítačová grafika

1-5


Jednotlivé situace jsou znázorněny na následujícím obrázku.

Obrázek 2: Ilustrace variant, které mohou nastat u algoritmu CS

6.3.2 Metoda Cyrus-Beck Tato metoda je zobecněním metody Liang-Barsky a je určená k ořezání úsečky libovolným konvexním mnohoúhelníkem. Je založena na parametrickém vyjádření úsečky. Počet ořezů, které je třeba vykonat, závisí na zvoleném pořadí řezecích hran.

KST/IPOGR Počítačová grafika

1-6


Na uvedeném obrázku je vyznačena ořezávaná úsečka AB, ořezávací oblast je definována jako mnohoúhelník pomocí bodů V1, V2, V3, V4 a V5. Úsečka po ořezání je určena body A1B3. Červenou barvou jsou naznačeny normálové vektory jednotlivých řezacích hran. Předpoklady a základní pravidla:  Ořezávací oblast je zadána pomocí orientovaných hran, orientace je proti směru hod. ruč.  Ořezávaná úsečka je orientována A→B  Parametrické vyjádření P(t)=A + t (B-A)

 

 Pro navzájem kolmé vektory platí: u . v  0  Normálový vektor (otočení v o 90° vpravo) se vytvoří na základě směrového vektoru záměnou souřadnic a jednou změnou znaménka:

   n  v , n  (vy,vx)  

 Tupý úhel: u . v  0

 

 Ostrý úhel: u . v  0 Na následujícím obrázku je znázorněn základní postup pro jednu hranu:


1-7


Hledáme bod C, který tvoří průsečík hrany V1V2 a AB. Hledaný bod C definujeme pomocí parametru tc z parametrické rovnice: 

C  P(tc)  A  tc( B  A)

Dále musí platit, že vektor V1C musí být kolmý na normálový vektor n1.

 n1.(V 1C )  0  n1.( P(tc)  V 1)  0  n1.( A  tc( B  A)  V 1)  0  n1.( A  V 1) n1x( Ax  V 1x )  n1 y ( Ay  V 1 y ) tc     n1.( B  A) n1x ( Bx  Ax )  n1 y ( By  Ay ) V algoritmu je nutno rolišovat případy, kdy úsečka AB směřuje dovnitř oblasti a situace, kdy směřuje ven. To lze zjistit na základě hodnoty součinu vektorů n1 a směrového vektoru úsečky AB:  směřuje dovnitř  směřuje ven:  je rovnoběžná s hranou:

 n1.( B  A)  0  n1.( B  A)  0  n1.( B  A)  0

Algoritmus výpočtu  inicializace parametrů začátku a konce úsečky: tZ=0, tK=1  pro každou hranu n-úhelníku:  určení normálového vektoru n  pokud skalární součin n.(B - A)<>0  výpočet tC  dle směru dovnitř/ven případná změna  tZ = max(tZ, tC) nebo  tK = min(tK, tC) KST/IPOGR Počítačová grafika

1-8


 jinak – úsečka je rovnoběžná s touto hranou  pokud leží v polorovině mimo n-úhelník: lze ořezávanou úsečku zcela vypustit  KONEC  jinak nemá tato hrana na ořezání vliv  POKRAČ. DALŠÍ HRANOU  pokud tZ < tK, potom se kreslí ořezaná úsečka P(tZ)P(tK), jinak po ořezu z úsečky nic nezbylo

Pojmy k zapamatování Rasterizace, rasterizační algoritmus, iterační způsob výpočtu, predikce, celočíselný algoritmus

Otázky na procvičení 1. Jaký je důvod k vyžívání ořezávacích algoritmů? 2. Co je to ořezávací oblast? 3. Jak se zjišťuje poloha bodu vzhledem k jednotlivým typům oblastí? 4. Jak fungují jednotlivé uvedené algoritmy pro ořez úsečky? 5. Jaký je systém pro vytváření kódů jednotlivých segmentů ořezávací oblasti u algoritmu Cohen-Shuterland? 6. Z jakého vyjádření úsečky vychází algoritmus Cyrus-Beck? 7. Jaké jsou výhody algoritmu Liang-Barsky oproti algoritmu CohenShuterland?

Odkazy a další studijní prameny  

Žára, J., Beneš, B., Felkel, P. Moderní počítačová grafika. Computer Press, Brno, 1998. ISBN 80-7226-049-9. Foley, Van D. Computer Graphics. Principles and Practice. Addison-Wesley,1991.


1-9


6 Algoritmy ořezávání a testování polohy

Recommend Documents