Algoritmy pro ořezávání 2D polygonů
Využití ořezávání v praxi
odstranění částí obrazu nacházejících se mimo zobrazitelnou oblast výstupního zařízení
Využití ořezávání v praxi
Vyplňování 3D objektů Vytvoření vysoce kvalitního povrchu zobrazovaných objektů pomocí zkoumání odrazů, odlesků a lomů paprsků světla Přidělování objektů scény multiprocesorovým systémům
Polygon
Uspořádaný seznam bodů /vrcholů/, kde první a poslední bod je identický
Algoritmus Cohen-Sutherland
Algoritmus slouží k ořezávání čar vůči obdélníku. Hlavní výhodou algoritmu je jednoduché a rychlé zakódování jednotlivých případů pozice úsečky vůči obdélníku. Po zakódování pozic můžeme snadno vynechat úsečky, které leží zcela mimo nebo uvnitř obdélníku.
Algoritmus Cohen-Sutherland
Hodnota 1 v kódu znamená hodnotu true a kód je tvořen podle následujících pravidel (bity počítáme zprava): – – – –
bit 0 - bod je vlevo od obdélníka bit 1 - bod je vpravo od obdélníka bit 2 - bod je pod obdélníkem bit 3 - bod je nad obdélníkem
Po zakódování mohou nastat následující případy: – – –
kód oblasti je roven nule pro oba koncové body úsečky - přímka leží uvnitř oblasti, kódy obou koncových bodů mají stejný bit nenulový - přímka leží mimo obdélník, u ostatních možností přímka prochází hranou obdélníka.
Průsečíky s ořezávacím oknem
Výpočet průsečíku s příslušnou hranou obdélníka se spočítá následovně: – – – –
je-li bod vlevo: (xmin, k*(xmin-x1)+y1) je-li bod vpravo: (xmax,k*(x1-xmax)+y1) je-li bod nad: (q*(y1-ymax)+x1,ymax) je-li bod pod: (q*(ymin-y1)+x1,ymin)
kde
k = (y2-y1)/(x2-x1) pro x1 != X2, q = (x2-x1)/(y2-y1) pro y1 != y2
Algoritmus Cohen-Sutherland
Algoritmus Cyrus-Beck
Tento algoritmus slouží k ořezávání úseček vůči konvexnímu n-úhelníku. Algoritmus je založen na znalosti normál hran konvexního n-úhelníka, podle kterého úsečky ořezáváme. Přímka může protínat tento n-úhelník nejvýše ve dvou bodech, pokud pomineme speciální případ, kdy úsečka leží na některé hraně.
Cyrus-Beck algoritmus
Algoritmus Weiler-Atherton
Algoritmus slouží k ořezávání obecného nekonvexních núhelníku jiným obecným nekonvexním n-úhelníkem Oba n-úhelníky mohou obsahovat i díry. Po oříznutí nám může vzniknout i několik samostatných n-úhelníků.
Weiler-Atherton
Algoritmus Greiner - Hormannův
Günther Greiner
Kai Hormann
Friedrich Alexander University Erlangen, Německo
Vstup
Uspořádané posloupnosti vrcholů ořezávaného a ořezávacího polygonu
Výstup
Množina všech bodů ležících v S && C
Polygon Seznam vzniklých polygonů
Sebeprotínající polygon
Oblasti, patřící do výsledku určíme pomocí tzv. WINDING NUMBER
Je–li WN liché, pak náleží výsledku
Winding Number double isLeft(Point P0, Point P1, Point P2) { return((P1.x - P0.x) * (P2.y - P0.y) - (P2.x - P0.x) * (P1.y - P0.y)); } int WindingNumber(Point P, Point * V, int n) { int WN = 0; // počítadlo otáček //smyčka přes všechny hrany polygonu for (int i=0; i
P.y) if(isLeft(V[i],V[i+1],P)>0 ++wn; // máme otáčku proti směru } else{ // V[i].y> P.y if(V[i+1].y <= P.y) if(isLeft(V[i],V[i+1],P)<0) --wn; // máme otáčku po směru }
}
} return wn;
Vlastnosti Winding Number Při pohybu bodu P nebo hrany E, zůstává WN konstantní, dokud P zůstane v kladné vzdálenosti od hrany E. Pro křivku ω je WN konstantní v podprostoru R x R – ω. Leží-li bod P v neohraničené komponentě, pak má WN = 0 Při překřížení paprsku a hrany se WN změní o +/-1.
První fáze algoritmu
Určení všech průsečíků hran C a S polygonu – – –
Složitost minimálně m*n /m = # vrcholů S, n = # vrcholů C/ Všechny tyto průsečíky budou vrcholy ve výsledku Ukládáme si ukazatele na stejný průsečík v seznamu druhého polygonu
Jejich následné zařazení do seznamu vrcholů obou polygonů – K tomu je zapotřebí spočítat tzv. α parametr, z kterého lze určit vzdálenost průsečíku od počátečního vrcholu hrany a zařadit tak správně všechny průsečíky na jedné hraně
Platí
– – –
0<α<1 P.x = V[i].x + α * V[i+1].x P.y = V[i].y + α * V[i+1].y
Zvláštní případy
Leží-li nám bod, či hrana na hraně druhého polygonu, je nutné jej posunout o nejmenší možný úsek, výsledek zůstane stejný
Druhá fáze algoritmu
V fázi dvě procházíme všechny průsečíky a přiřazujeme jim I/O atribut
Ten určuje, zda v daném průsečíku vstupujeme dovnitř polygonu nebo jej opouštíme. Stejný průsečík může mít rozdílné atributy v rámci polygonů Vezmeme libovolný vrchol polygonu, zjistíme pomocí WN, zda je uvnitř či vně a jdeme po seznamu vrcholů, vždy, když narazíme na průsečík, změníme atribut a uložíme jej k danému průsečíku Toto provedeme pro oba polygony
Třetí fáze algoritmu
Zdroje
Greiner, G. and Hormann, K. 1998. Efficient clipping of arbitrary polygons. ACM Trans. Graph. 17, 2 (Apr. 1998), 71-83. DOI= http://doi.acm.org/10.1145/274363.274364
Vatti, B. R. 1992. A generic solution to polygon clipping. Commun. ACM 35, 7 (Jul. 1992), 56-63. DOI= http://doi.acm.org/10.1145/129902.129906
http://notorola.sh.cvut.cz/~bruxy/Algoritmy_pocitacove_grafiky.doc
http://herakles.zcu.cz/education/ZPG/cviceni.php?no=9
