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

《直線裁剪算法研究(Cohen-Sutherland算法和Liang-Barsky算法).doc》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

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

2、herland算法、中點分割算法、Liang-Barsky算法、Sobkow-Pospisil-Yang算法，及Nicholl-Lee-Ncholl算法等。2直線裁剪的基本原理圖1所示的為直線與窗口邊界之間可能出現(xiàn)的幾種關(guān)系。可以通過檢查直線的兩個端點是否在窗口之確定如何對此直線裁剪。如果一直線的兩個端點均在窗口邊界之（如圖1中P5到P6的直線），則此直線應(yīng)保留。如果一條直線的一個端點在窗口外（如P9）另一個點在窗口（如P10），則應(yīng)從直線與邊界的交點（P9）處裁剪掉邊界之外的線段。如果直線的兩個端點均在邊界

3、外，則可分為兩種情況：一種情況是該直線全部在窗口之外；另一種情況是直線穿過兩個窗口邊界。圖中從P3到P4的直線屬于前一種情況，應(yīng)全部裁剪掉；從P7到P8的直線屬于后一種情況，應(yīng)保留P7到P8的線段，其余部分均裁剪掉。圖1直線相對干窗口邊界的栽剪直線裁剪算法應(yīng)首先確定哪些直線全部保留或全部裁剪，剩下的即為部分裁剪的直線。對于部分裁剪的直線則首先要求出這些直線與窗口邊界的交點，把從交點開始在邊界外的部分裁剪掉。一個復(fù)雜的畫面中可能包含有幾千條直線，為了提高算法效率，加快裁剪速度，應(yīng)當采用計算量較小的算法求直線與窗

4、口邊界的交點。3cohen－sutherland直線裁剪算法Cohen-Sutherland算法的大意是：對于每條線段P1P2，分為3種情況處理。①若P1P2完全在窗口，則顯示該線段P1P2，簡稱“取”之。②若P1P2明顯在窗口外，則丟棄該線段，簡稱“棄”之。③若線段既不滿足“取”的條件，也不滿足“棄”的條件，則把線段分為兩段。其中一段完全在窗口外，可棄之。然后對另一段重復(fù)上述處理。1．區(qū)域碼及其建立Cohen-Sutherland直線裁剪算法的核心是把所有直線的端點均分配一個表示其相對位置的4位二進制代碼。

5、此代碼稱為區(qū)域碼。區(qū)域碼按照端點與窗口邊界的相對位置編碼，即區(qū)域碼的4位分別代表端點位于窗口的上、下、左、右。區(qū)域碼從右到左的各位所代表的坐標區(qū)如下所示：位4321坐標區(qū)上下右左上述各位中某位為1，則表示點位于此坐標區(qū)。窗口周圍各坐標區(qū)的區(qū)域碼如圖2所示。由圖2可見，位于窗中的點，其區(qū)域碼應(yīng)為0000，位于窗口左下方的點，其區(qū)域碼應(yīng)為0101，其余類推。區(qū)域碼各位的值可以通過對端點坐標（x，y）與窗口邊界的比較求得。如果x

6、操作，因此，可以通過以下步驟建立區(qū)域碼：①計算出端點坐標與窗口邊界的差。②按計算出的各個差的符號把區(qū)域碼的相應(yīng)位置為0或1，即區(qū)域碼的第一位置為（x－xwmin）的符號位；區(qū)域碼的第二位置為（xwmin-x）的符號位；圖2區(qū)域碼區(qū)域碼的第三位置為（y-ywmin）的符號位；區(qū)域碼的第四位置為（ywmin-y）的符號位。2．區(qū)域碼裁剪算法對所有直線的端點都建立了區(qū)域碼之后，就可按區(qū)域碼判斷直線在窗口之或窗口之外。這可分為如下幾種情況：①若一直線的兩個端點的區(qū)域碼均為0000則此直線在窗口邊界之，應(yīng)子保留。②若一

7、直線的兩個端點的區(qū)域碼的同一位同時為1，則此直線全部在窗口邊界之外，應(yīng)子裁剪。例如，若一直線的一個端點的區(qū)域碼為1001，另一個端點的區(qū)域碼為0101，則此兩端點的區(qū)域碼的第一位均為1，說明此兩端點均在窗口邊界之左，因此，直線在窗口邊界之外，應(yīng)予裁剪。可用將直線兩個端點的區(qū)域碼進行與操作的方法，判斷直線是否在窗口之外，若與操作的結(jié)果為0000則兩端點的區(qū)域碼任何位均不同時為1，此直線不一定被裁剪。③以上兩種情況之外的直線，有可能穿過窗口，也有可能不穿過窗口，如圖87所示。圖中所示的兩條直線都不符合情況②的要求

8、，但一條直線（P1P2）穿過窗口，另一直線（P3P4）不守過窗口。對這類直線可以進行如下處理：取窗口外的一個端點與窗口邊界比較以確定可排除直線的哪一部分，然后，把直線剩下的部分與其他邊界比較，這樣一直到直線全部被排除或確定直線的哪一部分在窗口之為止?？砂础白?、右、下、上”的次序建立檢查直線端點與窗口邊界關(guān)系的算法。下面介紹對圖3所示的兩條直線進行處理的過程。從直線P1P2的下端點P1開始，依次檢查窗