杨玉婷， 康厚良

（云南大学旅游文化学院，云南 丽江 674100）

在2D图形引擎中，可见性判定的主要目的是对于给定的场景和观察视点，通过对遮挡关系进行快速判断，丢弃大量不需要绘制的图形对象，从而降低场景的复杂程度，增加整个场景的真实感，最终实现低负荷绘制和网络传输[1-3]，因此，是一个非常重要的问题。另外，不论是2D对象，还是3D对象最终都将被渲染到显示屏上，由于显示屏的大小是固定的，因此，不是场景中的所有可见部分都可以在显示屏中显示出来，需要根据显示屏的尺寸对场景中的可见部分进行裁剪，即屏幕裁剪[4]，如图1所示。通过图像流水线处理后的可见部分可能是一个或若干个多边形，所以在屏幕裁剪过程中，一般是先找出多边形和屏幕边界的交点，然后通过连接各边界点从而确定屏幕中的可见部分[5]。在一些特殊情况下，屏幕可能部分甚至全部位于待判定多边形内，此时则需要对屏幕各顶点与待判定多边形的内外关系进行判断，因此点与多边形内外关系的判断在2D图形引擎中很重要。

图1 屏幕裁剪

点与多边形内外关系的判断算法很多，常见算法包括射线法[6]、叉积判断法[7]、多边形方向法[8]、基于端点和交点编码法[9]、链码表及多边形特征形法[10]，以及基于单调性的相关边法[11]等等。结合2D图形引擎的特点和流行的内外点判别算法给出了在DirectX平台上使用VC++实现的平面多边形内外点判断算法，并将其应用于实际的2D图形引擎中。通过具体实例证明，该算法能实时的对点和多边形的内外关系进行较好的处理，并将裁剪后的多边形渲染到屏幕上。

1 算法的数据结构

在计算机图形学中提及的多边形一般多指简单多边形，并且规定多边形沿逆时针方向时为正，沿顺时针方向时为负。

为了方便多边形内外点判断算法的实现，首先设计适当的数据结构存储多边形顶点，并要求能满足顶点的排序、增加和删除等操作需要。因此，使用静态数组存储原始多边形（未进行任何处理的多边形）序列，而操作时使用静态链表存储。数组/链表以顶点为单位存储多边形的所有顶点信息，并规定如下：

（1）每一个存储单元对应多边形的一个顶点。

（2）每两个相邻元素的一个组合对应于多边形的一条边。

（3）有一个共同元素的一对组合对应于多边形的两条相邻边，其中公共元素即为两条相邻边的相交顶点。

因此，多边形单个顶点的数据结构和多边形顶点数组定义如下：

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 任意多边形

另外，定义多边形顶点的齐次坐标结构和多边形表示如下：

typedef struct VERTEX3D_TYP

{

int X,Y; // 顶点坐标

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方向的最大值和最小值，其中len=4

此时，多边形顶点Pi(i∈[0,∞))的齐次坐标表示为(Xi,Yi,Zi)，其中Zi表示方向向量，且值恒等于1，即Pi=(Xi,Yi,1)

2 算法描述

算法的基本思想是：首先，以待测点作为原点建立直角坐标系，生成多边形的水平链码表和垂直链码表；然后，删除与判断点和多边形无关的冗余边/冗余点，获得多边形的特征形。接着，判断待测点与特征形的内外关系；最后，确定待测点与平面多边形的内外关系。算法步骤的具体描述如下：

Step 1对多边形顶点序列进行逆时针排序。排序方法是：将多边形的n个顶点分别用Pi(i∈[0,n))表示，通过比较线段OPi（过坐标原点和多边形顶点Pi(i∈[0,n))的线段）与x正半轴组成的夹角的大小，确定多边形各个顶点逆时针排序时的先后关系，如图3所示。具体操作包括以下4个方向：

图3 多边形的逆时针排序

1）根据顶点个数n创建临时数组jiaodu[n],用于存储OPi与x正半轴组成的夹角的大小；

2）计算OPi与Ox的正弦值，若Pi.y＞ 0，

表1 temp在不同象限对应的角度值

4）对数组jiaodu[n]及与之对应的多边形顶点序列v2d进行逆时针排序

Step 2以待测点P为原点建立新的直角坐标系，具体操作包括以下2个方面：

1）根据待测点P，计算新坐标系的平移量dx=p.x，dy=p.y，因此平移矩阵

2）计算多边形的顶点Pi(i∈[0,n))在新坐标系x′oy′中的坐标值Pi′，即Pi′=Pi*MT，效果如图3所示。

Step 3根据Pi′ (i∈[0,n))的位置标记多边形顶点的水平链码值(HorizValue)和垂直链码值(VertiValue)。标记规则为：在垂直方向上编码时，对 点Pi′(i∈[0,n))，若 纵 坐 标yi′＞0，则VertiValue=1，否则，VertiValue=0；在水平方向上编码时，对点Pi′(i∈[0,n))，若横坐标xi′＞0，则HorizeValue=1，否则，HorizeValue=0[6]；最后，将计算结果分别存储在数组c和s中，且数组长度均为n。由此，图4中多边形的垂直编码表和水平编码表分别为11100000和10000001，且n=8。

Step 4删除多边形中与待测点无关的冗余边或冗余点，获得多边形的特征形。具体操作包括以下3个方面：

1）对垂直链码表进行连续的0（1）检测，方法是：检测垂直链码表c中是否存在连续的3个或3个以上的0或1，若有，则用第一个及最末一个0或1来代替这段连续的0（1）序列，并获得简化后的垂直链码表c_new；

2）据c_new计算相应的水平链码表s_new和多边形顶点数组v2d_new，顶点数n递减；

3）对水平链码表s_new重复执行步骤1)和2)的操作。

简化后的多边形的垂直链码表和水平链码表为：1100和1001，对应特征形的顶点序列为P0(10,4)，P2(-28,2)，P3(-20,-10)，P7(20,-20)，且n=4，如图4所示。

图4 多边形的垂直链码、水平链码和特征形

Step 5判断点与多边形的内外关系

1）当n=2时，多边形简化为线段，则只需线段是否过原点，若过原点，则待测点在多边形内；否则，点在多边形外。

2）当n≥3时，遍历特征形顶点序列查找沿x，y方向的最大值和最小值并存入数组most中，数组most的长度len∈[3,4]，如果most中存在相同的顶点坐标（多边形发生了退化现象[4]），则删除相同顶点，len值递减，并对most进行逆时针排序。

3）当len＞2时，取most序列中的前3个点分别赋给q0，q1，q2，定义矢量z={0,0,1}，如果(q0q1×q1q2)·z＞0，则多边形特征形的方向为正，否则为负。

4）当len=2时，设剩余两点分别为Pi，Pj，如果（Pi-1Pi×PiPi+1)·z＞0，则多边形特征形的方向为正，否则为负。

5）据特征形的方向性判断点与多边形的内外关系，即连接待测点P与多边形的任意两个相邻顶点，获得三角形△PPiPi+1，执行Step 3，计算三角形的方向，如果三角形的方向与特征形方向相同，则待测点P位于多边形内，否则位于多边形外。如图5所示，△PP3P7与多边形特征形P0P2P3P7方向相同，因此待测点P位于多边形内。

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

3 复杂性分析

设多边形顶点数为n，多边形的特征形的边数为m，待测点为P。首先，计算多边形的水平链码表和垂直链码表的时间复杂度均为O(2*n)；然后，分别对多边形Verti和Horize进行去0和去1运算，求得时间复杂度为O(4*n)；接着，计算待测点与特征形内外关系的时间复杂度，当m=2时为O(1)，m≥3时为所以时间复杂度的范围为最后，计算待测点与平面多边形的内外关系的时间复杂度为O(1)；因此，整个算法的时间复杂度范围为由此可知，算法的整体时间复杂度是线性的。

4 实验结果及分析

在所设计的2D线框引擎中，当多边形与屏幕边缘相交时，首先对多边形进行屏幕裁剪，获得顶点的渲染序列；然后判定屏幕顶点与多边形的内外关系，屏幕顶点位于多边形内，则作为新的渲染顶点被加入到渲染序列中，否则保持裁剪后的渲染序列不变；最后，对渲染序列进行排序，并根据顶点渲染序列将多边形渲染到屏幕上。

相应的测试内容包括：

1）当多边形完全位于屏幕内时的变化；

2）多边形部分位于屏幕内时的变化；

3）多边形发生动态变化（移动、旋转）时，屏幕顶点与多边形的关系。计算机硬件环境为：Duo T6400 2GHz*2，内存为2GHz，软件环境为：Visual Studio 2005和DirectX，测试效果如图6所示。

图6 多边形与屏幕顶点关系判定的测试

另外，以多边形边数分别为4,6,8,12,16,32随机生成的任意多边形为基础，判断1000,000个随机点与多边形的内外关系，测试算法效率。由于程序运行时间可能会受到外界的干扰，因此对每个多边形都进行了多次测试并取平均值作为最终结果，其中时间的单位由CPU滴答转换为秒，并与文献[8]比较，测试结果如表2所示。

表2 两种算法的耗时比较

从运行效果可以发现，随着处理的多边形边数的增加，本算法在判断速度上的优势更加明显，证明其具有较好的实际应用价值，并且也非常简单易行。

[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]普建涛, 查红彬. 大规模复杂场景的可见性问题研究[J]. 计算机研究与发展, 2005, 42(2): 236-246.

[3]杨玉婷, 康厚良. 大规模室内场景中的入口技术[J].重庆理工大学学报（自然科学版）, 2011, 25(11):78-85.

[4][美]Andre LaMothe著. “3D游戏编程大师技巧”[M].李祥瑞, 陈武译, 北京: 人民邮电出版社, 2005.

[5]林 芳, 康宝生. 平面多边形裁剪算法评述[J]. 西安建筑科技大学学报(自然科学版), 2003, 35(3):95-98.

[6]Taloy G. Point in polygon test [J]. Survey Review,1994, 32(254): 479-484.

[7]孙家广. 计算机图形学(第3版)[M]. 北京: 清华大学出版社, 2000: 414-418.

[8]李维诗, 李江雄, 柯映林. 平面多边形方向及内外点判断的新方法[J]. 计算机辅助设计与图形学学报,2000, 12(6): 405-407.

[9]彭 欢, 陆国栋, 谭建荣. 基于端点与交点编码的矩形窗口多边形裁剪新算法[J]. 工程图学学报,2006, 27(4): 72-76.

[10]周 欣, 张树有, 潘志庚. 基于链码和特征形的多边形内外点判断算法[J]. 计算机辅助设计与图形学学报, 2006, 18(9): 1317-1321.

[11]李基拓, 陆国栋, 冯 星. 基于单调性与相关边的多边形内外点判断算法[J]. 中国图象图形学报(A),2002,7(6): 596-600.