第五部分圖形變換與裁剪三

1、計(jì)算機(jī)學(xué)院蘇小紅xxxminmaxyyyminmaxpxyp xy000111(,)(,)為提高效率，算法設(shè)計(jì)時(shí)應(yīng)考慮：為提高效率，算法設(shè)計(jì)時(shí)應(yīng)考慮：1. 快速判斷情形快速判斷情形(1)(2)；2. 設(shè)法減少情形設(shè)法減少情形(3)求交次數(shù)和每次求交時(shí)所需的計(jì)算量求交次數(shù)和每次求交時(shí)所需的計(jì)算量(編碼算法)算法步驟：算法步驟：第一步第一步 判別線段兩端點(diǎn)是否都落在窗口內(nèi)，如果是，判別線段兩端點(diǎn)是否都落在窗口內(nèi)，如果是， 則線段完全可見(jiàn)；否則進(jìn)入第二步；則線段完全可見(jiàn)；否則進(jìn)入第二步；第二步第二步 判別線段是否為顯然不可見(jiàn)，如果是，則裁判別線段是否為顯然不可見(jiàn)，如果是，則裁 剪結(jié)束；否則進(jìn)行第三步

2、剪結(jié)束；否則進(jìn)行第三步 ；第三步第三步 求線段與窗口邊延長(zhǎng)線的交點(diǎn)，這個(gè)交點(diǎn)將求線段與窗口邊延長(zhǎng)線的交點(diǎn)，這個(gè)交點(diǎn)將 線段分為兩段，其中一段顯然不可見(jiàn)，丟棄。線段分為兩段，其中一段顯然不可見(jiàn)，丟棄。 對(duì)余下的另一段重新進(jìn)行第一步，第二步判斷，對(duì)余下的另一段重新進(jìn)行第一步，第二步判斷， 直至結(jié)束直至結(jié)束 裁剪過(guò)程是遞歸的。elseyyct0max1當(dāng)elsexxcr0max1當(dāng)elsexxcl0min1當(dāng)elseyycb0min1當(dāng)100000010010000001001001010101101010窗口bca對(duì)于那些非完全可見(jiàn)、又非完全不可見(jiàn)的線段，需要對(duì)于那些非完全可見(jiàn)、又非完全不可見(jiàn)的線

3、段，需要求交求交，求交前，求交前先測(cè)試先測(cè)試與窗口哪條邊所在直線有交？與窗口哪條邊所在直線有交？(按序判斷端點(diǎn)編碼中各位的值按序判斷端點(diǎn)編碼中各位的值clctcrcb） 1）特點(diǎn)：用編碼方法可快速判斷線段特點(diǎn)：用編碼方法可快速判斷線段- 完全可見(jiàn)和顯然不可見(jiàn)。完全可見(jiàn)和顯然不可見(jiàn)。 2）特別適用二種場(chǎng)合：）特別適用二種場(chǎng)合： 大窗口場(chǎng)合大窗口場(chǎng)合 窗口特別小的場(chǎng)合窗口特別小的場(chǎng)合 中點(diǎn)分割法p2p1 p2是離是離p1點(diǎn)最遠(yuǎn)的可見(jiàn)點(diǎn)點(diǎn)最遠(yuǎn)的可見(jiàn)點(diǎn)pmp1用用p1pm代替代替p1p2p2p2用用pmp2代替代替p1p2pmp1 p4p1p3p2ymaxyminxminxmaxrtsulabas是一

4、維窗口是一維窗口ts中的可見(jiàn)部分中的可見(jiàn)部分q,;,;,maxminmaxmin4321yyxxlppppl口),;,(),;,(maxminmaxminyylxxlturs p4p1p3p2ymaxyminxminxmaxrtsulabas是一維窗口是一維窗口ts中的可見(jiàn)部分中的可見(jiàn)部分tursab),max(),max(,min),min(),min(,maxmaxminutbautbaxxxxxxxxxxx),max(),max(,min),min(),min(,maxmaxminutbautbaxxxxxxxxxxxx左端點(diǎn)左端點(diǎn)右端點(diǎn)右端點(diǎn)),max(),max(,min),min(

5、),min(,maxmaxminutbautbaxxxxxxxxxx),min(,maxminbaxxxl ),max(,minmaxbaxxxr rxxxxlrlutut),min(),max(多邊形裁剪-1/2圖圖1 因丟失頂點(diǎn)信息而去法確定裁剪區(qū)域因丟失頂點(diǎn)信息而去法確定裁剪區(qū)域abab圖圖2 原來(lái)封閉的多邊形變成了孤立的線段原來(lái)封閉的多邊形變成了孤立的線段邊界不再封閉，需要用窗口邊界的恰當(dāng)部分來(lái)封閉它邊界不再封閉，需要用窗口邊界的恰當(dāng)部分來(lái)封閉它12123(a)(b)(c)ab圖圖3 裁剪后的多邊形頂點(diǎn)形成的幾種情況裁剪后的多邊形頂點(diǎn)形成的幾種情況分裂為幾個(gè)多邊形分裂為幾個(gè)多邊形多邊形

6、裁剪-2/2sutherland-hodgman算法-1/4：亦稱亦稱逐邊裁剪算法逐邊裁剪算法sutherland-hodgman算法-2/4 線段與當(dāng)前裁剪邊的位置關(guān)系線段與當(dāng)前裁剪邊的位置關(guān)系可見(jiàn)一側(cè)可見(jiàn)一側(cè)窗口窗口(a) 輸出輸出pi+1當(dāng)前裁剪邊pi+1pi可見(jiàn)一側(cè)可見(jiàn)一側(cè)窗口窗口(a) 無(wú)輸出無(wú)輸出當(dāng)前裁剪邊pi+1pi可見(jiàn)一側(cè)可見(jiàn)一側(cè)窗口窗口(a) 輸出輸出i當(dāng)前裁剪邊pi+1pi可見(jiàn)一側(cè)可見(jiàn)一側(cè)窗口窗口(a) 輸出輸出i和和pi+1當(dāng)前裁剪邊pi+1pisutherland-hodgman算法-3/4：優(yōu)點(diǎn)：優(yōu)點(diǎn)：裁剪算法采用流水線方式，適合硬件實(shí)現(xiàn)。裁剪算法采用流水線方式，適合

7、硬件實(shí)現(xiàn)?？赏茝V到任意凸多邊形裁剪窗口可推廣到任意凸多邊形裁剪窗口sutherland-hodgman算法-4/4存在的問(wèn)題圖6 逐邊裁剪法對(duì)凹多邊形裁剪時(shí)可能出現(xiàn)的問(wèn)題321876954103217654108932174108956原圖對(duì)左邊裁對(duì)頂邊裁32174108956對(duì)右邊裁對(duì)底邊裁c2c1c3c4c8c7c5c6i1i8i2i3i4i5i6i7裁剪結(jié)果區(qū)域的邊界由裁剪結(jié)果區(qū)域的邊界由sp的部分邊界和的部分邊界和cp的部分邊界兩部分構(gòu)成，并且在交點(diǎn)的部分邊界兩部分構(gòu)成，并且在交點(diǎn)處邊界發(fā)生交替，即由處邊界發(fā)生交替，即由sp的邊界轉(zhuǎn)至的邊界轉(zhuǎn)至cp的邊界，或由的邊界，或由cp的邊界轉(zhuǎn)至的邊界轉(zhuǎn)至sp的邊界的邊界 c2c1c3c4s1s2s3s4s5s6i1i2i3i4i5i6i7i8裁剪多邊形cp主多邊形sp算法裁剪后所生成的多邊形為算法裁剪后所生成的多邊形為i1i2i3s3i4i5i6i7s6i8 i1主多邊形表裁剪多邊形表s1s2i1s3s4s5s6i2i3i4i5i6i7i8c1c2i3i4c4i8i1i2i5c3i5i6s1i7c1開(kāi)始結(jié)束c2c1c3c4c8c7c5c6s2s1s3s4s8s7s5s6i1i8i2i3i4i5i6i7主多邊形表裁剪多邊形表s1s2i1i4s4s6i5