Geometrie/Ořezávání

Rovinné ořezávání

Ořezávací (clipping) algoritmy umožňují vybrat z kresby pouze ty části, které jsou viditelné v určité oblasti. Ačkoli existují obecné algoritmy, které pracují nad nekonvexním mnohoúhelníkem, bývá ořezávací oblast nejčastěji definována jako obdélník (typickým příkladem je ořezání objektu oknem obrazovky), toto v dalším textu předpokládejme.

V případě rovinného ořezávání bývá ořezávaným objektem polygon, úsečka. Výsledkem ořezání jsou opět tyto objekty. Pokud ořezáváme uzavřené polygony (oblasti), je žádoucí, aby i po ořezání byly uzavřené, tj. "je možno je i po ořezání vyplnit". Z tohoto důvodu je v některých případech potřeba zajistit přidání nových hran (viz níže popis algoritmu Sutherland-Hodgman).

Popis

Ořezávání úsečky

Algoritmů na ořezávání úseček obdélníkovým oknem je několik -- Cohen-Sutherland, Cyrus-Back, Liang-Barsky. Popišme si první z nich, který je také použit v naší implementaci.

Algoritmus Cohen-Sutherland

Základem algoritmu ořezávání úsečky Cohen-Sutherland je pojem ohodnocení bodu hraničními kódy (dále ohodnocení bodu ). Každý z bodů úsečky získá své ohodnocení v závislosti jeho polohy vůči ořezávacímu oknu. Ohodnocení bodu je možné reprezentovat různě (bitové pole, objektem obsahující vlastnosti jako boolean hodnoty,...), podstatné je to, aby bylo pro každý bod určeno, zda se nachází vlevo, vpravo, dole či nahoře od ořezávacího okna. Nechť je dále ohodnocení definováno jako čtveřice 0/1,0/1,0/1,0/1 (LEVO, PRAVO, DOLE, NAHORE -- kde 0 není splněno a 1 je splněno), tj. například 0101 označuje polohu bodu vpravo nahoře od ořezávacího okna.

Ohodnocení bodu hraničními kódy

Ořezávací algoritmus postupně zkoumá tři polohy úsečky vůči ořezávacímu oknu. Polohu úsečky zjistíme porovnáním ohodnocení hraničních bodů úsečky. Označíme-li si hraniční body jako A a B a jejich ohodnocení Val(A) a Val(B), mohou nastat následující případy (pozn: operace průnik a sjednocení probíhají po jednotlivých bitech ohodnocení):

Polohy úseček vůči ořezávacímu oknu

1. $Val(A)\cup Val(B)=\mathrm{\varnothing }$ -- tj. úsečka je celá v ořezávacím okně a není potřeba ji proto ořezávat. Tj. pro obě ohodnocení bodů platí, že jsou 0000 (oba body jsou "v ořezávacím okně").
2. $Val(A)\cap Val(B)\ne \mathrm{\varnothing }$ -- tj. úsečka je celá mimo ořezávací okno a není potřeba ji proto ořezávat. Tento test ovšem některé případy úseček procházejících vnějšími oblastmi neodhalí.
3. $Val(A)\cap Val(B)=\mathrm{\varnothing }$ -- tj. úsečka buď prochází ořezávacím oknem anebo jde o "neodhalený" případ úsečky mimo okno. Úsečka prochází několika oblastmi a je nutné ji ořezat. Provedeme to tak, že zvolíme bod úsečky, který neleží uvnitř (tj. jeho hraniční kód není 0000) a podle nastavené jedničky vybereme hranici, podle které ho úsečku zkrátíme (přesněji algoritmizace níže).

Ořezávání polygonu

Ořezat polygon by bylo možné i pomocí postupného aplikování výše uvedeného algorimu Cohen-Sutherland. Problém však nastává při požadavku zachování uzavřenosti, tj. nesmí dojít k rozpadu hran. Po ořezání musí být případně polygon doplněn o další úsečky (viz. obrázek). Je tedy zřejmé, že algoritmy pro ořezání úsečky se pro ořezávání polygonu příliš nehodí.

Algoritmus Sutherland-Hodgman

Velice jednoduchý postup pro ořezávání polygonu zvolili Sutherland a Hogman. Jejich algoritmus postupně ořezává daný polygon jednotlivými hranicemi okna, při čemž v případě potřeby je k ořezanému polygonu přidána hrana. Jestliže máme rovinou oblast ohraničenou polygonem, pak provedeme nejdřív ořezání podle levé strany okna. Výsledkem bude nový polygon. Tento polygon použijeme pro ořezání pravou stranou okna. Obdobně budeme pokračovat pro horní a dolní stranu okna.

Polygon si zorientujeme, na vstupu do algoritmu máme posloupnost vrcholů tohoto orientovaného polygonu a na výstupu na začátku prázdnou posloupnost. V i-tém kroku vezmeme vždy vrcholy $U_i$ a $U_{i+1}$ ze vstupní posloupnosti a do výstupní posloupnosti zapíšeme vrcholy podle následujících pravidel:

1. Oba vrcholy této úsečky leží vně vůči dané hranici okna. Pak do výstupní posloupnosti nezapíšeme žádný bod.
2. Počáteční vrchol $U_i$ leží vně okna a koncový vrchol $.U_{i+1}$ leží uvnitř okna, pak spočítáme průsečík $B$ strany polygonu s hranicí okna a do výsledné posloupnosti zařadíme tento vypočítaný průsečík.
3. Oba vrcholy leží uvnitř okna vzhledem k dané hranici okna, pak do výstupní posloupnosti zapíšeme počáteční bod $U_i$.
4. Počáteční vrchol $U_i$ leží uvnitř okna a koncový vrchol $U_{i+1}$ leží vně okna, pak spočítáme průsečík $B$ strany polygonu s hranicí okna a do výstupní posloupnosti přidáme počáteční vrchol $U_i$ a bod průsečíku $B$.

Tento algoritmus použijeme postupně pro všechny strany ořezávacího okna, přičemž na vstupu pro první stranu okna je ořezávaný polygon a pro každou další stranu okna je již polygon oříznutý v předchozím kroku.

Algoritmizace

Ořezávání úsečky, algoritmus Cohen-Sutherland

VSTUP

úsečka, ořezávací okno

VÝSTUP

ořezaná úsečka

Nechť je úsečka určena dvěma body "A" a "B". aktualniBod = "A"

1. Urči hraniční kódy bodů vůči ořezávacímu oknu.
2. Pokud nastal jeden z následujících případů, algoritmus ukonči (body "A" a "B" jsou hraničními body ořezané úsečky)
   • Oba body jsou uvnitř ořezávacího okna (prázdné sjednocení, viz výše popis algoritmu).
   • Úsečka neprochází ořezávacím oknem (neprázdný průnik, viz výše popis algoritmu).
3. Je nutné úsečku ořezat
   • Pokud má aktualniBod hraniční kód 0000 (je uvnitř okna), zaměň aktualniBod za bod, který ještě nebyl uvažován (aktualniBod="B")
4. Podle nastavené jedničky hraničního kódu bodu ořež úsečku podle odpovídajíci hrany (tj. pokud 1001, začínáme řezat levou hranou).
   • aktualniBod=průsečík úsečky a zvolené hrany
5. Pokračuj bodem 1.

Ořezávání polygonu, algoritmus Sutherland-Hodgman

VSTUP

polygon, ořezávací okno

VÝSTUP

ořezaný polygon

Polygon si zorientujeme, na začátku algoritmu máme tedy posloupnost bodů tohoto orientovaného polygonu a na výstupu na začátku prázdnou posloupnost.

V i-tém kroku vezmeme vždy body $U_i$ a $U_{i+1}$ ze vstupní posloupnosti a do výstupní posloupnosti zapíšeme body podle následujících pravidel:

1. Oba body leží vně vůči dané hranici okna. Pak do výstupní posloupnosti nezapíšeme žádný bod.
2. Počáteční bod $U_i$ leží vně okna a koncový bod $.U_{i+1}$ leží uvnitř okna, pak spočítáme průsečík $B$ strany polygonu s hranicí okna a do výsledné posloupnosti zařadíme tento vypočítaný průsečík.
3. Oba body leží uvnitř okna vzhledem k dané hranici okna, pak do výstupní

posloupnosti zapíšeme počáteční bod $U_i$.

1. Počáteční bod $U_i$ leží uvnitř okna a koncový bod $U_{i+1}$ leží vně okna, pak spočítáme průsečík $B$ strany polygonu s hranicí okna a do výstupní posloupnosti přidáme počáteční vrchol $U_i$ a bod průsečíku $B$.

Tento algoritmus použiji postupně pro všechny strany ořezávacího okna, přičemž na vstupu pro první stranu okna je ořezávaný polygon a pro každou další stranu okna je již polygon oříznutý v předchozím kroku.

Je také možné každou ořezanou hranu ihned poslat k ořezání další hranicí -- tzv. reentrant polygon clipping, tak si nemusíme pamatovat postupně ořezané polygon a jejich proměnlivý počet vrcholů. Tento způsob je použit v naší implementaci algoritmu.

Kód v jazyce C#

Program se skládá ze 2 komponent. Každou realizoval jeden z nás -- jedna je zodpovědná za prezentaci -- formular, druhá je jádrem -- Kernel, které provádí veškeré výpočty. Pro komunikaci jsme si definovali rozhraní IGeom vypadající následně:

Veškeré polygony jsou uloženy v jádře v hash tabulce, která umožňuje rychlý přístup k požadovanému objektu podle jeho ID. Jádro si pouze o polygony žádá při zobrazování, případně žádá jejich modifikaci -- podle operací definovaných v IGeom. Popis níže se už týká jen komponenty Kernel.

Pomocné objekty a metody

• Sef -- implementuje rozhraní IGeom, je fasádou k Kernel. Zodpovídá za veškerou funkčnost jádra.
• Bod2D -- objekt definující bod v 2D, obsahuje souřadnice
• OhodnoceniBodu -- ohodnocení bodu, váže se k bodu
• Polygon -- objekt reprezentující polygon (obsahuje seznam bodů)
• OrezavaciOkno -- speciální příklad obdélníkového polygonu. Definuje ořezávací okno

Vlastní algoritmus

Oba algoritmy SutherlandHodgman a CohenSutherland jsou specializací abstraktní třídy OrezavacAbstract definující společnou metodu nabízející možnost ořezání:

Při žádosti o ořezání polygonu je podle počtu bodů polygonu objektem Sef zvolen odpovídající algoritmus, pro úsečku CohenSutherland, pro jiné polygony SutherlandHodgman a volána metoda algoritmu Orez( polygon ).

Následuje kód hlavních metod ořezávacích algoritmů.

Algoritmus Sutherland-Hodgman - ořezání polygonu

Pozn.: v následujícím kódu je použita varianta algoritmu SutherlandHodgman, kdy dochází k předávání ořezané hrany ihned k ořezání další hranou (tzv. reentrant polygon clipping), tj. nedochází k ukládání mezivýsledku "polygonu ořezaného jednou hranou", jak je popsáno v algoritmu výše. Použitý postup má výhodu i nevýhodu: je optimálnější, avšak jednotlivé kroky nejsou na první pohled tak pochopitelné.

Autoři

Tento text vypracovali studenti Univerzity Palackého v Olomouci katedry Matematické informatiky jako součást zápočtového úkolu do předmětu Počítačová geometrie.