讲二维图形生成算法.ppt

第三讲 二维图形生成算法,二维图形生成算法,二维图形生成算法 线段的扫描变换 基本增量算法 中点线算法 Bresenham画线算法 圆与椭圆的扫描变换,线段的扫描变换,线段的扫描变换,象素，中心位于均衡栅格上的离散圆点 。 直线扫描变换算法就是获得一系列象素的坐标，使这些象素落在所要近似的理想直线上或位于该直线的附近。原则上讲，象素序列应尽可能逼近理想的直线，而且尽可能直一些。,基本增量算法,直线方程：y=mx+b ，0m1， m= y/ x= y ； x=1，xi+1=xi+ 1，yi+1=yi+m,基本增量算法,增量算法的定义：每一步都是根据前一步进行增量计算。这种算法通常被称作数值微分(DDA)算法。DDA(Digital Differential Analyzer algorithm)是用数值方法解决微分方程的一种手段 。 请注意如果m1，则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)=0 F(x,y)= x dy+B dx -y dx 中点M=(x+1,y+1/2) d=F(M） d 下一点中点取法取决于本次点亮点是E还是NE,中点线算法,中点线算法的目的在于改进DDA算法，使得只采用整形变量参加运算。 假设当前为old点，下一点为new点，则有： dold=a(xp1)+b(yp1/2)c 如果选择的是E，M在x方向增加一个步长，那么： dnew=F(xp2，yp1/2)=a(xp2)b(yp1/2)c dnew=dolda 用E表示选择E后加入到d的增量，则E=a=dy。 如果选择的是NE，那么M在x方向和y方向上均需增加一个步长，那么： dnew=F(xp2，yp3/2)=a(xp2)b(yp3/2)c dnew=doldab 用NE表示选择NE后加入到d的增量，则 NE=ab=dydx。,增量初始值的计算,因为第一个象素是端点(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算法,01时，只保留d的小数部分作为d的新值，x=x+1, y则根据d 0.5来决定点亮(x+1,y)还是 (x+1,y+1)。,?,Bresenham算法,令e=d0.5。 则当e0时，下一象素的y坐标增加1，而当e0时，下一象素的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 或 SE d0 中点在圆外;点亮可取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+ x0 y=RsinA+y0 可有: dx=-(y-y0)dA