基本光栅图形算法课件

1、2、 基本光栅图形算法2、 基本光栅图形算法数学表示的若干方法1）数学方程2）点集3）边界表示4）关系表示数学表示的若干方法1）数学方程常用的图形对象线段圆多边形字符等常用的图形对象线段一、直线在光栅显示器的荧光屏上生成一个对象，实质上是往帧缓存寄存器的相应单元中填入数据。线段 理想的是无数多的零面积的点构成。 而在实际显示中，在光栅扫描显示器上，线段是由有限多的像素组成的，像素是有面积的。 画一条从（x1, y1）到（x2, y2）的直线，实质上是一个发现最佳逼近直线的象素序列，并填入色彩数据的过程。这个过程也称为直线光栅化。 一、直线在光栅显示器的荧光屏上生成一个对象，实质上是往帧缓存而且

2、除了水平、垂直和对角线上的线段，其他的线段像素并不一定能准确地落在线段上。而且除了水平、垂直和对角线上的线段，其他的线段像素并不一定能最接近数学上的直线:生成的线要直：但实际选择最靠近直线的可寻址点来逼近。 理想的绘制绘制线段的要求最接近数学上的直线:绘制线段的要求绘制线段的要求起点和终点要准：在绘制线段的过程中由于受精度 的影响，线段的终点与原终点有一个累积误差， 导致线段的终点不准。 绘制线段的要求起点和终点要准：在绘制线段的过程中由于受精度绘制线段的要求粗细要均匀 ：由于选点不均匀，造成线段 粗细不均匀，直观上反映出线段的亮度不均匀。 绘制线段的要求粗细要均匀 ：由于选点不均匀，造成线段

3、光栅显示平面上，我们只能用二维光栅格网上尽可能靠近这条直线的象素点的集合来表示它。每个象素具有一定的尺寸，是显示平面上可被访问的最小单位，它的坐标x和y只能是整数，也就是说相邻象素的坐标值是阶跃的而不是连续的。光栅显示平面上，我们只能用二维光栅格网上尽可能靠近这条直线的实际绘制实际绘制线段的笛卡儿斜率截距方程若其始坐标和终点坐标分别为：则斜率为截距为(1)(2)(3)显示直线的算法可以直线方程（1）、（2）和（3）为基础。线段的笛卡儿斜率截距方程若其始坐标和终点坐标分别为：则斜率为1. 逐点比较法算法的基本思想：在绘制直线的过程中，每绘制一个点，就与原直线进行比较，根据比较的结果决定下一步的走

4、向，这样一步一步逼近直线。 保证要绘制的点尽可能的靠近直线而不发生远离直线的趋向。1. 逐点比较法算法的基本思想：在绘制直线的过程中，每绘制保绘制思路由一个点到下一个点的走法是只在X方向或Y 方向走一步。绘制思路由一个点到下一个点的走法是只在X方向或Y 方向走一步计算偏差 K1K2计算偏差 K1K2设 =tg-tg 于是有 1) =0，点在直线上； 2) 0，点在直线上方； 3) =0Fi=0Fiabs(dy) steps=abs(dx); else steps=abs (dy);delta_x=(float)dx / (float)steps;delta_y=(float)dy / (flo

5、at)steps;x=xa;y=ya;putpixel(round(x),round(y), c);for (k=1; k|dy|?D xD y1a 1m1bX1/m12a-1m2bX -1/m13a-1-m3bX -1/m-14a1-m4bX 1/m-1象限|dx|dy|?D xD y1a 1m1bX1/m绘制的直线时点的选取 yi yi+1 绘制的直线时点的选取 yi yi+1 选择哪一个点？(Xi1， Yi,r)还是 (Xi1，Yi+1,r)用Yi+1与Yi,r进行误差计算，误差大于0.5选择上面的点，否则选择下面的点。使用偏差来计算确定那一个点。选择哪一个点？偏差计算设偏差为当 时，计

6、算的点（实际直线上的点）在 中点的上方，取当 0 时，计算的点（实际直线上的点）在 中点的下方，取整理后，有偏差计算设偏差为当 时，计算偏差的递推关系误差因为有偏差的递推关系误差因为有此时，算法中仍有浮点数运算，而且m=dy/dx, 并且dx0，所以我们引入 F = 2*dx*F与 的符号相同可以用来作为判别式。因此，初始x=x1,y=y1,F1=2dy-dx其递推公式：若Fi=0,则xi+1=xi+1,yi+1=yi+1, Fi+1=Fi+2(dy-dx);此时，算法中仍有浮点数运算，而且m=dy/dx, 并且dx总结：算法公式初始条件： F1=2dy-dx当Fi0时： yi+1=yi+1,

7、xi+1=xi+1，Fi+1=Fi+2(dy-dx)否则：yi+1=yi,xi+1=xi+1， Fi+1=Fi+2dy总结：算法公式初始条件： 第一象限下算法思想如下：此时满足：0m1且x10 则yi+1=yi+1； 否则yi+1=yi；3、画点（xi+1, yi+1）；4、求下一个误差Pi+1； if Pi0 则Pi+1=Pi+2dy-2dx; 否则Pi+1=Pi+2dy；5、i=i+1; if idx+1则转4；否则end第一象限下算法思想如下：此时满足：0m1且x1|dy|为分支，并分别将2a, 3a象限的直线和3b, 4b象限的直线变换到1a, 4a和2b, 1b方向去，以求得程序处理

8、的简洁。 程序代码：由上述算法思想编制的程序如下。这个程序适用于所有8代码：void line (x1, y1, x2, y2, c)int x1, y1, x2, y2, c;int dx, dy,x, y, p, const1, const2, inc, tmp;dx=x2-x1;dy=y2-y1;if (dx*dy=0) /*准备x或y的单位递变值。*/ inc=1;elseinc= -1;if (abs(dx)abs(dy) if(dx0) tmp=x1; /*将2a, 3a象限方向*/ x1=x2; /*的直线变换到1a, 4a*/ x2=tmp; /*象限方向去*/ tmp=y1;

9、 y1=y2; dx=-dy; dy=-dy; p=2*dy-dx; const1=2*dy; /*注意此时误差的*/ const2=2*(dy-dx); /*变化参数取值. */ x=x1; y=y1; set_pixel(x, y, c); while (xx2) x+; if (p0) p+=const1; else y+=inc; p+=const2; set_piexl(x, y, c); 代码：void line (x1, y1, x2, y2, 代码：else if (dy0) tmp=x1; /* 将3b, 4b象限方向的*/ x1=x2; /*直线变换到2b, 1b */ x

10、2=tmp; /*象限方向去. */tmp=y1; y1=y2; dx=-dy; dy=-dy; p=2*dx-dy; /*注意此时误差的*/ const1=2*dx; /*变化参数取值. */ const2=2*(dx-dy); x=x1; y=y1; set_pixel (x, y, c);while (yy2) y+; if(p0) p+=const1; else x+=inc; p+=const2; set_pixel (x, y, c); 代码：else while (y= 1/2时，1的情况不会出现。而当m=1/2时，4的情况不是出现。双点bresenham画线算法双点的画线绘制，

11、每次决定两个点算法：0=m=1/2时，初始判别式（1）如果Fi=0，则采用模式2或者3，并且进一步判断为，如果，Fi2*y，则选择用模式2，否则，选择3模式。1/2=m=0，则采用模式4，并且（2）如果Fi0，则采用模式2或者3，并且进一步判断为，如果，Fi2*(y-x)，则选择用模式2，否则，选择3模式。算法：0=m=1/2时，初始判别式1/2=m=1时，圆 圆也是图形系统中常用的元素。我们将圆定义为所以距离中心位置 为给定值r的点集。圆的方程为：利用这个方程，我们可以沿x轴，从到 以单位步长计算对应的y值，从而得到圆周上每点的位置。圆 圆也是图形系统中常用的元素。我们将圆定义为利用这个但这

12、样做，由于有乘方和平方根运算，并且都是浮点运算，算法效率不高。而且这样求出的圆周上的点是不均匀的；|x-xc|越大，由于圆的斜率趋于无穷大，使得圆周上有较大的间隙 。对应生成圆周点之间的圆周距离也就越长。因此，所生成的圆不美观。 但这样做，由于有乘方和平方根运算，并且都是浮点运算，算法效率也可以用极坐标表示x=xc+rcosy=yc+rsin当 从0 度到360 作加1递增时，由此式便可求出圆周上均匀分布的360个点的x, y坐标。利用圆周坐标的对称性，此算法还可以简化：将圆周分为8个象限。只要将第1b象限中的圆周光栅点求出，其余7部分圆周就可以通过对称法则计算出来。图给出了圆心在0，0点时的

13、对称变换法则。但即使作了如此简化，用上述公式每算一点，都要经过三角函数计算，仍有相当大的计算量。(y,-x)极坐标法也可以用极坐标表示(y,-x)极坐标法下面的函数CirclePoints()用来显示P(x，y)及其七个对称点。 void CirclePoints(x,y,color)int x,y,color;putpixel(x,y,color);putpixel(x,y,color);putpixel(x,y,color);putpixel(x,y,color);putpixel(y,x,color);putpixel(y,x,color);putpixel(y,x,color);put

14、pixel(y,x,color); 下面的函数CirclePoints()用来显示P(x，y)及圆的位图圆的位图1. 中点圆算法考虑圆心在原点的圆。设函数：故有 （x,y)位于圆边界内 （x,y)位于圆边界上 （x,y)位于圆边界外对上述函数在每个取点步骤上，对接近圆周的两个象素点的中点进行测试来决定取点。1. 中点圆算法考虑圆心在原点的圆。设函数：故有 考虑一个八分之一圆弧从x=0到x=y的情况，曲线的曲率从0变化到-1，在该段弧上的正x方向取单位步长，并根据决策参数确定每一步可能的y的位置，哪一个更接近圆弧的位置。设已经取的点为P根据在第二象限的圆的走向，下一列中接近圆的像素只能在P的正右

15、方点或者是右下方点中选择。考虑一个八分之一圆弧从x=0到x=y的情况，曲线的曲率从0变如下图所示，图中有两条圆弧A和B，假定当前取点为Pi(xi，yi)，如果顺时针生成圆，那么下一点只能取正右方的点E(xi+1，yi)或右下方的点SE(xi+1，yi-1)两者之一。 如下图所示，图中有两条圆弧A和B，假定当前取点为Pi(xi，LPH),(kkyx1-ky1+kx),(1+kkyxLPH),(kkyx1-ky1+kx),(1+kkyx选择标准：以此来判断下一步 的点如何取。是 还是 。理想的选择标准是计算H和L到圆弧的距离，然后选择距离小的点。在此算法中我们选择用两个点的中点作为标准，判断这个中

16、点落在圆上、外还是内？分别选择L和H。选择标准：以此来判断下一步 故有中点位于圆边界内中点位于圆边界上中点位于圆边界外),(kkyx1-ky1+kx),(1+kkyx故有中点位于圆边界内),(kkyx1-ky1+kx),(1+递推判决函数其中 的取值，决定于 的符号。递推判决函数其中 的取值，决定于 有：若， =0 说明中点在圆外或上，那么下点取L，则判别式有：若， 0 说明中点在圆内，那么下点取H，初始时在圆点，所以D0=(0+1)2+（r-0.5)2-r2=1.25-r但是此算法中有浮点运算，因此我们令F=d-0.25 则F0=1-r则上面的递推判别式为Fk= -0.25 选择L 每次迭代

17、计算都是整数，而且初始F也为整数，所以可以等价于以0作为判别界限。初始时在圆点，所以中点画圆中点画圆2.Bresenham算法仍然考虑圆心在原点的一个第二象限的圆弧 。对于圆弧上的点p，其下一个可选择的点如图。LPH),(kkyx1-ky1+kx),(1+kkyx2.Bresenham算法仍然考虑圆心在原点的一个第二象限的选择方法：可以计算出这两点到圆心的距离和半径平方的差为：即两点与圆弧的距离：若：|D(H)| |D(L)| 则取L点。 |D(H)|= |D(L)| 则两点都可以取，我们约定取L。选择方法：可以计算出这两点到圆心的距离和半径平方的差为：若：令则选择标准可以表示为 di =0，

18、下一点选择L。根据分析,可以用 代替上面的式子，计算可以不用绝对值计算。因此，可以由这样的递推公式：若，di=0，则 走右下方点，y坐标减1，x坐标加1， di+1=di+4(xi-yi)+10PABCDEHL令则选择标准可以表示为PABCDEHL3.逐点比较法插补圆弧首先确定顺时针还是逆时针方向画圆若逆时针第一象限 C（Cx，Cy）圆心，起点S（Xs，Ys）末点E（Xe，Ye） 另一点M（Xm，Ym）半径Rs M点到圆心的距离Rm点M和圆的关系：以FmRm2Rs2（XmXc）2（YmYc）2 为判别函数 则有： Fm0 点在圆外，Fm0 xs-xc0 F1= 0 ，走 x ， xi+1 =

19、xi x ， yi+1 = yiFi= 0 ，走 终点比较： 当前点和终点的坐标值进行比较 其差的绝对值小于给定的一个小的正整数终点比较： 当前点和终点的坐标值进行比较 其差4.角度DDA画圆圆的参数方程，t从02x=xc+rcosty=yc+rsint圆点（xc，yc），半径r ，若从起始点ts到末点te 一段圆弧离散化圆弧，运动步数n可求出为 n（tets）/ dt + 0.5 titstdtdt如何确定？可以根据半径的大小给定dt的经验数据，并根据精度和速度进行调整由dt变化的值，只要把ti带入上面的参数方程中就能计算出xi，yi，连接点划线，绘制直线逼近圆弧即可4.角度DDA画圆圆的参

20、数方程，t从02圆点（xc，yc如果给定圆周上的3个点：起末点坐标和任一个圆周上点的坐标。求出圆心坐标和半径以及起末点所对应的角度，就可以用角度DDA法绘制圆弧了。如果给定圆周上的3个点：起末点坐标和任一个圆周上点的坐标。求椭圆圆是椭圆的一种特殊情况。若考虑椭圆的中心在坐标原点，长半轴为a，短半轴为b，则椭圆满足这样的参数方程：参数方程也可以表示为令函数 则可以由F(x,y)的值来判断点与椭圆的关系。 因此，我们可以将画圆的算法推广来画椭圆。椭圆圆是椭圆的一种特殊情况。1.中点画椭圆椭圆也具有对称性，只要绘制出来第一象限的1/4，其他的就可以用对称来生成。也就是说我们只要绘制出（0，b）到（a

21、，0）部分的按顺时针方向的最接近理想椭圆弧段的像素序列。思想：将第一象限的1/4圆弧分为两部分，分界点为椭圆弧线的斜率为-1的点，即该点法向量的x分量和y分量相等。也就是2b2x=2a2y处。（1）上部分：待选择的点（xi,yi）是已经绘制点的正右方点或者右下方点。用这两点的中点(xi+1,yi-0.5)和椭圆参数函数计算出来这一点和椭圆的关系。因此有判别式：选择的标准和递推公式： di=0，选择右下方点，此时，di+1=di+b2(2xi+3)+a2(-2yi+2)1.中点画椭圆椭圆也具有对称性，只要绘制出来第一象限的1/4 初始时，x0=0，y0=b，代入则可得到d0=F(1，（b-0.5

22、）)=b2+a2(-b+0.25)结束点(xi,yi)满足条件2b2xi=2a2yi（2）下半部分，即2b2xi = 2a2yi已选点(xi,yi)，选择下一点是在右下方或者正下方点中选择。则选择标准：di=0，选择正下方点，此时，di+1=di+a2(-2yi+3)初始点处d0=F(xi+0.5，yi-1)=b2(xi+0.5)2+a2(yi-1)2-a2b2 初始时，x0=0，y0=b，代入则可得到则选择标准：2.DDA绘椭圆椭圆的长、短半轴a、b起始点S(Xs,Ys)，起点角度ts，末点角度te，长轴和x轴方向的夹角xoyESxxxyytsC2.DDA绘椭圆椭圆的长、短半轴a、b起始点S

23、(Xs,Ys)坐标系xcy中， S点坐标为坐标系xcy中，S的坐标为坐标系xoy中，S的坐标为坐标系xcy中， S点坐标为坐标系xcy中，S的后面的问题就是求出S到E的椭圆上的各点坐标n（tets）/ dt + 0.5 titstdt后面的问题就是求出S到E的椭圆上的各点坐标n（tets）抛物线抛物线的方程分析其p为正的情况下，抛物线右边的情况，左半边可以使用其对称性绘制出来。对其方程求导由此可以知道抛物线的性质，在p大于0的情况下，右边的斜率为正，并且随着x值的增大而增大，在xpa的时候，斜率为1，两边分别小于和大于1。 因此 可以以xpa为分界点，左边斜率小于1，抛物线趋于水平，选择最逼近

24、抛物线的点则应该是当前点的正右方点或者是右上方点；右边斜率大于1，抛物线趋于垂直方向，所选择的下一个点则应该是当前点的正上方点或者是右上方点。抛物线抛物线的方程（1）x =pa从当前的象素点（xi，yi）的右方或者右上方点中选择一个合适的点作为下一点的位置。此时xi1xi1 抛物线上对应的y值为然后判断yi1和yi哪个离yr更近若di0，说明右上点离的近，否则右方点为最近点。（1）x =pa从当前的象素点（xi，yi）的右方或者右判别式变换，因为只有用到判别式的符号，所以避免使用除法和小数运算，所以对其进行边换，给其乘以p，由于p是正数所以判别式的符号没有变化。 Fidi p 2pyi p (

25、xi 1a)22bp可以计算出其递推关系式 Fi1 2pyi1 p (xi1 1a)22bp 如果选择右上点 则 yi1 yi 1 此时 Fi1 2p（yi 1）p (xi1 1a)22bp Fi 2p 2xi1 2a 1 如果选择右方点 则 yi+1 = yi 此时 Fi1 2pyi p (xi1 1a)22bp Fi 2xi1 2a 1判别式变换，因为只有用到判别式的符号，所以避免使用除法和小数总结如下： 若Fipa从当前的象素点（xi，yi）的上方或者右上方点中选择一个合适的点作为下一点的位置。此时yi1yi1 抛物线上对应的x值为然后判断xi1和xi哪个离xr更近若dipa从当前的象素点（xi，yi）的上方或者右上判别式变换，因为只有用到判别式的符号，而且上式的两项分别都为正（因为我们所考虑的式抛物线的右半边且此情况为xp+a；所以为了避免开方运算，对其进行变换；令：可以计算出其递推关系式如果选择右上点 则 Xi1 Xi 1否则选择上方点 则 Xi1 Xi判别式变换，因为只有用到判别式的符号，而且上式的两项分别都为总结如下： 若Fi0 则 否则：此段的起点（xi，yi）为上一段即x=p+a的末点，则F可由F变换而来， 此点处F4（Fxipa）3总结如