1、2、基本光栅图形算法数学表示的若干方法1）数学方程2）点集3）边界表示4）关系表示常用的图形对象n线段n圆n多边形n字符等一、直线n在光栅显示器的荧光屏上生成一个对象，实质上是往帧缓存寄存器的相应单元中填入数据。n线段 理想的是无数多的零面积的点构成。而在实际显示中，在光栅扫描显示器上，线段是由有限多的像素组成的，像素是有面积的。画一条从（x1,y1）到（x2,y2）的直线，实质上是一个发现最佳逼近直线的象素序列最佳逼近直线的象素序列，并填入色彩数据的过程。这个过程也称为直线光栅化。而且除了水平、垂直和对角线上的线段，其他的线段像素并不一定能准确地落在线段上。最接近数学上的直线最接近数学上的直
2、线:生成的线要直生成的线要直：但实际选择最靠近直线的可寻址点来逼近。理想的绘制理想的绘制绘制线段的要求绘制线段的要求起点和终点要准起点和终点要准：在绘制线段的过程中由于受精度 的影响，线段的终点与原终点有一个累积误差，导致线段的终点不准。绘制线段的要求粗细要均匀粗细要均匀：由于选点不均匀，造成线段 粗细不均匀，直观上反映出线段的亮度不均匀。n光栅显示平面上，我们只能用二维光栅格网上尽可能靠近这条直线的象素点的集合来表示它。每个象素具有一定的尺寸，是显示平面上可被访问的最小单位，它的坐标x和y只能是整数，也就是说相邻象素的坐标值是阶跃的而不是连续的。实际绘制线段的笛卡儿斜率截距方程bxmy若其始
3、坐标和终点坐标分别为：),(11yx),(22yx1212xxyym则斜率为11xmyb截距为(1)(2)(3)显示直线的算法可以直线方程（1）、（2）和（3）为基础。1.逐点比较法算法的基本思想：在绘制直线的过程中，每绘制一个点，就与原直线进行比较，根据比较的结果决定下一步的走向，这样一步一步逼近直线。偏差判别选择象素点终点判别偏差计算结束否保证要绘制的点尽可能的靠近直线而不发生远离直线的趋向。绘制思路由一个点到下一个点的走法是只在在X方向或方向或Y 方向走一步方向走一步。OA计算偏差OA K1K2设 =tg-tg 于是有 1)=0，点在直线上；2)0，点在直线上方；3)=0Fiabs(dy
4、)steps=abs(dx);else steps=abs(dy);delta_x=(float)dx/(float)steps;delta_y=(float)dy/(float)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绘制的直线时点的选取riy,riy,1 yi yi+1 n选择哪一个点？n(Xi1，Yi,r)还是(Xi1，Yi+1,r)n用Yi+1与Yi,r进行误差计算，误差大于0.5选择上面
5、的点，否则选择下面的点。n使用偏差来计算确定那一个点。偏差计算设偏差为5.0)(,11riiiyyx当 时，计算的点（实际直线上的点）在 中点的上方，取当 0 时，计算的点（实际直线上的点）在 中点的下方，取0)(1ix)(1ix1,1ririyyririyy,1整理后，有0)(0)(111,1,11iriiririiixyxyyxx偏差的递推关系5.0)(,11riiiyyx误差因为myyii 1有0)()(0)(1)(0)(5.00)(5.0)1(5.05.0)(,1,1,11iiiiiriiiriiriiriiixmxxmxxmyyxmyyymyyyx此时，算法中仍有浮点数运算，而且m=
6、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);总结：算法公式n初始条件：nF1=2dy-dxn当Fi0时：yi+1=yi+1,xi+1=xi+1，Fi+1=Fi+2(dy-dx)n否则：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 则
7、Pi+1=Pi+2dy-2dx;否则Pi+1=Pi+2dy；5、i=i+1;if i|dy|为分支，并分别将2a,3a象限的直线和3b,4b象限的直线变换到1a,4a和2b,1b方向去，以求得程序处理的简洁。代码：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;
8、/*的直线变换到1a,4a*/x2=tmp;/*象限方向去*/tmp=y1;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);代码：else if(dy0)tmp=x1;/*将3b,4b象限方向的*/x1=x2;/*直线变换到2b,1b*/x2=tmp;/*象限方向去.*/tmp=y1;y1=y2
9、;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(p=1/2时，1的情况不会出现。而当m=1/2时，4的情况不是出现。算法：xyF 41yFFii41xyFFii2410=m=1/2时，初始判别式（1）如果Fi=0，则采用模式2或者3，并且进一步判断为，如果，Fi2*y，则选择用模式2，否则，选择3模式。1/2=m=0，则采用模式4，并且（2）如果Fi0，则采用模式2或者3，并且进一步判断为，如果，Fi2*(
10、y-x)，则选择用模式2，否则，选择3模式。xyF341)(41xyFFiixyFFii241圆 圆也是图形系统中常用的元素。我们将圆定义为所以距离中心位置 为给定值r的点集。圆的方程为：),(ccyx222)()(ryyxxcc利用这个方程，我们可以沿x轴，从到 以单位步长以单位步长计算对应的y值，从而得到圆周上每点的位置。rxcrxc22)(ccxxryyn但这样做，由于有乘方和平方根运算，并且都是浮点运算，算法效率不高。n而且这样求出的圆周上的点是不均匀的；|x-xc|越大，由于圆的斜率趋于无穷大，使得圆周上有较大的间隙。对应生成圆周点之间的圆周距离也就越长。因此，所生成的圆不美观。也可
11、以用极坐标表示x=xc+rcosy=yc+rsin当 从0 度到360 作加1递增时，由此式便可求出圆周上均匀分布的360个点的x,y坐标。利用圆周坐标的对称性，此算法还可以简化：将圆周分为8个象限。只要将第1b象限中的圆周光栅点求出，其余7部分圆周就可以通过对称法则计算出来。图给出了圆心在0，0点时的对称变换法则。但即使作了如此简化，用上述公式每算一点，都要经过三角函数计算，仍有相当大的计算量。(y,-x)极坐标法n下面的函数CirclePoints()用来显示P(x，y)及其七个对称点。nvoid CirclePoints(x,y,color)int x,y,color;putpixel(
12、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);putpixel(y,x,color);圆的位图1.中点圆算法考虑圆心在原点的圆。设函数：222),(ryxyxF故有 （x,y)位于圆边界内 （x,y)位于圆边界上 （x,y)位于圆边界外000),(yxF对上述函数在每个取点步骤上，对接近圆周的两个象素点的中点进行测试来决定取点。考虑一个八分之一圆弧从x=0到x=y的情况，曲线的曲率
13、从0变化到-1，在该段弧上的正x方向取单位步长，并根据决策参数确定每一步可能的y的位置，哪一个更接近圆弧的位置。设已经取的点为P根据在第二象限的圆的走向，下一列中接近圆的像素只能在P的正右方点的正右方点或者是右下方点右下方点中选择。),(kkyxn如下图所示，图中有两条圆弧A和B，假定当前取点为Pi(xi，yi)，如果顺时针生成圆，那么下一点只能取正右方的点E(xi+1，yi)或右下方的点SE(xi+1，yi-1)两者之一。LPH),(kkyx1ky1kx),(1kkyx选择标准：222)5.0()1()5.0,1(ryxyxFdkkkkk以此来判断下一步 的点如何取。是 还是 。),(11k
14、kyx),1(kkyx)1,1(kkyx理想的选择标准是计算理想的选择标准是计算H H和和L L到圆弧的距离，然后选择距离小的到圆弧的距离，然后选择距离小的点。点。在此算法中我们选择用两个点的中点作为标准，判断这个中点在此算法中我们选择用两个点的中点作为标准，判断这个中点落在圆落在圆上、外还是内？分别选择上、外还是内？分别选择L L和和H H。故有1000111kkkkkkkkkyydyydyyd中点位于圆边界内中点位于圆边界上中点位于圆边界外),(kkyx1ky1kx),(1kkyx递推判决函数1)()()1(2)5.0(1)1()5.0,1(12212212111kkkkkkkkkkkyy
15、yyxdryxyxFd其中 的取值，决定于 的符号。kd1ky有：kd321kkkxddkd若，=0 说明中点在圆外或上，那么下点取L，则判别式5221kkkkyxdd初始时在圆点，所以D0=(0+1)2+（r-0.5)2-r2=1.25-r但是此算法中有浮点运算，因此我们令F=d-0.25 则F0=1-r则上面的递推判别式为Fk=-0.25 选择L 每次迭代计算都是整数，而且初始F也为整数，所以可以等价于以0作为判别界限。中点画圆2.Bresenham算法仍然考虑圆心在原点的一个第二象限的圆弧 。对于圆弧上的点p，其下一个可选择的点如图。)2,2(),0(rrrLPH),(kkyx1ky1k
16、x),(1kkyx选择方法：可以计算出这两点到圆心的距离和半径平方的差为：即两点与圆弧的距离：222222)1()1()()1()(ryxLDryxHDiiii若：|D(H)|D(L)|则取L点。|D(H)|=|D(L)|则两点都可以取，我们约定取L。)()(LDHDdi令则选择标准可以表示为 di=0，下一点选择L。根据分析,可以用 代替上面的式子，计算可以不用绝对值计算。因此，可以由这样的递推公式：若，di=0，则 走右下方点，y坐标减1，x坐标加1，di+1=di+4(xi-yi)+10)()(LDHDdiPABCDEHL3.逐点比较法插补圆弧n首先确定顺时针还是逆时针方向画圆n若逆时针
17、n第一象限 C（Cx，Cy）圆心，起点S（Xs，Ys）末点E（Xe，Ye）n 另一点M（Xm，Ym）半径Rs M点到圆心的距离Rm点M和圆的关系：以FmRm2Rs2（XmXc）2（YmYc）2 为判别函数 则有：Fm0 点在圆外，Fm0 xs-xc0 F1=0，走 x ，xi+1=xi x，yi+1=yiFi 0，走+y ，xi+1=xi，yi+1=yi+y 21)(2xxxxFFciiin终点比较：当前点和终点的坐标值进行比较 其差的绝对值小于给定的一个小的正整数4.角度DDA画圆n圆的参数方程，t从02nx=xc+rcostny=yc+rsint圆点（xc，yc），半径r，若从起始点ts到
18、末点te 一段圆弧离散化圆弧，运动步数n可求出为 n（tets）/dt +0.5 titstdtdt如何确定？可以根据半径的大小给定dt的经验数据，并根据精度和速度进行调整由dt变化的值，只要把ti带入上面的参数方程中就能计算出xi，yi，连接点划线，绘制直线逼近圆弧即可n如果给定圆周上的3个点：起末点坐标和任一个圆周上点的坐标。求出圆心坐标和半径以及起末点所对应的角度，就可以用角度DDA法绘制圆弧了。)12()32()23()21()23()23()23()23()21()21()21()21()2/()21()32()2/()12()23(yyxxyyxxCyyyyxxxxByyyyxxx
19、xAExxBxxAycEyyByyAxc其中：椭圆n圆是椭圆的一种特殊情况。n若考虑椭圆的中心在坐标原点，长半轴为a，短半轴为b，则椭圆满足这样的参数方程：n参数方程也可以表示为n令函数 则可以由F(x,y)的值来判断点与椭圆的关系。因此，我们可以将画圆的算法推广来画椭圆。tbytaxsincos12222byax222222),(bayaxbyxF1.中点画椭圆椭圆也具有对称性，只要绘制出来第一象限的1/4，其他的就可以用对称来生成。也就是说我们只要绘制出（0，b）到（a，0）部分的按顺时针方向的最接近理想椭圆弧段的像素序列。思想：将第一象限的1/4圆弧分为两部分，分界点为椭圆弧线的斜率为-
20、1的点，即该点法向量的x分量和y分量相等。也就是2b2x=2a2y处。（1）上部分：待选择的点（xi,yi）是已经绘制点的正右方点或者右下方点。用这两点的中点(xi+1,yi-0.5)和椭圆参数函数计算出来这一点和椭圆的关系。因此有判别式：选择的标准和递推公式：di=0，选择右下方点，此时，di+1=di+b2(2xi+3)+a2(-2yi+2)222222)5.0()1()5.0,1(bayaxbyxFdiiiii 初始时，x0=0，y0=b，代入则可得到d0=F(1，（b-0.5）)=b2+a2(-b+0.25)结束点(xi,yi)满足条件2b2xi=2a2yi（2）下半部分，即2b2xi
21、=2a2yi已选点(xi,yi)，选择下一点是在右下方或者正下方点中选择。222222)1()5.0()1,5.0(bayaxbyxFdiiiii则选择标准：di=0，选择正下方点，此时，di+1=di+a2(-2yi+3)初始点处d0=F(xi+0.5，yi-1)=b2(xi+0.5)2+a2(yi-1)2-a2b22.DDA绘椭圆n椭圆的长、短半轴a、b起始点S(Xs,Ys)，起点角度ts，末点角度te，长轴和x轴方向的夹角xoyESxxxyytsC坐标系xcy中，S点坐标为sssstbytaxsincos坐标系xcy中，S的坐标为cossin sincos ssssssyxyyxxscs
22、scsyyyxxx 坐标系xoy中，S的坐标为n后面的问题就是求出S到E的椭圆上的各点坐标n（tets）/dt +0.5 titstdtiiiitbytaxsincoscossin sincos iiiiiiyxyyxxiciiciyyyxxx 抛物线n抛物线的方程分析其p为正的情况下，抛物线右边的情况，左半边可以使用其对称性绘制出来。n对其方程求导由此可以知道抛物线的性质，在p大于0的情况下，右边的斜率为正，并且随着x值的增大而增大，在xpa的时候，斜率为1，两边分别小于和大于1。因此因此 可以以xpa为分界点，左边斜率小于1，抛物线趋于水平，选择最逼近抛物线的点则应该是当前点的正右方点或者
23、是右上方点；右边斜率大于1，抛物线趋于垂直方向，所选择的下一个点则应该是当前点的正上方点或者是右上方点。)(2)(2bypaxpaxdxdy（1）x=pan从当前的象素点（xi，yi）的右方或者右上方点中选择一个合适的点作为下一点的位置。此时xi1xi1 抛物线上对应的y值为bpaxyir2)1(2然后判断yi1和yi哪个离yr更近bpaxyyyyydiiirrii2)1(12)()1(2若di0，说明右上点离的近，否则右方点为最近点。判别式变换，因为只有用到判别式的符号，所以避免使用除法和小数运算，所以对其进行边换，给其乘以p，由于p是正数所以判别式的符号没有变化。Fidi p 2pyi p
24、 (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 11222111111axpFFyyxxiiiiiii总结如下：若Fipan从当前的象素点（xi，yi）的上方或者右上方点中选择一个合适的点作为下一点的位置。此时yi1yi1 抛物线上对应的x值为abypxir)1(2然后判断xi1和xi哪个离xr更近)1(2
25、2 1)(2)()1(bypaxxxxxdiiirrii若dip+a；所以为了避免开方运算，对其进行变换；令：可以计算出其递推关系式如果选择右上点 则 Xi1 Xi 1pFFii81否则选择上方点 则 Xi1 Xi)(8111111paxFFyyxxiiiiiii总结如下：若Fi0 则 否则：pFFyyxxiiiiii81111此段的起点（xi，yi）为上一段即x=p+a的末点，则F可由F变换而来，此点处F4（Fxipa）3n对称部分的抛物线 抛物线关于xa对称因此右半部分的点（x，y）根据对称性就可以知道其左半边的对应的电为（2ax，y）。算法程序：输入参数：（Xs，Ys），（Xe，Ye）顶
26、点（a，b）参数p。xXs；y=Ys；putpixel(x，y)；F p2（Xsa）1；/*设置F的值While x !=(p+a)x=x+1 if(F0)then y=y+1;F=F2（pax）1；else F=F+2(ax)-1 putpixel(x,y);putpixel(2a x,y);if xXe 结束；/*这一段计算的式x=pa段；F 4（Fxpa）3；/*设置F的值While y !=Ye y=y+1 if(F pa段；*二次曲线的参数拟合n二次曲线的一般参数方程22121)(tetecbtattQ22121)(tetectbtatyyyy22121)(tetectbtatxxx
27、x所对应的代数方程是：通常给三个控制点P0，P1，P2可计算出各系数为221110221110110110002111)1()2()1()2()2(2)2(2122yeeyeyaxeexexayeybxexbyxxceeelekyxyxyx3点就可确定曲线位置De124e2 表示曲线线型D0 抛物线D0 双曲线D0 椭圆抛物线nD0 e1e20cbtattQ2)(yyyctbtaty2)(xxxctbtatx2)(210210101000222222yyyaxxxayybxxbyxxcyxyxyx若以t1/2时点Pm为起末点外的另一点则：)2(2)2(234342020020200yyyaxx
28、xayyybxxxbyxxcmymxmymxyxn得出参数方程的系数，就可以计算出离散化方程为yiyiyictbtay2xixixictbtax2t从0到1变化双曲线ne11 e20tcbtattQ1)(2tctbtatyyyy1)(2tctbtatxxxx1)(221021010100023233232yyyaxxxayybxxbyxxcyxyxyxn得出参数方程的系数，就可以计算出离散化方程为iyiyiyitctbtay12ixixixitctbtax12t从0到1变化椭圆ne10 e21221)(tcbtattQ221)(tctbtatyyyy221)(tctbtatxxxx21021010100022222222yyyaxxxayybxxbyxxcyxyxyxn得出参数方程的系数，就可以计算出离散化方程为221iyiyiyitctbtay221ixixixitctbtaxt从0到1变化
