李竹林

(延安大學(xué) 計(jì)算機(jī)學(xué)院，陜西 延安 716000)

Cohen-Sutherland直線剪裁算法改進(jìn)

李竹林

(延安大學(xué) 計(jì)算機(jī)學(xué)院，陜西 延安 716000)

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

Cohen-Sutherland；直線裁剪算法；輔助線；夾角計(jì)算

0 引 言

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

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

1 Cohen-Sutherland裁剪原算法

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

(1)當(dāng)code1=code2=0時(shí)，完全可見，取之。

(2)當(dāng)code1&code2≠0時(shí)(&為位與運(yùn)算)，完全不可見，棄之。

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

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

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

圖2 求交直線與窗口的關(guān)系圖

但是，Cohen-Sutherland原裁剪算法存在以下兩個(gè)缺點(diǎn)：

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

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

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

2 改進(jìn)的Cohen-Sutherland裁剪算法

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

2.1 分類條件的進(jìn)一步約束

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

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

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

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

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

Sij=Ax+By+C

(1)

對于同一條直線，若存在四個(gè)頂點(diǎn)Sij同時(shí)大于等于零，或者Sij同時(shí)小于等于零，記Sij為同號(hào)，否則為異號(hào)。這樣，分類條件則修改為：

第一種情況：當(dāng)code1=code2=0時(shí)，則直線完全可見，“取”之；

第二種情況：當(dāng)code1&code2≠0且Sij為同號(hào)時(shí)，則直線完全不可見，“棄”之；

第三種情況：當(dāng)不滿足“取”或“棄”的條件時(shí)，直線與窗口有交點(diǎn)，需要求交運(yùn)算，進(jìn)行裁剪。

2.2 基于直線夾角計(jì)算的求交運(yùn)算降低法

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

2.2.1 算法改進(jìn)的基本思路

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

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

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

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

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

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

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

2.2.2 基于直線間夾角計(jì)算的算法改進(jìn)

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

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

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

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

(2)

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

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

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

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

為了幫助說明問題，將上面的推導(dǎo)進(jìn)行整理，如表1所示。

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

2.3 算法步驟

改進(jìn)后的算法步驟如下：

Step1:先計(jì)算待裁剪直線的兩個(gè)端點(diǎn)區(qū)域編碼；

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

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

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

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

Step6:算法結(jié)束。

3 算法驗(yàn)證與分析

3.1 算法實(shí)例驗(yàn)證

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

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

3.2 算法比較分析

3.2.1 算法改進(jìn)分析

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

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

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

改進(jìn)算法：對M條直線，符號(hào)計(jì)算需要4M次線性運(yùn)算。

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

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

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

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

3.2.2 算法比較

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

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

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

4 結(jié)束語

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

[1] 孫家廣.計(jì)算機(jī)圖形學(xué)[M].第3版.北京:清華大學(xué)出版社,2005.

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

[3] 陸國棟,吳烜暉.基于變窗口過濾技術(shù)的線段裁剪中點(diǎn)分割算法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),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分類器訓(xùn)練樣本裁剪方法的改進(jìn)[J].計(jì)算機(jī)應(yīng)用，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].哈爾濱理工大學(xué)學(xué)報(bào)，2001，6(2):7-10.

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

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

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

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

[14] 李竹林,張根耀,郭萬鑫.基于符號(hào)判斷的C-S直線裁剪算法改進(jìn)[J].微電子學(xué)與計(jì)算機(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)絡(luò)出版時(shí)間：2017-04-28

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

李竹林(1972-)，女，博士，副教授，研究方向?yàn)閳D形圖像處理。

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