直線裁剪算法研究(Cohen-Sutherland算法和Liang-Barsky算法)

1、直線裁剪算法研究摘要：直線裁剪是計算機圖形學中的一個重要技術(shù)，在對常見的直經(jīng)線裁剪的算法分 析的基礎(chǔ)上，針對Cohen-Sutherland 算法和Liang-Barsky算法進行了分析研究。并對兩 種算法了計算直線與窗口邊界的交點時，進行了有效有比較。關(guān)鍵詞：裁剪；算法；Cohen-Sutherland ； Liang Barsky ;1引言直線是圖形系統(tǒng)中使用最多的一個基本元素。所以對于直線段的裁剪算法是被研究最 深入的一類算法，目前在矩形窗口的直線裁剪算法中，出現(xiàn)了許多有效的算法。其中比較 著名的有：Cohen-Sutherland算法、中點分割算法、Liang -Ba rsky算法、S

2、obkow-Pospisil-Yang算法，及 Nicholl-Lee-Ncholl算法等。2直線裁剪的基本原理圖1所示的為直線與窗口邊界之間可能出現(xiàn)的幾種關(guān)系?？梢酝ㄟ^檢查直線的兩個端 點是否在窗口之內(nèi)確定如何對此直線裁剪。如果一直線的兩個端點均在窗口邊界之內(nèi)（如 圖1中P5到P6的直線），則此直線應保留。如果一條直線的一個端點在窗口外（如P9）另P7到P8的線段，其余部分均裁剪掉。一個點在窗口內(nèi)（如P10）,則應從直線與邊界的交點（P9）處裁剪掉邊界之外的線段。 如果直線的兩個端點均在邊界外，則可分為兩種情況：一種情況是該直線全部在窗口之外； 另一種情況是直線穿過兩個窗口邊界。 圖中從P3

3、到P4的直線屬于前一種情況，應全部裁剪 掉；從P7到P8的直線屬于后一種情況，應保留2圖1直線相對干窗口邊界的栽剪直線裁剪算法應首先確定哪些直線全部保留或全部裁剪，剩下的即為部分裁剪的直 線。對于部分裁剪的直線則首先要求出這些直線與窗口邊界的交點，把從交點開始在邊界 外的部分裁剪掉。一個復雜的畫面中可能包含有幾千條直線，為了提高算法效率，加快裁 剪速度，應當采用計算量較小的算法求直線與窗口邊界的交點。3 cohe n sutherla nd直線裁剪算法Cohen-Sutherland 算法的大意是：對于每條線段 P1P2，分為3種情況處理。 若P1P2完全在窗口內(nèi)，則顯示該線段P1P2,簡稱“

4、取”之。 若P1P2明顯在窗口外，則丟棄該線段，簡稱“棄”之。 若線段既不滿足“取”的條件，也不滿足“棄”的條件，貝創(chuàng)線段分為兩段。其中 一段完全在窗口外，可棄之。然后對另一段重復上述處理。1 .區(qū)域碼及其建立Cohe n-Sutherla nd 直線裁剪算法的核心是把所有直線的端點均分配一個表示其相對 位置的4位二進制代碼。此代碼稱為區(qū)域碼。區(qū)域碼按照端點與窗口邊界的相對位置編碼， 即區(qū)域碼的4位分別代表端點位于窗口的上、下、左、右。區(qū)域碼從右到左的各位所代表 的坐標區(qū)如下所示：位 _4321坐標區(qū) 一上下右左上述各位中某位為1,則表示點位于此坐標區(qū)。窗口周圍各坐標區(qū)的區(qū)域碼如圖 示。由圖2

5、可見，位于窗中內(nèi)的點，其區(qū)域碼應為 碼應為0101，其余類推。區(qū)域碼各位的值可以通過對端點坐標（X，y） 則區(qū)域碼的第一位為1，其余各位的確定與此相似。 因此，可以通過以下步驟建立區(qū)域碼： 計算出端點坐標與窗口邊界的差。 按計算出的各個差的符號把區(qū)域碼的相應位置為0或1，即X Xwmin ）的符號位； Xwmin -X ）的符號位； y-y wmin ）的符號位； ywmin -y ）的符號位。2所0000，位于窗口左下方的點，其區(qū)域與窗口邊界的比較求得。如果 XVXwmin , 現(xiàn)在的計算機語言都可以進行位操作，101)11000101004HIIOm' 曲UIIKI10011)11

6、101圖2區(qū)域碼區(qū)域碼的第一位置為（區(qū)域碼的第二位置為（區(qū)域碼的第三位置為（區(qū)域碼的第四位置為（2 .區(qū)域碼裁剪算法對所有直線的端點都建立了區(qū)域碼之后，就可按區(qū)域碼判斷直線在窗口之內(nèi)或窗口 之外。這可分為如下幾種情況： 若一直線的兩個端點的區(qū)域碼均為 0000則此直線在窗口邊界之內(nèi)，應子保留。 若一直線的兩個端點的區(qū)域碼的同一位同時為1，則此直線全部在窗口邊界之外，應子裁剪。例如，若一直線的一個端點的區(qū)域碼為1001，另一個端點的區(qū)域碼為0101，則此兩端點的區(qū)域碼的第一位均為 1，說明此兩端點均在窗口邊界之左，因此，直線在窗 口邊界之外，應予裁剪?？捎脤⒅本€兩個端點的區(qū)域碼進行與操作的方法，

7、判斷直線是否在窗口之外，若與操作的結(jié)果為 0000則兩端點的區(qū)域碼任何位均不同時為 1，此直線不 一定被裁剪。87所示。 以上兩種情況之外的直線，有可能穿過窗口，也有可能不穿過窗口，如圖圖中所示的兩條直線都不符合情況的要求，但一條直線（P1P2 ）穿過窗口，另一直線（P3P4）不守過窗口。對這類直線可以進行如下處理：取窗口外的一個端點與窗口邊界比 較以確定可排除直線的哪一部分，然后，把直線剩下的部分與其他邊界比較，這樣一直到 直線全部被排除或確定直線的哪一部分在窗口之內(nèi)為止?？砂础白蟆⒂?、下、上”的次序 建立檢查直線端點與窗口邊界關(guān)系的算法。1 )。下面介紹對圖3所示的兩條直線進行處理的過程。

8、從直線 P1P2的下端點P1開始，依 次檢查窗口的左、上、右及下邊界，可發(fā)現(xiàn)此點在窗口之下（因為區(qū)域碼的第三位為然后求得直線與下邊界的交點 P1排除線段P1 P1這樣直線就縮短為P1 P2。因為P2在邊界 之外，將此端點與各邊界比較，可發(fā)現(xiàn)此端點在窗口上面。計算出交點P2線段P1P2保留下來。這樣就完成了對這條線的處理并開始處理下一直線P3 P4。端點P3在窗口之左，可計算出交點P3講裁剪掉線段巳卩3。檢查P3P4的區(qū)域碼，可發(fā)現(xiàn)直線的這一剩余部分在窗口 之下故也可排除。由于窗口邊界均平行于坐標軸，所以直線與窗口邊界的交點可以用直線方程的各參數(shù) 很方便地求出，對于一條端點坐標為 X1, y1及

9、X2, y2的直線，其與一垂直邊界的交點的 y 坐標可以用下式計算：y y1 m X X1這里互的取值可取x或Xwmax，斜率m可用公式m y2 y1 / x?洛計算。同樣地, 與水平邊界交點的X坐標可用下式計算：X X1 y ym這里y的值可取幾 y w min 或 yw max。下面是區(qū)域碼直線裁剪算法的 C語言描述，其中每個端點的區(qū)域碼用4元素布爾數(shù)組表示。區(qū)域碼直線裁剪算法代碼Void Li ne_Cli ppin g(x1,y1,x2,y2,xw_xmi n,y w_ymi n, xw_max,yw_max)float x1,y1,x2,y2,xw_x min,yw_ymin, xw

10、_max,xw_max,yw_max;/* X1, y1和X2, y是線段端點坐標*/Int draw,d one;Int code1,code2,code;float x,y;Draw=FALSE; don e=FALSE;code1=get_code(x1,y1,xw_xmi n,y w_ymi n, xw_max,yw_max);code2=get_code(x2,y2,xw_x min,yw_ymin, xw_max,yw_max);while(! D one)if (code仁=0 && code= =2)draw=TRUE;d on e=TRUE;else if (

11、code1 & code2 !=0)don e=TRUE;elseIf (code1 !=0)code=code1;elsecode=code2;if (code&TOP!=0)y=yw_ymax;x=x1+(y-y1)*(x2-x1)/(y2-y1);else if (code&BOTTOM!=0)y=yw_ymin; x=x1+(y-y1)*(x2-x1)/(y2-y1);else if (code&RTGHT!=0)x=xw_xmax; y=y1+(x-x1)*(y2-y1)/(x2-x1);else if (code&LIFT!=0)x=xw_x

12、 min;y=y1+(x-x1)*(y2-y1)/(x2-x1);if (code= =code1)x1=x; y1=y;code1=get_codex1,y1,xw_xmi n,y w_ymi n, xw_max,yw_max;elsex2=x;y2=y;code2=get_codex2,y2,xw_x min,yw_ymin, xw_max,yw_max;If (draw)Draw_Li ne(x1,y1,x2,y2);int get_code(x,y,xw_x min,yw_ymin, xw_max,yw_max) float x,y,xw_x min,yw_ymin, xw_max,y

13、w_max;int code;code=0;if (y>yw_ymax)code| =TOP;else if (yvyw_ymin)code|=BOTTOM;if (x>xw_xmax)code|=RIGHT;else if (x<xw_x min)code|=LEFT;retur n code;4Liang Barsky 算法首先寫出端點xi,yi及X2,y2之間Liang （梁友棟）-Barsky算法又稱為參數(shù)方程法。連線的參數(shù)方程如下：XX-Ix2x1 uX1XUyi uy1yuy y1 y2其中，X X2 X1, y y y1。參數(shù)U可取0 1之間的值，坐標的U值定義

14、的直線上的一個點。當 U = 0時，x,y表示此范圍內(nèi)X, y Xi, yi ,直線的另一端U = 0時,X, yX2, y2。Xwmin , Ywmin 及 Xw max , Ywmax 所定義的窗口我們發(fā)現(xiàn)，如果直線上的某點處于X, y及之內(nèi)，則滿足以下條：y wm in W y1yu W ywmaxuPk Wqk，k=1,2,3,4P1X,q1X1XwminP2X,q2XwmaxX1P3y,q 3y1yw minP4y,q4yw maxy1這四個不等式可以表示為:其中，參數(shù)p,q定義為;按照直線與窗口邊界的相對位置，可分為以下幾種倩況。任何一條與窗口邊界平行的直線， 其Pk 0，此處k值

15、表示取哪一個邊界（k =1,2,3 及4，分別相應于左、右、下及上邊界）。如果對某一 k值，還滿足qk 0 ,貝U此直線完 全在邊界外，可不進一步考慮；如果 qk X），則此與邊界平行的直線在邊界內(nèi)。X2,y2連線方向作為正 ;然后分以下兩種情況如果qk 0，則情況較復雜。此時，可把直線按從 xi,yi到 向，將此直線無限延伸，同時把各窗口邊界也無限延伸（見圖 3） 討論：a當qk 0時，則是由窗口外發(fā)出的一條直線 的無限延伸線進入相應窗口邊界的無限延伸線的 內(nèi)部。b當qk 0時，情況相反。即直線的延伸線是 由窗口邊界延伸線的內(nèi)部到外部。A PN圖3直線與窗口邊界的相對以圖3中的直線Li為例，

16、說明以上兩種情況。 表1.1給出Li的延伸線相對于4個邊界延伸線的方 向及qk取值。邊界Pk取值方向交占八、左PjXx2x10由外到內(nèi)ui右P2XX2 X10由內(nèi)到外下P3y y2 yi 0由外到內(nèi)上P4 yy2yi0由內(nèi)到外u2表1.1直線方向與Pk取值當qk 0時，可以用下式計算出一參數(shù) u，此u值應于直線延伸線與窗口邊界 k的延 伸線的交點：u qk/pk對于每條直線，可計算出一對u值（U1及U2），由此兩參數(shù)可判斷直線是如何裁剪的。 其中，U1的值可由從窗口邊界外發(fā)出進人窗口邊界之內(nèi)的直線（Pk 0 ）所涉及的窗口邊界確定。對于這些窗口邊界，可計算出各rkqk/Pk，取各rk中最大值即

17、為回6 , u?可由自窗口邊界內(nèi)發(fā)出至窗口邊界外的直線(Pk0 )所涉及的窗口邊界確定，同樣可計算出這些窗口邊界的rk值，取各rk中的最小值即為U2。如果U1U2，則此直線全部在窗口外而3中標出直線U1及U2計算出可排除：否則，此直線在窗口內(nèi)，可由U1及U2計算出彼裁剪直線的端點。圖 L1及L2相應于U1及U2的與邊界的交點。L1的U2 U1，則L1彼裁剪，并可由 裁剪點；而L2的U1 U2，則此直線全部彼排除。1。對每一窗口此算法可用以下過程表示。此過程中開始把交點參數(shù)置為U10及U2邊界計算出相應的P及q值，然后用函數(shù)CliPtest由參數(shù)p及q決定此直線能否彼排除或 者決定交點參數(shù)是否要

18、調(diào)整。當P 0時，用參數(shù)r修改U1值：當P 0時，用參數(shù)r修改U2 值。如果最后的結(jié)果為U1 U2，則排除此直線；否則，只有當新的值使直線縮短時，才修 改相應的參數(shù)U。當P 0且q 0時，可排除此直線，因為直線與邊界平行且在邊界之外。如果四個P及q均被檢查而直線被排除，則被裁剪直線的端點可由U1及U2的值確定。Liang Barsky裁剪算法代碼Void Li ne_Cli pping (x1,y1,x2,y2,rect)Float x1,y1,x2,y2,*rect;Float dx,dy,t0,t1;t0=0;t1=1;if (Clip Top(-dx,x1-rect->xw_xmi

19、 n,& t0, &t1)if (Clip Top (dx,rect->xw_xmax-x1, &t0,& t1)dy=y2-y1;if (Clip Top (-dy,y1-rect->yx_xmi n,& tO,&t1)if (Clip To p(dy,rect->xw_xmax-y1, &t0, &t1)Line (i nt) (x1+t0*dx),(i nt) (y1+t0*dy)(int) (x1+t1*dx)(int) (y1+t1*dy);return;writeText( “ p1p2 完全不可見”);Void Li ne_Cli ppin g(q,d,*tO,*t1)float q,d,*tO,*t1;float r;if (r>t1)retum(FALSE);else if (r>t0)t0=r;return (TRUE);else if (q>0)r=d/q;if (r<t0)return (FALSE);else if (r<t1)t1=r;return (TRUE);else if (d<0)return (FALSE);return (TRUE);5兩種算法比較Cohen-Suther