ch03直线、圆、椭圆的生成.ppt

1、扫描转换直线段,DDA算法,中点画线法,Bresenham画线算法,2、圆弧、椭圆弧扫描转换,中点画圆算法,Bresenham画圆算法,中点画椭圆算法,本章内容,扫描转换原理,第三章 直线、圆、椭圆生成算法,1、输出图元(Output Primitive),图形生成的基本构造单元称为输出图元输出图元包括字符串和几何成分，如：点、直线，二次曲线、填充区域（多边形，圆）及由彩色阵列定义的形状2、扫描转换,图形的两种表示方法,,点阵表示,矢量表示,反映了图形的外表,反映了图形的内在联系,对光栅扫描器而言，矢量表示不能直接用于显示,将矢量表示的图形对象的转换为点阵表示称为扫描转换,,,任何图形的光栅化，必须显示在一个窗口内，否则不予显示即确定一个图形的哪些部分在窗口内，哪些在窗口外，即裁剪第三章 直线、圆、椭圆生成算法,图形的扫描转换（光栅化）：确定一个像素集合，用于显示一个图形的过程步骤如下：,1、确定有关像素,2、用图形的颜色或其它属性，对像素进行写操作对一维图形，不考虑线宽，则用一个像素宽的直线来显示图形二维图形的光栅化，即区域的填充：确定像素集，填色或图案图形显示前需要：扫描转换+裁剪,裁剪扫描转换：最常用，节约计算时间。

扫描转换裁剪：算法简单；,第三章 直线、圆、椭圆生成算法,屏幕坐标定义,由扫描转换原理知：数字设备通过绘制两端点间的离散点来显示直线段，线段上离散坐标位置是从线段方程中计算出来的，其所表示的对象用精确的坐标描述，其每一位置是数学上的无限小的点；,而在光栅扫描显示器中的点用一个像素表示其为一有限的屏幕区域，屏幕的位置用整数值，所以屏幕上绘制的点仅是实际坐标中点位置的近似要显示坐标系中指定几何形状就需要调整数学输入点到有限像素区域的映射,数学输入点到有限像素区域的映射方法有两种,1、对象与像素中心对齐,2、物体边界与像素边界对齐,见下图,第三章 直线、圆、椭圆生成算法,像素中心对准编址方式,像素边界对准编址方式,两种屏幕坐标的编址方法,注：在后面学习中使用像素中心对准编址方式,第三章 直线、圆、椭圆生成算法,直线段的扫描转换算法,直线的扫描转换:,确定最佳逼近于该直线的一组象素，并且按扫描线顺序，对这些象素进行写操作三个常用算法：,数值微分法（DDA）；,中点画线法；,Bresenham算法假定直线的起点、终点分别为：(x0,y0), (x1,y1)，且都为整数记直线的斜率为k数值微分(DDA)法,,,,,,,虚线交叉点为像素中心点,,基本思想,已知过端点P0 (x0, y0), P1(x1, y1)的直线段L:y=kx+b,直线斜率为,这种方法直观，但效率太低，因为每一步需要一次浮点乘法和一次舍入运算。

数值微分(DDA)法,即：当x每递增1，y递增k(即直线斜率)；,先考虑k ≤1的情形当 k 1时，必须把x，y地位互换,数值微分(DDA)法,在这种情况下，x每增加1，y最多增加1在这种情况下，y每增加1，x最多增加1即：当y每递增1，x递增1/k(即直线斜率倒数)；,数值微分(DDA)法,增量算法：在一个迭代算法中，如果每一步的x、y值是用前一步的值加上一个增量来获得，则称为增量算法DDA算法就是一个增量算法上面是从左端点开始计算的，若以右端点作为起始点,当k ≤1时：取x=-1, yi+1=yi-k,当k ≥1时：取y=-1, xi+1=xi-1/k,下面为一般DDA算法的一段伪代码,数值微分(DDA)法,if( abs(x1-x0)=abs(y1-y0) then Length= abs(x1-x0) else Length= abs(y1-y0) end if %选取x和y大者作为步长 x=(x1-x0)/Length y=(y1-y0)/Length x=x0+0.5 y=y0+0.5,%开始主循环 i=1 while(i=Length) Setpixel(int(x),int(y)) x=x+ x y=y+ y i=i+1 end while,DDA算法的伪代码,,#include #include inline int round (const float a) { return int (a + 0.5); } void lineDDA (int x0, int y0, int xEnd, int yEnd) { int dx = xEnd - x0, dy = yEnd - y0, steps, k; float xIncrement, yIncrement, x = x0, y = y0; if (fabs (dx) fabs (dy)) steps = fabs (dx); else steps = fabs (dy); xIncrement = float (dx) / float (steps); yIncrement = float (dy) / float (steps); setPixel (round (x), round (y)); for (k = 0; k steps; k++) { x += xIncrement; y += yIncrement; setPixel (round (x), round (y)); } },数值微分(DDA)法,例：画直线段P0(0,0)--P1(5,2),缺点：在此算法中，y、k必须是float，且每一步都必须对y进行舍入取整，不利于硬件实现。

数值微分(DDA)法,dx =5,dy =3 steps =5,x =1, y =2/5=0.4,,,,,,,假定直线斜率0k1，且已确定点亮象素点P(xp ,yp )，则下一个与直线最接近的像素只能是P1点或P2点设M为中点，Q为交点,原理：,现需确定下一个点亮的象素中点画线法,当M在Q的下方 P2离直线更近更近取P2 M在Q的上方 P1离直线更近更近取P1,M与Q重合， P1、P2任取一点中点画线法,问题：如何判断M与Q点的关系？,假设直线方程为：ax+by+c=0, 其中a=y0-y1, b=x1-x0 , c=x0y1-x1y0令F(x,y)=ax+by+c，由常识知：,∴欲判断M点是在Q点上方还是在Q点下方，只需把M代入F(x,y)，并检查它的符号中点画线法,dp=F(M) =F(xp+1,yp+0.5) =a(xp+1)+b(yp+0.5)+c,构造判别式：,当dp0, M在直线(Q点)下方,取右上方P2(xp+1,yp+1);,当dp 0,M在直线(Q点)上方,取右下方P1(xp+1,yp);,当dp=0，选P1或P2均可，约定取P1能否采用增量算法呢？,dp称为画线算法中第p步决策参数,中点画线法,若dp0M在直线上方(xp+1,yp+1)取P1(xp+1,yp);,此时再求下一个象素的判别式为,dp+1 =F(xp+2, yp+0.5) =a(xp+2)+b(yp+0.5)+c = a(xp +1)+b(yp +0.5)+c +a =dp+a；,增量为a,中点画线法,若dp0M在直线下方(xp+1,yp+1)取P2(xp+1,yp+1);,此时再求下一个象素的判别式为,dp+1= F(xp+2, yp+1.5) =a(xp+2)+b(yp+1.5)+c = a(xp +1)+b(yp +0.5)+c +a +b =dp+a+b ；,增量为a＋b,中点画线法,画线从(x0, y0)开始，d的初值,d0=F(x0+1, y0+0.5) = a(x0 +1)+b(y0 +0.5)+c = F(x0, y0)+a+0.5b = a+0.5b,由于只用dp 的符号作判断，为了只包含整数运算, 可以用2dp代替dp来摆脱小数，提高效率。

此时d0= 2a+b，增量分别为2a和2(a+b)中点画线法,|k|1时直线中点画线算法,1、输入线段的两个端点，并将左端点储存在(x0,y0)中.,2、将(x0,y0)装入帧缓存中，画出第一个点3、计算常量a=y0-y1, b=x1-x0, d1=2a, d2=2 (a+b); 并得到决策参数的第一个值d0=2a+b 4、从p=0开始,在沿路径的每个xp处,进行下列检测：,如果dp0,下一个绘制的点为(xp+1,yp+1)，并且dp+1=dp+d2；,否则，下一个绘制的点为(xp+1,yp)，并且dp+1=dp+d15、重复步骤4，直到xpx1为止中点画线法,void Midpoint_Line (int x0,int y0,int x1, int y1,int color),{ int a, b, d1, d2, d, x, y; a=y0-y1, b=x1-x0, d=2*a+b; d1=2*a, d2=2* (a+b); x=x0, y=y0; drawpixel(x, y, color); while (xx1) { if (d0) {x++; y++; d+=d2; } else {x++; d+=d1;} drawpixel(x, y, color); } /* while */ } /* mid PointLine */,中点画线法,例：用中点画线法P0(0,0) P1(5,2),a=y0-y1=-2 , b=x1-x0=5,,d0=2a+b=1, d1=2a=-4 ,d2=2(a+b)=6,i xi yi d,1 0 0 1,2 1 0 -3,3 2 1 3,4 3 1 -1,5 4 2 5,,,,,,,Bresenham画线算法,在直线生成的算法中Bresenham算法是最有效的算法之一,令 k= y/x，就0≤k≤1的情况来说明Bresenham算法,假设已确定要显示的像素(xi,yi)，下一步要确定在列xi+1上绘制在位置(xi+1,yi)像素，还是在位置(xi+1,yi+1)像素,设直线方程为 y=kx+b,其与x=xi+1的交点为(x,y),设d1,d2分别为交点(x,y)到y=yi和y=yi+1的距离,显然,又,令pi=x(d1-d2),所以pi=x(d1-d2)= 2yxi-2xyi+c,其中c= 2y+x(2b-1),由于x0，所以pi 与(d1-d2)同号,pi称为画线算法中第i步决策参数,Bresenham画线算法,pi 的增量算法,pi+1=2yxi+1-2xyi+1+c,pi+1-pi=2y(xi+1-xi)-2x(yi+1-yi),因为xi+1=xi+1, 所以有,pi+1=pi+2y-2x(yi+1-yi),显然 p0= x(2k-1)=2y-x,Bresenham画线算法,|k|1时直线Bresenham算法,1、输入线段的两个端点，并将左端点储存在(x0,y0)中.,2、将(x0,y0)装入帧缓存中，画出第一个点。

3、计算常量x、y、2y和2y-2x ，并得到决策参数的第一个值p0=2y- x 4、从i=0开始，在沿路径的每个xi处，进行下列检测：,如果pi0,下一个绘制的点为(xi+1,yi)，并且pi+1=pi+2y,否则，下一个绘制的点为(xi+1,yi+1)，并且pi+1=pi+2(y-x),Bresenham画线算法,5、重复步骤4，共x次Bresenham画线算法,【例】求过端点为(20,10)和(30,18)直线各像素点,x=10, y=8, d1=2y=16, d2=2y-2x=-4,p0=2y-x=6,k pk xk+1 yk+1,0 6 21 11,1 2 22 12,2 -2 23 12,3 14 24 13,4 10 25 14,5 6 26。