计算机图形学课程设计设计题目改进的有效边表算法对多边形的填充学院名称信息科学与技术学院
专业名称计算机科学与技术
学生姓名刘柯
学生学号201213030112
任课教师梅占勇
设计（论文）成绩
教务处制
2015年9 月28 日
目录
一、设计内容与要求 (3)
1.1设计题目 (3)
1.2 设计内容 (3)
1.3 设计目标 (3)
二、总体设计 (3)
2.1 多边形的表示 (3)
2.2 x-扫描线算法 (4)
2.3 改进的有效边表算法 (4)
2.3.1 改进的有效边表算法 (4)
2.3.2 有效边表 (5)
2.3.3 边表 (6)
三、详细设计 (8)
3.1 改进的有效边表算法的实现 (8)
3.2 有效边表算法程序流程图 (9)
四、测试结果 (9)
五、总结 (15)
六、源代码 (15)
参考文献 (26)
一、设计内容与要求
1.1设计题目
用改进的有效边表算法实现多边形的填充
1.2 设计内容
使用OpenGL实现用改进的有效边表算法填充多边形
1.3 设计目标
参照课本上改进的有效边表算法的思想，实现该算法的C语言代码，并用该算法搭配OpenGL以像素点的方式绘制出给定顶点坐标的多边形。
二、总体设计
2.1 多边形的表示
在计算机图形学中，多边形有2种重要的表示方法：顶点表示和点阵表示。
顶点表示用多边形的顶点序列来刻画多边形，这种方法直观、几何意义强，占用内存少，应用普遍，但它没有明确指出哪些像素在多边形内，故不能直接用于面着色。
点阵表示用位于多边形内的像素的集合来刻画多边形。这种表示法虽然失去了许多重要的几何信息，但便于运用帧缓存表示图形，是面着色所需要的图形表示形式。
大多数图形应用系统采用顶点序列表示多边形，而顶点表示又不能直接用于显示，那么就必须有从多边形的顶点表示到点阵表示的转换，这种转换称为多边形的扫描转
换或多边形的填充。即从多边形的顶点信息出发，求出位于其内部的各个像素，并将其颜色值写入帧缓存的相应单元中。
2.2 x-扫描线算法
x-扫描线算法的基本思想是，按照扫描线的顺序，计算扫描线与多边形的相交区间，再用要求的颜色显示这些区间的像素，即完成填充工作。区间的端点可以通过计算扫描线与多边形边界线的交点获得。根据此原理，x-扫描线算法可以填充凸的、凹的或带有孔的多边形区域。
x-扫描线的算法步骤如下：
(1)确定多边形顶点的最小和最大y值(y min和y max)，得到多边形所占有的最大扫描
线数。
(2)从y=y min到y=y max，每次用一条扫描线填充。每一条扫描线填充的过程分为4
个步骤：
①求交。计算扫描线与多边形所有边的交点。
②排序。把所有交点按x坐标递增的顺序进行排序。
③交点配对。配对第一与第二、第三与第四个交点等，每对交点代表一个填充
区间。
④区间填色。把这些相交区间内的像素置成不同于背景色的填充色。
x-扫描线算法在处理每条扫描线时，需要与多边形的所有边求交，这样处理效率非常低。因为一条扫描线往往只与少数几条边相交，甚至与整个多边形都不相交。因此，有必要对算法进行改进。
2.3 改进的有效边表算法
2.3.1 改进的有效边表算法
将x-扫描线算法加以改进可以得到改进的有效边表算法，也称y连贯算法。改进可以从三个方面进行：首先，在处理一条扫描线时，仅对与它相交的多边形的边（有效边）求交；其次，利用扫描线的连贯性，考虑到当前扫描线与各边的交点顺序与下一条扫描线与各边的交点顺序很可能相同或非常相似，因此在当前扫描线处理完毕之
后，不必为下一条扫描线从头开始构造交点信息；最后，利用多边形的连贯性，认为若某条边与当前扫描线相交，则它很可能也与下一条扫描线相交且其交点与上一次的
交点相关。如下图所示，设直线的斜率为k，若y=y
i 时，x=x
i
；则当y=y
i+1
时，有x
i+1
=x
i
+1/k。
2.3.2 有效边表
有效边（Active Edge）是指与当前扫描线相交的多边形的边，也称活性边。把有效边按与扫描线交点x坐标递增的顺序存放在一个链表中，此链表称为有效边表（Active Edge Table，AET）。有效边表的每个结点存放对应边的如下信息：
其中，x为当前扫描线与有效边交点的x坐标；y max是有效边所在的最大扫描线值，通过它可以知道何时才能“抛弃”该边；1/k是边斜率的倒数；next是下一个结点的指针。
如下图所示的多边形P0P1P2P3P4P5P6，其顶点表示为：
P0(7，8)，P1(3，12)，P2(1，7)，P3(3，1)，P4(6，5)，P5(8，1)，P6(12，9)。
当y=8时的有效边表如下图所示：
2.3.3 边表
有效边表给出了扫描线和有效边交点坐标的计算方法，但是没有给出新边出现的位置坐标。为了方便有效边表的建立与更新，就需要构造一个边表（Edge Table，ET），用以存放扫描线上多边形各条边的信息。由于水平边的1/k为∞，并且水平边本身就是扫描线，所以在建立边表时不予考虑。
边表的构造分为4个步骤：
①首先构造一个纵向链表，链表的长度为多边形占有的最大扫描线数，链表的每
个结点，称为一个桶，对应多边形覆盖的每一条扫描线。
②将每条边的信息装入与该边最小y坐标(y
min
)相对应的桶中。也就是说，若某
边的较低端点为y
min ，则该边就放在相应的y=y
min
的扫描线桶中。
③每条边的数据形成一个结点，内容包括该扫描线与该边的初始交点x(即较低
端点的x坐标值)，该边最大y坐标值y
max
，以及斜率的倒数1/k和下一个边结点的指针next:
④同一桶中若干条边按x|y min由小到大排列，若x|y min相等，则按1/k由小到大排
序。
从上面可以看出，边表是有效边表的特例，有效边表和边表可以使用同一个数据结构来表示。
对于多边形P0P1P2P3P4P5P6，它的边表结构如下图所示：
