计算机图形学PPT课件

.,第二章光栅图形学,2.1直线段的扫描转换算法2.2圆弧的扫描转换算法2.3多边形的扫描转换与区域填充2.4字符2.5裁剪2.6反走样2.7消隐,.,2.1直线段的扫描转换算法,数值微分法（DDA算法）中点画线法Bresenham画线算法,.,数值微分法（DigitalDifferentialAnalyzer）,基本思想假定直线的起点、终点分别为：（x0,y0),(x1,y1)，且都为整数。已知过端点P0(x0,y0),P1(x1,y1)的直线段L(P0,P1);直线斜率为,按照y=kx+b计算相应的y坐标。,.,数值微分(DDA)法,设步长为x，有xi+1=xi+x则yi+1=kxi+1+b=kxi+kx+b=yi+kx因为光栅点的单位是1，对每一个x方向的增量x=1时;有yi+1=yi+k。即：当x每递增1，y递增k(即直线斜率)。经过round()函数处理得到显示的光栅点(x,round(y)坐标。xi+1=xi+1yi+1=yi+k,.,voidDDALine(intx0,inty0,intx1,inty1,intcolor)intx；floatdx,dy,y,k;dx=x1-x0;dy=y1-y0;k=dy/dx;y=y0;for(x=x0;xx1;x+)drawpixel(x,int(y+0.5),color);y=y+k;,数值微分(DDA)法,例：画直线段P0(0,0)-P1(5,2),xy+0.5int(y+0.5),00+0.50,10.4+0.50,20.8+0.51,31.2+0.51,41.6+0.52,52.0+0.52,优点：在同一坐标上,不可能连续停留两次。缺点：在此算法中，y、k必须是float，且每一步都必须对y进行舍入取整，不利于硬件实现。,算法特点:,注意：网格点表示像素,.,增量算法：在一个迭代算法中，如果每一步的x、y值是用前一步的值加上一个增量来获得，则称为增量算法。DDA算法就是一个增量算法。缺点注意上述分析的算法仅适用于k1的情形。在这种情况下，x每增加1,y最多增加1。当k1时，必须把x，y地位互换，y每增加1，x相应增加1/k。在此算法中，y、k必须是float，且每一步都必须对y进行舍入取整，有浮点数取整运算,不利于硬件实现。效率低,数值微分(DDA)法,.,原理：,假定直线斜率0取P2。M在Q的上方-P1离直线更近更近-取P1M与Q重合，P1、P2任取一点。,算法原理,如何判断M点在Q点上方还是在Q点下方？,.,已知：线段两端点(x0,y0)，(x1,y1)直线方程为：F(x,y)=ax+by+c=0其中a=y0-y1,b=x1-x0,c=x0y1-x1y0,M,中点画线法,欲判断M点是在Q点上方还是在Q点下方，只需把M代入F(x,y),并检查它的符号。,.,构造判别式：d=F(M)=F(xp+1,yp+0.5)=a(xp+1)+b(yp+0.5)+c当d0，M在直线(Q点)上方，取右方P1；当d=0，选P1或P2均可，约定取P1；能否采用增量算法呢？,中点画线法,.,若d0，中点M在直线上方，取正右方像素P1(Xp+1,Yp)再下一个像素的判别式为：d1=F(Xp+1)+1,Yp+0.5)=a(Xp+2)+b(Yp+0.5)+c=d+ad的增量为a若d0，中点M在直线下方，取右上方像素P2(Xp+1,Yp+1)再下一个像素的判别式为：d2=F(Xp+1)+1,(Yp+1)+0.5)=a(Xp+2)+b(Yp+1.5)+c=d+a+bd的增量为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由于只用d的符号作判断，为了只包含整数运算,可以用2d代替d来摆脱小数，提高效率。优点：只有整数运算，不含乘除法可用硬件实现,中点画线法,因(X0,Y0)在直线上，所以F(X0,Y0)=0,.,voidMidpointLine(intx0,inty0,intx1,inty1,intcolor)inta,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;elsex+;d+=d1;drawpixel(x,y,color);/*while*/*midPointLine*/,中点画线法,例：用中点画线法P0(0,0)P1(5,2)a=y0-y1=-2b=x1-x0=5d0=2a+b=1d1=2a=-4d2=2(a+b)=6,Ixiyid,1001,210-3,3213,431-1,5425,6521,.,Bresenham算法,基本思想过各行各列像素中心构造一组虚拟网格线。按直线从起点到终点的顺序计算直线与各垂直网格线的交点，然后根据误差项的符号确定该列像素中与此交点最近的像素。,.,设直线方程为：，其中k=dy/dx。因为直线的起始点在像素中心，所以误差项d的初值d00。X下标每增加1，d的值相应递增直线的斜率值k，即ddk。一旦d1，就把它减去1，这样保证d在0、1之间。当d0.5时，最接近于当前像素的右上方像素（xi1，yi1）而当d0)thene=e-2x,.,算法步骤：1.输入直线的两端点P0(x0,y0)和P1(x1,y1)。2.计算初始值x、y、e=-x、x=x0、y=y0。3.绘制点(x,y)。4.e更新为e+2y，判断e的符号。若e0，则(x,y)更新为(x+1,y+1)，同时将e更新为e-2x；否则(x,y)更新为(x+1,y)。5.当直线没有画完时，重复步骤3和4。否则结束。,Bresenham算法,.,程序如下：BresenhamLine(intx0,inty0,intx1,inty1,intcolor)intx,y,dx,dy,e;dx=x1-x0;dy=y1-y0;e=-dx;x=x0;y=y0;for(i=0;i=0)y+;e=e-2*dx;,优点整数运算，速度快精度高乘2运算可用移位实现，适于硬件实现,.,斜率不同时：以上讨论的是0k1的情况，即0yx的情况；若是0xy的情况，则需将x和y的位置交换。方向不同时：若y0或x0时，要将算法中的yy1换成yy1、xx1换成xx1。,思考讨论：,.,几种画线算法的比较,DDA算法直观，易于实现，但是x、y、和k必须用浮点数表示，而且每一步都需要对x和y进行舍入取整，不利于硬件实现。中点算法可以替换成整数运算，便于硬件实现。Bresenham算法不计算斜率，不用浮点数，只做整数的加减运算或乘2运算，而乘2运算可以用移位操作来实现，因此Bresenham算法是速度最快的。,.,实验一直线的生成,在VisualC+6.0环境中设计MFC单文档程序，利用消息处理函数，搭建能运行图形算法程序的平台。实现直线段的3种生成算法：DDA算法(考虑k大于或小于等于1的情况)、中点法和Bresenham算法（原算法和改进算法）。,.,第二章光栅图形学,2.1直线段的扫描转换算法2.2圆弧的扫描转换算法2.3多边形的扫描转换与区域填充2.4字符2.5裁剪2.6反走样2.7消隐,.,2.2圆弧的扫描转换算法,直接离散生成算法中点画圆法Bresenham画圆算法椭圆的中点画法,.,圆弧扫描算法,下面仅以圆心在原点、半径R为整数的圆为例，讨论圆的生成算法。假设圆的方程为：x2+y2=R2圆的八对称性可以用四条对称轴x0，y0，xy，xy把圆分成8等份。只要绘制出第一象限内的1/8圆弧，根据对称性就可绘制出整圆，这称为八分法画圆算法。,P（y，x）P（y，x）,P（x,y）,P（x，y），P（y，x），P（y，x），P（x，y）。,假定第一象限内的任意点为P（x，y），可以确定另外7个点：,.,圆弧扫描算法,两种直接离散生成方法离散点开方运算离散角度三角函数运算缺点：计算量大所画像素位置间的间距不一致、不均匀,.,圆弧扫描算法,SimpleCircle(intr,intcolor)intx,y;for（x=0;x=r;x+)y=Round(sqrt(r*r-x*x)；circlepoints(x,y,color);ParameterCircle(intr,intcolor)intx,y;for（floatt=0;t=/2;t+=0.05)x=Round(r*cos(t)；y=Round(r*sin(t)；circlepoints(x,y,color);,.,第二个8分圆P（Xp，Yp）P为当前点亮像素，那么，下一个点亮的像素可能是P1（Xp+1，Yp）或P2（Xp+1，Yp-1)。,中点画圆法,.,中点画圆法,F(X,Y)=X2+Y2-R2=0中点M=(Xp+1,Yp-0.5)当F(M)0时，M在圆内，P1距离圆弧近，取P1当F(M)0时，M在圆外，P2距离圆弧近，取P2,.,中点画圆法,若d=0,取P1为下一像素，再下一像素的判别式为初始像素是（0,R），判别式d的初值为,P1(Xp+1,Yp),P2(Xp+1,Yp-1),.,算法步骤：1.输入圆的半径R。2.计算初始值d=1.25-R、x=0、y=R。3.绘制点(x,y)及其在八分圆中的另外七个对称点。4.判断d的符号。若d0，则先将d更新为d+2x+3，再将(x,y)更新为(x+1,y)；否则先将d更新为d+2(x-y)+5，再将(x,y)更新为(x+1,y-1)。5.当xy时，重复步骤3和4。否则结束。,中点画圆法（一般算法）,.,MidpointCircle(intr,intcolor)intx,y;floatd;x=0;y=r;d=1.25-r;circlepoints(x,y,color);while(xy)if(d0)d+=2*x+3;x+elsed+=2*(x-y)+5;x+;y-;circlepoints(x,y,color);,中点画圆法（一般算法）,思考题：如何将上面算法中的浮点数改写成整数，将乘法运算改成加法运算，即仅用整数实现中点画圆法，以进一步提高算法的效率？,.,为了进一步提高算法的效率，可以将上面的算法中的浮点数改写成整数，将乘法运算改成加法运算，即仅用整数实现中点画圆法。因为中点画圆算法的半径是整数，而用于该算法符号判别的变量d采用浮点运算，会花费较多的时间。为了将其改造成整数计算，对d作如下变换：使用d=d-0.25代替dd=1-R判别式d0等价于d-0.25,在d为整数的情况下，d-0.25与d0等价，仍将d写成d，可得到中点圆整数算法,中点画圆法,.,算法步骤：1.输入圆的半径R。2.计算初始值d=1-R、x=0、y=R。3.绘制点(x,y)及其在八分圆中的另外七个对称点。4.判断d的符号。若d0，则先将d更新为d+2x+3，再将(x,y)更新为(x+1,y)；否则先将d更新为d+2(x-y)+5，再将(x,y)更新为(x+1,y-1)。5.当xy时，重复步骤3和4。否则结束。程序,中点画圆法（整数算法）,.,MidpointCircleInt(intr,intcolor)intx,y,d;x=0;y=r;d=1-r;circlepoints(x,y,color);while(xy)if(d0)d+=2*x+3;x+elsed+=2*(x-y)+5;x+;y-;circlepoints(x,y,color);,中点画圆法（整数算法）,.,如图中点Pi-1是已选中的一个表示圆弧上的点，根据弧的走向，下一个点应该从Hi或者Li中选择。选择的原则是：考察精确值是靠近Hi还是Li，即精确值y是靠近yi还是yi-1假设圆的半径为R，计算式为y2=R2-(xi+1)2令d1、d2分别为yi(Hi)到y和yi-1(Li)到y的距离，可知：d1=yi2-y2=yi2-R2+(xi+1)2d2=y2-(yi-1)2=R2-(xi+1)2-(yi-1)2,Bresenham画圆算法,（1）如果di0，则y=yi，即选择当前像素的正右方作为下一个像素，递推公式为：（2）如果di0，则y=yi-1，即选择当前像素的右下方作为下一个像素，递推公式为：（3）计算判别式的初值。初始点为（0，R），则：,令判断式di=d1-d2，并代入d1、d2，则有：,.,Bresenham画圆算法,算法步骤：1.求误差初值d1=3-2r，i=1，画点（0，r）。2.求下一个光栅位置，其中xi+1=xi+1，如果di0：,判别式递推公式为：,判别式的初始值,p(x,i,y,i,),p,l,(x,i,y,i-1,),p,r,(x,i+1,y,i-1,),M,(x,i+1,y,i-0.5,),下半部分椭圆弧的绘制原理,再来推导椭圆弧下半部分的绘制公式原理,设椭圆当前点为pi(xi,yi),对应的下一候选像素是正下方的pl(xi,yi-1),或右下方的pr(xi+1,yi-1),判别式其中点是M(xi+0.5,yi-1),若d20，中点在椭圆外，取正下方像素Pl(xi,yi-1)若d20，中点在椭圆内，取右下方像素Pr