電腦圖形學——裁剪
- 2019 年 10 月 19 日
- 筆記
裁剪作用：
選擇顯示的內容–圖形在窗口內的部分被顯示出來，窗口外的部分被裁剪掉
圖形中每個圖形基本元素都要經過裁剪，因此裁剪直接影響整個圖形系統的效率。
裁剪窗口：矩形，凸多邊形，任意多邊形
裁剪類型：二維裁剪、三維裁剪
裁剪對象：直線段、多邊形、文字等
裁剪方法:
直線的裁剪方法: Sutherland-Cohen演算法 , Cyrus-Beck演算法,梁友棟-Barsky演算法
多邊形的裁剪方法:Sutherland-Hodgman演算法
三維的裁剪方法: Sutherland-Cohen演算法 ,梁友棟-Barsky演算法
一、Sutherland-Cohen演算法
本演算法又稱為編碼裁剪演算法
Sutherland–Cohen演算法分成兩部分：
第一步，判定：
1) 完全在窗口內的直線段，稱為完全可見的線段，如AB。保留著
2) 完全在窗口外的線段，稱為完全不可見線段，如CD。拋棄掉
第二步，處理不能斷定為完全可見或完全不可見的線段，如IJ、KL
*這時需要計算出直線段和窗口邊界的一個交點，這個交點把直線分成兩段，其中一條為完全不可見的線段,被拋棄。
*對餘下部分再作第一步的判斷，重複上述過程，直到直線段餘下的部分可用第一步的判斷得出肯定的結論為止。
1、判斷完全可見/不可見的線段
為使電腦能夠快速判斷一條直線段與窗口屬何種關係，採用如下編碼方法。窗口的四條邊把整個平面分成九個區域，每一個區域採用四位編碼表示：
在x=xL左側的區域,編碼的第四位是1；
在x=xR右側的區域,編碼的第三位是1；
在y=yB下側的區域,編碼的第二位是1；
在y=yT上側的區域,編碼的第一位是1。
如何判斷？
對要被裁剪的線段的兩個端點進行區域編碼。
如果其所在的區域的編碼均是0000（相與），則這條線段完全可見；
如果兩個編碼的邏輯與不為0000，則這條線段完全不可見
2、處理不能斷定為完全可見或完全不可見的線段
線段KL為例，從K點(1001)的編碼分析出K在x=xL的左側，KL必和x=xL有交點，求出其交點M，KM顯然是完全不可見的，因而只要對ML從第一步開始重複上述處理步驟。
由於ML還是不能用第一步下結論，又從M的編碼發現M在y=yT的上側，因而要求ML和y=yT的交點N。
丟掉MN，對NL用第一步的方法可斷定NL為完全可見，至此裁剪結束。
3、程式程式碼
float xl, xr, yt, yb; unsigned char code(float x, float y) { unsigned char c = 0; if (x < xl) c = c|1; //按位或 else if (x > xr) c = c|2; if (y < yb) c = c|4; else if (y > yt) c = c|8; return c; }//給九個區域編碼 void clip(float x0, float y0, float x2, float y2) { unsigned char c1, c2, c; float x, y, wx, wy; c1 = code(x0, y0); c2 = code(x2, y2); while ((!(c1 == 0)) || (!(c2 == 0))) { if ((c1& c2)) return; //兩端點邏輯與不為0，則在區域外，裁去 c = c1; if (c == 0) c = c2; wx=x2-x0; wy=y2-y0; if ((c & 1) == 1) { y = y0 + wy * (xl - x0) /wx; x = xl; }//端點在xl左側，求與xl的交點 else if ((c & 2) == 2) { y = y0 +wy * (xr - x0) /wx; x = xr; } //端點在xr右側，求與xr的交點 else if ((c & 4) == 4) { x = x0 +wx * (yb - y0) /wy; y = yb; } //端點在yb下方，求與yb的交點 else if ((c & 8) == 8) { x = x0 +wx * (yt - y0) / wy; y = yt; } //端點在yt上方，求與yt的交點 if (c == c1) { x0 = x; y0 = y; c1 = code(x0, y0); } else { x2 = x; y2 = y; c2 = code(x2, y2); } //用交點代替端點，再返回第一步 }// While() glLine(int(x0), int(y0), int(x2), int(y2)); }
4、小結
Cohen-Sutherland裁剪演算法對不與邊框相交的線段進行裁剪時效率較高,而對與窗口邊界有交點的線段裁剪效率低。
因而比較適合兩種情況的裁剪：一是大部分線段完全可見；二是大部分線段完全不可見。
而且很多的時候,被裁剪線段僅與窗口邊界延長線相交,求交點到最後是無效的操作,因為線段可能完全被丟棄;並且被裁剪線段與窗口邊界相交時交點的取得比較複雜。
比如像下圖這樣的裁剪，這條紅色線段完全是在裁剪窗口的外部，卻需要進行演算法計算，最後線段完全被丟棄！
二、中點分隔演算法
中點分隔演算法是對Sutherland-Cohen演算法在求交點方面的改進。
核心思想是通過二分逼近來確定直線段與 窗口的交點。
取線段的中點
1、若中點不在窗口內， 則把中點和離窗口邊界最遠點構成的線段丟掉，以線段上的另一點和該中點再構成線段求其中點
2、如中點在窗口內，則又以中點和最遠點構成線段， 並求其中點，直到中點與窗口邊界的 坐標值在規定的誤差範圍內相等
重複上述過程，直到線段長度小於給定的小數ε為止。
在顯示時ε可取成一個象素的寬度，對解析度為2N×2N的顯示器來說，上面講的二分的過程最多只要作N次。
三、Cyrus-Beck演算法
Cyrus-Beck演算法可以處理任意凸多邊形對線段的裁剪。
1、裁剪目標
考慮如圖所示一個凸多邊形區域R和一條線段P1P2，要求計算線段落在區域R中的部分。
2、線段表示
假定A是區域R邊界L上一點；N是區域邊界在A點的內法向量；線段P1P2用參數方程表示：
3、基本思想
對於線段P1P2的參數方程表示，如果能判斷出線段進入多邊形時候的參數ts和線段退出多邊形時的參數te，則tste之間的線段為裁剪完畢後的結果。
4、判定線段上的點和多邊形的關係
假定A為區域邊界L上的任意一點，記L的內法向量（垂直）為N對於線段上任意一點 Pi， Pi和多邊形邊界L的關係有三種可能(t 為此點的參數值)：
性質（1）: 如果點P(t)在多邊形所有邊的內側，則稱P是在多邊形的內側。
可見線段的參數區間
5、編程思路
6、程式程式碼
double ts,te; int Cyrus_Beck (int k,double A[][2],double N[][2],double x[2],double y[2],double *ts,double *te) { int i,j; double t,dn,nw,D[2],W[2]; *ts=0; *te=1; for(i=0; i<k; i++) { dn=N[i][0]*(x[1]- x[0])+N[i][1]* (y[1]-y[0]); nw=N[i][0]* (x[0]-A[i][0])+N[i][1]* (y[0]- A[i][1]); if(fabs(dn)<1.0e-6) //平行 { if(nw<0) return 0; //p在L外側 } else { t=-nw/dn; if(dn<0) { if(t< *te) *te=t; //終點 } else if(t> *ts) *ts=t; //起點 } if(*ts>*te) return 0; //在區域外 } return 1; }
三、梁友棟-Barsky演算法
當凸多邊形是矩形窗口，且矩形的邊平行於坐標軸時， Cyrus-Beck演算法可簡化為梁友棟-Barsky演算法。
基本步驟
初始化線段在邊界內的端點參數為ts=0、te=1。
計算出各個裁剪邊界的r、s值。
當r=0且s<0時，捨棄該線段；否則計算線段與邊界的交點參數t。
當r<0時，參數t用於更新ts；
當r>0時，參數t用於更新te。
如果更新了ts或te後，使ts>te，則捨棄該線段。
程式程式碼
double ts,te; double xL,xR,yB,yT; bool visible=false; void Liang_Barsky (double x[2],double y[2],double *ts,double *te) { double dx,dy; visible=false; dx=x[1]-x[0]; dy= y[1]-y[0]; *ts=0; *te=1; if(clipt(-dx,x[0]-xL,ts,te)) if(clipt(dx,xR-x[0],ts,te)) if(clipt(-dy,y[0]-yB,ts,te)) if(clipt(dy,yT-y[0],ts,te)) visible=true; } bool clipt (double r,double s,double * ts,double *te) { double t; if(r<0) { t=s/r; if(t>* te) return false; else if(t>* ts) *ts=t; } //起點組 else if(r>0) { t=s/r; if(t<*ts) return false; else if(t<* te) *te=t; } //終點組 else if(s<0) return false; //r=0且s<0則完全不可見 return true; }
梁友棟-Barsky演算法比Sutherland-Cohen演算法更有效,因為需要計算的交點數目減少了。更新參數僅僅需要一次除法,線段與窗口的交點只計算一次就計算出 ts、te的最後的值。而對於Sutherland-Cohen演算法,即使一條線段完全落在裁剪窗口之外,也要對其反覆求交點,而且每次求交都需要除法和乘法運算。
https://www.cnblogs.com/cnblog-wuran/p/9813841.html
四、Sutherland-Hodgman多邊形裁剪
該演算法的基本思想是將多邊形邊界作為一個整體，每次用窗口的一條邊對要裁剪的多邊形和中間結果多邊形進行裁剪，體現一種分而治之的思想
基本原理
只要對多邊形用窗口的四條邊依次裁剪四次便可得到裁剪後的多邊形。
每次用窗口的一條邊界（包括延長線）對要裁剪的多邊形進行裁剪，裁剪時順序地測試多邊形各頂點，保留邊界內側的頂點，刪除外側的頂點，同時，適時地插入新的頂點(即交點和窗口頂點)，從而得到一個新的多邊形頂點序列。
然後以此新的頂點序列作為輸入，相對第二條窗邊界線進行裁剪，又得到一個更新的多邊形頂點序列。
依次下去，相對於第三條、第四條邊界線進行裁剪，最後輸出的多邊形頂點序列即為所求的裁剪好了的多邊形。如下圖所示。
演算法的輸入是以頂點序列表示的多邊形，輸出也是一個頂點序列，構成一個或多個多邊形。
考慮以窗口的一條邊以及延長線構成的裁剪線，該線把平面分成兩部分：一部分包含窗口，稱為可見側；另一部分稱為不可見側。
每條線段端點S、P與裁剪線比較後可輸出0至2個頂點。
S、P都在可見一側，則輸出P。
S、P都在不可見一側，則輸出0個頂點。
S在可見一側，P在不可見一側，則輸出SP與裁剪線的交點I。
S在不可見一側，P在可見一側，則輸出SP與裁剪線的交點I和P。
五、字元裁剪
字元裁剪的策略有以下三種:
串精度裁剪
字元串完全落入窗口之內時才顯示，否則不顯示，裁剪結果如圖(b)所示。其思想是求出字元串的包圍盒，比較包圍盒的邊界極值與窗口的邊界極值，若包圍盒完全落於窗口之內，則顯示字元串，否則不顯示。
字元精度裁剪
當一個字元完全包含於窗口內時，顯示該字元，否則不顯示。可先用字元串包圍盒判斷應該完全、部分還是不顯示字元串，對部分顯示的字元串，再用每個字元的包圍盒判斷該字元是不是應該顯示。裁剪結果如圖(c)所示。
基於構成字元最小元素的裁剪
這種策略最為精確，即使字元只有一部分在窗口內，也要把這一部分顯示出來。對點陣字元來說，構成字元的最小元素為像素，此時字元的裁剪轉化為點裁剪；對矢量字元來說，構成字元的最小元素是曲線段，字元的裁剪轉化為曲線的裁剪。裁剪結果如圖(d)所示。 
