計算機圖形學中的二維裁剪算法研究

摘 要：計算機圖形學在計算機技術的發展中不斷被拓展，而且對于圖形的使用是越來越多，使得怎么樣更好的讓計算機圖形技術為我們工作和生活服務，就顯得更加重要了，本文將研究計算機圖形學中的二維裁剪算法。

關鍵詞：計算機圖形學；二維裁剪算法；研究

1 計算機圖形學中的二維裁剪算法認識

裁剪算法分為點裁剪、直線段裁剪、區域多邊形裁剪、曲線裁剪和文字裁剪，所以簡稱又叫裁剪，從數據集合中識別指定區域內或指定區域外圖形部分的過程。裁剪有多方面應用，主要應用的方面有使用實體造型創建對象、在三維視圖中標示出可見面、對圖形的一部分進行刪除、復制或移動操作、防止圖形邊界混淆、從特定場景中抽取指定部分等。本文主要討論二維裁剪算法是對二維線段的裁剪和對二維多邊形的裁剪，對二維線段的裁剪以及對二維多邊形的裁剪，在這兩方面，國內外許多專家學者都進行了深入的研究，出現了很多經典算法。對于前者，比較經典的算法有便于硬件實現的中點分割算法，基于編碼技術的Cyrus-Berk裁剪算法，Nicholl等提出的基于幾何變換技術的NLN算法，通過法向點積判別的Cyrus-Ber k裁剪算法，在NLN算法基礎上發展的ELC算法，以及Liang-Bars ky算法等。另外，還有一種比較高效的只用整數運算來計算整數交點的線裁剪算法，是由M.Dorr綜合了直線參數表示方法和Cohen-Suthcrland的編碼方法而得到的。裁剪就是確定哪些多邊形等幾何體位于裁剪窗口內。然后在一個矩形內，對組成的四條邊中指定的區域內進行裁剪口。四條邊分別從上、下（Xl，Yb），、左、右（Xr，Yt）。而裁剪的確定是確定哪些多邊形等幾何體位于裁剪窗口內。對于點（X，Y），只要判斷兩對不等式：Xl≤X≤Xr，Yb≤Y≤Yt即可。如果四個點坐標的不等式都不成立，則這個點在矩形窗口外，否則，在窗口內。

2 橢圓形裁剪窗口

在實際應用中經常要用到圓形或橢圓形裁剪窗口。關于橢圓窗口對線段的裁剪，由于計算更為復雜，計算量更大而難以找到一種快速的裁剪算法，橢圓有一條基本性質，即圓周上任意一點到兩個定點的距離和等于特定常數，又由橢圓方程可得，a為橢圓的長半軸長度，因此可以根據線段的兩端點到橢圓兩焦點的距離之和是否小于2a的方法，來確定線段的端點是否位于橢圓內。因為橢圓上任意一點到兩焦點的距離之和等于2a，在橢圓外部的點，到兩焦點的距離之和大于2a，而在橢圓內部的點，到兩焦點的距離之和大于2a。設標準橢圓的方程為：x2/a2+y2/b2=1，其中，標準橢圓的中心點為坐標軸的原點O，假設A（Xa，Ya）、B（Xb，Yb）（Xa≤Xb）為被裁剪線段的兩個端點，當Xa=Xb時，即坐標軸的縱軸與被裁減的線段平行，這時分為兩種情況，線段完全位于橢圓外部，即Xa>a；否則，則需求取橢圓和線段的交點，其橫坐標設為Xa。當Ya=Yb時，即坐標軸的橫軸與被裁剪線段平行，這時也有兩種情況，線段完全位于橢圓外部；即Ya>b；否則，求需要求橢圓與線段的交點，其縱坐標均為Ya。另一種情況就是線段與橢圓有一個交點，即線段的一個端點在橢圓內，一個在橢圓外，此時要通過聯立線段與橢圓的方程求出交點，進而得到交點和位于橢圓內的端點之間的線段，即為所求。假設兩個端點均位于橢圓外，就會出現線段完全位于橢圓窗口外，二者無交點，則可判定裁剪結束。或者是橢圓與線段有兩個交點，就需要看過原點位置，和距離大小。

3 橢圓形窗口線裁剪算法操作

橢圓形窗口裁剪后所得線段的兩個端點設為（X1，Y1）、（X2，Y2），線段兩端點到橢圓焦點的距離之和為Da、Db，原點O到AB 的垂足為P（Xp，Yp），平行于線段AB且和橢圓相切的線段CD到中心點的距離為Lt。

if（Xa==Xb）

{if（Xa>a）

break；//被裁剪線段完全位于橢圓窗口外的情況

else

X1=X2=Xa；

else if（Ya==Yb）

{if（Ya>b）

break；//被裁剪線段完全位于橢圓窗口外的情況

else

Y1=Y2=Ya；

}

else if（min{Xa，Xb}≥a或max{Xa，Xb}≤-a或min（Ya，Yb）≥b或max{Ya，Yb}≤-b）

break；//被裁剪線段完全位于橢圓窗口外的情況

else i

Y1=Y2=Ya；

}

else if（min{Xa，Xb}≥a或max{Xa，Xb}≤-a或min（Ya，Yb）≥b或max{Ya，Yb}≤-b）

break；//線段完全位于橢圓窗口外部的情況

else if （XaLr ）

break；//被裁剪線段完全位于橢圓外部的情況

else求出（X1，Y1）、（X2，Y2）；

} }else

break；//線段與橢圓無交點，完全位于橢圓外部的情況}，這就使得橢圓形窗口線裁剪算法得以實現。

[參考文獻]

[1]王浩朋.二維圖形的裁剪算法研究與改進[D].西安電子科技大學，2011.

[2]易飛.次橢圓方程在圖像處理中的應用[D].南京理工大學，2013.

[3]陳超.圓與橢圓對多邊形裁剪算法研究[D].哈爾濱工程大學，2008.

[4]李海姣.任意多邊形的裁剪算法及其在土建工程中的應用[D].華東交通大學，2005.

[5]閻雙.計算機圖形學算法可視化教學研究與實現[D].遼寧師范大學，2007.