計算機(jī)圖形學(xué)二維圖形裁剪

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

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

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

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

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

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

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

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

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

，tu]是可見線段的交點參數(shù)區(qū)間，否則，線段不可見。第30頁，課件共44頁，創(chuàng)作于2023年2月參數(shù)化算法當(dāng)凸多邊形是矩形窗口且矩形的邊與坐標(biāo)軸平行時，該算法退化為Liang-Barsky算法。第31頁，課件共44頁，創(chuàng)作于2023年2月Liang-Barsky算法所用的量第32頁，課件共44頁，創(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頁，課件共44頁，創(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頁，課件共44頁，創(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頁，課件共44頁，創(chuàng)作于2023年2月3.多邊形裁剪ABCDEF第36頁，課件共44頁，創(chuàng)作于2023年2月錯覺：多邊形裁剪是直線段裁剪的組合？新的問題：1)邊界不再封閉，需要用窗口邊界的恰當(dāng)部分來封閉它，如何確定其邊界？第37頁，課件共44頁，創(chuàng)作于2023年2月2）一個凹多邊形可能被裁剪成幾個小的多邊形，如何確定這些小多邊形的邊界？第38頁，課件共44頁，創(chuàng)作于2023年2月Sutherland-Hodgman算法分割處理策略：將多邊形關(guān)于矩形窗口的裁剪分解為多邊形關(guān)于窗口四邊所在直線的裁剪。流水線過程(左上右下)：前邊的結(jié)果是后邊的輸入。亦稱逐邊裁剪算法第39頁，課件共44頁，創(chuàng)作于2023年2月基本思想是一次用窗口的一條邊裁剪多邊形。這里明確一點:多邊形用頂點序列表示，被窗口的一條邊裁剪后，仍為多邊形，仍用頂點序列表示，裁剪的結(jié)果就是一系列的頂點?？紤]窗口的一條邊以及延長線構(gòu)成的裁剪線,

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