《计算机图形学 教学课件 ppt 作者 徐文鹏 第3章 基本图形光栅化》由会员分享，可在线阅读，更多相关《计算机图形学 教学课件 ppt 作者 徐文鹏 第3章 基本图形光栅化（55页珍藏版）》请在金锄头文库上搜索。
1、河南理工大学,计算机图形学,第3章 基本图形光栅化,Computer Graphics,第3章 基本图形光栅化,3.1 直线的光栅化 3.2 圆的光栅化 3.3 区域填充 3.4 字符表示 3.5 反走样,3.1 直线的光栅化,在数学上，理想的直线是没有宽度的、由无数个点构成的集合。当我们对直线进行光栅化时，只能在显示器所给定的有限个像素组成的矩阵中，确定最佳逼近该直线的一组像素，并且按扫描线顺序对这些像素进行写操作，这就是通常所说的直线的扫描转换。 通常用于直线光栅化的算法有数值微分法（DDA）、中点画线法和Bresenham画线算法。,3.1.1DDA算法,DDA（Digital Diff
2、erential Analyzer）法是根据直线的微分方程来画直线的。 设直线的起点坐标为Ps(xs,ys)，终点坐标为Pe(xe,ye)，令x= xe- xs，y= ye- ys，则要绘制的直线的微分方程为,取时间步长为1/t，则可得上述微分方程数 值解的递推公式为,3.1.1DDA算法,通常情况下，直线的方向分为8个不同的区域，每个区域的处理方法有所不同。,3.1.1DDA算法,例：画直线段P0(0,0)-P1(5,2) 解：斜率K=2/5=0.4，所以X方向每次步长为1，Y方向递增K. 初始点为（0，0）。 x int(y+0.5) y 0 0 0 1 0 0.4 2 1 0.8 3 1
3、 1.2 4 2 1.6 5 2 2.0,3.1.2中点画线法,为了讨论方便，假设直线的斜率在0到1之间，若直线在x方向上增加一个光栅单位，则在y方向上的增量只能在0到1之间。设P（x,y）是直线上的一点，与P点最近的网格点为（xi, yi）,那么，下一个与直线最近的像素只能是正右方的网格点PB（xi+1, yi）或右上方的网格点PT（xi+1,yi+1）两者之一。再以点M（xi+1, yi+0.5）表示PB和PT的中点，设Q是直线与垂直线x= xi+1的交点。显然，若M在Q的下方，则PT离直线较近，应取PT为下一个像素点，否则应取PB做为下一个像素点，这就是中点画线算法的基本思想。,3.1.
4、2中点画线法,设直线的起点和终点分别为（x0,y0)和(x1,y1)，则直线方程为F(x,y)=ax+by+c=0 其中a=y0-y1，b=x1-x0，c=x0y1-x1y0。 构造判别式：采用增量计算 d=F(M)=F(x+1, y+0.5)=a(x+1)+b(y+0.5)+c 在d0的情况下，取正右方像素PB， 判断下一像素应计算 d1=a(x+2)+b(y+0.5)+c =d+a 在d0的情况下，取右上方像素PT， 判断下一像素应计算 d2=a(x+2)+b(y+1.5) = d+a+b d的初始值d0 = a+0.5b,3.1.2中点画线法,由于我们使用的只是d的符号，而且d的增量都是
5、整数，只是其初始值包含小数。因此，我们可以用2d代替d，来摆脱小数。 如果进一步把算法中2*a改为a+a等等，那么这个算法不仅只包含整数变量，而且不包含乘除法，适合硬件实现。,3.1.3Bresenham画线算法,原理:过各行各列像素中心构造一组虚拟网格线，按直线从起点到终点的顺序计算直线与各垂直网格线的交点，然后确定该列像素中与此交点最近的像素。,若st，则Si比较靠近理想直线，应选Si; 若st，则Ti比较靠近理想直线，应选Ti。,设直线的起点和终点分别为（x1,y1)和(x2,y2)， 则直线方程为y=y1+dy/dx(x-x1)，其中dx=x2-x1，dy=y2-y1,直线方程经变换后
6、可表示为从（0，0）到(dx,dy)，方程可简化为y=dy/dx*x,s-t=2* *(xi-1+1)-2yi-1-1,s= *(xi-1+1)-yi-1,t=(yi-1+1)- *(xi-1+1),dx(s-t)=2(xi-1dy-2yi-1dx)+2dy-dx,3.1.3Bresenham画线算法,递推公式 ：,当di0时，选Ti,当di0时，选Si，,di的初值：,令di=dx(s-t), 则 di+1=2(xidy-2yidx)+2dy-dx,di+1-di=2dy(xi-xi-1)-2dx(yi-yi-1),di=2(xi-1dy-2yi-1dx)+2dy-dx,3.1.3Brese
7、nham画线算法,3.1.3Bresenham画线算法,上面讨论的是直线斜率0k1的情况。对于一般情况可作如下处理： （1）当斜率的绝对值k1时，将x、y和dx、dy对换，即以y向作为增长方向，y总是增1（或减1），x是否增减1，则根据的符号判断：d0时x增1（或减1）；d0时，x不变。 （2）根据dx和dy的符号来控制(x或y)增1还是减1。,双步算法,1987年有人提出二步法，即每循环一次不是绘制一个象素，而是绘制二个象素，这样无疑可以把生成直线的速度提高一倍。下图为双步算法的四种情况 。,3.2 圆的光栅化,与直线的生成类似，圆的生成算法的好坏将直接影响到绘图的效率。本节仅讨论圆心位于坐
8、标原点的圆弧生成算法，对于圆心为任意的圆弧，可以先将其平移到原点，然后光栅化，再平移到原来的位置。,3.2.1中点画圆算法,假设圆的半径为R，则圆的方程为 当点（x,y）在圆内时，F（x,y）0; 当点（x,y）在圆上时，F（x,y）=0;,3.2.1中点画圆算法,中点画圆算法的基本原理是：假设点P（xp,yp）为圆弧上一点，如图3-5所示，那么，下一个与圆弧最近的像素点只能是正右方的点P1（xp+1,yp）或右下方的点P2(xp+1,yp-1)。令M为P1和P2的中点，易知M的坐标为（xp+1,yp-0.5）。显然，若M在圆内，则P1离圆弧近，应取为下一个像素点；否则应取P2作为下一个像素点
9、。,判别式d： d的初始值为： 在d0的情况下，取右下方像素P2， 在d0的情况下，取正右方像素P1，,3.2.1中点画圆算法,为了消除在计算判别式初始值产生的浮点数运算，将用4d来代替d。,3.2.1中点画圆算法,下述程序使用中点画圆算法绘制一个1/8圆弧。 void MidPointCircle(int r,int color) int x,y,d x=0; y=r; d=5-4r; CirclePoint(x,y,color); while(x=y) if(d=0) d+=8x+12; else d+=8(x-y)+20;y-; x+; CirclePoint(x,y,color); ,
10、3.2.2Bresenham画圆算法,Bresenham画圆算法是最有效的算法之一。Bresenham画圆算法的基本原理是如下图所示，若Pi-1（xi-1,yi-1）为已经选定的点，那么下一个可能的像素点为其正右方的点Si或右下方的点Ti。若Si到圆弧的距离小于Ti到圆弧的距离，则取Si ，反之取 Ti。,3.2.2Bresenham画圆算法,设R为圆弧的半径，记P（x,y）到原点的距离的平方与圆的半径的平方之差为D（P），即,3.2.2Bresenham画圆算法,当di0时，点Si做为下一个像素点xi+1=xi+1,yi= yi-1,故 当di0时，点Ti做为下一个像素点xi+1=xi+1,
11、yi= yi-1-1,故,3.2.2Bresenham画圆算法,根据算法，可得Bresenham生成圆弧的程序如下： void bresenham_arc(int R,int color) int x,y,d; x=0;y=R; d=3-2*R; while(xy) putpixel(x,y,color); if(d0) d+=4*x+6; else d+=4*(x-y)+10; y-=1; x+; if(x=y) putpixel(x,y,color); ,3.3 区域填充,区域填充即给出一个区域的边界，要求对边界范围内的所有像素单元赋予指定的颜色代码。区域填充中最常用的是多边形填色。,3.
12、3.1多边形填充算法,1多边形的表示方法 在计算机图形学中，多边形有两种重要的表示方法：顶点表示和点阵表示。 顶点表示是用多边形的顶点序列来描述多边形，用序列表示多边形。 点阵表示用位于多边形内的像素集合来描述多边形。,逐点判断法,多边形填充最简单的方法就是逐点判断，即逐个判断绘图窗口内的像素，确定它们是否在多边形区域内部，从而求出位于多边形区域内的像素的集合。通常有两种方法：射线法，累计角度法。 1）射线法 从v点发出射线与多边形P的边相交，若交点的个数为奇数，则v位于多边形P内；若为偶数，则v位于多边形P外部。,累计角度法,计算各边的夹角的和，若代数和为零，该点域外；若代数和为2，该点域内
13、。,扫描线多边形填充算法,从前画的介绍已知，多边形填充给出一个多边形的边界，要求给多边形边界范围的所有像素单元赋予指定的颜色代码。要完成这个任务，一个首要的问题是判断一个像素是在多边形内还是在多边形外。数学上经常采用的方法是“扫描线交点的奇偶数判断”法：用一根水平扫描线自左而右通过多边形而与多边形的边界相交，扫描线与边界相交奇次数后进入该多边形，相交偶次数后走出该多边形。,扫描线多边形填充算法,顶点计数问题： 当顶点在多边形两边之下方时，该点计2次； 当顶点在多边形两边之上方时，该点计0次； 当顶点在多边形两边之间时，该点计1次； 对于多边形的水平边，不计它与扫描线的交点,扫描线多边形填充算法
14、,扫描线多边形填充算法是按扫描顺序，计算扫描线与多边形的相交区间，再用要求的颜色显示这些区间的像素，即完成填充工作，多边形填充过程可以分为以下4个步骤： （1）求交：计算扫描线与多边形各条边的交点； （2）排序：把所有交点按x值递增顺序排序； （3）配对：第一个与第二个，第三个与第四个等，每对交点代表扫描线与多边形的一个相交区间； （4）填色：把相交区间内的像素置成多边形颜色，把相交区间外的像素置成背景色。,扫描线多边形填充算法,扫描线算法中采用了较灵活的数据结构，即边的分类表ET（Edge Table）和活化边表AEL（Active Edge List），两个表结构中的基本元素都是边结构。边
15、结构的定义为： Typedef struct int ymax; float x,deltax; struct Edge *nextEdge; Edge; 其中各变量的含义如下： ymax：边的上端点的y坐标； x：在AEL中表示当前扫描线与边的交点的x坐标，初值（即在ET中的值）为边的下端点的x坐标； deltax：边的斜率的倒数； nextEdge：指向下一条边的指针；,扫描线多边形填充算法,边表一般是由一系列存储桶构成的，存储桶的数目与扫描线的数目一样多，按照扫描线递增（减）顺序存放。边表可以通过如下方法建立：先按照下端点的y坐标值对所有边进行分组，若某边的下低端点y值为ymin,则该边
16、就放在ymin所对应的桶中，按下端点的x坐标值递增的顺序将同一组中的边排列成行。 活化边表AEL由与当前扫描线相交的边组成，它记录了多边形的边和当前扫描线的所有交点的x坐标，并且随着扫描线的递增而不断变化。,扫描线多边形填充算法,扫描线多边形填充算法,ET表,扫描线多边形填充算法,这样建立了边表ET后，扫描多边形填充算法可按如下步骤进行： （1）初始化AEL，使之为空，取扫描线纵坐标y的初始值为ET中非空元素的最小序号。 （2）按从下到上的顺序对每条扫描线重复以下各步，直至AEL和ET为空。 1）将ET中与当前y有关的结点加入至AEL，同时保存AEL中按x值从小到大实现的顺序序列。 2）对于AEL中的扫描线y，在一对交点之间填充所需的像素值。 3）从AEL中删掉yymax的结点。 4）对于留在AEL中的每个结点，执行xi+1=xi+deltax。 5）对AEL中的各结点按x值从小到大排序。 6）使y=y+1成为下一条扫描线的
