2D圖形引擎中的平面多邊形內(nèi)外點(diǎn)判別

楊玉婷， 康厚良

（云南大學(xué)旅游文化學(xué)院，云南 麗江 674100）

在2D圖形引擎中，可見性判定的主要目的是對于給定的場景和觀察視點(diǎn)，通過對遮擋關(guān)系進(jìn)行快速判斷，丟棄大量不需要繪制的圖形對象，從而降低場景的復(fù)雜程度，增加整個(gè)場景的真實(shí)感，最終實(shí)現(xiàn)低負(fù)荷繪制和網(wǎng)絡(luò)傳輸[1-3]，因此，是一個(gè)非常重要的問題。另外，不論是2D對象，還是3D對象最終都將被渲染到顯示屏上，由于顯示屏的大小是固定的，因此，不是場景中的所有可見部分都可以在顯示屏中顯示出來，需要根據(jù)顯示屏的尺寸對場景中的可見部分進(jìn)行裁剪，即屏幕裁剪[4]，如圖1所示。通過圖像流水線處理后的可見部分可能是一個(gè)或若干個(gè)多邊形，所以在屏幕裁剪過程中，一般是先找出多邊形和屏幕邊界的交點(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)行較好的處理，并將裁剪后的多邊形渲染到屏幕上。

1 算法的數(shù)據(jù)結(jié)構(gòu)

在計(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）每一個(gè)存儲單元對應(yīng)多邊形的一個(gè)頂點(diǎn)。

（2）每兩個(gè)相鄰元素的一個(gè)組合對應(yīng)于多邊形的一條邊。

（3）有一個(gè)共同元素的一對組合對應(yīng)于多邊形的兩條相鄰邊，其中公共元素即為兩條相鄰邊的相交頂點(diǎn)。

因此，多邊形單個(gè)頂點(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)

2 算法描述

算法的基本思想是：首先，以待測點(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個(gè)頂點(diǎn)分別用Pi(i∈[0,n))表示，通過比較線段OPi（過坐標(biāo)原點(diǎn)和多邊形頂點(diǎn)Pi(i∈[0,n))的線段）與x正半軸組成的夾角的大小，確定多邊形各個(gè)頂點(diǎn)逆時(shí)針排序時(shí)的先后關(guān)系，如圖3所示。具體操作包括以下4個(gè)方向：

圖3 多邊形的逆時(shí)針排序

1）根據(jù)頂點(diǎn)個(gè)數(shù)n創(chuàng)建臨時(shí)數(shù)組jiaodu[n],用于存儲OPi與x正半軸組成的夾角的大?。?/p>

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個(gè)方面：

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個(gè)方面：

1）對垂直鏈碼表進(jìn)行連續(xù)的0（1）檢測，方法是：檢測垂直鏈碼表c中是否存在連續(xù)的3個(gè)或3個(gè)以上的0或1，若有，則用第一個(gè)及最末一個(gè)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個(gè)點(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與多邊形的任意兩個(gè)相鄰頂點(diǎn)，獲得三角形△PPiPi+1，執(zhí)行Step 3，計(jì)算三角形的方向，如果三角形的方向與特征形方向相同，則待測點(diǎn)P位于多邊形內(nèi)，否則位于多邊形外。如圖5所示，△PP3P7與多邊形特征形P0P2P3P7方向相同，因此待測點(diǎn)P位于多邊形內(nèi)。

圖5 特征形的方向性及△PPiPi+1的方向性

3 復(fù)雜性分析

設(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)；因此，整個(gè)算法的時(shí)間復(fù)雜度范圍為由此可知，算法的整體時(shí)間復(fù)雜度是線性的。

4 實(shí)驗(yàn)結(jié)果及分析

在所設(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個(gè)隨機(jī)點(diǎn)與多邊形的內(nèi)外關(guān)系，測試算法效率。由于程序運(yùn)行時(shí)間可能會受到外界的干擾，因此對每個(gè)多邊形都進(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.