4基本图形生成算法2

2020/5/6,第四章基本图形生成算法（二）,2020/5/6,2/56,主要内容：,直线的扫描转换圆与椭圆的扫描算法区域填充线宽与线型的处理字符裁剪反走样,2020/5/6,3/56,区域填充,区域：点阵表示的图形，像素集合；表示方法：内点表示、边界表示：内点表示：区域填充算法枚举处区域内部的所有像素；内部的所有像素填充同一个颜色；边界像素填充与内部像素不同的颜色；边界表示：枚举出边界上所有的像素边界填充算法；边界上的所有像素填充同一颜色；内部像素填充与边界像素不同的颜色；区域填充：对区域重新着色的过程，即从给定位置开始涂描直到指定的边界条件为止；将指定的颜色从种子点扩展到整个区域的过程；区域填充算法要求区域是连通的；一般步骤：确定那些像素位于填充图元的内部；确定以什么颜色填充这些像素；,2020/5/6,4/56,多边形的扫描转换,扫描转换矩形（1/2）：,voidFillRectangle(Rectangle*rect,intcolor)intx,y;for(y=rect-ymin;yymax;y+)for(x=rect-xmin;xxmax;x+)PutPixel(x,y,color);/*endofFillRectangle()*/,2020/5/6,5/56,多边形的扫描转换,扫描转换矩形（2/2）：矩形是简单的多边形，那么为什么要单独处理矩形？比一般多边形可简化计算；应用多:如窗口系统；共享边界如何处理？原则：左闭右开，下闭上开,2020/5/6,6/56,多边形的扫描转换,多边形的表示方法：顶点表示：用多边形的顶点序列刻划多边形；点阵表示：用位于多边形内象素的集合来刻划多边形；扫描转换多边形：将顶点表示形式转换成点阵表示形式；三种方法：逐点判断法；扫描线算法；边缘填充法；,2020/5/6,7/56,多边形的扫描转换,逐点判断法,#defineMAX100typedefstructintPolygonNum;/多边形顶点个数PointvertexcesMAX/多边形顶点数组Polygon/多边形结构voidFillPolygonPbyP(Polygon*P,intpolygonColor)intx,y;for(y=ymin;y=ymax;y+)for(x=xmin;x=xmax;x+)if(IsInside(P,x,y)PutPixel(x,y,polygonColor);elsePutPixel(x,y,backgroundColor);/*endofFillPolygonPbyP()*/,2020/5/6,8/56,多边形的扫描转换,逐点判断法,逐个判断绘图窗口内的像素：如何判断点在多边形的内外关系？1）射线法;2）累计角度法;3）编码法；1）射线法步骤：1)从待判别点v发出射线;2)求交点个数k;3)K的奇偶性决定了点与多边形的内外关系;4)奇异情况处理;,2020/5/6,9/56,多边形的扫描转换,逐点判断法,2）累计角度法步骤:从v点向多边形P顶点发出射线，形成有向角;计算有相交的和，得出结论;预处理;离散计算方法：编码方法;,2020/5/6,10/56,多边形的扫描转换,逐点判断法,3）编码方法：累计角度方法的离散方法Step:a.预处理，测试点在边上否？b.V为中点作局部坐标系,对象限按逆时针（或顺时针）编码；c.顶点编码Ipi，d.边编码。PiPi+1:PiPi+1=Ipi+1-Ipie.计算PiPi+1（其中PnPn+1=PnP0)：若为0,V在P外；若为+/-4，V在P内；,结论：逐点判断法程序简单，速度太慢，效率低。,2020/5/6,11/56,几个概念：边的连贯性：某条边与当前扫描线相交，也可能与下一条扫描线相交；扫描线的连贯性：当前扫描线与各边的交点顺序与下一条扫描线与各边的交点顺序可能相同或类似；区间连贯性：同一区间上的像素取同一颜色属性；,多边形的扫描转换：扫描线算法：,2020/5/6,12/56,扫描线算法：目标：利用相邻像素之间的连贯性，提高算法效率；处理对象：非自交多边形（边与边之间除了顶点外无其它交点）；,多边形的扫描转换：扫描线算法：,2020/5/6,13/56,扫描线算法基本思想：一条扫描线与多边形的边有偶数个交点,多边形的扫描转换：扫描线算法：,2020/5/6,14/56,区域填充（扫描线算法）,算法步骤：(1)确定多边形所占有的最大扫描线数，得到多边形顶点的最小和最大y值（ymin和ymax）；(2)从y=ymin到y=ymax，每次用一条扫描线进行填充；(3)对一条扫描线填充的过程可分为四个步骤：a.求交：扫描线与各边的交点；b.排序：按X大小对各交点排序；c.交点配对：每对交点表示一个区间；d.区间填色：区间内置填充色；区间外填背景色；,2020/5/6,15/56,例：扫描线6的填充。1、求交：A(2),B(3.5),C(7),D(11)；2、排序:A(2),B(3.5),C(7),D(11)；3、交点配对:(0,2),(2,3.5),(3.5,7),(7,11),(11,以后)；,存在问题：当扫描线与多边形顶点相交时，交点的取舍问题。如：扫描线2正确,扫描线7错误。,区域填充（扫描线算法）,2020/5/6,16/56,解决方法：当扫描线与多边形的顶点相交时：若共享顶点的两条边分别落在扫描线的两边，交点只算一个；若共享顶点的两条边在扫描线的同一边，这时交点作为零个或两个。多边形边界上象素的取舍问题：例：22图形填充：若不加处理则变成33；解决办法：下闭上开；左闭右开；,区域填充（扫描线算法）,2020/5/6,17/56,扫描线算法：扫描线与边的交点类型：第一类交点：新出现的边与扫描线的交点；第二类交点：位于同一条边上的后继交点；,多边形的扫描转换：扫描线算法：,2020/5/6,18/56,扫描线算法：交点的取整规则要求：使生成的像素全部位于多边形之内用于线画图元扫描转换的四舍五入原则导致部分像素位于多边形之外，从而不可用假定非水平边与扫描线y=e相交，交点的横坐标为x,规则如下：,多边形的扫描转换：扫描线算法：,2020/5/6,19/56,扫描线算法：交点的取整规则规则1：X为小数，即交点落于扫描线上两个相邻像素之间；(a)交点位于左边之上，向右取整；(b)交点位于右边之上，向左取整；,多边形的扫描转换：扫描线算法：,2020/5/6,20/56,扫描线算法：交点的取整规则规则2：边界上象素的取舍问题，避免填充扩大化;解决方法：边界象素：规定落在右上边界的象素不予填充；具体实现时，只要对扫描线与多边形的相交区间左闭右开；,多边形的扫描转换：扫描线算法：,2020/5/6,21/56,扫描线算法：交点的取整规则规则3：扫描线与多边形的顶点相交时，交点的取舍，保证交点正确配对。解决方法：检查两相邻边在扫描线的哪一侧。只要检查顶点的两条边的另外两个端点的Y值，两个Y值中大于交点Y值的个数是0，1，2，来决定取0，1，2个交点。,多边形的扫描转换：扫描线算法：,2020/5/6,22/56,计算扫描线与多边形各边的交点：最简单的方法：将多边形的所有边放在一个表中；缺点：效率低改进的有效边表算法（Y连贯性算法）改进原理：处理一条扫描线时，仅对有效边求交；利用扫描线的连贯性；利用多边形边的连贯性；,多边形的扫描转换：扫描线算法：,2020/5/6,23/56,活性边（ActiveEdge）：指与当前扫描线相交的多边形的边，也称为活性边。活性边表（ActiveEdgeTable,AET）：把活性边按与扫描线交点x坐标递增的顺序存放在一个链表中，此链表称活性边表。活性边表的每个结点：xymax1/knext边表（EdgeTable）的构造（1/2）：(1)首先构造一个纵向链表，链表的长度为多边形所占有的最大扫描线数，链表的每个结点，称为一个桶，对应多边形覆盖的每一条扫描线。(2)将每条边的信息链入与该边最小y坐标（ymin）相对应的桶处。也就是说，若某边的较低端点为ymin，则该边就放在相应的扫描线桶中。,多边形的扫描转换：扫描线算法：,2020/5/6,24/56,边表（EdgeTable）的构造（2/2）：(3)每条边的数据形成一个结点，内容包括：该扫描线与该边的初始交点x（即较低端点的x值），1/k，以及该边的最大y值ymax。x|yminymax1/kNEXT(4)同一桶中若干条边按X|ymin由小到大排序，若X|ymin相等，则按照1/k由小到大排序。,多边形的扫描转换：扫描线算法：,2020/5/6,25/56,多边形的扫描转换：扫描线算法：,算法涉及的数据结构:1）活性边：与当前扫描线相交的边。按交点x的增量顺序存放在一个链表中；该链表称作活性边表（AET);,typedefstructintymax;floatx,deltax;Edge*nextEdge;Edge;,AET的结点信息：Ymax:所交边的最高扫描线号;X：当前扫描线与边的交点的x坐标;X：边的斜率的倒数;Nextage:下一条边的指针;,2020/5/6,26/56,2）新边表:按照边的下端点y坐标对非水平边进行分类的指针数组,下端点y坐标值等于i的边属于第i类;作用：方便活性边表的建立与更新。,typedefstructintymax;floatx,deltax;Edge*nextEdge;Edge;,作用:避免盲目求交:处理一条扫描线时，为求出它与多边形边的所有交点，必须将它与所有的边进行求交测试。实际上只有某几条边与该扫描线有交点。边的新建表正是用来排除不必要的求交测试。,多边形的扫描转换：扫描线算法：,2020/5/6,27/56,活性边表算法步骤：(1)初始化：构造边表，AET表置空；(2)将第一个不空的ET表中的边与AET表合并；(3)由AET表中取出交点对进行填充。填充之后删除y=ymax的边；(4)yi+1=yi+1,根据xi+1=xi+1/m计算并修改AET表，同时合并ET表中y=yi+1桶中的边，按次序插入到AET表中，形成新的AET表；(5)AET表不为空则转(3)，否则结束。,多边形的扫描转换：扫描线算法：,2020/5/6,28/56,边填充算法：求余运算：假定A为一个正整数，则M的余定义为AM,记为。计算机中取A为n位能表示的最大整数。即，A=0 xFFFFFFFF算法由来：光栅图形中，如果某区域已着上值为M的颜色值做偶数次求余运算，该区域颜色不变；而做奇数次求余运算，则该区域颜色变为值的颜色。这一规律应用于多边形扫描转换，就为边填充算法。求余运算可用异或显示模式实现:算法基本思想：对于每条扫描线和每条多边形边的交点，将该扫描线上交点右方的所有象素取余。,多边形的扫描转换：边填充算法：,2020/5/6,29/56,多边形的扫描转换,边填充算法：算法1（以扫描线为中心的边填充算法）：1、将当前扫描线上的所有象素着上颜色；2、求余：for(i=0;i=m;i+)在当前扫描线上从横坐标为Xi的交点向右求余；,2020/5/6,30/56,多边形的扫描转换,边填充算法：算法2（以边为中心的边填充算法）：1、将绘图窗口的背景色置为；2、对多边形的每一条非水平边做：从该边上的每个象素开始向右求余；,2020/5/6,31/56,多边形的扫描转换,边填充算法：结论：适于具有帧缓存的图形系统。处理后，按扫描线顺序读出帧缓存的内容，送入显示设备；优点：算法简单；缺点：对于复杂图形，每一象素可能被访问多次，输入/输出的量比扫描线算法大得多；,2020/5/6,32/56,区域填充（多边形域填充）,栅栏填充算法：栅栏:一条经过多边形顶点且与扫描线垂直的直线。它把多边形分为两半；基本思想：对于每个扫描线与多边形边的交点,将交点与栅栏之间的象素取补。若交点位于栅左边,则将交点之右,栅栏之左的所有像素取补;若交点位于栅栏右边,则将栅栏之右交点之左的象素取补；左图为采用栅栏填充算法填充多边形的示意图：,缺点：还是有些象素会重复访问,2020/5/6,33/56,区域填充（多边形域填充）,边标志算法：分为两步骤：第一步，对多边形的每条边进行直线扫描转换，亦即对多边形边界所经过的象素打上边标志；第二步，填充。对每条与多边形相交的扫描线，依从左到右顺序，逐个访问该扫描线上象素。使用一个布尔量inside来指示当前点的状态，若点在多边形内，则inside为真。若点在多边形外，则inside为假。inside的初始值为假，每当当前访问象素为被打上边标志的点，就把inside取反。对未打标志的象素，inside不变。若访问当前象素时，对inside作必要操作之后，inside为真，则把该象素置为多边形色。,当用软件实现本算法时，速度与改进的有效边表算法相当，但用硬件实现后速度会有很大提高；,2020/5/6,34/56,区域填充（多边形域填充）,种子填充算法区域填充对区域重新着色的过程；将指定的颜色从种子点扩展到整个区域的过程；区域填充算法要求区域是连通的；连通性：4连通、8连通；4连通：8连通：,2020/5/6,35/56,区域填充（多边形域填充）,4连通与8连通区域的区别：连通性：4连通可看作8连通区域，但对边界有要求；对边界的要求：,2020/5/6,36/56,区域填充（多边形域填充）,递归填充算法内点表示的4连通区域,voidFloodFill4(intx,inty,intoldColor,intnewColor)if(GetPixel(x,y)=oldColor)PutPixel(x,y,newColor);FloodFill4(x,y+1,oldColor,newColor);FloodFill4(x,y-1,oldColor,newColor);FloodFill4(x-1,y,oldColor,newColor);FloodFill4(x+1,y,oldColor,newColor);/*endofFloodFill4()*/,取(x,y)为种子点,2020/5/6,37/56,区域填充（多边形域填充）,2020/5/6,38/56,区域填充（多边形域填充）,递归填充算法问题：内点表示与边界表示的8连通区域？缺点：(1)有些象素会入栈多次，降低算法效率；栈结构占空间；(2)递归执行，算法简单，但效率不高，区域内每一象素都引起一次递归，进/出栈，费时费内存；改进算法，减少递归次数，提高效率；方法之一：使用扫描线填充算法；,2020/5/6,39/56,扫描转换扇形区域(1/5),扇形区域的描述:原理：同扫描转换多边形；问题：如何确定扫描线与直线段和圆弧段的相交顺序；方法：分类：按点和点所处象限的不同，需要将扇形区域分成44=16种情况；,2020/5/6,40/56,扫描转换扇形区域(2/5),假设点落在第一象限,扇形区域的扫描转换分四种情况（1/3）：1、落在第一象限,2020/5/6,41/56,扫描转换扇形区域(3/5),2、落在第二象限时分两种情况当时当时,2020/5/6,42/56,扫描转换扇形区域(4/5),3、落在第三象限4、落在第四象限,2020/5/6,43/56,扫描转换扇形区域(5/5),遗留问题：当落在其它区域时?其它方法：多边形逼近法,2020/5/6,44/56,区域填充圆域的填充,将多边形区域填充原理推广到圆域的填充；1）计算每条扫描线与圆域的相交区间；2）把区间内象素用指定颜色填充；相交区间的确定：中点画圆法计算交点确定相交区间；函数F的计算可以采用增量法提高效率；,2020/5/6,45/56,主要内容：,直线的扫描转换圆与椭圆的扫描