2D图形引擎中的平面多边形内外点判别

杨玉婷， 康厚良

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

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

图1 屏幕裁剪

点与多边形内外关系的判断算法很多，常见算法包括射线法[6]、叉积判断法[7]、多边形方向法[8]、基于端点和交点编码法[9]、链码表及多边形特征形法[10]，以及基于单调性的相关边法[11]等等。结合2D图形引擎的特点和流行的内外点判别算法给出了在DirectX平台上使用VC++实现的平面多边形内外点判断算法，并将其应用于实际的2D图形引擎中。……