Fakulta Aplikovaných věd Západočeská Univerzita v Plzni Katedra informatiky a výpočetní techniky
Oborový projekt
Algoritmy ořezávání přímky konvexním n-úhelníkem
Plzeň, 2006
Martina Málková
Algoritmy ořezávání přímky konvexním n-úhelníkem (Line clipping algorithms against convex polygon) Zadání: Algoritmus Cyrus-Beck, Liang Barsky, LSSB průsečíku přímky s konvexním n-úhelníkem - v E2 a urychlovací techniky - s použitím homogenních souřadnic, porovnání výpočtu v Eukleidovských a homogenních souřadnicích, přímka dána v homogenních souřadnicích, použití lineární interpolace s lineární parametrizací, nelineární parametrizaci a Plückerových souřadnic, pokud jsou aplikovatelné.
-1-
Abstract Clipping algorithms are used to remove those parts of the image that lie outside specific region (in 2D it is usually rectangular window, in 3D viewing pyramid). This work concentrates on 2D line clipping algorithms, first describing algorithms used for clipping by a rectangular window and convex polygon, then trying to transform them to use homogeneous coordinates. Although homogeneous coordinates are not much used in contemporary algorithms, they are powerful device when talking about transforming objects, and they can be also used in clipping to gain speed and stability of the algorithms.
-2-
Prohlašuji, že jsem tuto práci vypracovala samostatně a výhradně s použitím citovaných pramenů a nebyla součástí semestrálních prací v jiných předmětech mého studia.
V Plzni dne …………………….
………………………….. Martina Málková
-3-
1
Úvod .............................................................................................................................................................. 5 Pozadí problému .................................................................................................................................. 5 Téma práce........................................................................................................................................... 5 2 Známé metody ............................................................................................................................................... 6 2.1 Ořezávání v obdélníkovém okně.......................................................................................................... 6 2.1.1 Cohen-Sutherland ....................................................................................................................... 6 2.1.2 LSSB .......................................................................................................................................... 7 2.1.3 Liang Barsky ............................................................................................................................ 10 2.1.4 LSB........................................................................................................................................... 11 2.2 Ořezávání vůči konvexnímu n-úhelníku ............................................................................................ 12 2.2.1 Cyrus-Beck............................................................................................................................... 12 2.2.2 ECB (Efficient Cyrus-Beck)..................................................................................................... 14 2.2.3 Algoritmus O(logN) ................................................................................................................. 16 2.3 Porovnání metod ................................................................................................................................ 17 3 Homogenní souřadnice.................................................................................................................................. 17 3.1 Cyrus-Beck ........................................................................................................................................ 18 3.2 Liang Barsky...................................................................................................................................... 20 3.3 Algoritmus O(logN)........................................................................................................................... 21 3.4 Shrnutí................................................................................................................................................ 21 4 Odhad složitosti a časová náročnost algoritmů ............................................................................................. 22 5 Implementace ................................................................................................................................................ 24 6 Závěr ............................................................................................................................................................. 25 6.1 Celkové zhodnocení........................................................................................................................... 25 6.2 Další možné směry modifikací, resp. práce ....................................................................................... 25 7 Literatura....................................................................................................................................................... 25 Příloha 1: Naměřené výsledky ....................................................................................................................... 26 1.1 1.2
-4-
1
Úvod 1.1
Pozadí problému
Algoritmy ořezávání hrají důležitou roli při zobrazování rozsáhlých kreseb. Umožňují vybrat z kresby jen ty části, které budou viditelné v určité oblasti – např. ve 2D okno na obrazovce, ve 3D pohledová pyramida. Tyto algoritmy nejen vybírají, které objekty jsou mimo a uvnitř daných oblastí, ale hlavně „ořezávají“ objekty, které jsou zčásti uvnitř a zčásti vně. Během vývoje ořezávacích algoritmů nezůstala myšlenka pouze při obdélníkovém oknu či pohledové pyramidě, ale vznikly i obecnější algoritmy, které se zabývaly složitějšími tvary (konvexní a obecný n-úhelník, konvexní a obecný mnohostěn).
Obr. 1.1 – Ořezávání vůči obdélníkovému oknu (převzato z [4])
1.2
Téma práce
V této práci se zaměříme na ořezávání ve 2D. Algoritmy pracující ve 2D můžeme rozdělit dvěma způsoby: podle primitiv, která ořezávají, nebo podle oblasti, vůči které primitiva ořezávají.
1) Podle oblastí: a) Obdélníkové okno (Cohen-Sutherland, LSSB, Liang Barsky, LSB) b) Konvexní n-úhelník (Cyrus-Beck, ECB) c) Obecný n-úhelník (Weiler-Atherton) 2) Podle ořezávaných primitiv: a) Test polohy bodu (vzhledem k tomu, že jde o bod, je toto spíše test než ořezávání) b) Ořezávání úsečky nebo přímky (lomené čáry, křivky nahrazené posloupností úseček) c) Ořezávání oblasti (uzavřené oblasti, výsledkem je jedna nebo více uzavřených oblastí) Zde se budeme zabývat ořezáváním úsečky/přímky – tedy část 2b). Úsečku/přímku budeme ořezávat konvexním n-úhelníkem. Vzhledem k tomu, že obdélník je speciální případ konvexního n-úhelníku, patří sem obě části 1a) a 1b). V následující kapitole – Známé metody – ukážeme několik známých metod spadajících do těchto oblastí. Těmi jsou pro úsečku v obdélníkovém okně Cohen-Sutherland a LSSB, pro přímku v obdélníkovém okně Liang Barsky a LSB, pro úsečku/přímku v konvexním n-úhelníku Cyrus-Beck, ECB (Efficient Cyrus-Beck) a algoritmus pracující v O(logN). Některé další algoritmy lze nalézt v [1]. Na konci kapitoly budou algoritmy zhodnoceny a porovnány. Protože pro ořezávání v Eukleidovském prostoru už existuje mnoho algoritmů a v rámci této jednosemestrální práce nebylo možno vymyslet efektivnější algoritmus než ty, které již existují, zaměříme se na použití homogenních souřadnic u popsaných algoritmů, neboť homogenní souřadnice přináší algoritmům vyšší rychlost a potřebnou stabilitu. Jejich použití bude popsáno ve třetí kapitole – Homogenní souřadnice.
-5-
V třetí kapitole – Odhad složitosti a časová náročnost algoritmů – odhadneme složitost jednotlivých algoritmů pomocí naměřených časů jednotlivých operací dělení, násobení a sčítání. Díky této složitosti pak budeme moci jednotlivé algoritmy porovnat. Čtvrtá kapitola – Implementace – pojednává o tom, kde a jakým způsobem byly algoritmy implementovány. Na přiloženém CD či na internetových stránkách práce lze nalézt zdrojové kódy jednotlivých algoritmů a funkční program pro otestování jejich funkčnosti a rychlosti.. V páté kapitole – Analýza výsledků – budou ukázány naměřené časy výpočtu jednotlivých algoritmů a diskutovány porovnání odhadovaných a skutečně naměřených časů. Na závěr budou zhodnoceny výsledky porovnání, vhodnost použití jednotlivých metod.
2
Známé metody 2.1
Ořezávání v obdélníkovém okně
Protože ořezávání vůči obdélníkovému oknu je ve 2D nejpoužívanějším případem, existuje zde mnoho algoritmů. Rozsah této práce nám nedovolí zde jmenovat všechny, proto budou uvedeny jen ty nejznámější. Pro ořezávání úsečky jimi budou algoritmy Cohen-Sutherland a LSSB. Pro ořezávání přímky Liang Barsky a LSB.
2.1.1
Cohen-Sutherland
Algoritmus Cohen-Sutherland je určen pro ořezávání úsečky vůči obdélníkovému oknu. Myšlenkou algoritmu je rozdělit prostor na 9 částí, které ohodnotíme čtyřmístným binárním kódem (Obr. 2.1 vlevo). Při ořezávání úsečky pak ohodnotíme stejným způsobem oba její body (Obr. 2.1 vpravo, Algoritmus 2.1)
Obr. 2.1 – Algoritmus Cohen-Sutherland (převzato z [2]) Vlevo: ohodnocení částí prostoru binárním kódem Vpravo: Ohodnocení úseček
Na obr. 2.1 vpravo lze také vidět funkčnost algoritmu. Počet průchodů algoritmu závisí na poloze úsečky, resp. na počtu rozdílných bitů zakódovaných krajních bodů úsečky. Nejhorší případ tedy bude, pokud jeden krajní bod úsečky bude ležet v jedním z rohů (např. bude mít kód 1001) a druhý krajní bod úsečky bude ležet v opačném rohu (např. 0110). Jinými slovy, nejhorší případ nastane, pokud se zakódované krajní body úsečky budou lišit ve všech čtyřech bitech. Vstup: úsečka AB – A=[x1,y1],B=[x2,y2] obdélníkové okno - xmin, xmax, ymin, ymax Značení: & - bitový součin, | - bitový součet, EXIT – konec algoritmu, DRAW(X,Y) – vykresli úsečku XY, CODE(X) – vypočítá kód daného bodu a vrátí ho jako integer Algoritmus: ca := CODE(A) cb := CODE(B) if (ca & cb) <> 0 then EXIT while (ca | cb) != 0 do begin if ca != 0 then c = ca else c = cb if (C&1) <> 0 then begin x := xmin y := y1+(xmin-x1)*(y2-y1)/(x2-x1) end else if (C&2) <> 0 then
{určíme kódy krajních bodů úsečky}
{úsečka úplně mimo} {dokud nejsou oba krajní body uvnitř} {do c přiřadím bod mimo okno} {liší se -> průsečík s levým krajem} {průsečík uložím do pomocného bodu}
{průsečík s pravým okrajem}
-6-
begin x := xmax y := y1+(xmax-x1)*(y2-y1)/(x2-x1) end else if (C&4) <> 0 then begin x := x1+(ymin-y1)*(x2-x1)/(y2-y1) y := ymin end else if (C&8) <> 0 then begin x := x1+(ymax-y1)*(x2-x1)/(y2-y1) y := ymax end if c = ca then begin x1 := x y1 := y ca := CODE(A) end else x2 := x y2 := y cb := CODE(B) end
{průsečík s horním okrajem}
{pokud jsme upravovali bod A}
{musime prepocitat kod A} {jinak jsme upravovali B}
{přepočítáme kod B}
if (ca & cb) <> 0 then EXIT end DRAW(A,B)
2.1.2
{průsečík s dolním okrajem}
{ořezání způsobilo, že je úsečka mimo} {vykreslení ořezané úsečky} Algoritmus 2.1 – Algoritmus Cohen-Sutherland
LSSB
Název je zkratkou algoritmu Line Segment Skala Bui. Je rozšířením algoritmu Cohen-Sutherland o aritmetický součet kódů krajních bodů úsečky a použití směrového vektoru pro vyhledání, s kterou hranou počítat průsečík (Obr. 2.2). Algoritmus byl poprvé publikován v [2]. Použijeme opět kódy krajních bodů c A , c B . Navíc φ označíme vnitřek okna, α , γ ,η , ω nazveme rohové
oblasti a β , δ , θ , ξ postranní oblasti (Obr. 2.2). Pomocí součtu kódů krajních bodů můžeme rozlišit následující situace: 1) c A + c B ∈ {1,2,4,8} Jeden bod je uvnitř okna a druhý v jedné z postranních částí. Potřebujeme vypočítat jeden průsečík. 2) c A + c B ∈ {3,12} Body jsou v postranních částech naproti sobě. Potřebujeme vypočítat dva průsečíky, zároveň už víme, se kterými hranami. 3) c A + c B ∈ {7,11,13,14} Jeden bod je v rohu a jeden v postranní části. Jeden průsečík (na straně bodu v postranní části) víme se kterou hranou počítat, hrana pro druhý průsečík bude buď protější nebo vedlejší (další testy). 4) c A + c B ∈ {5,6,9,10} Zde mohou nastat dvě možnosti: a) Oba body jsou v sousedních postranních oblastech - ( β , δ ), (δ , ξ ), (ξ ,θ ), (θ , β ) . Vypočítáme dva průsečíky, víme s jakými hranami. b) Jeden bod je uvnitř okna a druhý v jedné z rohových oblastí. Existuje jen jeden průsečík, musíme určit zda s vodorovnou nebo svislou hranou. 5) c A + c B = 15 Oba body jsou v rohových oblastech. Abychom určili, se kterými hranami počítat průsečík, porovnáme směrový vektor úsečky s diagonálou okna (Obr. 2.1.2 tučně) Pseudokód algoritmu je ukázán v Algoritmus 2.2
-7-
Obr. 2.2 – ukázka součtu krajních bodů možných úseček (převzat z [2]) Vstup: úsečka AB – A=[x1,y1],B=[x2,y2] obdélníkové okno - xmin, xmax, ymin, ymax Značení: & - bitový součin, | - bitový součet, EXIT – konec algoritmu, DRAW(X,Y) – vykresli úsečku XY, CODE(X) – vypočítá kód daného bodu a vrátí ho jako integer Algoritmus: ca := CODE(A) cb := CODE(B) if (ca & cb) <> 0 then EXIT if (ca | cb) = 0 then begin DRAW(A,B) EXIT end dx := x2-x1 dy := y2-y1 case ca+cb of 1: {podobně pro 2,4,8} if ca = 1 then begin x1 := xmin y1 := (xmin-x2)*dy/dx+y2 end else begin x2 := xmin y2 := (xmin-x1)*dy/dx+y1 end 3: {podobně pro 12} begin k := dy/dx y1 := (xmin-x1)*k+y1 x1 := xmin y2 := (xmax-x2)*k+y2 x2 := xmax end 5: {podobně pro 6,9,10} v sousedních postranních oblastech} begin k := dy/dx r := (xmin-x1)*k+y1 if(r < ymin) then case ca of 0: begin x2 := x2+(ymin-y2)/k y2 := ymin end 5: begin x1 := x1+(ymin-y1)/k
{určíme kódy krajních bodů úsečky}
{úsečka úplně mimo} {úsečka uvnitř}
{jeden uvnitř, druhý v postranní č.} {bod A leží mimo okno}
{body v protějších postranních část.}
{jeden bod uprostřed a druhý v rohu, nebo body
{A je uvnitř}
{B je uvnitř}
-8-
y1 := ymin end else EXIT; {přímka mimo} else case ca of 0: begin x2 := xmin y2 := r end 1: begin x2 := x2+(ymin-y2)/k y2 := ymin x1 := xmin y1 := r end 4: begin x1 := x1+(ymin-y1)/k y1 := ymin x2 := xmin y2 := r end 5: begin x1 := xmin y1 := r end end 7: {podobně pro 11,13,14} {jeden bod uprostřed a druhý v postranní oblasti} begin case ca of 1: begin {podobně pro případy 2,5,6} k := dy/dx y1 := (xmin-x2)*k+y2 if y1 < ymin then EXIT {přímka mimo} x1 := xmin y2 := (xmax-xmin)*k+y1 if y2 < ymin then begin x2 := (ymin-y2)/k+xmax y2 := ymin end else x2 := xmax end end 15: {body v protějších rozích} begin case ca of 5: {z levého dolního do pravého horního} if dy*(xmax-xmin) < dx*(ymax-ymin) then {porovnáme úhel s diagonálou} begin k := dy/dx y1 := (xmin-x2)*k+y2 if y1 > ymax then EXIT {přímka je nad obdélníkem} y2 := (xmax-xmin)*k+y1 if y2 < ymin then EXIT {přímka je pod obdélníkem} if y1 < ymin then begin x1 := (ymin – y1)/k + xmin y1 := ymin x2 := xmax end else begin x1 := xmin if y2 > ymax then begin x2 := (ymax-y2)/k+xmax y2 := ymax end else x2 := xmax end else begin k := dx/dy x1 := (ymin-y2)*k+x2
-9-
if x1 > xmax then EXIT x2 := (ymax-ymin)*k+x1 if x2 < xmin then EXIT if x1 < xmin begin y1 := (xmin–x1)/k+ymin x1 := xmin y2 := ymax; end else begin y1 := ymin if x2 > xmax then begin y2 := (xmax-x2)/k+ymax x2 := xmax end else y2 := ymax end
{přímka míjí obdélník zvrchu} {přímka míjí obdélník zespoda}
Algoritmus 2.2: LSSB (převzat z [2] a upraven pro konzistenci značení)
2.1.3
Liang Barsky
Liang Barsky algoritmus je efektivnější úpravou algoritmu Cyrus-Beck (kap. 2.2.1) pro obdélníkové okno. Tento algoritmus je upraven tak, aby skutečně vyloučil všechny přímky jdoucí mimo okno (speciálně ošetřuje i případ rovnoběžky s hranou okna). Algoritmus (Algoritmus 2.3) zakládá na tom, že hrany obdélníkového okna mají triviální normály (obr. 2.3). Pokud parametry okna označíme x min , x max , y min , y max , krajní body úsečky A=[x1,y1], B=[x2,y2] a dx rozdíl x2-x1, dy rozdíl y2-y1, můžeme v původní rovnici (algoritmu Cyrus-Beck) pro výpočet průsečíku přímky s hranou n-úhelníku (vzorec 2.3) dosadit normály a přepsat ji do čtyř nerovností: t * ri ≤ q i , i = 1,2,3,4 [2.1] Kde
r1 = −dx r2 = dx r3 = − dy r4 = dy
q1 = x1 − x min q 2 = x max − x1 q 3 = y1 − y min q 4 = y max − y1
Zároveň platí, že pokud ri = 0 (přímka rovnoběžná s i-tou hranou) a zároveň qi< 0 , přímka leží mimo okno.
Obr. 2.3 – Normály hran okna Vstup: přímka AB – A=[x1,y1],B=[x2,y2] obdélníkové okno - xmin, xmax, ymin, ymax Značení: EXIT – konec algoritmu DRAW(X,Y) – vykresli úsečku XY Algoritmus: t1 := -∞ t2 := ∞ dx := x2-x1
{pro úsečku bychom položili t1 = 0} {pro úsečku t2 = 1}
- 10 -
if TEST(-dx,x1-xmin,t1,t2) then if TEST(dx,xmax-x1,t1,t2) then begin dy := y2-y1 if TEST(-dy,y1-ymin,t1,t2) then if TEST(dy,ymax-y1,t1,t2) then begin x2 := x1+dx*t2 y2 := y1+dy*t2 x1 := x1+dx*t1 y1 := y1+dy*t1 DRAW(A,B) end end
{vlevo} {vpravo}
{dole} {nahoře}
Funkce TEST: function TEST (r, q: real; var t1, t2: real):boolean {zjisti zda existuje prusecik s touto casti, pripadne ho vypocita} var m : real {pomocná proměnná} begin TEST:=true if r<0 then {přímka „vstupuje“ do okna} begin {budeme přepisovat t1} m:=q/r if m>t2 then TEST:=false {t1>t2 – min>max přímka mimo} else if m>t1 then t1:=m end else if r>0 then {přímka „vystupuje” z okna} begin m:=q/r; if m
2.1.4
LSB
LSB algoritmus je úpravou algoritmu Liang Barsky. Pomocí porovnání směrnice přímky s diagonálou obdélníku určí, se kterými hranami (vodorovnými či svislými) počítat průsečík nejdříve. Vstup: přímka AB – A=[x1,y1],B=[x2,y2] obdélníkové okno - xmin, xmax, ymin, ymax Značení: EXIT – konec algoritmu DRAW(X,Y) – vykresli úsečku XY Algoritmus: dx := x2-x1 if dx=0 then begin if (x1<xmin)or(x1>xmax) then EXIT y1 := ymin y2 := ymax DRAW(X,Y) EXIT end dy := y2-y1 if dy=0 then begin if (y1
ymax) then EXIT x1 := xmin x2 := xmax DRAW(X,Y) EXIT end if dx>0 then if dy>0 then if dy*(xmax-xmin)
{svislá přímka} {přímka mimo} {ořízneme vodorovnými hranami}
{body vedle sebe} {přímka mimo} {ořízneme svislými hranami}
{sklon 0-PI/2} {porovnám sklon s diagonálou}
{y souřadnice průsečíku s hranou xmin}
- 11 -
if y1 > ymax then EXIT y2 := (xmax-xmin)*k+y1 if y2 < ymin then EXIT if y1 < ymin then begin x1 := (ymin-y1)/k+xmin y1 := ymin x2 := xmax end else begin x1 := xmin if y2 > ymax then begin x2 := (ymax-y2)/k+xmax y2 := ymax end else x2 := xmax end end else begin k := dx/dy x1 := (ymin-y2)*k+x2 if x1 > xmax then EXIT x2 := (ymax-ymin)*k+x1 if x2 < xmin then EXIT if x1 < xmin then begin y1 := (xmin-x1)/k+ymin x1 := xmin y2 := ymax end else begin y1 := ymin if x2 > xmax then begin y2 := (xmax-x2)/k+ymax x2 := xmax end else y2 := ymax end end {podobně pro ostatní případy} DRAW(A,B)
{přímka je nad obdélníkem} {y souřadnice průsečíku s hranou xmax} {přímka je pod obdélníkem} {A průsečík s hranou ymin, B xmax}
{A průsečík s hranou xmin, B nevíme}
{s kt. hranou má strana u B průsečík} {s vodorovnou}
{se svislou – y2 už spočteno}
{prudší sklon než diagonála}
{přímka míjí obdélník zprava} {přímka míjí obdélník zleva} {část u A protíná hranu xmin,u B ymax}
{x2 už známe} {část u A protíná hranu ymin,B nevíme} {x1 už známe} {pokud protíná část u B hranu xmax}
{část u B protíná hranu ymax} {x2 už známe}
Algoritmus 2.3: LSB (převzat z 1 a upraven pro konz. značení)
2.2
Ořezávání vůči konvexnímu n-úhelníku
2.2.1
Cyrus-Beck
Tento algoritmus je případem algoritmu ořezávajícího přímku (popř. úsečku) vůči konvexnímu n-úhelníku. Pokud A,B označíme body na ořezávané přímce (A≠B), můžeme zapsat přímku v parametrickém tvaru:
X (t ) = A + (B − A)t
[2.2]
Jednotlivé hrany n-úhelníku zapíšeme jejich obecnou rovnicí
a i x + bi y + d i = 0 , i = 1,2,...,n kde n je počet hran. Platí, že
ni = [a i , bi ]T je normála i-té hrany.
Vlastní algoritmus pak pracuje tak, že pro každou hranu n-úhelníku vypočítá průsečík této hrany s přímkou pomocí vzorce
ti =
(
− niT A + d i niT (B − A)
)
kde ti je parametr z rovnice 2.2 určující průsečík s i-tou hranou.
- 12 -
[2.3]
Základní forma algoritmu je popsána pseudokódem (Algoritmus 2.4). Není vypsán preprocessing, kdy se předpočítají rovnice jednotlivých hran n-úhelníku (ty lze získat např. jako z-souřadnici vektorového součinu dvou různých bodů ležících na přímce). Vstup: přímka AB – A=[x1,y1],B=[x2,y2], konvexní polygon o N hranách Značení: ni*X+di=0 – rovnice hrany polygonu, CONTINUE – pokračuj dalším krokem cyklu, EXIT – konec algoritmu, DRAW(X,Y) – vykresli úsečku XY Algoritmus: tmin := -∞ tmax := ∞
{pro úsečku bychom položili tmin = 0} {pro úsečku tmax = 1}
for i:=0 to N do begin ta := -(ni*A+di) tb := ni*(B-A) if tb <> 0 then t := ta/tb else CONTINUE if tb < 0 then begin if t > tmin then tmin := t end else if t < tmax then tmax := t end if (tmin > tmax) then EXIT
dx dy x2 y2 x1 y1
:= := := := := :=
{pro všechny hrany polygonu}
{přímka rovnoběžná s danou hranou}
{průsečík, kterým přímka „vstupuje“} {průsečík, kterým přímka „vystupuje“}
{přímka mimo těleso – pro úsečku navíc podmínky (tmin > 1)OR(tmax < 0)}
x2-x1 y2-y1 x1 + dx*tmax y1 + dy*tmax x1 + dx*tmin y1 + dy*tmin
DRAW(A,B) EXIT Algoritmus 2.4 – Algoritmus Cyrus-Beck
Na rozdíl od předchozích algoritmů tento neořeže správně úplně všechny úsečky. Neošetřuje totiž případ, kdy je přímka rovnoběžná s jednou z hran n-úhelníku. Pokud taková přímka leží mimo n-úhelník, ořeže se jen zčásti. Na následující sérii obrázků (2.4 – 2.7) je ukázáno, jak se algoritmus chová pro různé přímky.
tmin1 tmin3
tmin2
tmax
Obr. 2.4 – Přímka protíná n-úhelník
tmin1 tmin2 tmax1 Obr. 2.5 – Přímka leží na jedné z hran n-úhelníku (ořízne se jen zčásti)
- 13 -
tmin1 tmin2
tmax1
Obr. 2.6 – Přímka je rovnoběžná s hranou n-úhelníku, leží mimo (případ kdy nedojde k vyloučení přímky, přestože by mělo)
tmin1
tmax1 tmin2
tmax2 Obr. 2.7 – Přímka leží mimo n-úhelník (tmin > tmax : přímka se nevykreslí)
2.2.2
ECB (Efficient Cyrus-Beck)
Algoritmus Cyrus-Beck nejprve spočítá průsečíky přímky se všemi hranami a pak až vyhodnocuje, které z nich jsou ty, kde přímka skutečně vstupuje/vystupuje z tělesa. Tato myšlenka je spíše tzv. „brutální síla“. U algoritmů ořezávání se ale snažíme směrovat k tomu, abychom nejdříve co nejvíce otestovali a pak až vypočítali případné průsečíky. K tomu používá algoritmus ECB (pseudokód v Algoritmus 2.5) vektorový součin. Nejprve otestuje, zda přímka danou hranu skutečně protíná, a až pokud ano, vypočítá samotný průsečík. Tím zamezí zbytečnému dělení probíhajícímu v algoritmu Cyrus-Beck. Jak se lze dočíst v [1] a vidět na obr. 2.8: Znakem s označíme směrový vektor ořezávané přímky daný dvěma různými body (A,B) na přímce:
s = ( B − A)
Vektor si bude značit vektor z bodu A do i-tého vrcholu n-úhelníku. Pak přímka protíná i-tou hranu n-úhelníku, právě když s leží mezi vektory si a si+1. To lze zapsat formálně: ξ ,η označíme vektorové součiny
ξ = [s × si ],η = [s × si +1 ]
kde N je počet hran n-úhelníku. Přímka protíná hranu pouze tehdy, když
i = 0,..., N − 1
(ξ > 0) xor (η > 0) , tedy ξ *η < 0
- 14 -
Obr. 2.8 – Přímka protíná hranu X0X1(převzat z [1])
Výhodou této myšlenky je, že je nezávislá na orientaci jednotlivých hran n-úhelníku. Algoritmus ale počítá s tím, že přímka protíná n-úhelník maximálně ve dvou místech, tudíž lze použít pouze pro konvexní n-úhelníky. Vstup: přímka AB, konvexní polygon o N hranách Značení: Xi – itý vrchol polygonu, s-směrový vektor přímky, sj – vektor z A do vrcholu polygonu (viz Obr. 2.8), EXIT – konec algoritmu, DRAW(X,Y) – vykresli úsečku XY Algoritmus: tmin,tmax,t1,t2: real i,j,k: integer k i j s
ξ
:= 0 := N-1 := 0 := B-A := [s × ( X N −1 − A)]
Z
while j
{z složka vektorového součinu}
{opět z složka vektorového součinu}
if ξ *η < 0 then {pokud přímka protíná hranu} begin k := k+1 {uchováme index této hrany} indexk := i end else if ξ *η = 0 then speciální případ else průsečík neexistuje ξ := η i := j j := j+1 end if k = 0 then EXIT {nenašli jsme žádný průsečík-mimo} {jinak předpokládáme, že k <= 2 (konvexní n-úhelník)} tmin := -∞ tmax := ∞ i := index1 t1 := det[ Xi − A | Xi − X (i + 1)] / det[s | Xi − X (i + 1)] i := index2 t2 := det[ Xi − A | Xi − X (i + 1)] / det[s | Xi − X (i + 1)]
{pro úsečku bychom položili tmin = 0} {pro úsečku tmax = 1}
{pokud se změnily krajní body úsečky/ přímka byla ořezána} {musíme zjistit, který z parametrů t je „vstupní“ a který „výstupní“} if t1>t2 then begin if t1tmax then EXIT {ošetření vyloučení pro případ úsečky} if t1tmin then A := A+s*t2 {opravím první bod} end else {to samé, význam t1 a t2 se prohodí}
- 15 -
begin if t2tmax then EXIT if t2tmin then A := A+s*t1 end DRAW(A,B) Algoritmus 2.5 – Algoritmus ECB (Efficient Cyrus-Beck)
2.2.3
Algoritmus O(logN)
Algoritmus ECB pracuje správně nezávisle na pořadí hran n-úhelníku. Nastává otázka, zda by nám v případě, že známe pořadí hran, tato informace nějakým způsobem nepomohla k zvýšení efektivity algoritmu. V [1] je popsáno, jak této informace využít pro zvýšení efektivity algoritmu z O(N) na O(logN).
Obr. 2.9: Algoritmus O(logN) (převzat z [1])
Algoritmus je založen na půlení intervalů. Vstupní přímka je dána funkcí F(x), která rozdělí vrcholy polygonu do dvou částí – ty vrcholy, které mají F(x)<0 a ty, které mají F(x)>0 (Obr. 2.9). Algoritmus (Algoritmus 2.6) postupuje tak, že udělá tento znaménkový test na první vrchol n-úheníku a N / 2 vrchol. Tyto dva vrcholy rozdělí n-úhelník na dva řetězce. V každém z nich se hledá hrana, kterou prochází přímka, pomocí půlení intervalů (tedy index k z obr. 2.9 volíme jako N / 2 ). Pak musí algoritmus ještě ošetřit případ, kdy mají oba dva vrcholy stejné znaménko – buď kladné, nebo záporné. V takovémto případě neproběhne prohledání hned napoprvé, ale nejprve se pomocí dalších porovnání vyřadí ten z řetězců, kudy přímka určitě neprochází. Vstup: přímka AB, konvexní polygon o N hranách Značení: F(X)=A*x+B*y+C – obecná rovnice přímky AB, Xi – itý vrchol polygonu, EXIT – konec algoritmu, DRAW(X,Y) – vykresli úsečku XY Algoritmus: i := 0 j := N while(j-i) ≥ 2 do begin k := (i+j)div2 if F(Xi)*F(Xk) < 0 then begin t1 = Solve(i,k)
{nalezni průsečík v části
XiXk }
t2 = Solve(k,j) {nalezni průsečík v části XkXj } {následující 4 řádky platí pouze pro ořezávání úsečky} if t1 > t2 then swap t1,t2 {seřazení aby v t1 bylo min} t1 = max(0,t1) t2 = min(1,t2) if =Ø then EXIT {konec části pro úsečku} DRAW(X(t1),X(t2)) EXIT end if F(Xi) > 0 then if F(Xi) < F(Xk) then if F(X(i+1))
XkXj } {vyřadíme část XiXk } {vyřadíme část
- 16 -
j := k else i := k else {stejné pro F(Xk) > 0} end Funkce Solve(i,j): while j-i ≥ 2 do begin k := (i+j)div2 if F(Xi)*F(Xk)<0 then j := k else i := k Solve := Intersection(p,Xi,Xj)
2.3
{j je vždy ≥ i}
{výběr kde se nachází průsečík} {tam budeme pokračovat}
{už víme hranu – spočítáme průsečík} Algoritmus 2.6: Algoritmus O(logN)
Porovnání metod
Pro ořezávání přímky obdélníkem zde byly vysvětleny čtyři algoritmy – Algoritmus Cohen-Sutherland, jeho rozšíření LSSB, algoritmus Liang-Barsky a jeho rozšíření LSB. Algoritmus LSSB je urychlením základního algoritmu Cohen-Sutherland – nejprve pomocí testů zjistí, se kterou hranou počítat průsečík, a až následně ho vypočítá – tím zamezí zbytečnému dělení, které je v algoritmu CS prováděno v případě, že jeden z krajních bodů úsečky nebo oba dva leží v rozích prostoru vytvořeném hranami obdélníku (obr. 2.1). To zajišťuje zrychlení algoritmu pro tyto případy. Dle [2] dosahuje algoritmus LSSB oproti CS celkového zrychlení 1.08- 2.08. Ohledně stability algoritmus LSSB nepřináší žádné zlepšení. Navíc implementace algoritmu je velmi komplikovaná, ale vzhledem k využitelnosti ořezávacích algoritmů se vyplatí. Přes jejich rychlost neumí ani algoritmus CS, ani LSSB ořezávat přímku. Pro přímku lze využít algoritmu Liang Barsky, který je zefektivněním algoritmu Cyrus-Beck pro případ obdélníku. Liang Barsky se také drží myšlenky nejprve co nejvíce otestovat a pak až vypočítat průsečíky. V algoritmu lze ale stále najít neefektivní místa, kdy se počítá víc průsečíků, než je nutno – proto vznikla jeho modifikace zvaná LSB. Ta zakládá na myšlence testu sklonu přímky vůči sklonu normály – ten jí pomůže určit, se kterými hranami v daném případě průsečík počítat. Dle [1] je tímto postupem algoritmus 1,2-3,0x rychlejší než původní LB. Porovnání rychlostí (jak teoretických, tak praktických) těchto dvojic algoritmů lze nalézt v [1].
3
Homogenní souřadnice
Při použití homogenních souřadnic se pozmění význam použitého značení: Přímka/úsečka teď bude dána body
A = [x1 , y1 , w1 ] , B = [x2 , y 2 , w2 ] T
kde
T
wi <> 0; i = 1,2 . Body ořezané přímky/úsečky pak budeme označovat
[
]
T
[
A' = x1' , y1' , w1' , B ' = x2' , y 2' , w2'
]
T
Přímku/úsečku lze zapsat parametrickou rovnicí
X (t ) = A + (B − A)t
kde pro úsečku
[3.1]
t ∈ 0,1 , pro přímku t ∈ R .
Vzorec 3.1 lze rozepsat po složkách (nelineární parametrizace):
x = x1 + ( x 2 − x1 )t
y = y1 + ( y 2 − y1 )t
w = w1 + (w2 − w1 )t Algoritmy budou počítat s obecnými rovnicemi hran n-úhelníku: a i x + bi y + d i w = 0 i =1,2,…,N kde N je počet hran n-úhelníku. Ty je možno získat pomocí vektorového součinu bodů udávajících danou hranu. Rovnici lze přepsat na kde pi = [ai , bi , di ] a X = [x, y, w] T
piT X = 0
T
- 17 -
[3.2]
3.1
Cyrus-Beck
Myšlenka algoritmu už byla popsána v kapitole 2.2.1. Při použití homogenních souřadnic se poněkud pozmění vlastní výpočet průsečíku: Použijeme značení z úvodu kapitoly 3. Protože chceme spočítat průsečík přímky s hranou n-úhelníku, dosadíme rovnici [3.1] do rovnice [3.2] :
p iT X (t ) = 0
p iT [ A + (B − A)t i ] = 0
piT A + piT (B − A)t i = 0 Pokud z rovnice vyjádříme parametr ti, vznikne:
ti =
− p iT A p iT ( B − A)
[3.3]
Při použití homogenních souřadnic ale dělit nemusíme. Rozdělíme ti do dvou složek (už psáno bez indexu, ale toto dělení proběhne při každém výpočtu ti):
τ = − pT A
[3.4]
τ w = − p T ( B − A) Místo původních tmin a tmax , které používal originální algoritmus Cyrus-Beck, vytvoříme na začátku čtyři proměnné: τ min ,τ min w ,τ max ,τ max w . Po celou dobu výpočtu pak budeme udržovat τ min w ≥ 0,τ max w ≥ 0 . Rozhodnutí, zda průsečík patří mezi ty „vstupující“ do tělesa, nebo „vystupující“, probíhá porovnáním zda τ w < 0 . Pokud tomu tak je, porovnáváme vypočítané τ , τ w s τ min ,τ min w . V opačném případě s τ max ,τ max w . Pro výběr minima proběhne porovnání takto:
τ τ t min = max min , τ min w τ w tedy porovnáváme zda
τ minτ w > ττ min w kde když je podmínka splněna, tak
τ min ,τ min w
přepíšeme hodnotami
τ ,τ w .
Pro výběr maxima:
τ τ t max = min max , τ max w τ w Tedy
τ maxτ w > ττ max w kde když je podmínka splněna, tak
τ max ,τ max w přepíšeme hodnotami τ , τ w .
Na konci potřebujeme zjistit, zda τ min > τ max , τ min > 1, τ max < 0 . V takovýchto případech je přímka
τ min w
τ max w τ min w
τ max w
kompletně vyloučena a není poslána na vykreslení. Aby nedocházelo k dělení, přepíšeme vzorce na následující (protože platí, že τ max w ≥ 0,τ min w ≥ 0 ):
τ min * τ max w > τ max * τ min w τ min > τ min w
- 18 -
τ max < 0 Pokud se přímka touto podmínkou nevyloučí, výsledné body spočítáme následujícím způsobem:
A' = A * τ min w + (B − A) * τ min B ' = B * τ max w + (B − A) * τ max Vstup: přímka AB – A=[x1,y1,w1],B=[x2,y2,w2], konvexní polygon P o N hranách Značení: piX=0 – rovnice hrany polygonu, CONTINUE – pokračuj dalším krokem cyklu, EXIT – konec algoritmu, DRAW(X,Y) – vykresli úsečku XY Algoritmus: tmin := -∞ tminw := 1 tmax := ∞ tmaxw := 1
{pro úsečku bychom položili tmin = 0} {pro úsečku tmax = 1}
for i:=0 to N do begin t := -pi*A tw := pi*(B-A) if tw < 0 then begin if t*tminw > tmin*tw then begin tmin := -t tminw := -tw end end else if t*tmaxw < tmax*tw then begin tmax := t tmaxw := tw end end if(tmin*tmaxw > tmax*tminw) then EXIT
{pro všechny hrany polygonu}
{průsečík, kterým přímka „vstupuje“} {udržujeme tminw > 0}
{průsečík, kterým přímka „vystupuje“}
{pro úsečku navíc podmínky (tmin > tminw)OR(tmax < 0)} {úsečka mimo těleso}
dx := x2-x1 dy := y2-y1 dw := w2-w1 x2 y2 w2 x1 y1 w1
:= := := := := :=
x1*tmaxw y1*tmaxw w1*tmaxw x1*tminw y1*tminw w1*tminw
+ + + + + +
dx*tmax dy*tmax dw*tmax dx*tmin dy*tmin dw*tmin
DRAW(A,B) EXIT Algoritmus 3.1 – Algoritmus Cyrus-Beck pro homogenní souřadnice
- 19 -
3.2
Liang Barsky
Jak již bylo popsáno v kapitole 2.1.3, algoritmus Liang Barsky vychází vzorce pro průsečík přímky s hranou núhelníku (2.3), kam dosadí normály hran obdélníkového okna a vyjádří z něj čtyři nerovnosti (2.1). Použitím homogenních souřadnic se nerovnosti pozmění pro využití w. Místo do vzorce 2.3 teď budeme dosazovat do jeho verze upravené pro homogenní souřadnice – vzorce 3.3. Vzorce pro pi a qi (viz značení v kapitole 2.1.3) teď budou:
ri = p iT s , q i = piT A
[3.6]
kde pi = [nix,niy,d] T, s = [dx,dy,dw] T, A = [x1,y1,w1] T. Po dosazení jednotlivých normál do vzorců 3.6 vyjdou následující vztahy:
= − dx + x min * dw q1 = x1 − x min * w1 = dx − x max * dw q 2 = x max * w1 − x1 = − dy + y min * dw q 3 = y1 − y min * w1 = dy − y max * dw q 4 = y max * w1 − y1 rozdělíme na τ min ,τ min w , τ max ,τ max w stejně jako je popsáno v předchozí kapitole (viz r1 r2 r3 r4
Parametry tmin,tmax
vzorec 3.4. Porovnávání těchto parametrů a následný výpočet bodů (pomocí nelineární parametrizace) je také stejný jako v předchozí kapitole (Pseudokód je uveden v Algoritmus 3.2). Vstup: přímka AB – A=[x1,y1,w1],B=[x2,y2,w2] obdélníkové okno - xmin, xmax, ymin, ymax Značení: EXIT – konec algoritmu DRAW(X,Y) – vykresli úsečku XY Algoritmus: t1 := -∞ t1w := 1 t2 := ∞ t2w := 1 dx := x2-x1 dw := w2-w1
{pro úsečku bychom položili t1 = 0} {pro úsečku t2 = 1}
if TEST(-dx+xmin*dw,x1-xmin*w1,t1,t2,t1w,t2w) then {vlevo} if TEST(dx-xmax*dw,xmax*w1-x1,t1,t2,t1w,t2w) then {vpravo} begin dy := y2-y1 if TEST(-dy+ymin*dw,y1-ymin*w1,t1,t2,t1w,t2w) then {dole} if TEST(dy-ymax*dw,ymax*w1-y1,t1,t2,t1w,t2w) then {nahoře} begin x2 := x1*t2w+dx*t2 y2 := y1*t2w+dy*t2 w2 := w1*t2w+dw*t2 x1 := x1*t1w+dx*t1 y1 := y1*t1w+dy*t1 w1 := w1*t1w+dw*t1 DRAW(A,B) end end Funkce TEST: function TEST (r, q: real; var t1, t2, t1w, t2w: real):boolean {zjisti zda existuje prusecik s touto casti, pripadne ho vypocita} begin TEST:=true if p<0 then {přímka „vstupuje“ do okna} begin {budeme přepisovat t1} if q*t2wt2 – min>max přímka mimo} else if q*t1w 0} t1w := -p end end else if p>0 then {přímka „vystupuje” z okna} begin if q*t1w
- 20 -
begin t2 := q t2w := p end end else if q<0 then TEST:=false {přímka rovnoběžná s hranou + mimo okno} end {of TEST} Algoritmus 3.2: Liang Barsky pro homogenní souřadnice
3.3
Algoritmus O(logN)
Tento algoritmus přepíšeme pro použití homogenních souřadnic jednoduše a s pomocí znalostí popsaných v předchozích kapitolách – rozklad vzorce 3.3 na t a tw, použití nelineární parametrizace. Pseudokód algoritmu se příliš nemění, přesto je pro úplnost ukázán v Algoritmus 3.3. Vstup: přímka AB, konvexní polygon o N hranách Značení: F(X)=A*x+B*y+C*w – obecná rovnice přímky AB, Xi – itý vrchol polygonu, EXIT – konec algoritmu, DRAW(X,Y) – vykresli úsečku XY Algoritmus: i := 0 j := N while(j-i) ≥ 2 do begin k := (i+j)div2 if F(Xi)*F(Xk) < 0 then begin t1 = Solve(i,k)
{nalezni průsečík v části
XiXk }
t2 = Solve(k,j) {nalezni průsečík v části XkXj } {následující 4 řádky platí pouze pro ořezávání úsečky} if t1*t2w > t2*t1w then swap t1,t2 t1w,t2w {seřazení aby v t1 bylo min} t1 = max(0,t1) {v případě vybrání 0 přepíšeme i t1w} t2 = min(1,t2) {porovnáme t2=Ø then EXIT {konec části pro úsečku} DRAW(X(t1),X(t2)) EXIT end if F(Xi) > 0 then if F(Xi) < F(Xk) then if F(X(i+1))
XkXj } {vyřadíme část XiXk } {vyřadíme část
j := k else i := k else if F(Xk) < F(X(k+1)) then j := k else i := k else {stejné pro F(Xk) > 0} end Funkce Solve(i,j):
while j-i ≥ 2 do {j je vždy ≥ i} begin k := (i+j)div2 if F(Xi)*F(Xk)<0 then {výběr kde se nachází průsečík} j := k {tam budeme pokračovat} else i := k end Solve := Intersection(p,Xi,Xj) {už víme hranu – spočítáme průsečík} Algoritmus 3.3: O(logN) při použití homogenních souřadnic
3.4
Shrnutí
Použití homogenních souřadnic přináší do algoritmů stabilitu – nedochází zde k dělení, proto není nebezpečí výskytu dělení nulou. Ohledně složitosti nepřináší žádný velký průlom, sice ubude operace dělení, která je mnohokrát pomalejší než operace násobení, ale operací násobení musíme provádět více (zde už záleží na daném algoritmu). Podrobněji budou složitosti algoritmů probrány v následující kapitole.
- 21 -
4
Odhad složitosti a časová náročnost algoritmů
Protože vzájemné porovnání jednotlivých algoritmů vůči sobě už je uvedeno v [1], zde uvedeme pouze porovnání algoritmů s jejich protějšky v homogenních souřadnicích. V kapitole 3 jsme do homogenních souřadnic přepsali algoritmy Cyrus-Beck, Liang Barsky a O(logN). Proto budou v následujících tabulkách (4.14.3) uvedena porovnání jejich složitostí. Při měření je předpokládán homogenní vstup i výstup, proto mají algoritmy pracujících v Eukleidovském prostoru o 4 dělení navíc (2 dělení pro každý bod definující přímku) Protože algoritmy jsou primárně určeny pro ořezávání přímky, budou testovány na tento případ. Pro testy algoritmů n-úhelníku jsou zváženy jsou následující možnosti (Obr. 4.1): 1) přímka je zcela mimo n-úhelník (l1) 2) přímka je rovnoběžná s jednou z hran a je mimo n-úhelník (stejný případ jako když je totožná s jednou z hran) (l2) 3) přímka protíná n-úhelník ve dvou bodech (l3) Protože algoritmus Cyrus-Beck testuje přímku vůči všem hranám a algoritmus O(logN) prochází polygon půlením intervalů, tak místo, kde dochází k průsečíku (index vrcholů) neovlivňuje výsledný čas – při testech bude počítáno s libovolnou přímkou. Protože algoritmus Liang Barsky pracuje s obdélníkovým oknem na podobné bázi jako Cyrus-Beck s núhelníkem, bude testován na stejných případech (Obr. 4.2) (zde sice na poloze úsečky přímo závisí výsledný počet operací, ale tyto tři případy jsou pro testy dostatečně reprezentativní).
l1
l2
l3
Obr. 4.1: Případy měřené pro algoritmy ořezávající přímku vůči konvexnímu n-úhelníku
l1
l3
l2
Obr. 4.2: Případy měřené pro algoritmy ořezávající přímku vůči obdélníkovému oknu Použité značení: t .. časová jednotka s .. sčítání n .. násobení d .. dělení p .. porovnání pr .. přiřazení T[t] .. výsledný počet časových jednotek
s = 1t n = 1,41229t d = 30,983716t není změřeno, budeme ho tedy uvažovat pouze ve vektorech počtu operací, a ne ve výsledném čase zde platí to samé co pro porovnání
- 22 -
Testování proběhlo na počítači s procesorem Intel® Pentium® 4, 2,8 GHz a operační pamětí 2 GB. Odhad složitostí d l1 n+4 l2 n+4 l3 n+4
n 4n 4n+4 4n+4
CB - Eukl. s p 5n 3n+1 5n+6 3n+1 5n+6 3n+1
pr 3n+2 3n+8 3n+8
T 41,63n+123,92 41,63n+135,57 41,63n+135,57
d 0 0 0
n 8n+2 8n+14 8n+14
s 7n 7n+9 7n+9
CB - Hom. p pr 2n+1 2n+6 2n+1 2n+15 2n+1 2n+15
T 18,3n+2,82 18,3n+28,77 18,3n+28,77
Tcb/Tcbh 2,27 2,27 2,27
Tabulka 4.1: Porovnání algoritmu Cyrus-Beck s jeho homogenní formou – teoretický odhad
Naměřené výsledky CB-Eukl CB-Hom Tcb/Tcbh t[ms] t[ms] 2,59E-04 3,06E-05 8,45 2,56E-04 1,77E-05 14,41 2,88E-04 3,14E-05 9,17 Tabulka 4.2: Porovnání algoritmu Cyrus-Beck s jeho homogenní formou – měření Odhad složitostí d l1 l2 l3
n 5 6 8
s 0 0 4
LB - Eukl. p 2 1 3 4 10 8
pr
T 5 9 13
d 156,9 0 188,9 0 263,48 0
n
s 4 10 36
4 6 17
LB - Hom. p pr 1 7 4 10 8 24
Tcb/Tcbh
T 9,65 20,12 67,84
16,26 9,39 3,88
Tabulka 4.3: Porovnání algoritmu Liang Barsky s jeho homogenní formou - teoretický odhad
Naměřené výsledky LB-Eukl LB-Hom Tcb/Tcbh t[ms] t[ms] 1,33E-04 1,22E-04 1,09 8,58E-05 1,02E-04 0,85 1,42E-04 1,41E-04 1,01 Tabulka 4.4: Porovnání algoritmu Liang Barsky s jeho homogenní formou - měření Odhad složitostí d
n
s 7 7
O(LogN) - Eukl. p pr 6 5 3 6 5 3
T
d 139,79 0 139,79 0
n
s 10 10
O(LogN) - Hom. p pr 6 5 3 6 5 3
Tcb/Tcbh
T
l1 l2
4 4
20,12 20,12
6,95 6,95
l3
2.4 5 14+log(4n) 12+log(4n) 2+log(2n) 10+logn 186,64+2.4log(4n) 0 30+log(6n) 17+log(4n) 3+log(2n) 15+logn 59 . 4 + log( 49 .2 n 2 .4 ) log(49.2n )
2.4 log(4n)
Tabulka 4.5: Porovnání algoritmu O(logN) s jeho homogenní formou – teoretický odhad
Naměřené výsledky O(LogN)-Eukl O(LogN)-Hom Tcb/Tcbh t[ms] t[ms] 7,01E-07 8,32E-07 0,84 6,00E-07 5,65E-07 1,06 6,94E-07 7,64E-07 0,91 Tabulka 4.6: Porovnání algoritmu O(logN) s jeho homogenní formou - měření
V tabulkách s výsledky měření jsou uvedeny průměrné časy naměřené při testování algoritmů. Podrobné výsledky měření lze nalézt v příloze č.1. Z výsledků lze vidět, že homogenní souřadnice přináší urychlení pouze pro případ základního algoritmu CyrusBeck. Vysoké číslo urychlení lze těžko vysvětlit. Možným důvodem by mohl být špatně naměřený čas jedné operace dělení, protože ten ve výsledku hraje velkou roli. Pro algoritmus Liang Barsky by sice dle teoretických složitostí měl být výpočet v homogenních souřadnicích rychlejší, v praxi tomu tak ale není. V algoritmu O(logN) dochází pouze k jednomu dělení, zde použití homogenních souřadnic za účelem urychlení nemá smysl. To lze pozorovat jak na časových poměrech teoretického odhadu, tak na praktickém měření.
- 23 -
5
Implementace
Algoritmy byly implementovány s použitím prostředí Microsoft Visual Studio 2005, v jazyce C#, .NET Framework 2.0. V případě úsečkových algoritmů i přímkových bylo implementováno ořezávání pro úsečku, protože přímkové algoritmy jdou snadno pozměnit pro úsečky a v jejich průběhu přibude pouze na konci test zda by úsečku oříznutím „neprodloužili“ (tedy zda jeden z jejích konců není uvnitř). Homogenní formy byly u všech algoritmů řešeny pomocí nelineární parametrizace, při které použití knihovny PLib [3] nepřináší žádné výrazné změny (je nutno používat typy proměnných Vector3 místo Vector2P). Proto nebyla knihovna PLib v programu použita.
- 24 -
6
Závěr 6.1
Celkové zhodnocení
V práci byla ukázána většina algoritmů ořezávajících přímku (popř. úsečku) konvexním n-úhelníkem (popř. obdélníkem). Některé z nich jsou všeobecně známé (Cyrus-Beck, Liang Barsky), jiné poměrně nové (LSSB, LSB). Pro ořezávání přímky konvexním n-úhelníkem už existují algoritmy pracující v čase O(1). Tato práce se proto nezaměřila přímo na urychlení existujících algoritmů, ale na použití homogenních souřadnic v již existujících algoritmech. Homogenní souřadnice mohou přinést rychlost, neboť složité operace dělení nahrazují několika operacemi násobení. Přesto to není pravidlem, závisí na daném algoritmu, kolik násobení bude při použití homogenních souřadnic potřeba, a zda jich nebude příliš mnoho v porovnání s původním počtem operací dělení. Zde přinesly homogenní souřadnice urychlení pouze pro případ základního algoritmu Cyrus-Beck. Přesto ale přináší do algoritmů velkou výhodu – stabilitu. Vzhledem k chybějícím operacím dělení zde totiž nemůže nastat dělení nulou. Plückerovy souřadnice jsou přínosem ve 3D, kde je lze s výhodou použít např. při metodě ray tracingu, kdy s jejich použitím jednoduše zjistíme, zda přímka protíná daný trojúhelník. Ve 2D ale pomocí postupu výpočtu Plückerových souřadnic (viz [5]) pro přímku získáme její obecnou rovnici, se kterou už algoritmy běžně počítají.
6.2
Další možné směry modifikací, resp. práce
Další směry modifikací by mohly směřovat do ořezávání ve 3D, kde není půda ještě tolik prozkoumána, a kde by i homogenní souřadnice mohly mít velké uplatnění.
7
Literatura
[1] Bui, D.H.: Algorithms for Line Clipping and Their Complexity. Dissertation thesis, University of West Bohemia in Pilsen, 1999. [2] Bui, D.H., Skala, V.: Fast Modifications of Cohen-Sutherland algorithm for Line Segment and Line Clipping in E2, SCCG’97 International Conference Proceedings, pp. 205-212, 1997. [3] Kaiser,J.,Ondracka,V.: ZcuMathUtils.dll [4] Pelikán, J.: Ořezávání v rovině. Materiál k přednáškám KSVI MFF UK Praha, 2001. [5] Shoemake,K: Plücker Coordinate Tutoriál,Ray Tracing News, vol.11/1, 1998.
- 25 -
Příloha 1: Naměřené výsledky V tabulkách je použita hodnota N: pro algoritmus Liang Barsky má význam počtu přímek, pro algoritmy CyrusBeck a O(logN) má význam N = n*m, kde n je počet vrcholů n-úhelníku (zvoleno konstantně 1000) a m je počet přímek. Prázdná místa v tabulce jsou u algoritmu O(logN) v místech, kde jsou pro měření příliš malé vstupy a došlo by k nepřesnosti. CB N t[ms] průměrný 1000000 281 2,81E-04 1600000 531 3,32E-04 2500000 828 3,31E-04 4000000 1266 3,17E-04 6300000 1875 2,98E-04 10000000 2625 2,63E-04 16000000 5390 3,37E-04 25000000 8188 3,28E-04 40000000 10344 2,59E-04 63000000 16250 2,58E-04 100000000 25781 2,58E-04 160000000 41250 2,58E-04 250000000 64453 2,58E-04 400000000 103125 2,58E-04 2,88E-04
t[ms] 172 203 437 671 859 1359 2453 3297 5219 8281 13094 20937 32797 52468
LB LOGN CBH průměrný t[ms] průměrný t[ms] průměrný 1,72E-04 32 3,20E-05 1,27E-04 63 3,94E-05 1,75E-04 78 3,12E-05 1,68E-04 157 3,93E-05 1,36E-04 188 2,98E-05 1,36E-04 281 2,81E-05 1,53E-04 16 1,00E-06 625 3,91E-05 1,32E-04 15 6,00E-07 719 2,88E-05 1,30E-04 31 7,75E-07 1140 2,85E-05 1,31E-04 32 5,08E-07 1828 2,90E-05 1,31E-04 63 6,30E-07 2859 2,86E-05 1,31E-04 110 6,88E-07 4609 2,88E-05 1,31E-04 172 6,88E-07 7171 2,87E-05 1,31E-04 266 6,65E-07 11484 2,87E-05 1,42E-04 6,94E-07 3,14E-05 Tabulka 1: Přímka protíná n-úhelník
LBH LOGNH t[ms] průměrný t[ms] průměrný 187 1,87E-04 266 1,66E-04 375 1,50E-04 609 1,52E-04 781 1,24E-04 1313 1,31E-04 2891 1,81E-04 15 9,38E-07 3062 1,22E-04 16 6,40E-07 4860 1,22E-04 31 7,75E-07 7687 1,22E-04 47 7,46E-07 12219 1,22E-04 78 7,80E-07 24141 1,51E-04 125 7,81E-07 30516 1,22E-04 188 7,52E-07 48985 1,22E-04 281 7,03E-07 1,41E-04 7,64E-07
CB LB LOGN CBH LBH LOGNH N t[ms] průměrný t[ms] průměrný t[ms] průměrný t[ms] průměrný t[ms] průměrný t[ms] průměrný 1000000 266 2,66E-04 78 7,80E-05 15 1,50E-05 110 1,10E-04 1600000 390 2,44E-04 141 8,81E-05 31 1,94E-05 172 1,08E-04 2500000 688 2,75E-04 203 8,12E-05 32 1,28E-05 250 1,00E-04 4000000 1016 2,54E-04 344 8,60E-05 78 1,95E-05 390 9,75E-05 6300000 1579 2,51E-04 546 8,67E-05 109 1,73E-05 625 9,92E-05 10000000 2594 2,59E-04 875 8,75E-05 188 1,88E-05 1015 1,02E-04 16000000 4359 2,72E-04 1422 8,89E-05 281 1,76E-05 1750 1,09E-04 25000000 6406 2,56E-04 2219 8,88E-05 31 1,24E-06 516 2,06E-05 2484 9,94E-05 16 6,40E-07 40000000 10031 2,51E-04 3453 8,63E-05 16 4,00E-07 719 1,80E-05 3984 9,96E-05 16 4,00E-07 63000000 15765 2,50E-04 5391 8,56E-05 31 4,92E-07 1125 1,79E-05 6297 1,00E-04 31 4,92E-07 100000000 25047 2,50E-04 8625 8,63E-05 47 4,70E-07 1781 1,78E-05 9938 9,94E-05 62 6,20E-07 160000000 40047 2,50E-04 13766 8,60E-05 78 4,88E-07 2859 1,79E-05 15875 9,92E-05 94 5,88E-07 250000000 62594 2,50E-04 21562 8,62E-05 141 5,64E-07 4531 1,81E-05 24828 9,93E-05 157 6,28E-07 400000000 100218 2,51E-04 34344 8,59E-05 219 5,48E-07 7109 1,78E-05 39860 9,97E-05 234 5,85E-07 2,56E-04 8,58E-05 6,00E-07 1,77E-05 1,02E-04 5,65E-07 Tabulka 2: Přímka je rovnoběžná s jednou z hran n-úhelníku a neprotíná ho CB N
t[ms]
průměrný
LB t[ms]
průměrný
LOGN t[ms] průměrný
CBH t[ms]
průměrný
LBH t[ms]
průměrný
LOGNH t[ms] průměrný
1000000
266
2,66E-04
125
1,25E-04
47
4,70E-05
125
1,25E-04
1600000
406
2,54E-04
219
1,37E-04
46
2,88E-05
188
1,18E-04
2500000
672
2,69E-04
375
1,50E-04
78
3,12E-05
312
1,25E-04
4000000
1032
2,58E-04
531
1,33E-04
125
3,13E-05
484
1,21E-04
6300000
1641
2,60E-04
828
1,31E-04
188
2,98E-05
765
1,21E-04
10000000
2562
2,56E-04
1328
1,33E-04
297
2,97E-05
1219
1,22E-04
16000000
4125
2,58E-04
2109
1,32E-04
16
1,00E-06
453
2,83E-05
1969
1,23E-04
16
25000000
6437
2,57E-04
3281
1,31E-04
16
6,40E-07
719
2,88E-05
3062
1,22E-04
16
6,40E-07
40000000
10312
2,58E-04
5266
1,32E-04
31
7,75E-07
1156
2,89E-05
4860
1,22E-04
31
7,75E-07
1,00E-06
63000000
16250
2,58E-04
8266
1,31E-04
47
7,46E-07
1828
2,90E-05
7672
1,22E-04
62
9,84E-07
100000000
25750
2,58E-04 13141
1,31E-04
62
6,20E-07
2891
2,89E-05 12156
1,22E-04
78
7,80E-07
160000000
41219
2,58E-04 20969
1,31E-04
93
5,81E-07
4657
2,91E-05 19406
1,21E-04
141
8,81E-07
250000000
64437
2,58E-04 32797
1,31E-04
156
6,24E-07
7281
2,91E-05 30485
1,22E-04
203
8,12E-07
400000000 103016
2,58E-04 52546
1,31E-04
250
6,25E-07 11547
2,89E-05 48719
1,22E-04
313
7,83E-07
2,59E-04
1,33E-04
7,01E-07
3,06E-05
1,22E-04
- 26 -
8,32E-07
s
Tabulka 3: Přímka míjí n-úhelník
- 27 -
