计算机图形学基本光栅图形算法.ppt

本章内容本章内容3.1 3.1 用用JavaJava语言绘图语言绘图13.2 3.2 直线的扫描转换直线的扫描转换23.3 3.3 圆的扫描转换圆的扫描转换33.4 3.4 多边形的扫描转换多边形的扫描转换43.5 3.5 区域填充区域填充53.6 3.6 字符的生成字符的生成63.7 3.7 光栅图形的反走样算法光栅图形的反走样算法73.2 3.2 直线的扫描转换直线的扫描转换 图形图像是由屏幕上不同亮度不同颜色的光点图形图像是由屏幕上不同亮度不同颜色的光点（像素）组成。在光栅显示器的荧光屏上生成一（像素）组成。在光栅显示器的荧光屏上生成一个对象，实质上是个对象，实质上是往帧缓存寄存器的相应单元中往帧缓存寄存器的相应单元中填入数据填入数据。所以所以 对对直线直线进行进行光栅化光栅化的时候，只能在显示器所给的时候，只能在显示器所给定的有限个像素组成的点阵中确定定的有限个像素组成的点阵中确定最佳逼近于该最佳逼近于该直线的一组像素直线的一组像素，用这些像素表示该直线。，用这些像素表示该直线。所以所以 生成直线的主要工作是：生成直线的主要工作是：快速找出快速找出距离直线最距离直线最近的网格点近的网格点，用这些网格点对应的像素表示该直，用这些网格点对应的像素表示该直线。线。3像素逼近直线示意图像素逼近直线示意图图像元素图像元素可寻址点可寻址点43.2.1 3.2.1 基本增量算法基本增量算法 设直线设直线 满足满足 ，由于直线的斜，由于直线的斜率小于等于率小于等于1 1，所以，该直线的扫描转换可从最左端开，所以，该直线的扫描转换可从最左端开始，始，每次递增一个单位，对每个每次递增一个单位，对每个 ，相应的有，相应的有 ，则，则 所以，所以，每增加一个单位，每增加一个单位，只需加上一个只需加上一个 ，这样，这样就去掉了乘法运算，提高了算法效率。在该算法中，就去掉了乘法运算，提高了算法效率。在该算法中，直直线上的所有点的线上的所有点的 和和 值可由前一点的值加一个基本增值可由前一点的值加一个基本增量得到量得到，所以该算法称为，所以该算法称为基本增量算法基本增量算法。3.2.1 基本增量算法基本增量算法(DDA-digital differential (DDA-digital differential analyzer)analyzer)1、基本思想：、基本思想：53.2.1 3.2.1 基本增量算法基本增量算法注：注：上述讨论只适合上述讨论只适合 的情况，当的情况，当 时，只需将时，只需将 和和 的角色的角色互换互换，即，即 每每次增加一个单位，次增加一个单位，每次增加每次增加 。基本增量算法也叫基本增量算法也叫数字微分分析器算法数字微分分析器算法（Digital Differential Analyzer，DDA）。）。DDA是是用数值方法求解微分方程的一种设备，即根据用数值方法求解微分方程的一种设备，即根据 111和和 的一阶导数，在的一阶导数，在 和和 方向上渐进地以小步方向上渐进地以小步长移动，由此产生连续的像素坐标长移动，由此产生连续的像素坐标 。6 2、直线的表示：直线的表示：设直线的起点坐标为设直线的起点坐标为(xs，ys)，终点坐标为终点坐标为(xe,ye)，令令xxe-xs，y ye-ys，则，则直线参数直线参数方程方程为为v目标：能快速地求出能很好地表示直线的目标：能快速地求出能很好地表示直线的像素像素第第 步时步时(3.1)73 3、提高速度的方法：、提高速度的方法：乘法用加法乘法用加法实现，每一个点坐标都可以由前一个坐标变化一实现，每一个点坐标都可以由前一个坐标变化一个个增量增量得到。得到。设设(xi,yi)是第是第i 步得的直线上的点，则直线上第个步得的直线上的点，则直线上第个i+1 点是点是(xi+1,yi+1)，其中其中 当当x y0，即即直线斜率小于直线斜率小于1 1，应使，应使x x方向每次增加方向每次增加1 1，y方方向最多增加向最多增加1 1，此时取，此时取t=1/x；同理同理,当当yx0,直线斜率大于直线斜率大于1 1，取，取t=1/y，所以所以(3.2)令令 ，将参数区间，将参数区间0，1分为分为 等份，等份，即即 每次的增量为每次的增量为 。8 下图中，用公式（下图中，用公式（3.2）求得的直线）求得的直线 上的上的点用空心圆表示，但显示时要用像素来表示，点用空心圆表示，但显示时要用像素来表示，即采用即采用四舍五入四舍五入的办法得到最靠近空心圆点的的办法得到最靠近空心圆点的像素，用这些像素（下图中的实心圆点）来表像素，用这些像素（下图中的实心圆点）来表示直线。示直线。图中实心圆点表示用图中实心圆点表示用DDA方法生成的直线方法生成的直线9图中黑点表示用DDA法生成的直线4 4、直线的、直线的DDA算法程序算法程序void dda(Graphics g,int x1,int x2,int y1,int y2)int k;float x,y,dx,dy;k=Math.abs(x2-x1);if(Math.abs(y2-y1)k)k=Math.abs(y2-y1);dx=(float)(x2-x1)/k;dy=(float)(y2-y1)/k;/变化的增量变化的增量 x=(float)(x1);y=(float)(y1);for(int i=0;ik;i+)g.drawLine(int)(x+.5f),(int)(y+.5f),(int)(x+.5f),(int)(y+.5f);x=x+dx;y=y+dy;/end DDA 完成四舍五入完成四舍五入10实实 例例设给定直线的起点坐标为设给定直线的起点坐标为(0，0)，终点坐标为终点坐标为(9，6)，则上述，则上述DDA算法画出的直线如下图所示。算法画出的直线如下图所示。DDA方法所画直线图方法所画直线图DDA算法缺点：算法缺点：需要进行浮点数需要进行浮点数运算，产生一个运算，产生一个像素要做两次加像素要做两次加法和两次取整运法和两次取整运算，运行效率低算，运行效率低且取整运算不利且取整运算不利于硬件实现。于硬件实现。11算法背景算法背景设直线的起点坐标为设直线的起点坐标为 ，斜率为，斜率为 。下面就。下面就 的情况来说明该算的情况来说明该算法。取法。取 为像素所在点的横坐标（整为像素所在点的横坐标（整数），令数），令 ，直线上相邻，直线上相邻两点的坐标满足关系两点的坐标满足关系(3.3)一般来说，一般来说，不一定是整数，所以不一定是整数，所以 也不一定是整数，因此也不一定是整数，因此要用靠近该点最近的网格点要用靠近该点最近的网格点 来近似。由于来近似。由于取整取整计算量较大，为了提高效率，计算量较大，为了提高效率，Bresenham算法用下面的方算法用下面的方法来避免使用取整运算。法来避免使用取整运算。3.2.2 3.2.2 Bresenham算法算法12当当B在在A的下面时，的下面时，此时应取，此时应取C点作为点作为 ；当当B在在A的上面时，的上面时，则应取，则应取D点作为点作为 。BACD图图3.4 3.4 的几何意义的几何意义设图设图3.4中已得到第中已得到第 个显示的点个显示的点 ，B点是直线与第点是直线与第 列列网格线的交点网格线的交点 ，则第，则第 个显个显示的点示的点 只能从只能从C或或D点点中中去选。设去选。设A为为CD边的中点，令误边的中点，令误差项差项(3.4)算法思想：算法思想：13通过递推的方式，高效地计算点序列和通过递推的方式，高效地计算点序列和 ，由图，由图3.4可得可得(3.5)由式（由式（3.3）（）（3.5）可得）可得=(3.6)14注：注：式（式（3.5）和（）和（3.6）是根据图）是根据图3.4所示的情况推出所示的情况推出的，容易验证，式（的，容易验证，式（3.5）和（）和（3.6）对图）对图3.5所示所示的两种情况也成立。的两种情况也成立。CBADBACD图图3.5 3.5 的几何意义的其他两种情况的几何意义的其他两种情况15算法的程算法的程序实现序实现由式（由式（3.3）和（）和（3.4）可得）可得假设直线段起始点的坐标分假设直线段起始点的坐标分量量 和和 均为整数，则均为整数，则有有m=(double)dy/(double)dx；e=m0.5；for(i=0;i=0)y=y+1；e=e1;x=x+1；e=e+m;该算法在计算直线斜率和误差项该算法在计算直线斜率和误差项时用到了小数与除法，可改用整时用到了小数与除法，可改用整数来避免除法，以提高算法的效数来避免除法，以提高算法的效率和减少算法的复杂性。由于算率和减少算法的复杂性。由于算法中只用到误差项的符号，因此法中只用到误差项的符号，因此可进行如下替换：可进行如下替换：。16改进后的改进后的算法程序算法程序void bresenham(Graphics g,int xs,int ys,int xe,int ye)int dx=xe-xs;int dy=ye-ys;int e=2*dy-dx;int x=xs;int y=ys;for(int i=0;i=0)y=y+1;e=e-2*dx;x=x+1;e=e+2*dy;注：注：上面讨论了上面讨论了 的情况，如果的情况，如果 ，则需把，则需把 和和 的地位的地位互换互换。如果。如果 或或 ，程序中，程序中 或或 需换成需换成 或或 ，同时，同时 也应也应相应地改变。相应地改变。173.3 3.3 圆的圆的扫描转换扫描转换1 1、基本原理：、基本原理：假设已选取假设已选取Pi-1为第为第i-1个像素，个像素，则如果则如果Pi-1在在圆内圆内，就要，就要向圆向圆外外方向走一步，若方向走一步，若Pi-1在在圆外圆外就要就要向圆内向圆内走一步。若走一步。若Pi-1在在圆上圆上，则可以向圆内走一步，则可以向圆内走一步，也可以向圆外走。也可以向圆外走。xypiPi+1Pi-1BA(0,0)图图3.9 对圆弧对圆弧AB用正负法取点用正负法取点3.3.1 3.3.1 正负法正负法这样用于表示圆弧的点均在理想这样用于表示圆弧的点均在理想圆弧附近且时正时负，因此称为圆弧附近且时正时负，因此称为正负法正负法。由于这种方法每走完一步，都要比较当前位置的。由于这种方法每走完一步，都要比较当前位置的函数值，以决定下一步的走向，因而也称为函数值，以决定下一步的走向，因而也称为逐点比较法逐点比较法。182 2、正负法的具体实现、正负法的具体实现1 1）圆的表示：设圆的圆心为）圆的表示：设圆的圆心为(0,0),半半径为径为R，则圆的方程为：则圆的方程为：F(x,y)=x2+y2R2=0 ypiPi+1Pi-1BA(0,0)图图3.9 对圆弧对圆弧AB用用正负法取点正负法取点v如何判断一个点和圆的内外关系如何判断一个点和圆的内外关系v当点当点(x,y)在圆内时在圆内时，F(x,y)0；v当点当点(x,y)在圆上时，在圆上时，F(x,y)=0。192 2）实现步骤）实现步骤第第1 1步：步：x0=0，y0=R第第2 2步：步：求得求得Pi(xi,yi)后找点后找点Pi+1的原则为：的原则为：yPiBA(0,0)当当Pi在圆内在圆内时时(F(xi,yi)0)，要向右走一步得要向右走一步得Pi+1，这是向圆外方这是向圆外方向走去。取向走去。取xi+1=xi+1,yi+1=yiPi+1 当当Pi在圆外在圆外时时(F(xi,yi)0)，要要向向下下走走一一步步得得Pi+1，这这是是向向圆圆内内方方向走去，取向走去，取xi+1=xi,yi+1=yi-1Pi+1用来表示圆弧的点均在圆弧附近且用来表示圆弧的点均在圆弧附近且 F(xi,yi)时正时负时正时负 x20当当 时，时，假设已经算出假设已经算出F(xi,yi)，如何计算如何计算F(xi+1,yi+1)？由上可知由上可知 。如果。如果 的值已算出，计算的值已算出，计算 时可分为两种情况：时可分为两种情况：(3.9)当当 时，时，(3.10)由式（由式（3.9）和式）和式(3.10)知知，21算法的程算法的程序实现序实现void pnarc(Graphics g,int radius)int x,y,f;x=0;y=0+radius;f=0;while(y 0)g.drawLine(x,y,x,y);if(f 0)f=f 2*y+1;y-;else f=f+2*x+1;x+;if(y=0)g.drawLine(x,y,x,y);223.3.2 3.3.2 BresenhamBresenham 算法算法 假设圆心假设圆心(0,0)为原点，为原点，考虑考虑AB弧的画法，显示一弧的画法，显示一个整圆时，只要在显示个整圆时，只要在显示AB上任一点上任一点(x,y)时，同时显时，同时显示在圆周上其它示在圆周上其它七个对称七个对称点点(y,x),(y,-x),(x,-y),(-x,-y),(-y,-x),(-y,x),(-x,y)。7 7个对称点个对称点231 1、基本原理、基本原理考虑考虑AB弧段弧段，x每步增加每步增加1，从从 x=0开始开始，到到x=y结束。结束。即有：即有：xi+1=xi+1 相应的相应的yi+1则在两种则在两种 可能中选择：可能中选择：yi+1=yi，或者或者 yi+1=yi-1。所以所以 选择的原则是确定这两个点哪一选择的原则是确定这两个点哪一 个更接近于圆弧。个更接近于圆弧。Pi-1HiLi即：设即：设Pi-1是已选中的一个表示圆弧上的点，下一是已选中的一个表示圆弧上的点，下一个点应从个点应从Hi或或Li中选择。设中选择。设Hi和和Li两点的坐标分别两点的坐标分别为为(xhi,yhi)和和(xli,yli)242 2、BresenhamBresenham的具体实现的具体实现1）令令D(P)=(x2+y2)-R2，表示点表示点P到原点的距离平方与圆的半径的到原点的距离平方与圆的半径的平方之差。令：平方之差。令：当当di=0时时，点点Hi和和Li距距弧弧AB的距离相等的距离相等当当di0时，时，|D(Hi)|D(Li)|，取取Li来显示弧来显示弧AB。Pi-1HiLidi=D(Hi)+D(Li)252 2）di递推公式递推公式设已选中的点设已选中的点Pi-1=(xi-1,yi-1)，则则Hi和和Li点的坐标分别点的坐标分别为为(xi,yi-1)和和(xi,yi-11),Hi+1和和Li+1的坐标分别为的坐标分别为(xi+1,yi)和和(xi+1,yi 1)。因为因为 x0=0,y0=R,x1=x0+1，所以所以 d1=D(H1)+D(L1)=(12+y20-R2)+(12+(y0-1)2-R2)=3-2y0=3-2R di=(x2i+y2i-1-R2)+(x2i+(yi-1-1)2-R2)=2x2i+2y2i-1-2yi-1-2R2+1 di+1=(xi+1)2+y2i-R2+(xi+1)2+(yi-1)2-R2 =2x2i+4xi+2y2i-2yi-2R2+326 di=2x2i+2y 2i-1-2yi-1-2R2+1 (3.13)di+1=2x2i+4xi+2y2i-2yi-2R2+3 (3.14)当当 di0时时,点点 Hi被被 选选 中中,xi=xi-1+1，yi=yi-1，由由 (3.13)-(3.14)得得 di+1=di+4xi+2=di+4xi-1+6 (3.15)当当di0时时,点点Li被选中被选中,xi=xi-1+1，yi=yi-1-1，由由(3.13)-(3.14)得得 di+1=di+4xi-4yi-1+6=di+4(xi-1-yi-1)+10 (3.16)27算法的程算法的程序实现序实现void bresenham_arc(Graphics g,int radius)int x,y,d;x=0;y=radius;d=3-2*radius;while(x y)g.drawLine(x,y,x,y);if(d0)d=d+4*x+6;else d=d+4*(x-y)+10;y-;x+;if(x=y)g.drawLine(x,y,x,y);Bresenham算法在候选的两个像素中，总是选算法在候选的两个像素中，总是选离圆弧最近离圆弧最近的像素为的像素为圆弧的一个近似点，因此，它比正负法决定的像素更合理。圆弧的一个近似点，因此，它比正负法决定的像素更合理。28基本思想基本思想按一定方式计算给定圆弧轨迹上的一系列按一定方式计算给定圆弧轨迹上的一系列顶点顶点，然后用连接相邻点的一系列然后用连接相邻点的一系列直线段直线段来逼近圆弧。来逼近圆弧。用正多边形迫近圆弧法用正多边形迫近圆弧法 设圆弧所在圆的半径为设圆弧所在圆的半径为R，圆弧的起始角和终止角分别为，圆弧的起始角和终止角分别为 和和 ，把圆弧分割成把圆弧分割成 份，则相邻两个顶点之间的夹角为份，则相邻两个顶点之间的夹角为 。设。设顶点序列的第顶点序列的第 个点为个点为 ，为该点的幅角。则下为该点的幅角。则下一个顶点一个顶点 的的坐标坐标为为 或表示为或表示为矩阵形式矩阵形式3.3.3 3.3.3 圆的多边形迫近法圆的多边形迫近法29椭圆弧椭圆弧的生成的生成设椭圆的中心在原点，长短轴分别为设椭圆的中心在原点，长短轴分别为a 和和b，且平行于坐标柚，则该且平行于坐标柚，则该椭圆的参数方程椭圆的参数方程为为，设顶点序列的第设顶点序列的第i个顶点为个顶点为 ,则下一个顶点则下一个顶点 的的坐标坐标应满足应满足 ,由此可得由此可得其中其中303.4.1 3.4.1 多边形的扫描转换多边形的扫描转换1 1、表示方法、表示方法：顶点表示和点阵表示：顶点表示和点阵表示1 1）顶点表示）顶点表示是用多边形的是用多边形的顶点的序列顶点的序列来描述多边形，该表示几何意义强、占来描述多边形，该表示几何意义强、占内存少，但它不能直观地说明哪些像素内存少，但它不能直观地说明哪些像素在多边形内。在多边形内。2 2）点阵表示点阵表示是用位于多边形内的是用位于多边形内的像素像素的集合的集合来描述多边形，该方法虽然没有来描述多边形，该方法虽然没有多边形的几何信息，但具有面着色所需多边形的几何信息，但具有面着色所需要的图像表示形式。要的图像表示形式。3.4 3.4 多边形的扫描转换多边形的扫描转换图图3.11 3.11 多边形顶点表示多边形顶点表示P1P0P2P3P4图图3.16 3.16 多边形点阵表示多边形点阵表示 多边形的扫描转换就是把多边形的顶点表示转换为点阵表示，多边形的扫描转换就是把多边形的顶点表示转换为点阵表示，即从多边形的给定边界出发，求出位于其内部的各个像素，即从多边形的给定边界出发，求出位于其内部的各个像素，并为帧缓存内的各个对应元素设置相应的灰度或颜色。并为帧缓存内的各个对应元素设置相应的灰度或颜色。313.4.2 3.4.2 扫描线算法扫描线算法特点特点：充分利用了相邻像素之间的：充分利用了相邻像素之间的连续性连续性，避免对像素的逐，避免对像素的逐点判断和反复求交运算，减少了计算量，提高了算法速度。点判断和反复求交运算，减少了计算量，提高了算法速度。基本概念：基本概念：1 1）扫描线的连续性扫描线的连续性 2 2）边的连续性边的连续性 3 3）奇点奇点基本思想基本思想 先求出扫描线与多边形边的交点，利用先求出扫描线与多边形边的交点，利用扫扫描线的连续性描线的连续性求出多边形与扫描线相交的连续求出多边形与扫描线相交的连续区域，然后利用多边形区域，然后利用多边形边的连续性边的连续性，求出下一，求出下一条扫描线与多边形的交点，对所有扫描线由下条扫描线与多边形的交点，对所有扫描线由下到上依次处理。到上依次处理。扫描线算法是按扫描线算法是按扫描线的顺序扫描线的顺序计算出扫描线与多边形的计算出扫描线与多边形的相相交区间交区间，然后用要求的颜色填充这些区间内的像素。，然后用要求的颜色填充这些区间内的像素。321扫描线的连续性扫描线的连续性设多边形设多边形P的顶点的顶点 ，将各顶点，将各顶点 的纵坐的纵坐标标 按按递减顺序递减顺序排列排列 ,即即设当前扫描线设当前扫描线 ，与多边形与多边形P的边的边 的交点记为的交点记为 。设。设为为 与与P的边界各交点横坐标的的边界各交点横坐标的递增递增序列，该序列称为序列，该序列称为交点序列。交点序列。(3.21)当知道一条扫描线上当知道一条扫描线上一点一点与多边形的内外关系时，即与多边形的内外关系时，即可确定该可确定该扫描线上所有点扫描线上所有点与多边形之间的内外关系。与多边形之间的内外关系。33 交点序列具有以下交点序列具有以下性质性质：1)交点个数交点个数 l 是偶数；是偶数；2)扫描线上的区间扫描线上的区间 l1位于多边位于多边形形P内（图内（图3.13中的实线段部分），其余区间都在中的实线段部分），其余区间都在P 外（图外（图3.13中的虚线段部分），两类区间沿扫描线相间排列。这中的虚线段部分），两类区间沿扫描线相间排列。这些性质就称为些性质就称为扫描线的连续性扫描线的连续性。P0P1P2P3P4P5P6P7P8xe01xe22xe33xe74xe65xe46图图3.13 扫描线的连续性扫描线的连续性图中图中 -表示在多边形外的区间表示在多边形外的区间 表示在多边形内的区间表示在多边形内的区间根据扫描线的连根据扫描线的连续性，只需求出续性，只需求出扫描线与多边形扫描线与多边形P的边界的所有交的边界的所有交点，就可确定扫点，就可确定扫描线位于多边形描线位于多边形P内的区间。内的区间。342边的连续性边的连续性扫描线的连续性知，序列（扫描线的连续性知，序列（3.21）和（）和（3.22）的点满足以下关系：）的点满足以下关系：（1）两序列元素的个数相等，即）两序列元素的个数相等，即 ；（2）点（）点（）与（）与（）位于多边形）位于多边形P的同一边的同一边 上（见上（见图图3.14），所以），所以 可由下式计算可由下式计算 (3.23)以上性质称为以上性质称为边的连续性边的连续性。若若 ,成立，则扫描线成立，则扫描线 与与扫描线扫描线 和多边形和多边形P相同的边相交，由相同的边相交，由图图3.14 边的连续性边的连续性P0P1P2P3P4P5P6P7P8xe01xe22xe33xe74xe65xe46xd01xd65xd46 设当前扫描线设当前扫描线 的下的下一条扫描线为一条扫描线为 ，且，且 ,设位于扫描线设位于扫描线 上的交点序列为上的交点序列为（3.22）35 但当扫描线与多边形但当扫描线与多边形P 的边界的交点恰好是的边界的交点恰好是P的顶点时的顶点时（该交点称为（该交点称为奇点奇点），必须按不同的情况区别对待。），必须按不同的情况区别对待。3奇点的处理奇点的处理上述两种形式的连续上述两种形式的连续性都基于一个几何事性都基于一个几何事实：每一条扫描线与实：每一条扫描线与多边形多边形P 的边界的的边界的交交点个数都是偶数点个数都是偶数（包（包括零）。括零）。设多边形设多边形P 的顶点为的顶点为 这些顶点可分为两类：这些顶点可分为两类：极值点和非极值点极值点和非极值点。如果。如果 ，则称顶点，则称顶点 为极为极值点（如图值点（如图3.15中的中的 ）；否则称为非极值点（如图）；否则称为非极值点（如图3.15中的中的 ）。）。图图3.15 一个多边形与若干条扫描线一个多边形与若干条扫描线P8P0P1P2P3P4P5P6P736 为使每一条扫描线与多边形为使每一条扫描线与多边形P 的边界的交点个数始终的边界的交点个数始终为偶数，规定当奇点是多边形为偶数，规定当奇点是多边形P 的的极值点极值点时，该点按时，该点按两个两个交点交点计算，计算，否则否则按按一个交点一个交点计算。计算。图图3.16 非极值点的处理非极值点的处理（a）（b）实际计算中，可如下实际计算中，可如下处处理非极值点理非极值点：若：若 是非是非极值点，则将极值点，则将 ,两边中位于扫描线两边中位于扫描线 上方的那条边在上方的那条边在 处处截去一个单位长，这样截去一个单位长，这样就能保证扫描线就能保证扫描线 只和只和 ，中的一边相交，只有一中的一边相交，只有一个交点。个交点。374算法的实现步骤与数据结构算法的实现步骤与数据结构对于每一条扫描线，多边形的填充过程可分为以下对于每一条扫描线，多边形的填充过程可分为以下4步：步：计算扫描线与多边形各边的计算扫描线与多边形各边的交点交点，设交点个数为，设交点个数为n；把所有的交点按把所有的交点按x值递增的顺序进行值递增的顺序进行排列排列；将排序后的第将排序后的第1个与第个与第2个交点，第个交点，第3个与第个与第4个交点，个交点，第第n-1个与第个与第n个交点个交点配对配对，每对交点就代表扫描，每对交点就代表扫描 线与多边形的一个相交区间；线与多边形的一个相交区间；把把相交区间内的像素置成多边形的颜色相交区间内的像素置成多边形的颜色，相交区间外，相交区间外 的像素置成背景色。的像素置成背景色。1234上述方法要计算每一条扫描线与所有边的交点，计算量很大。上述方法要计算每一条扫描线与所有边的交点，计算量很大。为提高效率，可以对每一条扫描线，仅对与它为提高效率，可以对每一条扫描线，仅对与它相交的多边形相交的多边形进进行行求交运算求交运算。38 使用增量计算时，还要知道一条边何时不再与下一条扫描线相交，使用增量计算时，还要知道一条边何时不再与下一条扫描线相交，以及时地把该边从活性边表中删除，因此需要记录下与该边相交以及时地把该边从活性边表中删除，因此需要记录下与该边相交的的最高扫描线号最高扫描线号。活性边表活性边表 与当前扫描线相交的边称为与当前扫描线相交的边称为活性边活性边。把活性边与扫描线的交点按把活性边与扫描线的交点按x坐标递增坐标递增的顺序放在一个链表中，该链表就称为的顺序放在一个链表中，该链表就称为活性边表活性边表（Active Edge List,AEL）。）。设多边形某一条边的方程为设多边形某一条边的方程为 ，当前扫，当前扫描线描线 与该边的交点坐标为与该边的交点坐标为 ，则下一条扫描则下一条扫描线线 与该边的交点与该边的交点 不需要重新计算，不需要重新计算，只要加一个增量只要加一个增量 即可。因为此时有即可。因为此时有其中其中 为常数，并规定为常数，并规定 时，时，。39综上，综上，AELAEL中的节点应由如下中的节点应由如下四四个域组成：个域组成：:边的上端点的边的上端点的y y坐标，即与该边相交的最高扫描线号。坐标，即与该边相交的最高扫描线号。x:边与扫描线的交点的边与扫描线的交点的x x坐标。坐标。:从当前扫描线到下一条扫描线间的从当前扫描线到下一条扫描线间的x x坐标的增量，即边坐标的增量，即边的斜率的倒数。的斜率的倒数。Next:指向下一条边的指针。指向下一条边的指针。新边表新边表 为方便活性边表的建立与更新，还要为每为方便活性边表的建立与更新，还要为每一条扫描线建立一个一条扫描线建立一个新边表新边表（New Edge List,NEL），存放在该扫描线上第一次出），存放在该扫描线上第一次出现的边。也就是说，如果某边的现的边。也就是说，如果某边的较低端点较低端点为为 ，则该边放在扫描线，则该边放在扫描线 的新边表中。的新边表中。注意：水平边不放到任何扫描线的注意：水平边不放到任何扫描线的NEL中，即水平边不参加中，即水平边不参加分类。分类。NEL中的节点结构与中的节点结构与AEL相同，只是相同，只是 x 在这里不再表在这里不再表示边与扫描线的交点，而是表示该边示边与扫描线的交点，而是表示该边较低端点较低端点的的 x 坐标值。坐标值。40具体例子具体例子 图图3.18和和3.19是图是图3.17中多边形中多边形 的新边表的新边表NEL和活性和活性边表边表AEL。在左图中。在左图中 表示边表示边 ，各，各顶点为顶点为 P0P1P6=(2,5)(2,10)(9,6)(16,9)(16,4)(12,2)(7,2)其中，其中，是非极值点，在分类前已是非极值点，在分类前已对边对边 作了预处理，即分别在作了预处理，即分别在 处处把它们截去一个单位长，这样保证扫把它们截去一个单位长，这样保证扫描线描线 只和只和 两边中的一边两边中的一边相交，求得一个交点，相交，求得一个交点，是水平边，是水平边，不参加分类。不参加分类。图图3.17 边形边形P0P1P6P0P3P4e410155P1P2P5P6P0e0e2e3e5e1e641-5/35 16/3AELe0e54214AEL在在y=3扫描线上的状态扫描线上的状态AEL-5/35 11/3e0e54216AEL在在y=4扫描线上的状态扫描线上的状态AEL-5/35 2e0e49016AEL在在y=5扫描线上的状态扫描线上的状态 010 2e1e210-7/411/2AEL在在y=8扫描线上扫描线上的状态的状态AEL 97/341/3e3 9016e4图图3.18 新边表新边表NEL123456e11002xxymaxnexte49016e54212图图3.17 多边形多边形P0P1P6P0P3P4e410155P1P2P5P6P0e0e2e3e5e1e6e210 9-7/4e3997/357e0-5/3423.4.3 3.4.3 边缘填充算法边缘填充算法1 1、特点：、特点：采用对图像进行采用对图像进行逐位求补逐位求补的方法，的方法，免去对边排序免去对边排序 的工作量。的工作量。2、预备知识：预备知识：假设某像素的颜色是假设某像素的颜色是C，对该像素做，对该像素做偶数偶数次求补运算次求补运算后，其颜色还是后，其颜色还是C；做；做奇数奇数次求补运算后，其颜色变为次求补运算后，其颜色变为C。在光栅图形中，如某区域已着上值为在光栅图形中，如某区域已着上值为M的某种颜色，则上的某种颜色，则上述求补运算的结果是：对区域作偶数次求反运算后，该区域述求补运算的结果是：对区域作偶数次求反运算后，该区域的颜色不变；作奇数次求反运算后，该区域的颜色则变成值的颜色不变；作奇数次求反运算后，该区域的颜色则变成值为为M的颜色。的颜色。43 对多边形对多边形 P 的每一的每一非水平边非水平边 （i=0,1,n）上的各像素进）上的各像素进行行向右求补运算向右求补运算，当相对于所有边的求补运算都完成后，多边，当相对于所有边的求补运算都完成后，多边形的扫描转换也随之完成。图形的扫描转换也随之完成。图3.20a为给定的多边形；为给定的多边形；b为对区为对区域赋初值；域赋初值；c、d、e和和f表示逐边向右求补。表示逐边向右求补。(c)(d)(f)(e)(a)(b)图图3.20 边缘填充算法的过程边缘填充算法的过程3 3、边缘填充算法的实现、边缘填充算法的实现443.4.4 边界标志算法边界标志算法1 1、基本原理：、基本原理：首先用一种首先用一种特殊的颜色特殊的颜色在帧缓冲器中将多边形的在帧缓冲器中将多边形的边界边界（水（水平边的部分边界除外）勾画出来。然后再把位于多边形平边的部分边界除外）勾画出来。然后再把位于多边形内内的各个像素着上所需的的各个像素着上所需的颜色颜色。2、算法具体实现步骤：算法具体实现步骤：步骤步骤1 1：以值为以值为boundary_color 的特殊颜色的特殊颜色勾画勾画多边形多边形P的的边界边界。设多边形顶点为。设多边形顶点为Pi=(xi,yi),0in，xi,yi均为均为整数整数；置置Pn+1=P0。每一条扫描线上着上这种特殊颜色的点的个数必每一条扫描线上着上这种特殊颜色的点的个数必定是定是偶数偶数(包括零包括零)。45int red=Color.red.getRGB();public Image boundary()Image image;/定义定义Image对象对象 for(i=0;i0)x=pi.x;else x=pi+1.x;ymax=(Math.max(pi.y,pi+1.y);ymin=(Math.min(pi.y,pi+1.y);for(y=ymin+1;y=ymax;y+)x=(int)(x+dx+.5);if(pixelsy*w+x=red)pixelsy*w+x+1=red;else pixelsy*w+x=red;ImageProducer ip=new MemoryImageSource(w,h,pixels,0,w);image=createImage(ip);return image;图图3.17 多边形多边形P0P1P6P0P3P4e410155P1P2P5P6P0e0e2e3e5e1e646/maxx、maxy、minx、miny是获得的多边形最小矩形包围盒边界值是获得的多边形最小矩形包围盒边界值public Image interior()Image image;int maxx=150,minx=20,maxy=120,miny=20,l;int in_flag；/多边形内部标志变量多边形内部标志变量 for(y=miny;y=maxy;y+)in_flag=0;for(x=minx;xmaxx;x+)l=pixelsy*w+x;if(l=red)if(in_flag=0)in_flag=1;else in_flag=0;if(in_flag=1)pixelsy*w+x=red;ImageProducer ip=new MemoryImageSource(w,h,pixels,0,w);image=createImage(ip);return image;步骤步骤2 2：设设in_flag是一是一布尔变量。对每一条扫布尔变量。对每一条扫描线从左到右进行搜索，描线从左到右进行搜索，如果当前如果当前像素像素位于位于多边多边形形P内内，则，则in_flag=true，需要需要填上填上值为值为polygon_color的颜色；的颜色；否则该否则该像素像素在在多边形多边形P外外，需要填上值为，需要填上值为background_color的颜的颜色。色。图图3.17 多边形多边形P0P1P6P0P3P4e410155P1P2P5P6P0e0e2e3e5e1e6473 3、边界标志算法实例、边界标志算法实例XXXXXXP2(9,6)XXXXXXP0(2,5)P1(2,11)P3(15,9)P4(15,3)P5(12,1)P6(7,1)XXXXxXXxXXXXXX Y=2 Y=3Y=4Y=5Y=648实例最终结果实例最终结果XXXXXXXXXX 49 区域填充是指先将区域内的一点（常称区域填充是指先将区域内的一点（常称种子点种子点）赋予给定颜）赋予给定颜色，然后将这种颜色扩展到整个区域内的过程。色，然后将这种颜色扩展到整个区域内的过程。3.5 3.5 区域填充区域填充 区域区域是指已经表示成是指已经表示成点阵形式点阵形式的的像素集像素集合合。在光栅图形中，区域可采用。在光栅图形中，区域可采用内点表示内点表示和和边界表示边界表示两种形式进行描述。两种形式进行描述。1、内点表示法：、内点表示法：把位于给定区域把位于给定区域内内的所有的所有像像素素一一一一列举列举出来的方法称为内点表示法。出来的方法称为内点表示法。2、边界表示法：、边界表示法：把位于给定区域把位于给定区域边界边界上的上的像素像素一一一一列举列举出来的方法称为边界表示法。出来的方法称为边界表示法。3.5.1 3.5.1 区域的表示和类型区域的表示和类型图图3.22 内点表示的区域内点表示的区域 图图3.23 边界表示的区域边界表示的区域501 1）4 4连通的区域连通的区域:取区域内取区域内任意两任意两点点，在该区域内若从其中一点出发，在该区域内若从其中一点出发通过通过上、下、左、右上、下、左、右四种运动可到四种运动可到达另一点。达另一点。图图3.24 3.24 四个方向的运动四个方向的运动2 2）8 8连通的区域连通的区域:取区域内取区域内任意两任意两 点点，若从其中任一点出发，在该，若从其中任一点出发，在该区域内通过沿区域内通过沿水平方向、垂直方向水平方向、垂直方向和对角线方向的八种运动和对角线方向的八种运动可到达另可到达另一点。一点。图图3.25 3.25 八个方向的运动八个方向的运动3