资源描述：
《计算机图形学---多边形填充算法知识讲解.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、计算机图形学---多边形填充算法4.3.1多边形的表示方法顶点表示是用多边形的顶点的序列来描述多边形该表示几何意义强、占内存少但它不能直观地说明哪些像素在多边形内点阵表示是用位于多边形内的像素的集合来刻划多边形该方法虽然没有多边形的几何信息是面着色所需要的图像表示形式多边形填充就是把多边形的顶点表示转换为点阵表示即从多边形的给定边界出发，求出位于其内部的各个像素，并将帧缓冲器内的各个对应元素设置相应的灰度或颜色。多边形的填充方法：扫描线方法边缘填充方法边界标志方法栅栏填充方法4.3.2多边形填充的扫描线算法算法特点：基本概念：充分利用了相邻象素之间的连续性，避免对象
2、素的逐点判断和反复求交运算，减少了计算量，提高了算法速度，是效率较高的多边形填充算法，处理对象为非自交多边形。区域的连续性扫描线的连续性边的连续性关于一般多边形的填充过程,对于一条扫描线,可分为四步:求交排序交点配对区间填色奇点的处理区域的连续性设多边形P的顶点各顶点Pi的纵坐标yi的递减数列p0p1p7p2p3p4p5p6p8p1,p7,p3,p6,p2,p5,p0,p4,p8(1)梯形的两底边分别在y=和y=两条扫描线上，腰在多边形P的边上或在显示屏幕的边界上。它们具有下列性质(设为整数)：(2)梯形可分为两类：一类位于多边形P的内部；另一类在多边形P的外部。(
3、3)两类梯形在长方形区域{，}内相间的排列。位于y=和y=两条扫描线之间的长方形区域被多边形P的边分割成若干梯形p0p1p7p2p3p4p5p6p8由区域的相关性知当知道一个区域内一点与多边形的位置关系，即可确定该区域内所有点与多边形之间的内外关系扫描线的连续性扫描线的连续性是区域连续性在扫描线上的体现012345678设e为一整数≥e≥若扫描线y=e与多边形P的边Pi-1Pi相交，则记其交点的横坐标为y=e该扫描线与P的边界各交点横坐标的递增序列此交点序列具有以下性质：(1)l是偶数(2)扫描线被分成好多区段,一部分在多边形内,一部分在多边形外(3)两类线段间隔排
4、列由区域的连贯性和扫描线的连续性知:若已知某一点与多边形的位置关系,就可知该点所在线段与多边形的位置关系边的连续性若d为一整数，d=e–1，且yi0≥y≥yin；设位于扫描线y=d上的交点序列为012345678y=ey=d则两交点序列之间有以下关系:1两序列元素的个数相等2点()与()位于多边形P的同一边上，即以上性质称为边的连续性奇点定义如果，则称顶点Pi为极值点；否则称Pi为非极值点。奇点的处理当扫描线与多边形P的边界的交点是P的顶点时，则称该交点为奇点p0p1p7p2p3p4p5p6p8要把奇点作为几个交点来处理呢??多边形P的顶点可分为两类：极值点和非极值
5、点如果把每一奇点简单地计为一个交点，则交点个数可能出现奇数。若将每一奇点都简单地计为两个交点，同样会导致反常的结果为了使交点个数保持为偶数,规定当奇点是P的极值点时，该点按两个交点计算；否则按一个交点计算。预处理:若Pi是非极值点，则将两边中位于扫描线y=yi上方的那条边在Pi点处截去一单位长扫描线算法的数据结构和实现步骤扫描线算法的数据结构多边形P0P1P2P3P4P5P6P0数据结构边的分类表ET和边的活化链表AELET和AEL中的多边形的边由四个域组成：ymax边的上端点的y坐标在ET中为边的下端点的x坐标x在AEL中是边与扫描线交点的x坐标Δx边的斜率的倒数
6、next指向下一条边的指针[P0P1P2P3P4P5P6]=[(2,5)(2,10)(9,6)(16,11)(16,4)(12,2)(7,2)]多边形P0P1P2P3P4P5P6P0[P0P1P2P3P4P5P6]=[(2,5)(2,10)(9,6)(16,11)(16,4)(12,2)(7,2)]对奇点采用了预处理的边y筒分类表ET是按边下端点的纵坐标y对边进行分类的指针数组同一类中，各边按x值递增的顺序排列成行下端点的纵坐标y等于i的边归入第i类，水平边除外[P0P1P2P3P4P5P6]=[(2,5)(2,10)(9,6)(16,11)(16,4)(12,2)
7、(7,2)]多边形P0P1P2P3P4P5P6P0对奇点采用了预处理的边y筒边的活化链表AEL由与当前扫描线相交的所有多边形的边组成-5/357AELe7e54212AEL在y=2扫描线上的当前状态它记录了多边形沿扫描线的交点序列,并根据递推关系,不断地更新交点序列它是一个动态列表，新边插入，旧边删除[P0P1P2P3P4P5P6]=[(2,5)(2,10)(9,6)(16,11)(16,4)(12,2)(7,2)][P0P1P2P3P4P5P6]=[(2,5)(2,10)(9,6)(16,11)(16,4)(12,2)(7,2)]-5/35AELe7e5421
