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

《有效边表填充算法的实现计算机图形学课程设计》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、计算机图形学课程设计设计题目改进的有效边表算法对多边形的填充学院名称信息科学与技术学院专业名称计算机科学与技术学生姓名刘柯学生学号201213030112任课教师梅占勇设计（论文）成绩教务处制2015年9月28日27目录一、设计内容与要求31.1设计题目31.2设计内容31.3设计目标3二、总体设计32.1多边形的表示32.2x-扫描线算法42.3改进的有效边表算法42.3.1改进的有效边表算法42.3.2有效边表52.3.3边表6三、详细设计83.1改进的有效边表算法的实现83.2有效边表算法程序流程图9四、测试结果9五、

2、总结15六、源代码15参考文献2627一、设计内容与要求1.1设计题目用改进的有效边表算法实现多边形的填充1.2设计内容使用OpenGL实现用改进的有效边表算法填充多边形1.3设计目标参照课本上改进的有效边表算法的思想，实现该算法的C语言代码，并用该算法搭配OpenGL以像素点的方式绘制出给定顶点坐标的多边形。二、总体设计2.1多边形的表示在计算机图形学中，多边形有2种重要的表示方法：顶点表示和点阵表示。顶点表示用多边形的顶点序列来刻画多边形，这种方法直观、几何意义强，占用内存少，应用普遍，但它没有明确指出哪些像素在多边形内

3、，故不能直接用于面着色。点阵表示用位于多边形内的像素的集合来刻画多边形。这种表示法虽然失去了许多重要的几何信息，但便于运用帧缓存表示图形，是面着色所需要的图形表示形式。27大多数图形应用系统采用顶点序列表示多边形，而顶点表示又不能直接用于显示，那么就必须有从多边形的顶点表示到点阵表示的转换，这种转换称为多边形的扫描转换或多边形的填充。即从多边形的顶点信息出发，求出位于其内部的各个像素，并将其颜色值写入帧缓存的相应单元中。2.2x-扫描线算法x-扫描线算法的基本思想是，按照扫描线的顺序，计算扫描线与多边形的相交区间，再用要求的

4、颜色显示这些区间的像素，即完成填充工作。区间的端点可以通过计算扫描线与多边形边界线的交点获得。根据此原理，x-扫描线算法可以填充凸的、凹的或带有孔的多边形区域。x-扫描线的算法步骤如下：(1)确定多边形顶点的最小和最大y值(ymin和ymax)，得到多边形所占有的最大扫描线数。(2)从y=ymin到y=ymax，每次用一条扫描线填充。每一条扫描线填充的过程分为4个步骤：①求交。计算扫描线与多边形所有边的交点。②排序。把所有交点按x坐标递增的顺序进行排序。③交点配对。配对第一与第二、第三与第四个交点等，每对交点代表一个填充区间

5、。④区间填色。把这些相交区间内的像素置成不同于背景色的填充色。x-扫描线算法在处理每条扫描线时，需要与多边形的所有边求交，这样处理效率非常低。因为一条扫描线往往只与少数几条边相交，甚至与整个多边形都不相交。因此，有必要对算法进行改进。2.3改进的有效边表算法2.3.1改进的有效边表算法27将x-扫描线算法加以改进可以得到改进的有效边表算法，也称y连贯算法。改进可以从三个方面进行：首先，在处理一条扫描线时，仅对与它相交的多边形的边（有效边）求交；其次，利用扫描线的连贯性，考虑到当前扫描线与各边的交点顺序与下一条扫描线与各边的交

6、点顺序很可能相同或非常相似，因此在当前扫描线处理完毕之后，不必为下一条扫描线从头开始构造交点信息；最后，利用多边形的连贯性，认为若某条边与当前扫描线相交，则它很可能也与下一条扫描线相交且其交点与上一次的交点相关。如下图所示，设直线的斜率为k，若y=yi时，x=xi；则当y=yi+1时，有xi+1=xi+1/k。2.3.2有效边表有效边（ActiveEdge）是指与当前扫描线相交的多边形的边，也称活性边。把有效边按与扫描线交点x坐标递增的顺序存放在一个链表中，此链表称为有效边表（ActiveEdgeTable，AET）。有效边

7、表的每个结点存放对应边的如下信息：其中，x为当前扫描线与有效边交点的x坐标；ymax是有效边所在的最大扫描线值，通过它可以知道何时才能“抛弃”该边；1/k是边斜率的倒数；next是下一个结点的指针。如下图所示的多边形P0P1P2P3P4P5P6，其顶点表示为：27P0(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边表有效边表给出了扫描线和有效边交点坐标的计算方法，但是没有给出新边出现的位置坐标。为了方便有效边表的建立与

8、更新，就需要构造一个边表（EdgeTable，ET），用以存放扫描线上多边形各条边的信息。由于水平边的1/k为∞，并且水平边本身就是扫描线，所以在建立边表时不予考虑。27边表的构造分为4个步骤：①首先构造一个纵向链表，链表的长度为多边形占有的最大扫描线数，链表的每个结点，称为一个桶，对应多