计算机图形学课程设计有效边表填充算法的实现

计算机图形学 课程设计

设计题目 改进的有效边表算法对多边形的填充

学院名称 信息科学与技术学院 专业名称 计算机科学与技术

学生姓名 刘 柯

学生学号 201213030112 任课教师 梅 占 勇

设计（论文）成绩

教务处 制 2015年 9 月 28 日

1

目录

一、设计内容与要求 .................................................................................................................................. 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

2

一、设计内容与要求

1.1 设计题目

用改进的有效边表算法实现多边形的填充

1.2 设计内容

使用OpenGL实现用改进的有效边表算法填充多边形

1.3 设计目标

参照课本上改进的有效边表算法的思想，实现该算法的C语言代码，并用该算法搭配OpenGL以像素点的方式绘制出给定顶点坐标的多边形。

二、总体设计

2.1 多边形的表示

在计算机图形学中，多边形有2种重要的表示方法：顶点表示和点阵表示。 顶点表示用多边形的顶点序列来刻画多边形，这种方法直观、几何意义强，占用内存少，应用普遍，但它没有明确指出哪些像素在多边形内，故不能直接用于面着色。

点阵表示用位于多边形内的像素的集合来刻画多边形。 这种表示法虽然失去了许多重要的几何信息，但便于运用帧缓存表示图形，是面着色所需要的图形表示形式。

大多数图形应用系统采用顶点序列表示多边形，而顶点表示又不能直接用于显示，那么就必须有从多边形的顶点表示到点阵表示的转换，这种转换称为多边形的扫描转

3

换或多边形的填充。即从多边形的顶点信息出发，求出位于其内部的各个像素，并将其颜色值写入帧缓存的相应单元中。

2.2 x-扫描线算法

x-扫描线算法的基本思想是，按照扫描线的顺序，计算扫描线与多边形的相交区间，

再用要求的颜色显示这些区间的像素，即完成填充工作。区间的端点可以通过计算扫描线与多边形边界线的交点获得。根据此原理，x-扫描线算法可以填充凸的、凹的或带有孔的多边形区域。

x-扫描线的算法步骤如下：

(1) 确定多边形顶点的最小和最大y值(ymin和ymax)，得到多边形所占有的最大扫描线数。

(2) 从y=ymin到y=ymax，每次用一条扫描线填充。每一条扫描线填充的过程分为4个步骤：

① 求交。计算扫描线与多边形所有边的交点。 ② 排序。把所有交点按x坐标递增的顺序进行排序。

③ 交点配对。配对第一与第二、第三与第四个交点等，每对交点代表一个填充

区间。

④ 区间填色。把这些相交区间内的像素置成不同于背景色的填充色。 x-扫描线算法在处理每条扫描线时，需要与多边形的所有边求交，这样处理效率非常低。因为一条扫描线往往只与少数几条边相交，甚至与整个多边形都不相交。因此，有必要对算法进行改进。

2.3 改进的有效边表算法

2.3.1 改进的有效边表算法

将x-扫描线算法加以改进可以得到改进的有效边表算法，也称y连贯算法。改进可以从三个方面进行：首先，在处理一条扫描线时，仅对与它相交的多边形的边（有效边）求交；其次，利用扫描线的连贯性，考虑到当前扫描线与各边的交点顺序与下一条扫描线与各边的交点顺序很可能相同或非常相似，因此在当前扫描线处理完毕之

4

后，不必为下一条扫描线从头开始构造交点信息；最后，利用多边形的连贯性，认为若某条边与当前扫描线相交，则它很可能也与下一条扫描线相交且其交点与上一次的交点相关。如下图所示，设直线的斜率为k，若y=yi时，x=xi；则当y=yi+1时，有xi+1=xi+1/k。

2.3.2 有效边表

有效边（Active Edge）是指与当前扫描线相交的多边形的边，也称活性边。把有

效边按与扫描线交点x坐标递增的顺序存放在一个链表中，此链表称为有效边表（Active Edge Table， AET）。有效边表的每个结点存放对应边的如下信息：

其中，x为当前扫描线与有效边交点的x坐标；ymax是有效边所在的最大扫描线值，

通过它可以知道何时才能“抛弃”该边；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)。

5