Cohen-Sutherland直線剪裁算法改進

李竹林

(延安大學 計算機學院，陜西 延安 716000)

Cohen-Sutherland直線剪裁算法改進

李竹林

(延安大學 計算機學院，陜西 延安 716000)

對直線段進行裁剪是計算機圖形學需要解決的最基本問題之一，直線段的裁剪速度直接影響到整個圖形的裁剪效率。Cohen-Sutherland直線段裁剪算法因分類的不徹底和計算了直線與窗口邊延長線上的交點而降低了算法的效率。提出了一種改進Cohen-Sutherland裁剪算法，其基本思想是根據(jù)裁剪窗口頂點與直線的位置關系對直線的分類條件進行改進，引入一條從待剪裁直線的端點距窗口最近頂點的輔助線，計算出引入的輔助線與待裁剪直線的夾角，根據(jù)夾角的大小，判斷出直線究竟與窗口的哪條邊相交，從而使求交點次數(shù)降低為最高2次。改進后的算法不僅思想簡單直觀、易實現(xiàn)、效率高，而且對圖形裁剪算法的理論研究與應用均有很高的價值。

Cohen-Sutherland；直線裁剪算法；輔助線；夾角計算

0 引 言

直線段裁剪是計算機圖形學中一個非常重要的知識點，是二維及三維圖形剪裁的基礎。從60年代開始到目前為止，廣泛使用的三種經(jīng)典直線裁剪算法是Cohen-Sutherland裁剪算法、中點分割算法以及Liang-Barsky參數(shù)裁剪算法[1-4]。其中，Cohen-Sutherland裁剪算法是最早開發(fā)的快速線段裁剪算法，得到了高度關注與廣泛應用[5-6]。該算法是一種基于區(qū)域編碼的方法，直線的每個端點均賦予四位二進的區(qū)域碼，快速判斷該條線段是完全在裁剪窗口之內還是窗口之外，或直線的部分在窗口內部分在窗口外，并且能判斷出直線可能與窗口的哪條邊相交，從而提高了算法效率[1-2]。為了進一步提高Cohen-Sutherland裁剪算法的效率，提出了多種改進方法[7-14]。

在文獻[13-14]的基礎上，提出了一種更高效的新方法。該算法思路簡單直觀、易實現(xiàn)，對圖形裁剪算法的理論研究與應用都有很高的參考價值。

1 Cohen-Sutherland裁剪原算法

Cohen-Sutherland裁剪算法是利用矩形裁剪窗口的四條邊把二維平面分成9個區(qū)域，用4位二進制編碼CtCbCrCl進行標記，如圖1所示。算法的基本思想：待裁剪的直線段兩端的編碼分別記為code1和code2，與窗口的關系有三種情況：

(1)當code1=code2=0時，完全可見，取之。

(2)當code1&code2≠0時(&為位與運算)，完全不可見，棄之。

(3)當不滿足“取”或“棄”的條件，則在與窗口邊界的交點處把線段分為兩段，其中一段完全在窗口外，棄之；然后對另一段重復上述處理。

圖1 窗口編碼區(qū)域

Cohen-Sutherland裁剪算法的優(yōu)點是：第一種情況和第二種情況不需要求交運算；在第三種情況下，為了減少運算量，進行如下處理。首先求交前先判斷與窗口哪條邊所在直線有交點。判斷規(guī)則是線段端點編碼CtCbCrCl中哪位上的值為“1”，則直線與窗口對應的那條邊有交點，需要求此交點；反之，對應邊上沒有交點。如圖2中的直線P1P2，P1的編碼是1000，說明與窗口的上邊有交點；P2的編碼是0100，說明與窗口的下邊有交點。

圖2 求交直線與窗口的關系圖

但是，Cohen-Sutherland原裁剪算法存在以下兩個缺點：

(1)不能將所有的完全在窗口外的直線全部判斷出來。根據(jù)原算法，當code1&code2≠0，并沒有將所有的在窗口之外的直線段都判斷出來，比如圖2中的直線段P3P4，有code1&code2=0。因此，直線與窗口邊要做2次求交運算。而實際上，該直線段完全在窗口之外，所有的求交運算沒有任何意義。

(2)擴大了直線與窗口邊的求交次數(shù)。在第三種情種下，所求交點可能有：1個、2個、3個或4個。比如圖2中的直線P5P6與窗口的四條邊的交點分別為A、B、C、D。而實際上，P5P6只與窗口的上邊和右邊相交，只需2次求交運算；再如P1P2,實際上與窗口邊只有1個交點，而根據(jù)原算法，也要進行2次求交運算。實際上，沒必要求交的點都是發(fā)生在邊的延長線上，不妨記為虛交點，可以看出虛交點的求交運算和裁剪過程是沒有任何實際意義的。

綜合上述問題，可以看出算法的時間復雜度正是由這些不能完全判斷和求虛交點的運算以及多出來的裁剪過程帶來的。針對這些問題，提出了一種改進的基于直線夾角計算的Cohen-Sutherland裁剪算法，不僅避免了求虛交點的過程，而且大大提高了裁剪算法的效率。

2 改進的Cohen-Sutherland裁剪算法

對原算法的改進是從兩方面進行的，首先是對分類條件，然后對直線與窗口是否有交點，在增加輔助線的基礎上,提出一種計算直線間夾角的新判斷方法。

2.1 分類條件的進一步約束

原算法對完全在窗口之外的判斷條件為：當code1&code2≠0時，完全不可見。

如圖2所示的直線P3P4、P7P8完全在窗口外，卻不能滿足code1&code2≠0，可見，原算法給的是充分不必要條件。在原有的基礎上，進一步增加約束條件。

改進的基本思想是根據(jù)直線與窗口的位置，對第二種(直線完全在窗口外)、第三種(直線與窗口有交點)情況重新作分類判斷，并做一些約定：

約定：T(Top)、L(Left)、B(Bottom)、R(Right)分別表示裁剪窗口的上邊、左邊、下邊及右邊；記窗口的頂點Vij,即VTL、VLB、VBR、VRT，分別表示左上、左下、右下、右上頂點；待裁剪直線L與窗口的位置關系記為Sij,即STL、SLB、SBR、SRT。Sij取值通過式(1)計算。

設直線L的方程為f(x,y)=Ax+By+C，將窗口的頂點Vij(x,y)代入直線方程，計算得到:

Sij=Ax+By+C

(1)

對于同一條直線，若存在四個頂點Sij同時大于等于零，或者Sij同時小于等于零，記Sij為同號，否則為異號。這樣，分類條件則修改為：

第一種情況：當code1=code2=0時，則直線完全可見，“取”之；

第二種情況：當code1&code2≠0且Sij為同號時，則直線完全不可見，“棄”之；

第三種情況：當不滿足“取”或“棄”的條件時，直線與窗口有交點，需要求交運算，進行裁剪。

2.2 基于直線夾角計算的求交運算降低法

經(jīng)過2.1節(jié)的分類條件改進，完全在窗口內和完全在窗口外的直線均能全部判斷出來，因此本節(jié)只針對2.1節(jié)中對直線與窗口有交點且擴大了求交次數(shù)的情況進行討論并提出改進措施。

2.2.1 算法改進的基本思路

從2.1節(jié)知，原算法只所以存在虛求交次數(shù)的可能，是因為不僅求解了直線與窗口的實邊相的交點，而且還求解了直線與窗口的延長線的交點。因此，要降低求交次數(shù)，必須能判斷出直線究竟與窗口的哪些實邊有交點，從而避免求直線與窗口邊的延長線的交點運算。

經(jīng)過總結歸納，可得出如圖3所示的三種情況，即直線的一個端點一定落在四位編碼中有兩位同時不等于零的角區(qū)域(如圖3中的陰影區(qū)，在文中任選了左上角1001區(qū)域)，而另一端有如下三種情況：

(1)另一端也落在角區(qū)域，如直線P1P2。該種情況下，原算法也不能解決直線究竟與窗口的哪條邊有實際交點，需要改進。

(2)另一端也落在完全可見區(qū)，即編碼為0000區(qū)域，如直線P5P6。此時從這個端點的編碼判斷，與窗口的邊只有一個相交點，且不是虛點，用原算法即可。

(3)另一端落在既非完全可見區(qū)，也非角區(qū)域，如直線P3P4。該種情況，從這個端點的編碼判斷，與窗口的邊沒有交點，因此用原算法即可。

圖3 直線與窗口的延長邊相交情況

根據(jù)上面三種情況的分析，得出如下事實：只要解決了端點落在角區(qū)域時，與窗口的哪條邊而非延長線上有交點，則問題得以解決。

2.2.2 基于直線間夾角計算的算法改進

以左上角(1001)區(qū)域為例，如圖4所示。直線為P0P1，現(xiàn)將左上角區(qū)域的直線端點P0與窗口的左上角頂點VTL連接起來，形成一條輔助線P0VTL，這樣就形成一個夾角θ(-π/2<θ<π/2)。

圖4 直線與輔助線間的夾角圖

現(xiàn)在計算θ的大小。設直線P0P1的斜率為k1，輔助線P1VTL的斜率為k2，計算夾角θ的表達式為：

tanθ=(k2-k1)/(1+k1k2)

(2)

(1)左上角(1001)區(qū)域。當tanθ>0時，直線P0P1與窗口的左邊相交，如圖4所示；若當tanθ<0時，直線P0P1與窗口的下邊相交；若tanθ=0，則說明直線經(jīng)過窗口的對角線，從直線的該端點考察，與窗口只有一個交點，且為VTL。

(2)右上角(1010)區(qū)域。當tanθ>0時，直線P0P1與窗口的上邊相交；當tanθ<0時，直P0P1與窗口的右邊相交；當tanθ=0，直線經(jīng)過窗口的對角線，從直線的該端點考察，與窗口只有一個交點，且為VRT。

(3)右下角(0110)區(qū)域。當tanθ>0時，直線P0P1與窗口的右邊相交；當tanθ<0時，直線P0P1與窗口的下邊相交；當tanθ=0，直線經(jīng)過窗口的對角線，從直線的該端點考察，與窗口只有一個交點，且為VBR。

(4)左下角(0101)區(qū)域。當tanθ>0時，直線P0P1與窗口的下邊相交；當tanθ<0時，直線P0P1與窗口的左邊相交；tanθ=0，直線經(jīng)過窗口的對角線，從直線的該端點考察，與窗口只有一個交點，且為VLB。

為了幫助說明問題，將上面的推導進行整理，如表1所示。

表1 直線與窗口邊相交判斷表

2.3 算法步驟

改進后的算法步驟如下：

Step1:先計算待裁剪直線的兩個端點區(qū)域編碼；

Step2:根據(jù)2.1中改進的分類條件判斷直線屬于哪類，若屬于第一、二類轉Step6，否則繼續(xù)；

Step3:若直線的端點沒有落在角區(qū)域內，則按原算法進行判斷、裁剪，否則繼續(xù)；

Step4:根據(jù)2.2節(jié)中的方法，作輔助線，并計算直線間夾角的正切值；

Step5:根據(jù)表1，判斷直線究竟與窗口的哪條邊有交點，然后求交運算并裁剪；

Step6:算法結束。

3 算法驗證與分析

3.1 算法實例驗證

設有裁剪窗口：VTL(4,6)、VRT(12,6)、VBR(12,2)、VLB(4,2)，直線：M(13,10)、N(0,1)。

從落在右上角(1010)區(qū)域的端點M考察，經(jīng)計算得斜率k1=0.69,k2=4.0,tanθ=0.88。根據(jù)表現(xiàn)，直線MN應該和窗口的上邊相交。同理，考察直線MN的另一個在左下角(0101)區(qū)域的端點N，可計算出tanθ=-0.377。根據(jù)表1，直線與窗口的左邊相交。這樣，就得知直線與窗口的上邊和左邊相交，只需求2個交點，避免了與窗口的右邊、下邊的延長線求虛交點，從而提高了算法效率。

3.2 算法比較分析

3.2.1 算法改進分析

(1)對分類條件的改進分析[10]。

設在M條直線屬于表1中的第二類情況，即完全不可見。其中有N(M≥N)條直線用原算法不能判斷，但用改進算法可以。

原算法：對N條直線，可能需要求交2次、3次或4次，在這里不妨記作n次。這N條直線的操作包括n×N次求交運算、n×N次編碼運算、n×N次的判斷。因此，共需要3n×N次線性運算。

改進算法：對M條直線，符號計算需要4M次線性運算。

(2)降低求交次數(shù)的改進分析。

設有M條直線，至少直線的一個端點落在角區(qū)域，即code∈{1001,1010,0101,0110}。

原算法：設求交次數(shù)為n(n=2,3或4),求交需要n×M次線性運算,編碼需要n×M次，判斷需要n×M次，總計3n×M次運算。

改進算法：求兩條直線的斜率k1、k2及兩直線之間的夾角tanθ，然后根據(jù)表1判斷的結果，做h次求交運算(h=1或2)，總計3M+h×M=(3+h)×M次運算。要使算法改進有意義，只要滿足(3+h)×M<3n×M，即h<3(n-1)。根據(jù)n的取值范圍，當n=2時，3(n-1)=3值最小。顯然h的取值足夠滿足該條件。而事實上，當n=4時，3(n-1)=9，h的取值與之相比小多了?？梢娝惴ǖ母倪M有較大意義。

3.2.2 算法比較

文獻[13-14]是文中提出的Cohen-Sutherland直線裁剪算法的改進方法，也是將求交運算從4次或3次降低為2次。文中改進算法與它們比較，除了消除擴張的虛求交次數(shù)外，還具有以下優(yōu)點：

(1)與文獻[13]相比，復雜度降低了。雖然也引入了輔助線，但不需要再分區(qū)再編碼，明顯降低了算法的復雜度。

(2)與文獻[14]相比，算法更簡潔、直觀。文中沒有引入復雜的計算與判斷，只借助了一條輔助線，使得改進算法直觀明了、簡單易行。

4 結束語

為了解決Cohen-Sutherland原算法中存在的分類不徹底和求交點次數(shù)過高的缺點，提出了一種基于直線夾角計算與判斷的Cohen-Sutherland直線段裁剪算法的改進方法，避免了求直線與窗口延長線的交點，將求交點次數(shù)降低到最高2次。算法簡潔、直觀、高效，且易于實現(xiàn)。與原算法及一些相關算法改進的文獻相比，大大提高了效率，但是以除法和浮點運算為代價。

[1] 孫家廣.計算機圖形學[M].第3版.北京:清華大學出版社,2005.

[2] Hearn D, Baker M P, Carithers W.Computer graphics with OpenGL[M].4th ed.[s.l.]:Prentice Hall,2010.

[3] 陸國棟,吳烜暉.基于變窗口過濾技術的線段裁剪中點分割算法[J].計算機輔助設計與圖形學學報,2002,14(6):513-517.

[4] Peng H， Lu Guodong， Tan J R.A new algorithm of polygon clipping against rectangular window based on the endpoint and intersection-point encoding[J].Journal of Engineering Graphics,2006,27(4):72-76.

[5] 熊忠陽，楊營輝，張玉芳.基于密度的kNN分類器訓練樣本裁剪方法的改進[J].計算機應用，2010，30(3)：799-801.

[6] Guid N,Kolmanic S.A new approach in CAD system for design shoes[J].Journal of Computing and Information Technology，2003,11(4):319-326.

[7] Qatawneh M，Sleit A，Almobaideen W.Parallel implementation of polygon clipping using transputer[J].American Journal of Applied Sciences,2009,6(2):214-218.

[8] Ray B K.A line segment clipping algorithm in 2D[J].International Journal of Computer Graphics,2012,3(2):51-76.

[9] 熊中敏，李宏偉，馬春光.二維線段裁剪新算法[J].哈爾濱理工大學學報，2001，6(2):7-10.

[10] 孔德慧，尹寶才，劉媛媛.對Cohen-Sutherland線段裁剪算法的改進[J].北京工業(yè)大學學報，2002,28(4):483-486.

[11] 黃初華，陳孝威.對Cohen-Sutherland裁剪算法的改進[J].貴州大學學報:自然科學版，2008，25(3):268-271.

[12] 王慧玲，馮雪花.對Cohen-sutherland線段裁剪算法的分析及改進[J].伊犁師范學院學報:自然科學版，2008(4):38-41.

[13] 李竹林，雷 崗.一種改進的Sutherland-Cohen 裁剪算法[J].計算機工程與應用，2012，48(34)：175-178.

[14] 李竹林,張根耀,郭萬鑫.基于符號判斷的C-S直線裁剪算法改進[J].微電子學與計算機,2015,32(8):150-153.

Modification of Cohen-Sutherland Line Clipping Algorithm

LI Zhu-lin

(Institute of Computer Science,Yan’an University,Yan’an 716000,China)

Line segment clipping is one of the most basic problems to be solved in computer graphics,and the clipping speed directly affects the clipping efficiency of the whole graph.Cohen-Sutherland line segment clipping algorithm has lower efficiency because line segment classification is not complete and the intersection points are still calculated between straight line and the window extension edge.A modified Cohen-Sutherland line clipping algorithm based on linear angle calculation has been proposed.It is the idea that the line classification conditions can be improved using sign relations of four windows vertex and line,then if an auxiliary line from the end of the line to be cut to the nearest vertex of the window is made,the angle between an auxiliary line and a line to be cut can be calculated,and the intersecting window edge is determined according to the sign of angle.This method reduces the number of intersection.The modified algorithm not only simple and intuitive,easy to implement and of high efficiency,but also valuable for theory research and application of clipping technology.

Cohen-Sutherland;line segment clipping algorithm;auxiliary line;angle calculation

2016-05-20

2016-08-24 網(wǎng)絡出版時間：2017-04-28

國家自然科學基金資助項目(11471007);延安市重大科技攻關項目(2014CGZH-13);國家大學生創(chuàng)新訓練項目(1498)

李竹林(1972-)，女，博士，副教授，研究方向為圖形圖像處理。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170428.1702.012.html

TP301.6

A

1673-629X(2017)06-0032-04

10.3969/j.issn.1673-629X.2017.06.007