lesson05多边形填充

《lesson05多边形填充》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第三节多边形填充1、概述2、多边形扫描线填充3、简单种子填充算法4、扫描线种子填充5、模式填充1、多边形填充算法概述在计算机图形学中，多边形有两种重要的表示方法：顶点表示和点阵表示。顶点表示是用多边形的顶点序列来表示多边形。特点：表示直观、几何意义强、占内存少，易于进行几何变换，但由于它没有明确指出哪些象素在多边形内，故不能直接用于面着色；点阵表示是用位于多边形内的象素集合来刻画多边形。特点：这种表示丢失了许多几何信息，但便于帧缓冲器表示图形，是面着色所需要的图形表示形式。两个概念光栅图形的一个基本问题是把多边

2、形的顶点表示转换为点阵表示，这种转换称为多边形的扫描转换。区域填充：则是指先将在点阵表示的多边形区域内的一点（称为种子点）赋予指定的颜色和灰度，然后将这种颜色和灰度扩展到整个区域内的过程。2、多边形扫描线填充原理多边形扫描线填充根据多边形内部点的连续性知：一条扫描线与多边形的交点中，入点和出点之间所有点都是多边形的内部点。所以，对所有的扫描线填充入点到出点之间所有的点就可填充多边形。判断扫描线上的点是否在多边形之内对于一条扫描线，多边形的扫描转换过程可以分为四个步骤：（1）求交：计算扫描线与多边形各边的交点；

3、（2）排序：把所有交点按x值递增顺序排序；（3）配对：第一个与第二个，第三个与第四个等等；每对交点代表扫描线与多边形的一个相交区间;（4）着色：把相交区间内的象素置成多边形颜色，把相交区间外的象素置成背景色。0246810122468101234P3P2P1P4P5P6e3e4e2e1e5e6多边形扫描线填充原理多边形扫描线填充p1,p3,p4,p5属于局部极值点，要把他们两次存入交点表中。如扫描线y=7上的交点中，有交点(2,7,13)，按常规方法填充不正确，而要把顶点(7,7)两次存入交点表中(2,7,7,

4、13)。p2，p6为非极值点，则不用如上处理。0246810122468101234024681012246810123P1P4P5P6e3e4e2e1e5e6P3P2P1P4P5P6e3e4e2e1e5e6P3P2算法原理为了提高效率，在处理一条扫描线时，仅对与它相交的多边形的边进行求交运算。把与当前扫描线相交的边称为活性边，并把它们按与扫描线交点x坐标递增的顺序存放在一个链表中，称此链表为活性边表(AET)。x为交点，Δx当前扫描线与下一扫描线的x增量Ymax边所交的最大的扫描线号6的AET表7的AET表公

5、式推导设该边的直线方程为：ax+by+c=0，当前扫描线及下一条扫描线与边的交点分别为(xi,yi)、(xi+1,yi+1)，则：axi+byi+c=0axi+1+byi+1+c=0由此得：xi+1=(-b*yi+1-c)/a由于yi+1=yi+1所以xi+1=1/a*(-b*yi+1-ci)=xi-b/a其中△x=-b/a为常数分析结论综上所述，活性边表的结点应为对应边保存如下内容：第1项存当前扫描线与边的交点坐标x值；第2项存从当前扫描线到下一条扫描线间x的增量Dx；第3项存该边所交的最高扫描线号ymax。

6、为了方便活性边表的建立与更新，我们为每一条扫描线建立一个新边表（ET）,存放在该扫描线第一次出现的边。也就是说，若某边的较低端点为ymin，则该边就放在扫描线ymin的新边表中。多边形扫描线填充原理数据结构：按扫描线建立一个吊桶，边表ET挂在与该边低端y值相同的扫描线桶中。ET表中的每一项都表示一条边，包含的信息有:该边的与扫描线初始交点x(较低点）；该边的斜率倒数；该边最大y值ymax；指向下一条具有相同较低端y坐标的边的指针。^^^825^7-1576543210^8011^702^3352-35多边形扫

7、描线填充原理多边形扫描线填充由前可知：局部极小点对应的桶内有两条边的信息；局部极大点对应的桶内为空；非局部极值水平线不用表示，水平线上的边按非极值点处理；局部极值水平线不用表示，水平线上的边也不作处理。特殊情况表的处理扫描线与多边形相交的边分别位于扫描线的两侧，则计一个交点，如点P5，P6。扫描线与多边形相交的边位于扫描线同侧，且yiyi-1，yi>yi+1，则计0个交点(不填色)，如P1。扫描线与多边形边界重合(当要区分边界和边界内区域时需特殊

8、处理)，则计1个交点。具体实现时，只需检查顶点的两条边的另外两个端点的y值。按这两个y值中大于交点y值的个数是0,1,2来决定。多边形扫描线填充算法描述多边形扫描线填充置y为AET表中非定桶的最小y坐标值置AET表为空，且把y桶中ET表的边加入AET表中whileAET表中非空do     begin对AET表中的xmin值按升序排列按照AET表中交点前后次序，在每对奇偶交点间的x段