楊玉婷, 康厚良
(云南大學(xué)旅游文化學(xué)院,云南 麗江 674100)
在2D圖形引擎中,可見性判定的主要目的是對于給定的場景和觀察視點(diǎn),通過對遮擋關(guān)系進(jìn)行快速判斷,丟棄大量不需要繪制的圖形對象,從而降低場景的復(fù)雜程度,增加整個場景的真實(shí)感,最終實(shí)現(xiàn)低負(fù)荷繪制和網(wǎng)絡(luò)傳輸[1-3],因此,是一個非常重要的問題。另外,不論是2D對象,還是3D對象最終都將被渲染到顯示屏上,由于顯示屏的大小是固定的,因此,不是場景中的所有可見部分都可以在顯示屏中顯示出來,需要根據(jù)顯示屏的尺寸對場景中的可見部分進(jìn)行裁剪,即屏幕裁剪[4],如圖1所示。通過圖像流水線處理后的可見部分可能是一個或若干個多邊形,所以在屏幕裁剪過程中,一般是先找出多邊形和屏幕邊界的交點(diǎn),然后通過連接各邊界點(diǎn)從而確定屏幕中的可見部分[5]。在一些特殊情況下,屏幕可能部分甚至全部位于待判定多邊形內(nèi),此時(shí)則需要對屏幕各頂點(diǎn)與待判定多邊形的內(nèi)外關(guān)系進(jìn)行判斷,因此點(diǎn)與多邊形內(nèi)外關(guān)系的判斷在2D圖形引擎中很重要。
圖1 屏幕裁剪
點(diǎn)與多邊形內(nèi)外關(guān)系的判斷算法很多,常見算法包括射線法[6]、叉積判斷法[7]、多邊形方向法[8]、基于端點(diǎn)和交點(diǎn)編碼法[9]、鏈碼表及多邊形特征形法[10],以及基于單調(diào)性的相關(guān)邊法[11]等等。結(jié)合2D圖形引擎的特點(diǎn)和流行的內(nèi)外點(diǎn)判別算法給出了在DirectX平臺上使用VC++實(shí)現(xiàn)的平面多邊形內(nèi)外點(diǎn)判斷算法,并將其應(yīng)用于實(shí)際的2D圖形引擎中。通過具體實(shí)例證明,該算法能實(shí)時(shí)的對點(diǎn)和多邊形的內(nèi)外關(guān)系進(jìn)行較好的處理,并將裁剪后的多邊形渲染到屏幕上。
在計(jì)算機(jī)圖形學(xué)中提及的多邊形一般多指簡單多邊形,并且規(guī)定多邊形沿逆時(shí)針方向時(shí)為正,沿順時(shí)針方向時(shí)為負(fù)。
為了方便多邊形內(nèi)外點(diǎn)判斷算法的實(shí)現(xiàn),首先設(shè)計(jì)適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)存儲多邊形頂點(diǎn),并要求能滿足頂點(diǎn)的排序、增加和刪除等操作需要。因此,使用靜態(tài)數(shù)組存儲原始多邊形(未進(jìn)行任何處理的多邊形)序列,而操作時(shí)使用靜態(tài)鏈表存儲。數(shù)組/鏈表以頂點(diǎn)為單位存儲多邊形的所有頂點(diǎn)信息,并規(guī)定如下:
(1)每一個存儲單元對應(yīng)多邊形的一個頂點(diǎn)。
(2)每兩個相鄰元素的一個組合對應(yīng)于多邊形的一條邊。
(3)有一個共同元素的一對組合對應(yīng)于多邊形的兩條相鄰邊,其中公共元素即為兩條相鄰邊的相交頂點(diǎn)。
因此,多邊形單個頂點(diǎn)的數(shù)據(jù)結(jié)構(gòu)和多邊形頂點(diǎn)數(shù)組定義如下:
typedef struct VERTEX2DI_TYP
{
int X,Y; // the vertex
} VERTEX2D, *VERTEX2D_PTR;
因此,如圖2所示的多邊形P0P1P2… P7表示為:
VERTEX2DI_PTR v2d=new VERTEX2DI[n]; //n=8
VERTEX2D_PTR pv2d=v2d; //指向多邊形序列的指針
VERTEX2D_PTR pt; //多邊形的特征值列表
int *c, *s; // 多邊形的垂直鏈碼表和水平鏈碼表
圖2 任意多邊形
另外,定義多邊形頂點(diǎn)的齊次坐標(biāo)結(jié)構(gòu)和多邊形表示如下:
typedef struct VERTEX3D_TYP
{
int X,Y; // 頂點(diǎn)坐標(biāo)
int Z; // 方向向量
} VERTEX3D, *VERTEX3D_PTR;
VERTEX3D v3d[8]= {P0, P1, P2, P3, P4, P5, P6, P7};
VERTEX3D_PTR *pv3d=v3d;//指向多邊形序列的指針
VERTEX3D most[len]; // 存儲多邊形沿x方向和y方向的最大值和最小值,其中l(wèi)en=4
此時(shí),多邊形頂點(diǎn)Pi(i∈[0,∞))的齊次坐標(biāo)表示為(Xi,Yi,Zi),其中Zi表示方向向量,且值恒等于1,即Pi=(Xi,Yi,1)
算法的基本思想是:首先,以待測點(diǎn)作為原點(diǎn)建立直角坐標(biāo)系,生成多邊形的水平鏈碼表和垂直鏈碼表;然后,刪除與判斷點(diǎn)和多邊形無關(guān)的冗余邊/冗余點(diǎn),獲得多邊形的特征形。接著,判斷待測點(diǎn)與特征形的內(nèi)外關(guān)系;最后,確定待測點(diǎn)與平面多邊形的內(nèi)外關(guān)系。算法步驟的具體描述如下:
Step 1對多邊形頂點(diǎn)序列進(jìn)行逆時(shí)針排序。排序方法是:將多邊形的n個頂點(diǎn)分別用Pi(i∈[0,n))表示,通過比較線段OPi(過坐標(biāo)原點(diǎn)和多邊形頂點(diǎn)Pi(i∈[0,n))的線段)與x正半軸組成的夾角的大小,確定多邊形各個頂點(diǎn)逆時(shí)針排序時(shí)的先后關(guān)系,如圖3所示。具體操作包括以下4個方向:
圖3 多邊形的逆時(shí)針排序
1)根據(jù)頂點(diǎn)個數(shù)n創(chuàng)建臨時(shí)數(shù)組jiaodu[n],用于存儲OPi與x正半軸組成的夾角的大??;
2)計(jì)算OPi與Ox的正弦值,若Pi.y> 0,
表1 temp在不同象限對應(yīng)的角度值
4)對數(shù)組jiaodu[n]及與之對應(yīng)的多邊形頂點(diǎn)序列v2d進(jìn)行逆時(shí)針排序
Step 2以待測點(diǎn)P為原點(diǎn)建立新的直角坐標(biāo)系,具體操作包括以下2個方面:
1)根據(jù)待測點(diǎn)P,計(jì)算新坐標(biāo)系的平移量dx=p.x,dy=p.y,因此平移矩陣
2)計(jì)算多邊形的頂點(diǎn)Pi(i∈[0,n))在新坐標(biāo)系x′oy′中的坐標(biāo)值Pi′,即Pi′=Pi*MT,效果如圖3所示。
Step 3根據(jù)Pi′ (i∈[0,n))的位置標(biāo)記多邊形頂點(diǎn)的水平鏈碼值(HorizValue)和垂直鏈碼值(VertiValue)。標(biāo)記規(guī)則為:在垂直方向上編碼時(shí),對 點(diǎn)Pi′(i∈[0,n)),若 縱 坐 標(biāo)yi′>0,則VertiValue=1,否則,VertiValue=0;在水平方向上編碼時(shí),對點(diǎn)Pi′(i∈[0,n)),若橫坐標(biāo)xi′>0,則HorizeValue=1,否則,HorizeValue=0[6];最后,將計(jì)算結(jié)果分別存儲在數(shù)組c和s中,且數(shù)組長度均為n。由此,圖4中多邊形的垂直編碼表和水平編碼表分別為11100000和10000001,且n=8。
Step 4刪除多邊形中與待測點(diǎn)無關(guān)的冗余邊或冗余點(diǎn),獲得多邊形的特征形。具體操作包括以下3個方面:
1)對垂直鏈碼表進(jìn)行連續(xù)的0(1)檢測,方法是:檢測垂直鏈碼表c中是否存在連續(xù)的3個或3個以上的0或1,若有,則用第一個及最末一個0或1來代替這段連續(xù)的0(1)序列,并獲得簡化后的垂直鏈碼表c_new;
2)據(jù)c_new計(jì)算相應(yīng)的水平鏈碼表s_new和多邊形頂點(diǎn)數(shù)組v2d_new,頂點(diǎn)數(shù)n遞減;
3)對水平鏈碼表s_new重復(fù)執(zhí)行步驟1)和2)的操作。
簡化后的多邊形的垂直鏈碼表和水平鏈碼表為:1100和1001,對應(yīng)特征形的頂點(diǎn)序列為P0(10,4),P2(-28,2),P3(-20,-10),P7(20,-20),且n=4,如圖4所示。
圖4 多邊形的垂直鏈碼、水平鏈碼和特征形
Step 5判斷點(diǎn)與多邊形的內(nèi)外關(guān)系
1)當(dāng)n=2時(shí),多邊形簡化為線段,則只需線段是否過原點(diǎn),若過原點(diǎn),則待測點(diǎn)在多邊形內(nèi);否則,點(diǎn)在多邊形外。
2)當(dāng)n≥3時(shí),遍歷特征形頂點(diǎn)序列查找沿x,y方向的最大值和最小值并存入數(shù)組most中,數(shù)組most的長度len∈[3,4],如果most中存在相同的頂點(diǎn)坐標(biāo)(多邊形發(fā)生了退化現(xiàn)象[4]),則刪除相同頂點(diǎn),len值遞減,并對most進(jìn)行逆時(shí)針排序。
3)當(dāng)len>2時(shí),取most序列中的前3個點(diǎn)分別賦給q0,q1,q2,定義矢量z={0,0,1},如果(q0q1×q1q2)·z>0,則多邊形特征形的方向?yàn)檎?,否則為負(fù)。
4)當(dāng)len=2時(shí),設(shè)剩余兩點(diǎn)分別為Pi,Pj,如果(Pi-1Pi×PiPi+1)·z>0,則多邊形特征形的方向?yàn)檎?,否則為負(fù)。
5)據(jù)特征形的方向性判斷點(diǎn)與多邊形的內(nèi)外關(guān)系,即連接待測點(diǎn)P與多邊形的任意兩個相鄰頂點(diǎn),獲得三角形△PPiPi+1,執(zhí)行Step 3,計(jì)算三角形的方向,如果三角形的方向與特征形方向相同,則待測點(diǎn)P位于多邊形內(nèi),否則位于多邊形外。如圖5所示,△PP3P7與多邊形特征形P0P2P3P7方向相同,因此待測點(diǎn)P位于多邊形內(nèi)。
圖5 特征形的方向性及△PPiPi+1的方向性
設(shè)多邊形頂點(diǎn)數(shù)為n,多邊形的特征形的邊數(shù)為m,待測點(diǎn)為P。首先,計(jì)算多邊形的水平鏈碼表和垂直鏈碼表的時(shí)間復(fù)雜度均為O(2*n);然后,分別對多邊形Verti和Horize進(jìn)行去0和去1運(yùn)算,求得時(shí)間復(fù)雜度為O(4*n);接著,計(jì)算待測點(diǎn)與特征形內(nèi)外關(guān)系的時(shí)間復(fù)雜度,當(dāng)m=2時(shí)為O(1),m≥3時(shí)為所以時(shí)間復(fù)雜度的范圍為最后,計(jì)算待測點(diǎn)與平面多邊形的內(nèi)外關(guān)系的時(shí)間復(fù)雜度為O(1);因此,整個算法的時(shí)間復(fù)雜度范圍為由此可知,算法的整體時(shí)間復(fù)雜度是線性的。
在所設(shè)計(jì)的2D線框引擎中,當(dāng)多邊形與屏幕邊緣相交時(shí),首先對多邊形進(jìn)行屏幕裁剪,獲得頂點(diǎn)的渲染序列;然后判定屏幕頂點(diǎn)與多邊形的內(nèi)外關(guān)系,屏幕頂點(diǎn)位于多邊形內(nèi),則作為新的渲染頂點(diǎn)被加入到渲染序列中,否則保持裁剪后的渲染序列不變;最后,對渲染序列進(jìn)行排序,并根據(jù)頂點(diǎn)渲染序列將多邊形渲染到屏幕上。
相應(yīng)的測試內(nèi)容包括:
1)當(dāng)多邊形完全位于屏幕內(nèi)時(shí)的變化;
2)多邊形部分位于屏幕內(nèi)時(shí)的變化;
3)多邊形發(fā)生動態(tài)變化(移動、旋轉(zhuǎn))時(shí),屏幕頂點(diǎn)與多邊形的關(guān)系。計(jì)算機(jī)硬件環(huán)境為:Duo T6400 2GHz*2,內(nèi)存為2GHz,軟件環(huán)境為:Visual Studio 2005和DirectX,測試效果如圖6所示。
圖6 多邊形與屏幕頂點(diǎn)關(guān)系判定的測試
另外,以多邊形邊數(shù)分別為4,6,8,12,16,32隨機(jī)生成的任意多邊形為基礎(chǔ),判斷1000,000個隨機(jī)點(diǎn)與多邊形的內(nèi)外關(guān)系,測試算法效率。由于程序運(yùn)行時(shí)間可能會受到外界的干擾,因此對每個多邊形都進(jìn)行了多次測試并取平均值作為最終結(jié)果,其中時(shí)間的單位由CPU滴答轉(zhuǎn)換為秒,并與文獻(xiàn)[8]比較,測試結(jié)果如表2所示。
表2 兩種算法的耗時(shí)比較
從運(yùn)行效果可以發(fā)現(xiàn),隨著處理的多邊形邊數(shù)的增加,本算法在判斷速度上的優(yōu)勢更加明顯,證明其具有較好的實(shí)際應(yīng)用價(jià)值,并且也非常簡單易行。
[1]Cohen D, Chrysanthou Y, Silva C, et al. A survey of visibility for walkthrough applications [J]. IEEE Transactions on Visualization and Computer Graphics,2003, 9(3): 412-431.
[2]普建濤, 查紅彬. 大規(guī)模復(fù)雜場景的可見性問題研究[J]. 計(jì)算機(jī)研究與發(fā)展, 2005, 42(2): 236-246.
[3]楊玉婷, 康厚良. 大規(guī)模室內(nèi)場景中的入口技術(shù)[J].重慶理工大學(xué)學(xué)報(bào)(自然科學(xué)版), 2011, 25(11):78-85.
[4][美]Andre LaMothe著. “3D游戲編程大師技巧”[M].李祥瑞, 陳武譯, 北京: 人民郵電出版社, 2005.
[5]林 芳, 康寶生. 平面多邊形裁剪算法評述[J]. 西安建筑科技大學(xué)學(xué)報(bào)(自然科學(xué)版), 2003, 35(3):95-98.
[6]Taloy G. Point in polygon test [J]. Survey Review,1994, 32(254): 479-484.
[7]孫家廣. 計(jì)算機(jī)圖形學(xué)(第3版)[M]. 北京: 清華大學(xué)出版社, 2000: 414-418.
[8]李維詩, 李江雄, 柯映林. 平面多邊形方向及內(nèi)外點(diǎn)判斷的新方法[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),2000, 12(6): 405-407.
[9]彭 歡, 陸國棟, 譚建榮. 基于端點(diǎn)與交點(diǎn)編碼的矩形窗口多邊形裁剪新算法[J]. 工程圖學(xué)學(xué)報(bào),2006, 27(4): 72-76.
[10]周 欣, 張樹有, 潘志庚. 基于鏈碼和特征形的多邊形內(nèi)外點(diǎn)判斷算法[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2006, 18(9): 1317-1321.
[11]李基拓, 陸國棟, 馮 星. 基于單調(diào)性與相關(guān)邊的多邊形內(nèi)外點(diǎn)判斷算法[J]. 中國圖象圖形學(xué)報(bào)(A),2002,7(6): 596-600.