計算機圖形學(xué)裁剪算法.doc

《計算機圖形學(xué)裁剪算法.doc》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、一、實驗?zāi)繕?.了解Cohen-SutherLand線段裁剪算法、Liang-Barsky線段裁剪算法、SutherLand-Hodgeman多邊形裁剪算法的基本思想；2.掌握Cohen-SutherLand線段裁剪算法、Liang-Barsky線段裁剪算法、SutherLand-Hodgeman多邊形裁剪算法的算法實現(xiàn)；二、實驗內(nèi)容本次實驗主要是實現(xiàn)Cohen-SutherLand線段裁剪算法、Liang-Barsky線段裁剪算法、SutherLand-Hodgeman多邊形裁剪算法。Cohen-sutherland線段裁剪算法思想：

2、該算法也稱為編碼算法，首先對線段的兩個端點按所在的區(qū)域進行分區(qū)編碼，根據(jù)編碼可以迅速地判明全部在窗口內(nèi)的線段和全部在某邊界外側(cè)的線段。只有不屬于這兩種情況的線段，才需要求出線段與窗口邊界的交點，求出交點后，舍去窗外部分。對剩余部分，把它作為新的線段看待，又從頭開始考慮。兩遍循環(huán)之后，就能確定該線段是部分截留下來，還是全部舍棄。Cohen-sutherland線段裁剪算法步驟：1、分區(qū)編碼延長裁剪邊框?qū)⒍S平面分成九個區(qū)域，每個區(qū)域各用一個四位二進制代碼標識。各區(qū)代碼值如圖中所示。四位二進制代碼的編碼規(guī)則是：(1)第一位置1：區(qū)域在左邊界

3、外側(cè)(2)第二位置1：區(qū)域在右邊界外側(cè)(3)第三位置1：區(qū)域在下邊界外側(cè)(4)第四位置1：區(qū)域在上邊界外側(cè)裁剪窗口內(nèi)（包括邊界上）的區(qū)域，四位二進制代碼均為0。設(shè)線段的兩個端點為P1（x1，y1）和P2（x2，y2），根據(jù)上述規(guī)則，可以求出P1和P2所在區(qū)域的分區(qū)代碼C1和C2。2、判別根據(jù)C1和C2的具體值，可以有三種情況：（1）C1=C2＝0，表明兩端點全在窗口內(nèi)，因而整個線段也在窗內(nèi)，應(yīng)予保留。（2）C1&C2≠0（兩端點代碼按位作邏輯乘不為0），即C1和C2至少有某一位同時為1，表明兩端點必定處于某一邊界的同一外側(cè)，因而整個線段

4、全在窗外，應(yīng)予舍棄。（3）不屬于上面兩種情況，均需要求交點。3、求交點假設(shè)算法按照：左、右、下、上邊界的順序進行求交處理，對每一個邊界求完交點，并相關(guān)處理后，算法轉(zhuǎn)向第2步，重新判斷，如果需要接著進入下一邊界的處理。為了規(guī)范算法，令線段的端點P1為外端點，如果不是這樣，就需要P1和P2交換端點。當(dāng)條件(C1&0001≠0)成立時，表示端點P1位于窗口左邊界外側(cè)，按照求交公式，進行對左邊界的求交運算。依次類推，對位于右、下、上邊界外側(cè)的判別，應(yīng)將條件式中的0001分別改為0010、0100、1000即可。求出交點P后，用P1=P來舍去線段

5、的窗外部分，并對P1重新編碼得到C1，接下來算法轉(zhuǎn)回第2步繼續(xù)對其它邊界進行判別。Liang-Barsky線段裁剪算法思想：我們知道，一條兩端點為P1（x1，y1）、P2（x2，y2）的線段可以用參數(shù)方程形式表示：x=x1+u·（x2-x1）=x1+u·Δxy=y1+u·（y2-y1）=y1+u·Δy0≤u≤1式中，Δx=x2-x1，Δy=y2-y1，參數(shù)u在0～1之間取值，P（x，y）代表了該線段上的一個點，其值由參數(shù)u確定，由公式可知，當(dāng)u=0時，該點為P1（x1，y1），當(dāng)u=1時，該點為P2（x2，y2）。如果點P（x，y）位于

6、由坐標（xwmin，ywmin）和（xwmax，ywmax）所確定的窗口內(nèi)，那么下式成立：xwmin≤x1+u·Δx≤xwmaxywmin≤y1+u·Δy≤ywmax這四個不等式可以表示為：u·pk≤qk，k=1，2，3，4其中，p、q定義為：p1=-Δx，q1=x1-xwminp2=Δx，q2=xwmax-x1p3=-Δy，q3=y1-ywminp4=Δy，q4=ywmax-y1從上式可以知道：任何平行于窗口某邊界的直線，其pk=0，k值對應(yīng)于相應(yīng)的邊界（k=1，2，3，4對應(yīng)于左、右、下、上邊界）。如果還滿足qk<0，則線段完全在邊

7、界外，應(yīng)舍棄該線段。如果pk=0并且qk≥0，則線段平行于窗口某邊界并在窗口內(nèi)，見圖中所示。上式還告訴我們：1、當(dāng)pk<0時，線段從裁剪邊界延長線的外部延伸到內(nèi)部；2、當(dāng)pk>0時，線段從裁剪邊界延長線的內(nèi)部延伸到外部；對于每條直線，可以計算出參數(shù)u1和u2，該值定義了位于窗口內(nèi)的線段部分：1、u1的值由線段從外到內(nèi)遇到的矩形邊界所決定（pk<0），對這些邊界計算rk=qk/pk，u1取0和各個r值之中的最大值。2、u2的值由線段從內(nèi)到外遇到的矩形邊界所決定（pk>0），對這些邊界計算rk=qk/pk，u2取0和各個r值之中的最小值。3

8、、如果u1>u2，則線段完全落在裁剪窗口之外，應(yīng)當(dāng)被舍棄；否則，被裁剪線段的端點可以由u1和u2計算出來。Liang-Barsky線段裁剪算法實現(xiàn)：1、初始化線段交點的參數(shù)：u1=0，u2=1；2、計算出各