計(jì)算機(jī)圖形學(xué)二維圖形裁剪第1頁(yè)，課件共44頁(yè)，創(chuàng)作于2023年2月第2頁(yè)，課件共44頁(yè)，創(chuàng)作于2023年2月主要內(nèi)容1.點(diǎn)的裁剪2.直線的裁剪3.多邊形的裁剪4.字符的裁剪第3頁(yè)，課件共44頁(yè)，創(chuàng)作于2023年2月1.點(diǎn)的裁剪

設(shè)窗口由x=xL,x=xR,y=yB,y=yT圍成。對(duì)于點(diǎn)(x,y)判別兩對(duì)不等式：xL<=x<=xR，yB<=y<=yT；若四個(gè)不等式均成立，則點(diǎn)在窗口之內(nèi)；否則，點(diǎn)在窗口之外。最簡(jiǎn)單的裁剪方法是把各種圖形掃描轉(zhuǎn)換為點(diǎn)之后，再判斷各點(diǎn)是否在窗內(nèi)。但那樣太費(fèi)時(shí)，一般不可取。這是因?yàn)橛行﹫D形組成部分全部在窗口外，可以完全排除，不必進(jìn)行掃描轉(zhuǎn)換。所以一般采用先裁剪再掃描轉(zhuǎn)換的方法。第4頁(yè)，課件共44頁(yè)，創(chuàng)作于2023年2月2.直線段裁剪直線段裁剪算法比較簡(jiǎn)單，但非常重要，是復(fù)雜圖元裁剪的基礎(chǔ)。因?yàn)閺?fù)雜的曲線可以通過(guò)折線段來(lái)近似，從而裁剪問(wèn)題也可以化為直線段的裁剪問(wèn)題。常用的線段裁剪方法有三種：Cohen-Sutherland，中點(diǎn)分割算法和參數(shù)化算法。第5頁(yè)，課件共44頁(yè)，創(chuàng)作于2023年2月Cohen-Sutherland裁剪算法該算法的思想是：對(duì)于每條線段P1P2分為三種情況處理。（1）若P1P2完全在窗口內(nèi)，則顯示該線段P1P2簡(jiǎn)稱“取”之。（2）若P1P2明顯在窗口外，則丟棄該線段，簡(jiǎn)稱“棄”之。（3）若線段既不滿足“取”的條件，也不滿足“棄”的條件，則在交點(diǎn)處把線段分為兩段。其中一段完全在窗口外，可棄之。然后對(duì)另一段重復(fù)上述處理。第6頁(yè)，課件共44頁(yè)，創(chuàng)作于2023年2月第7頁(yè)，課件共44頁(yè)，創(chuàng)作于2023年2月問(wèn)題：如何判斷線段與窗口的關(guān)系？為使計(jì)算機(jī)能夠快速判斷一條直線段與窗口屬何種關(guān)系，采用如下編碼方法。延長(zhǎng)窗口的邊，將二維平面分成九個(gè)區(qū)域。每個(gè)區(qū)域賦予4位編碼CtCbCrCl.其中各位編碼的定義如下：<第8頁(yè)，課件共44頁(yè)，創(chuàng)作于2023年2月第9頁(yè)，課件共44頁(yè)，創(chuàng)作于2023年2月裁剪一條線段時(shí)，先求出P1P2所在的區(qū)號(hào)code1,code2。若code1=0,且code2=0，則線段P1P2在窗口內(nèi)，應(yīng)取之。若按位與運(yùn)算code1&code2≠0，則說(shuō)明兩個(gè)端點(diǎn)同在窗口的上方、下方、左方或右方?？膳袛嗑€段完全在窗口外，可棄之。否則，按第三種情況處理。求出線段與窗口某邊的交點(diǎn)，在交點(diǎn)處把線段一分為二，其中必有一段在窗口外，可棄之。在對(duì)另一段重復(fù)上述處理。在實(shí)現(xiàn)本算法時(shí)，不必把線段與每條窗口邊界依次求交，只要按順序檢測(cè)到端點(diǎn)的編碼不為0，才把線段與對(duì)應(yīng)的窗口邊界求交。Cohen-Sutherland裁剪算法步驟：第10頁(yè)，課件共44頁(yè)，創(chuàng)作于2023年2月第11頁(yè)，課件共44頁(yè)，創(chuàng)作于2023年2月已知直線：（X1，Y1）（X2，Y2）與水平線Y＝K的交點(diǎn)為：

與垂直直線X＝R的交點(diǎn)為：

第12頁(yè)，課件共44頁(yè)，創(chuàng)作于2023年2月

在進(jìn)行裁剪是除了要求直線與邊界線的交點(diǎn)外，還要判斷端點(diǎn)與窗口的位置關(guān)系。為此有：若編碼&0001<>0，端點(diǎn)與左邊界有交點(diǎn)；若編碼&0010<>0，端點(diǎn)與右邊界有交點(diǎn)；若編碼&0100<>0，端點(diǎn)與下邊界有交點(diǎn)；若編碼&1000<>0，端點(diǎn)與上邊界有交點(diǎn)；第13頁(yè)，課件共44頁(yè)，創(chuàng)作于2023年2月Cohen-Sutherland裁剪如何判定應(yīng)該與窗口的哪條邊求交呢？ 編碼中對(duì)應(yīng)位為1的邊。計(jì)算線段P1(x1,y1)P2(x2,y2)與窗口邊界的交點(diǎn)

if(LEFT&code!=0) { x=XL; y=y1+(y2-y1)*(XL-x1)/(x2-x1);} elseif(RIGHT&code!=0) { x=XR; y=y1+(y2-y1)*(XR-x1)/(x2-x1);} elseif(BOTTOM&code!=0){ y=YB; x=x1+(x2-x1)*(YB-y1)/(y2-y1);}elseif(TOP&code!=0){ y=YT; x=x1+(x2-x1)*(YT-y1)/(y2-y1);}第14頁(yè)，課件共44頁(yè)，創(chuàng)作于2023年2月算法偽代碼#defineLEFT1#defineRIGHT2#defineBOTTOM4#defineTOP8intencode(floatx,floaty){intc=0;

if(x<XL)c|=LEFT;

if(x>XR)c|=RIGHT;

if(x<YB)c|=BOTTOM;

if(x<YT)c|=TOP;

retrunc;}第15頁(yè)，課件共44頁(yè)，創(chuàng)作于2023年2月void

CS_LineClip(x1,y1,x2,y2,XL,XR,YB,YT)floatx1,y1,x2,y2,XL,XR,YB,YT;//(x1,y1)(x2,y2)為線段端點(diǎn)坐標(biāo)，其他參數(shù)定義窗口邊界{intcode1,code2,code;

code1=encode(x1,y1);

code2=encode(x2,y2);

while(code1!=0||code2!=0)

{if(code1&code2!=0)return;

code=code1;

if(code1==0)code=code2;

if(LEFT&code!=0)

{x=XL;

y=y1+(y2-y1)*(XL-x1)/(x2-x1);}

第16頁(yè)，課件共44頁(yè)，創(chuàng)作于2023年2月elseif(RIGHT&code!=0)

{x=XR;

y=y1+(y2-y1)*(XR-x1)/(x2-x1);

}

elseif(BOTTOM&code!=0)

{y=YB;x=x1+(x2-x1)*(YB-y1)/(y2-y1);}elseif(TOP&code!=0){y=YT;

x=x1+(x2-x1)*(YT-y1)/(y2-y1);}

if(code==code1){

x1=x;y1=y;code1=encode(x,y);}else{x2=x;y2=y;code2=encode(x,y);}

}

displayline（x1,y1,x2,y2);}第17頁(yè)，課件共44頁(yè)，創(chuàng)作于2023年2月第18頁(yè)，課件共44頁(yè)，創(chuàng)作于2023年2月Cohen-Sutherland

直線裁剪算法小結(jié)本算法的優(yōu)點(diǎn)在于簡(jiǎn)單，易于實(shí)現(xiàn)。他可以簡(jiǎn)單的描述為將直線在窗口左邊的部分刪去，按左，右，下，上的順序依次進(jìn)行，處理之后，剩余部分就是可見(jiàn)的了。在這個(gè)算法中求交點(diǎn)是很重要的，他決定了算法的速度。特點(diǎn)：用編碼方法可快速判斷線段的完全可見(jiàn)和顯然不可見(jiàn)。第19頁(yè)，課件共44頁(yè)，創(chuàng)作于2023年2月中點(diǎn)分割裁剪算法基本思想：從P0點(diǎn)出發(fā)找出離P0最近的可見(jiàn)點(diǎn)，和從P1點(diǎn)出發(fā)找出離P1最近的可見(jiàn)點(diǎn)。這兩個(gè)可見(jiàn)點(diǎn)的連線就是原線段的可見(jiàn)部分。與Cohen-Sutherland算法一樣首先對(duì)線段端點(diǎn)進(jìn)行編碼，并把線段與窗口的關(guān)系分為三種情況，對(duì)前兩種情況，進(jìn)行一樣的處理；對(duì)于第三種情況，用中點(diǎn)分割的方法求出線段與窗口的交點(diǎn)。A、B分別為距P0

、P1最近的可見(jiàn)點(diǎn)，Pm為P0P1中點(diǎn)。

第20頁(yè)，課件共44頁(yè)，創(chuàng)作于2023年2月中點(diǎn)分割算法-求線段與窗口的交點(diǎn)從P0出發(fā)找距離P0最近可見(jiàn)點(diǎn)采用中點(diǎn)分割方法先求出P0P1的中點(diǎn)Pm,若P0Pm不是顯然不可見(jiàn)的，并且P0P1在窗口中有可見(jiàn)部分，則距P0最近的可見(jiàn)點(diǎn)一定落在P0Pm上，所以用P0Pm代替P0P1；否則取PmP1代替P0P1。再對(duì)新的P0P1求中點(diǎn)Pm。重復(fù)上述過(guò)程，直到PmP1長(zhǎng)度小于給定的控制常數(shù)為止，此時(shí)Pm收斂于交點(diǎn)。從P1出發(fā)找距離P1最近可見(jiàn)點(diǎn)采用上面類似方法。第21頁(yè)，課件共44頁(yè)，創(chuàng)作于2023年2月對(duì)分辯率為2N*2N的顯示器，上述二分過(guò)程至多進(jìn)行N次。主要過(guò)程只用到加法和除法運(yùn)算，適合硬件實(shí)現(xiàn)，它可以用左右移位來(lái)代替乘除法，這樣就大大加快了速度。中點(diǎn)分割裁剪算法第22頁(yè)，課件共44頁(yè)，創(chuàng)作于2023年2月參數(shù)化算法(Cyrus-Beck)考慮凸多邊形區(qū)域R和直線段P1P2 P(t)=(P2-P1)*t+P1設(shè)A是區(qū)域R的邊界上一點(diǎn)，N是區(qū)域邊界在A點(diǎn)的內(nèi)法線向量AP2RNP1第23頁(yè)，課件共44頁(yè)，創(chuàng)作于2023年2月參數(shù)化算法(Cyrus-Beck)則對(duì)于線段P1P2上任一點(diǎn)P(t)N·(P(t)-A)<0->外側(cè)N·(P(t)-A)>0->內(nèi)側(cè)N·(P(t)-A)=0->邊界或其延長(zhǎng)線上AP2RNP1第24頁(yè)，課件共44頁(yè)，創(chuàng)作于2023年2月參數(shù)化算法(Cyrus-Beck)凸多邊形的性質(zhì)：點(diǎn)P(t)在凸多邊形內(nèi)的充要條件是，對(duì)于凸多邊形邊界上任意一點(diǎn)A和該點(diǎn)處內(nèi)法向N，都有

N·(P(t)-A)>0第25頁(yè)，課件共44頁(yè)，創(chuàng)作于2023年2月參數(shù)化算法(Cyrus-Beck)k條邊的多邊形，可見(jiàn)線段參數(shù)區(qū)間的解:Ni·(p(t)-Ai)>=0,i=0,…,k,0≤t≤1.即：Ni·(P1-Ai)+Ni·(P2-P1)t>=0(1)式可得：

令ti=Ni·(P1-Ai)/[Ni·(P2-P1)]第26頁(yè)，課件共44頁(yè)，創(chuàng)作于2023年2月參數(shù)化算法(Cyrus-Beck)Ni·(P2-P1)=0->平行于對(duì)應(yīng)邊。此時(shí)判斷Ni·(P1-Ai)若Ni·(P1-Ai)<0->P1P2在多邊形外側(cè)->不可見(jiàn)，若Ni·(P1-Ai)>0->P1P2在多邊形內(nèi)側(cè)->繼續(xù)其它邊的判斷第27頁(yè)，課件共44頁(yè)，創(chuàng)作于2023年2月參數(shù)化算法(Cyrus-Beck)對(duì)于t值的選擇：首先，要符合0≤t≤1；其次，對(duì)于凸窗口來(lái)說(shuō)，每一個(gè)線段與其至多有兩個(gè)交點(diǎn)，即有兩個(gè)相應(yīng)的t值。所以我們可以把計(jì)算出的t值分成兩組：一組為下限組，是分布在線段起點(diǎn)一側(cè)的；一組為上限組，是分布在線段終點(diǎn)一側(cè)的。這樣，只要找出下限組中的最大值及上限組中的最小值，就可確定線段了。分組的依據(jù)是：如果Ni·(P2-P1)＜0，則計(jì)算出的值屬于上限組如果Ni·(P2-P1)＞0，則計(jì)算出的值屬于下限組第28頁(yè)，課件共44頁(yè)，創(chuàng)作于2023年2月下限上限P1P2參數(shù)化算法的幾何意義下限組以Ni·(P2-P1)>0為特征，表示在該處沿P1P2方向前進(jìn)將接近或進(jìn)入多邊形內(nèi)側(cè)。上限組以Ni·(P2-P1)<0為特征，表示在該處沿P1P2方向前進(jìn)將越來(lái)越遠(yuǎn)地離開(kāi)多邊形區(qū)域。第29頁(yè)，課件共44頁(yè)，創(chuàng)作于2023年2月參數(shù)化算法(Cyrus-Beck)因此，線段可見(jiàn)的交點(diǎn)參數(shù)：tl=max{0,max{ti:Ni·(P2-P1)>0}}tu=min{1,min{ti:Ni·(P2-P1)<0}}若tl<=tu,[tl

，tu]是可見(jiàn)線段的交點(diǎn)參數(shù)區(qū)間，否則，線段不可見(jiàn)。第30頁(yè)，課件共44頁(yè)，創(chuàng)作于2023年2月參數(shù)化算法當(dāng)凸多邊形是矩形窗口且矩形的邊與坐標(biāo)軸平行時(shí)，該算法退化為L(zhǎng)iang-Barsky算法。第31頁(yè)，課件共44頁(yè)，創(chuàng)作于2023年2月Liang-Barsky算法所用的量第32頁(yè)，課件共44頁(yè)，創(chuàng)作于2023年2月voidLB_LineClip(p1,p2,tmin,tmax,visible)floatp1[2],p2[2],y2,XL,XR,YB,YT;{floatdx,dy,u1,u2;

tl=0;tu=1;

dx=x2-x1;

dy=y2-y1;

if(ClipT(-dx,x1-Xl,&u1,&u2)

if(ClipT(dx,XR-x1,&u1,&u2)if(ClipT(-dy,y1-YB,&u1,&u2)

if(ClipT(dy,YT-y1,&u1,&u2){displayline(x1+u1*dx,y1+u1*dy,x1+u2*dx,y1+u2*dy)

return;

}}第33頁(yè)，課件共44頁(yè)，創(chuàng)作于2023年2月boolClipT(p,q,u1,u2)floatp,q,*u1,*u2;{floatr;

if(p<0)

{r=q/p;

if(r>*u2)returnFALSE;

elseif(r>*u1)

{*u1=r;

returnTRUE;

}

}

第34頁(yè)，課件共44頁(yè)，創(chuàng)作于2023年2月elseif(p>0)

{r=p/q;

if(r<*u1)returnFALSE;

elseif(r<*u2)

{*u2=r;

returnTRUE;

}

}

elseif(q<0)returnFALSE;

returnTRUE;}第35頁(yè)，課件共44頁(yè)，創(chuàng)作于2023年2月3.多邊形裁剪ABCDEF第36頁(yè)，課件共44頁(yè)，創(chuàng)作于2023年2月錯(cuò)覺(jué)：多邊形裁剪是直線段裁剪的組合？新的問(wèn)題：1)邊界不再封閉，需要用窗口邊界的恰當(dāng)部分來(lái)封閉它，如何確定其邊界？第37頁(yè)，課件共44頁(yè)，創(chuàng)作于2023年2月2）一個(gè)凹多邊形可能被裁剪成幾個(gè)小的多邊形，如何確定這些小多邊形的邊界？第38頁(yè)，課件共44頁(yè)，創(chuàng)作于2023年2月Sutherland-Hodgman算法分割處理策略：將多邊形關(guān)于矩形窗口的裁剪分解為多邊形關(guān)于窗口四邊所在直線的裁剪。流水線過(guò)程(左上右下)：前邊的結(jié)果是后邊的輸入。亦稱逐邊裁剪算法第39頁(yè)，課件共44頁(yè)，創(chuàng)作于2023年2月基本思想是一次用窗口的一條邊裁剪多邊形。這里明確一點(diǎn):多邊形用頂點(diǎn)序列表示，被窗口的一條邊裁剪后，仍為多邊形，仍用頂點(diǎn)序列表示，裁剪的結(jié)果就是一系列的頂點(diǎn)?？紤]窗口的一條邊以及延長(zhǎng)線構(gòu)成的裁剪線,

該線把平面分成兩個(gè)部分:可見(jiàn)一側(cè)；不可見(jiàn)一側(cè);多邊形的各條邊的兩端點(diǎn)S、P。它們與裁剪線的位置關(guān)系只有四種第40頁(yè)，課件共44頁(yè)，創(chuàng)作于2023年2月Sutherland-Hodgman算法情況（1）僅輸出頂點(diǎn)P；情況（2）輸出0個(gè)頂點(diǎn)；情況（3）輸出線段SP與裁剪線的交點(diǎn)I；