計算機圖形學二維圖形裁剪第1頁，課件共44頁，創作于2023年2月第2頁，課件共44頁，創作于2023年2月主要內容1.點的裁剪2.直線的裁剪3.多邊形的裁剪4.字符的裁剪第3頁，課件共44頁，創作于2023年2月1.點的裁剪

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

與垂直直線X＝R的交點為：

第12頁，課件共44頁，創作于2023年2月

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

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頁，課件共44頁，創作于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頁，課件共44頁，創作于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)為線段端點坐標，其他參數定義窗口邊界{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頁，課件共44頁，創作于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頁，課件共44頁，創作于2023年2月第18頁，課件共44頁，創作于2023年2月Cohen-Sutherland

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

、P1最近的可見點，Pm為P0P1中點。

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

N·(P(t)-A)>0第25頁，課件共44頁，創作于2023年2月參數化算法(Cyrus-Beck)k條邊的多邊形，可見線段參數區間的解: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頁，課件共44頁，創作于2023年2月參數化算法(Cyrus-Beck)Ni·(P2-P1)=0->平行于對應邊。此時判斷Ni·(P1-Ai)若Ni·(P1-Ai)<0->P1P2在多邊形外側->不可見，若Ni·(P1-Ai)>0->P1P2在多邊形內側->繼續其它邊的判斷第27頁，課件共44頁，創作于2023年2月參數化算法(Cyrus-Beck)對于t值的選擇：首先，要符合0≤t≤1；其次，對于凸窗口來說，每一個線段與其至多有兩個交點，即有兩個相應的t值。所以我們可以把計算出的t值分成兩組：一組為下限組，是分布在線段起點一側的；一組為上限組，是分布在線段終點一側的。這樣，只要找出下限組中的最大值及上限組中的最小值，就可確定線段了。分組的依據是：如果Ni·(P2-P1)＜0，則計算出的值屬于上限組如果Ni·(P2-P1)＞0，則計算出的值屬于下限組第28頁，課件共44頁，創作于2023年2月下限上限P1P2參數化算法的幾何意義下限組以Ni·(P2-P1)>0為特征，表示在該處沿P1P2方向前進將接近或進入多邊形內側。上限組以Ni·(P2-P1)<0為特征，表示在該處沿P1P2方向前進將越來越遠地離開多邊形區域。第29頁，課件共44頁，創作于2023年2月參數化算法(Cyrus-Beck)因此，線段可見的交點參數：tl=max{0,max{ti:Ni·(P2-P1)>0}}tu=min{1,min{ti:Ni·(P2-P1)<0}}若tl<=tu,[tl

，tu]是可見線段的交點參數區間，否則，線段不可見。第30頁，課件共44頁，創作于2023年2月參數化算法當凸多邊形是矩形窗口且矩形的邊與坐標軸平行時，該算法退化為Liang-Barsky算法。第31頁，課件共44頁，創作于2023年2月Liang-Barsky算法所用的量第32頁，課件共44頁，創作于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頁，課件共44頁，創作于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頁，課件共44頁，創作于2023年2月elseif(p>0)

{r=p/q;

if(r<*u1)returnFALSE;

elseif(r<*u2)

{*u2=r;

returnTRUE;

}

}

elseif(q<0)returnFALSE;

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

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