計算機圖形學(xué)中二維裁剪算法的研究
2011-12-31 00:00:00歐中亞
中小企業(yè)管理與科技·上旬刊 2011年8期
摘要：隨著計算機技術(shù)的發(fā)展，計算機圖形學(xué)也日益成熟。在我們的日常生活中，也成了隨處可見的必需部分。在醫(yī)學(xué)、娛樂、圖形藝術(shù)、商業(yè)、教育培訓(xùn)、科學(xué)工程等眾多領(lǐng)域，計算機圖形學(xué)的應(yīng)用非常普遍。
計算機圖形學(xué)主要研究的是在計算機中構(gòu)造圖形，將用數(shù)學(xué)模型描述的圖形數(shù)據(jù)采用合適的算法轉(zhuǎn)換為屏幕上圖形的顯示。計算機圖形學(xué)學(xué)科研究的對象為二維圖形學(xué)和三維圖形學(xué)及其顯示和變化情況。點、線、面為二維圖形學(xué)范疇，幾何體和場等數(shù)學(xué)構(gòu)造方法則為三維圖形學(xué)范疇。
現(xiàn)在，計算機圖形學(xué)的一些基本算法已經(jīng)形成了固化在硬件中的規(guī)范軟件包，這個學(xué)科也日趨成熟和完善。但是依然有很多算法還需要不斷的改進才能應(yīng)用到實際中，而裁剪算法就是其中之一。本文主要對二維圖形裁剪中的橢圓形窗口裁剪算法進行了研究，使其具有較高的效率和穩(wěn)定性。
關(guān)鍵詞：計算機圖形學(xué) 裁剪算法 橢圓形窗口線裁剪算法
1 裁剪概述
裁剪算法，簡稱裁剪，是計算機圖形學(xué)中很多重要問題的基礎(chǔ)，它就是從數(shù)據(jù)集合中識別指定區(qū)域內(nèi)或指定區(qū)域外圖形部分的過程。裁剪用途很廣泛，最典型的就是確定場景中位于指定區(qū)域內(nèi)的景物部分。其中，指定區(qū)域成為裁剪窗口，一般為矩形，由四條邊組成，上、下、左、右，即：(Xl，Yb)，(Xr，Yt)。實質(zhì)上來說，裁剪就是確定哪些多邊形等幾何體位于裁剪窗口內(nèi)。對于點(X，Y)，只要判斷兩對不等式：Xl≤X≤Xr，Yb≤Y≤Yt即可。
如果四個點坐標的不等式都不成立，則這個點在矩形窗口外，否則，在窗口內(nèi)。有一種最簡單的裁剪方法，就是將所有圖形掃描轉(zhuǎn)換成點，然后在進行判斷。但是這種方法時間消耗太大，非常不可取。倘若將全部在窗口外的圖形完全排除而不進行掃描轉(zhuǎn)換，則時間上面可以高效很多，故一般采用先裁剪再掃描的方法。
按裁減對象來分，裁剪算法大概分為如下幾種：點裁剪、直線段裁剪、區(qū)域多邊形裁剪、曲線裁剪和文字裁剪。
裁剪有多方面應(yīng)用，主要包括：使用實體造型創(chuàng)建對象、在三維視圖中標示出可見面、對圖形的一部分進行刪除、復(fù)制或移動操作、防止圖形邊界混淆、從特定場景中抽取指定部分等。在不同的應(yīng)用中，裁剪窗口的形狀也不盡相同。然而，裁剪算法是否高效關(guān)鍵在減少求交運算，高效識別裁剪線段是否與裁剪窗口邊界相交。
二維裁剪算法分為兩種，對二維線段的裁剪以及對二維多邊形的裁剪，在這兩方面，國內(nèi)外許多專家學(xué)者都進行了深入的研究，出現(xiàn)了很多經(jīng)典算法。對于前者，比較經(jīng)典的算法有便于硬件實現(xiàn)的中點分割算法，基于編碼技術(shù)的Cyrus-Berk裁剪算法，Nicholl等提出的基于幾何變換技術(shù)的NLN算法，通過法向點積判別的Cyrus-Ber
k裁剪算法，在NLN算法基礎(chǔ)上發(fā)展的ELC算法，以及Liang-Bars
ky算法等。另外，還有一種比較高效的只用整數(shù)運算來計算整數(shù)交點的線裁剪算法，是由M.Dorr綜合了直線參數(shù)表示方法和Cohen-Suthcrland的編碼方法而得到的。
2 橢圓形窗口線裁剪算法描述
橢圓形不僅是計算機圖形學(xué)中的基本幾何元素之一，而且許多實際問題的解決中，橢圓也是作為處理對象進行操作的。對于計算機圖形學(xué)中的裁剪算法來說，關(guān)于橢圓形窗口的裁剪算法是非常重要的。設(shè)標準橢圓的方程為：
x2/a2+y2/b2=1
其中，標準橢圓的中心點為坐標軸的原點O，假設(shè)A(Xa，Ya)、B(Xb，Yb)(Xa≤Xb)為被裁剪線段的兩個端點，則裁剪可按如下步驟進行：
2.1 特殊情況的處理
當Xa=Xb時，即坐標軸的縱軸與被裁減的線段平行，這時分為兩種情況，線段完全位于橢圓外部，即Xa>a；否則，則需求取橢圓和線段的交點，其橫坐標設(shè)為Xa。
當Ya=Yb時，即坐標軸的橫軸與被裁剪線段平行，這時也有兩種情況，線段完全位于橢圓外部；即Ya>b；否則，求需要求橢圓與線段的交點，其縱坐標均為Ya。
2.2 去除所有位于橢圓外切矩形外的線段。本步采用外切矩形包圍盒的方法，外切矩形由四條直線組成，x=-a、x=a、y =-b、y=b。當min(Xa，Xb)≥a或max(Xa，Xb)≤-a或min(Ya，Yb}≥b或max{Ya，Yb)≤-b時，線段AB位于外切矩形的同側(cè)，然后轉(zhuǎn)步驟3。
2.3 線段端點與橢圓窗口的位置關(guān)系
橢圓有一條基本性質(zhì)，即圓周上任意一點到兩個定點的距離和等于特定常數(shù)。又由橢圓方程可得，a為橢圓的長半軸長度，因此可以根據(jù)線段的兩端點到橢圓兩焦點的距離之和是否小于2a的方法，來確定線段的端點是否位于橢圓內(nèi)。因為橢圓上任意一點到兩焦點的距離之和等于2a，在橢圓外部的點，到兩焦點的距離之和大于2a，而在橢圓內(nèi)部的點，到兩焦點的距離之和大于2a。
最簡單的直接可以顯示的情況就是，線段兩端點均位于橢圓內(nèi)部，進而不需要求交點，因為該線段移動位于橢圓內(nèi)。另一種情況就是線段與橢圓有一個交點，即線段的一個端點在橢圓內(nèi)，一個在橢圓外，此時要通過聯(lián)立線段與橢圓的方程求出交點，進而得到交點和位于橢圓內(nèi)的端點之間的線段，即為所求。最復(fù)雜的情況就是線段的兩個端點均位于橢圓外，這個時候，又有兩種情況產(chǎn)生：
①線段完全位于橢圓窗口外，二者無交點，則可判定裁剪結(jié)束。
②當橢圓與線段有兩個交點時，要進行如下區(qū)分，首先過原點O向線段AB做垂線交線段AB于點P(Xp，Yp)，設(shè)L為橢圓兩個焦點與P的距離和。此時點P分為如下情況：當Xa 3 橢圓形窗口線裁剪算法實現(xiàn) 橢圓形窗口裁剪算法的偽代碼如下，其中，裁剪后所得線段的兩個端點設(shè)為(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 if( Da < 2a Db < 2a) { //線段完全位于橢圓窗口內(nèi)的情況 X1=Xa； Y1=Ya； X2=Xb； Y2=Yb； break； } else if(Da<2aDb>2a或Da>2aDb<2a) 求(X1，Y1)、(X2，Y2)； else { if( Xa < Xb< Xp 或者Xp< Xa < Xb ) break；//線段完全位于橢圓窗口外部的情況 else if ( Xa < Xp < Xb ) { if( Lp < 2a )// 點P位于橢圓窗口內(nèi)部的情況 求(X1，Y1)、(X2，Y2)； break； else { If ( Lp > Lr ) break；//被裁剪線段完全位于橢圓外部的情況 else 求出(X1，Y1)、(X2，Y2)； } } else break；//線段與橢圓無交點，完全位于橢圓外部的情況 } 橢圓是計算機圖形學(xué)中的基本圖形元素之一，近年來，在橢圓的研究上也取得了很大的進步，很多橢圓生成方面的有效算法應(yīng)運而生。由于橢圓窗口裁剪情況在工程設(shè)計當中應(yīng)用非常廣泛，故上文中的橢圓窗口裁剪算法在實際中是非常有效的。 參考文獻： [1]韓明峰，李傳林.基于一般多邊形窗口的線裁剪算法.計算機工程與科學(xué)，1999. [2]吳章文，勾成俊，楊代倫，羅正明.有共線邊的多邊形窗口的線裁剪算法.計算機輔助設(shè)計與圖形學(xué)報，2004. [3]劉永奎，劉桂芳.一般多邊形窗口的線裁剪.計算機輔助設(shè)計與圖形學(xué)學(xué)報，1993. [4]陸國棟，邢世海.基于頂點編碼的多邊形窗口線裁剪算法.計算機學(xué)報，2002 [5]姚涵珍，宋鵬，張國安.圓形窗口線裁剪算法的研究與實踐.計算機輔助設(shè)計與圖形學(xué)學(xué)報，1992. [6]劉勇奎.圓形及橢圓形裁剪窗口.計算機工程與設(shè)計，1994. [7]沈慶云，周來水，周儒榮.一種圓形窗口裁剪的新方法.計算機輔助設(shè)計與圖形學(xué)學(xué)報，1997. 作者簡介：歐中亞（1973.09-），男，漢族，河南省周口市人，助教，碩士研究生，研究方向：圖像處理。
