(精品)第三讲：二维图形生成算法.ppt

二维图形生成算法二维图形生成算法二维图形生成算法线段的扫描变换基本增量算法中点线算法Bresenham画线算法圆与椭圆的扫描变换线段的扫描变换线段的扫描变换线段的扫描变换象素象素，中心位于均衡栅格上的离散圆点中心位于均衡栅格上的离散圆点。直线扫描变换算法直线扫描变换算法就是获得一系列象素就是获得一系列象素的坐标，使这些象素落在所要近似的理的坐标，使这些象素落在所要近似的理想直线上或位于该直线的附近。原则上想直线上或位于该直线的附近。原则上讲，象素序列应尽可能逼近理想的直线，讲，象素序列应尽可能逼近理想的直线，而且尽可能直一些。而且尽可能直一些。基本增量算法基本增量算法直线方程：直线方程：y=mx+b，0m1，则，则x的步进会使的步进会使y的步进的步进超过超过1，此时，如果采用上述算法将会使得点，此时，如果采用上述算法将会使得点亮的象素个数太少，画出来的线没有很好的模亮的象素个数太少，画出来的线没有很好的模拟理想直线，例如：从拟理想直线，例如：从(0,2)点到点到(2,100)点画点画线，则会只点亮线，则会只点亮3个点来表示，光栅点太稀了。个点来表示，光栅点太稀了。解决办法是颠倒解决办法是颠倒x与与y的位置，给的位置，给y以单位增量，以单位增量，而而x的增量为的增量为x=y/m=1/m，即，即取取x轴和轴和y轴中轴中变化最快的轴作为参考轴变化最快的轴作为参考轴以保证直线被光栅化以保证直线被光栅化后有足够多的象素。后有足够多的象素。基本增量算法基本增量算法的实现的实现#include/*加入加入c图形库图形库*/#include/*数学库数学库*/#include/*键盘控制键盘控制*/void Line(int x0,int y0,int x1,int y1,int value)/*从坐标从坐标(x0,y0)到到(x1,y1)画颜色为画颜色为value的直线的直线*/int x;float dx,dy,m,y;dx=x1-x0;dy=y1-y0;m=dy/dx;/*取得斜率取得斜率*/y=y0;for(x=x0;x=x1;x+)putpixel(x,(int)(y+0.5),value);/*找到距理想直线最近的点找到距理想直线最近的点，putpixel为画点为画点函数函数*/y=y+m;/*计算下一步的计算下一步的y值值，增幅为增幅为m*/基本增量算法基本增量算法考虑基本增量算法是否是考虑基本增量算法是否是最优最优的！的！1.运算符的快速性运算符的快速性采用增量思想的采用增量思想的DDA算法算法,每计算一个象素，每计算一个象素，只需计算一个加法。加法已经是最快的算法了只需计算一个加法。加法已经是最快的算法了（加减乘除开方三角函数等）（加减乘除开方三角函数等）2.参数运算的快速性参数运算的快速性DDA算法的计算中含有浮点数运算。算法的计算中含有浮点数运算。把浮点把浮点运算的加法变成整数加法，因为运算的加法变成整数加法，因为整数的加法比整数的加法比浮点的加法要快很多浮点的加法要快很多 中点线算法中点线算法直线方程：直线方程：F(x,y)=0F(x,y)=x dy+B dx-y dx 中点中点M=(x+1,y+1/2)d=F(M）d下一点中点取法取决于本次下一点中点取法取决于本次点亮点是点亮点是E还是还是NE=0 M是直线一点0 M在直线下方=0 点亮E或者NE0点亮NE中点线算法中点线算法中点线算法的目的中点线算法的目的在于改进在于改进DDA算法，使得只采用算法，使得只采用整整形变量参加运算。形变量参加运算。假设当前为假设当前为old点，下一点为点，下一点为new点，则有：点，则有：dold=a(xp1)+b(yp1/2)c如果选择的是如果选择的是E，M 在在x方向增加一个步长，那么：方向增加一个步长，那么：dnew=F(xp2，yp1/2)=a(xp2)b(yp1/2)cdnew=dolda用用E表示选择表示选择E后加入到后加入到d的增量的增量，则，则E=a=dy。如果选择的是如果选择的是NE，那么，那么M在在x方向和方向和y方向上均需增加方向上均需增加一个步长，那么：一个步长，那么：dnew=F(xp2，yp3/2)=a(xp2)b(yp3/2)cdnew=doldab用用NE表示选择表示选择NE后加入到后加入到d的增量的增量，则，则NE=ab=dy dx。增量初始值的计算增量初始值的计算因为第一个象素是端点因为第一个象素是端点(x0，y0)，可直接计算，可直接计算d的初始值的初始值dstart，以此决定是选，以此决定是选E还是还是NE。第。第一个中点在一个中点在(x01，y0 1/2)处，有：处，有：dstart=F(x01，y01/2)=a(x01)b(y01/2)c=ax0by0cab/2=F(x0，y0)ab/2由于由于(x0，y0)在线上，因此在线上，因此F(x0，y0)=0；故；故dstart=ab/2=dydx/2。对对DDA的改进的改进为为消除分数部分消除分数部分，将，将F乘上乘上2重新定义重新定义F：F(x，y)=2(axbyc)，使每个常量，使每个常量和判断变量均乘上和判断变量均乘上2，但这并不影响判，但这并不影响判断变量断变量d的符号，因此仍可作为中点检的符号，因此仍可作为中点检测的标准。测的标准。最终结果：最终结果：每一步每一步dnew值的计算只需值的计算只需做简单的加法，无需耗时的乘法。做简单的加法，无需耗时的乘法。中点线算法中点线算法举例举例中点线算法中点线算法改进：改进：中点算法进一步把效率提高到每中点算法进一步把效率提高到每步只做一个整数加法，如果再想在算法步只做一个整数加法，如果再想在算法的效率上作文章已经是不可能了。但是的效率上作文章已经是不可能了。但是DDA和中点算法严格依赖直线方程，不和中点算法严格依赖直线方程，不能再推广。而下面讲述的能再推广。而下面讲述的Bresenham画画线算法不但能解决直线的光栅化，还能线算法不但能解决直线的光栅化，还能解决圆弧、抛物线甚至自由曲线的光栅解决圆弧、抛物线甚至自由曲线的光栅化问题，使算法的覆盖域扩大。化问题，使算法的覆盖域扩大。Bresenham算法算法0m1时，只保留时，只保留d的小数部分作为的小数部分作为d的新的新值，值，x=x+1,y则根据则根据d 0.5来决定点亮来决定点亮(x+1,y)还是还是(x+1,y+1)。?Bresenham算法算法令令e=d0.5。则当则当e 0时，下一象素的时，下一象素的y坐标增加坐标增加1，而当而当e 0时，下一象素的时，下一象素的y坐标不变。坐标不变。e的初值为的初值为0.5。从而利用从而利用e代替代替d，来判断下一点的取舍，来判断下一点的取舍圆的扫描变换利用对称性可以利用对称性可以加速画圆过程加速画圆过程;只需计算只需计算45弧段弧段,通过对称变换可通过对称变换可完成整圆完成整圆.圆的扫描变换(中点算法）思路思路:当前显示点当前显示点P=(Xp,Yp),取第取第二八分圆二八分圆圆方程为圆方程为x2+y2=R2,因此令因此令:F(x,y)=x2+y2-R2中间点中间点M=(Xp+1,Yp-(1/2)令令:d=F(M)判断判断:d=0 中点在圆上中点在圆上;点亮可取点亮可取E 或或 SEd0 中点在圆外中点在圆外;点亮可取点亮可取SE椭圆的扫描变换（中点算法）思路思路:方程为方程为:F(X,Y)=b2x2+a2y2-a2b2=0由于对称性由于对称性,只考虑第一象限中的椭圆生成只考虑第一象限中的椭圆生成把此象限内的弧段分成两段把此象限内的弧段分成两段,以法向量中两分量相等处为分界线以法向量中两分量相等处为分界线,既斜率为既斜率为-1处处.上部中点为上部中点为(xp+1,yp-(1/2),亮点选择有亮点选择有E和和SE,取取y的的中值中值.下部中点为下部中点为(xp+(1/2),yp-1),亮点选择有亮点选择有S和和SE,取取x的中值的中值.判断何时从上部转入下部的条件判断何时从上部转入下部的条件:法向量的两个分量是否相等法向量的两个分量是否相等.起始点起始点:(0,b);终止点终止点:(a,0)曲线曲线DDA算法算法 y=f (x)x;可按步长逐点画出这条曲线可按步长逐点画出这条曲线例如对于圆周上任意一点的坐标方程为：例如对于圆周上任意一点的坐标方程为：x=RcosA+x0y=RsinA+y0可有可有:dx=-(y-y0)dAdy=(x-x0)dA因而因而 x2=x1+dx=x1-(y1-y0)dAy2=y1+dy=y1+(x2-x0)dA其中角度的增量其中角度的增量dA很小，用弧度表示，很小，用弧度表示，A是圆弧的张角。是圆弧的张角。(y0,x0)是曲率中心点，圆弧是曲率中心点，圆弧应在（应在（x,y）处）处起始逆时针画出。起始逆时针画出。