计算机图形学03-二维图形生成.

1ComputerGraphics计算机图形学第3讲：二维图形生成2目录CONTENTS01绪论02图形系统03二维图形生成04图形几何变换05二维观察06三维观察07三维对象08真实感图形技术09交互技术10计算机动画3图元primitive•任何复杂的图形通常被看作是由一些基本图形元素（图元）构成的。基本二维图元包括点、直线、圆弧、多边形、字体符号和位图等，它们的显示问题是任何复杂二维图形及图像显示技术的基础。•三维图形的显示最终也是通过投影转化成二维图形的显示。•图元通常是指不可再分的独立的图形实体。•基本图元显示问题就是根据基本图元的描述信息来生成像素组合。§3.1直线生成算法4图元的描述除了含有坐标信息外，还描述了图元的一些属性信息，比如线宽、线型、颜色、填充图案等图元的属性5ComputerGraphics第3章：二维图形生成1•直线生成算法2•圆弧绘制算法3•区域填充4•字符5•反走样技术6曲线和各种复杂的图形均是离散成许多直线段来绘制，因而直线是二维图形生成技术的基础。理论上认为，根据直线的数学方程算出直线上的一个个点即可，但这样做运算效率不高。常见算法：1数值微分法2逐点比较法3中点画线法4Bresenham算法§3.1直线生成算法7数值微分法（DDA法）是根据直线的微分方程来画直线的，它是最简单的一种画线方法。•设直线的起点坐标是Ps(xs,ys)，终点坐标为Pe(xe,ye)，令Δx=xe-xs，Δy=ye-ys，则要绘制的直线的微分方程为•对上面的式子用中的微商用差商来代替，即得•令Δm=max(|Δx|,|Δy|)，取时间步长t2-t1=1/Δm，则对每一步，可得上述微分方程数值解的递推公式为xi+1=xi+Δx/Δm，yi+1=yi+Δy/Δm1数值微分法xdtdxydtdyxttxxiiii11yttyyiiii118按照直线的斜率k=Δx/Δy可分两种情况来分析：•|k|1时，y方向为计长方向，这时Δm=|Δy|，增加或减少的步长Δy/Δm始终为1个单位。x方向的变化步长为Δx/Δm。•|k|≤1时，x方向为计长方向。这时Δm=|Δx|，x方向的变化量Δx/Δm为1个单位，y方向的变化步长则为Δy/Δm。1数值微分法1a2a3a4a1b2b3b4b1Δy/ΔmΔx/Δm19DDA算法程序voidLineDDA(intx1,inty1,intx2,inty2,intcolor){intdm=0;if(abs(x2-x1)=abs(y2-y1)//abs是求绝对值的函数dm=abs(x2-x1);//x为计长方向elsedm=abs(y2-y1);//y为计长方向floatdx=(float)(x2-x1)/dm;//当x为计长方向时，dx的值为1floatdy=(float)(y2-y1)/dm;//当y为计长方向时，dy的值为1floatx=x1+0.5;floaty=y1+0.5;for(inti=0;idm;i++){setpixel((int)x,(int)y,color);x+=dx;y+=dy;}}DDA法每产生一个像素点只需要加法运算，但如果绘制的线很长时会产生累积误差，尽管这种误差通常不会产生很大的影响。10P2P1MQP(xp,yp)1.构造判别式假定直线斜率0k1，且已确定当前处理过的像素点P(xp,yp)，则下一个与直线最接近的像素只能是P1或P2。设M为P1与P2的中点，Q为交点，见图。现确定下一个要画的像素的位置。•如果M在Q下方，则P2离直线近，取P2；•如果M在Q上方，则P1离直线近，取P1。•M与Q重合，P1、P2任取一点。•问题转换为如何判断M与Q点的关系。4中值画线法11中值画线算法•假设直线方程为F(x,y)=ax+by+c=0其中a=y0-y1,b=x0-x1,c=x0y1-x1y0.•则由数学知识可知有下面的关系：F(x,y)=0，点在直线上，F(x,y)0，点在直线上方，F(x,y)0，点在直线下方。所以，欲判断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)下方，取右上方P2；当d≥0，M在直线(Q)上方，取右方P1。12中值画线算法2.判别式的增量算法当d≥0，此时取P1，新的判别式为（将xp+1代入xp）d1=F(xp+2,yp+0.5)=a(xp+2)+b(yp+0.5)+c=a(xp+1)+b(yp+0.5)+c+a=d+a增量为a；若d0，此时取P2，新的判别式为（将yp+1代入yp）d2=F(xp+2,yp+1.5)=a(xp+2)+b(yp+1.5)+c=a(xp+1)+b(yp+0.5)+c+a+b=d+a+b增量为a+b。13中值画线算法3.判别式的初始值画线从(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来摆脱小数，提高效率。4.其它斜率情形用同样的推导过程，不难得出当直线斜率-1k0时：当d≥0，此时再下一个像素的判别式为d1=d-a；当d0，此时再下一个像素的判别式为d2=d-a+b；当斜率|k|1时，将x,y坐标互换以完成递推过程。在画点时再将x,y坐标互换。14Bresenham画线算法是最广泛的直线生成算法，它采用加减与乘2运算（即移位运算）来实现。•先从直线斜率为0≤k≤1的八分之一象限开始讨论。•首先从像素P1(x1,y1)开始，每次在水平方向朝P2(x2,y2)移动一个像素，由于受斜率k的限制，每一个被选中像素的下一个像素点或者是右边的点S，或者是右上边的点。3Bresenham画线法TSstP1P2(xi,yi)153Bresenham画线法1.判别式假设所绘制的直线方程为y=mx+b当x=xi+1时，直线对应的y坐标是y=mxi+1+b=m(xi+1)+b点S到直线的距离为s=y-yi；点T到直线的距离为t=yi+1-y；通过考虑两个距离之差即s-t的值来确定应选哪个点：当st时，直线离S点近，选S;当s≥t时，直线离T点近，选T点；而s-t=(y-yi)-[(yi+1)-y]=2y-2yi-1=2m(xi+1)+2b-2yi-1163Bresenham画线法2.迭代公式令Δx=x2-x1，Δy=y2-y1，则m=Δy/Δx，用Δy/Δx代替m得两边同乘以Δx后得：Δx(s-t)=2Δy(xi+1)+Δx(2b-2yi-1)=2Δy∙xi-2Δx∙yi+2Δy+Δx(2b-1)令di=Δx(s-t)，由于Δx0，所以di和s-t符号相同，因此可得：di=2Δy∙xi-2Δx∙yi+C其中，C=2Δy+Δx(2b-1)，它是个常量。同理，通过使下标增1后，得到di+1为di+1=2Δy∙xi+1-2Δx∙yi+1+C两者相减得到di+1-di=2Δy∙(xi+1-xi)-2Δx∙(yi+1-yi)=2Δy-2Δx(yi+1-yi)di+1=di+2Δy-2Δx(yi+1-yi)122)1(2iiybxxyts173Bresenham画线法当di≥0时，即s-t≥0，该选择T，yi+1=yi+1，所以di+1=di+2(Δy–Δx)；当di0时，即s-t0，该选择S，yi+1=yi，所以di+1=di+2Δy。因此得到的判别式迭代公式总结为起点的判别式：-1≤k≤0由于di=Δx(s-t)，所以对于直线的起点有di=Δx[2m(xi+1)+2b-2yi-1]=Δx[2(mxi+b-yi)-2m-1]由于起点在直线上，所以满足mxi+b-yi=0，可得d1=2mΔx-Δx=2Δy-Δxydxyddiii2)(2100iiddvoidBresenham_Line(intx1,inty1,intx2,inty2,intcolor){setpixel(x1,y1,color);intdx=abs(x2-x1);intdy=abs(y2-y1);if(dx==0&&dy==0)return;intflag=0;if(dxdy)//下面将斜率变换至0≤|k|≤1区间{flag=1;swap_value(&x1,&y1);swap_value(&x2,&y2);swap_value(&dx,&dy);}inttx=(x2-x1)0?1:-1;intty=(y2-y1)0?1:-1;intcurx=x1;intcury=y1;intdS=2*dy;intdT=2*(dy-dx);intd=dS-dx;while(curx!=x2){if(d0)d+=dS;else{cury+=ty;d+=dT;}if(flag)setpixel(cury,curx,color);elsesetpixel(curx,cury,color);curx+=tx;}}voidswap_value(int*a,int*b){inttemp=*a;*a=*b;*b=temp;}19ComputerGraphics第3章：二维图形生成1•直线生成算法2•圆弧绘制算法3•区域填充4•字符5•反走样技术20二次曲线是指那些能用二次函数表示的曲线，包括圆弧、椭圆以及抛物线。它们的绘制通常是离散成相互连接的小直线段来逼近理想曲线的。这里主要介绍圆的绘制，其它曲线不再赘述。§3.2圆弧绘制算法022FEyDxcyBxyAx21(x,y)(x,-y)(y,-x)(y,x)(-y,-x)(-y,x)(-x,y)(-x,-y)(x,y)(x,-y)(y,-x)(y,x)(-y,-x)(-y,x)(-x,y)(-x,-y)整圆绘制算法有逐点比较法、Bresenham算法和中点画圆法，这些算法可以借助四路对称或八路对称来加速。四路对称是指生成1/4象限的圆弧，其它象限的圆弧是由已生成的一个象限对称而获得。同理，八路对称是只生成1/8象限的圆弧，其它部分全部由对称规则生成。圆心位于原点时，该圆有四条对称轴x=0，y=0，x=y，x=-y。从而若已知圆弧上的一点(x,y)，就可以得到关于其关于四条对称轴的七个对称点。§3.2.1基于光栅的整圆绘制算法22中点画圆算法•假设P为当前点亮象素，那么下一个点亮的象素可能是T(xp+1,yp)或S(xp+1,yp-1)。•令M为T和S和中点，M的坐标为(xp+1,yp-0.5)。构造一个函数将中点M的坐标代入函数，则有如下结论：若F(M)0，M在圆内，此时下一个点取T；若F(M)≥0，M在圆上或圆外，此时下一个点取S。222),(ryxyxFTSstPMTSstPTSstPM23中点画圆算法为此，可采用如下判别式假定当前判别式d为已知，且d0，则T被选为新的点亮象素，那么再下一个像素的判别式为故d的增量为2xp+3。若d≥0，则S被选为新的点亮像素，则再下一个像素的判别式为即d的增量为2(xp-yp)+5。2220.5)(1)(0.5)1,()(ryxyxFMFdppppi320.5)(2)(0.5)2()(2221pippppixdryxy,xFMFd2)2()3(21.5)(2)(1.5)2,()(2221ppippppiyxdryxyxFMFd24中点画圆算法voidMidPoint_Circle(intx0,inty0,intr,intcolor){intx=0;inty=r;intd=1-r;//是d=1.25–r取整后的结果Cirpot(x0,y0,x,y,color);while(xy){if(d0)d+=2*x+3;else{d+=2(x-y)+5;y--;