第四章二维线画图元和属性课件

-2024/7/171内容内容n 直线的扫描转换算法直线的扫描转换算法n 圆的扫描转换算法圆的扫描转换算法n 属性控制属性控制n 字符的生成字符的生成-二维线画图元及属性二维线画图元及属性2基本概念基本概念n图形的扫描转换（光栅化）n确定最佳逼近图形的像素集合，并用指定的颜色和灰度设置象素的过程。n指将图元的几何定义转化为像素表示。n图形光栅化的步骤n确定有关像素n用图形的颜色或其它属性，对像素进行写操作。-二维线画图元及属性二维线画图元及属性3基本概念基本概念n一般情况下，图形在光栅化之前，需要确定该图形的哪些部分在窗口内，哪些在窗口外，即裁剪。只将裁减窗口内的图形进行光栅化，并最终显示在屏幕上。n图形显示前需要：扫描转换+裁剪n裁剪扫描转换：最常用，节约计算时间。n扫描转换裁剪：算法简单；-二维线画图元及属性二维线画图元及属性4基本概念基本概念MultiGen 模型-二维线画图元及属性二维线画图元及属性5直线的扫描转换算法直线的扫描转换算法n直线的扫描转换n确定最佳逼近于该直线的一组象素，并且按扫描线顺序，对这些象素进行写操作。n三个常用算法n数值微分法（DDA）n中点画线法nBresenham算法。-二维线画图元及属性二维线画图元及属性6直线的扫描转换算法直线的扫描转换算法n画一条从(x1,y1)到(x2,y2)的直线，实质上是一个发现最佳逼近直线的像素序列，并填入色彩数据的过程。这过程也称为直线光栅化。n连续性n粗细、亮度要均匀n像素逼近待画直线n速度-二维线画图元及属性二维线画图元及属性7直线的扫描转换算法直线的扫描转换算法n假定直线的起点、终点（x0,y0),(x1,y1)，都为整数，且直线段的斜率为 。对 的情况，转化为 的情况即可。n假定栅格的交点表示像素的位置，像素间的距离是均匀的，像素相互不重叠。x0yP0P1x0=x0 xn=x1xixi+1=xi+1yiyi+1y0y1-二维线画图元及属性二维线画图元及属性8直接计算法生成直线直接计算法生成直线n基本思想已知过端点P0(x0,y0),P1(x1,y1)的直线段L：y=kx+b直线斜率为：n这种方法直观，但效率太低，因为每一步需要一次浮点乘法和一次舍入运算。nround（y）=int（y+0.5）返回的是最接近直线的（像素）浮点数y的整数值-二维线画图元及属性二维线画图元及属性9数值微分法（）数值微分法（）n即：当x每递增1，y递增k(即直线斜率)；n注意上述分析的算法仅适用于k 1的情形。在这种情况下，x每增加1,y最多增加1。n当 k 1时，必须把x，y地位互换x0yP0P1x0=x0 xn=x1xixi+1=xi+1yiyi+1y0y1n计算计算y yi+1i+1=kx=kxi+1i+1+b+b =k =k（x xi i+x x）+b+b =kx =kxi i+b+k+b+k x x =y =yi i+k+k x x 当当 x=1;x=1;y yi+1i+1=y=yi i+k+k-二维线画图元及属性二维线画图元及属性10数值微分法（）数值微分法（）n增量算法：在一个迭代算法中，如果每一步的x、y值是用前一步的值加上一个增量来获得，则称为增量算法。nDDA算法就是一个增量算法。-二维线画图元及属性二维线画图元及属性11数值微分法（）数值微分法（）n nD D D DDADADADA算法生成直线算法生成直线算法生成直线算法生成直线void DDALine(int x0,int y0,int x1,int y1,int color)int x；float dx,dy,y,k;dx=x1-x0,dy=y1-y0;k=dy/dx,y=y0;for(x=x0;x x1,x+)Putpixel(x,int(y+0.5),color);y=y+k;-二维线画图元及属性二维线画图元及属性12数值微分法（）数值微分法（）n例：画直线段P0(0,0)-P1(5,2)x int(y+0.5)y+0.500 0100.4+0.5210.8+0.5311.2+0.5421.6+0.5522.0+0.5绘制直线的绘制直线的DDA法程序演示结果法程序演示结果-二维线画图元及属性二维线画图元及属性13数值微分法（）数值微分法（）n缺点n在此算法中，y、k一般情况下是float，且每一步都必须对y进行舍入取整，不利于硬件实现。-二维线画图元及属性二维线画图元及属性14中点画线法中点画线法n假定直线斜率0K P2离直线更近-取P2；n当M在Q的上方-P1离直线更近-取P1；n当M与Q重合，P1、P2任取一点。P=(x pyp)QP2P1Mn问题：如何判断M与Q点的关系？-二维线画图元及属性二维线画图元及属性16中点画线法中点画线法n假设直线方程为：F(x,y)=ax+by+c=0n其中a=y0-y1,b=x1-x0,c=x0y1-x1y0n判断中点M在Q点的上方还是下方，只要把M代入F（x，y），并判断它的符号即可 P=(x pyp)QP2P1M-二维线画图元及属性二维线画图元及属性17中点画线法中点画线法n构造判别式：d=F(M)=F(xp+1,yp+0.5）=a(xp+1)+b(yp+0.5)+c P=(x pyp)QP2P1Mn当d0，M在直线(Q点)上方，取右方P1；n当d=0，选P1或P2均可，约定取P1；n能否采用增量算法呢？-二维线画图元及属性二维线画图元及属性18中点画线法中点画线法n若d0，M在直线上方，取P1n此时再下一个象素的判别式为：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；n增量为a P=(x pyp)QP2P1M-二维线画图元及属性二维线画图元及属性19中点画线法中点画线法n若d0，M在直线下方，取P2n此时再下一个象素的判别式为：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；n增量为ab P=(x pyp)QP2P1M-二维线画图元及属性二维线画图元及属性20中点画线法中点画线法n画线从(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 P=(x pyp)QP2P1Mn由于只用d 的符号作判断，为了只包含整数运算,可以用2d代替d来去掉小数，提高效率。-二维线画图元及属性二维线画图元及属性21中点画线法中点画线法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;putpixel(x,y,color);while(xx1)if(d0)x+;y+;d+=d2;else x+;d+=d1;drawpixel(x,y,color);/*while*/*mid PointLine*/-二维线画图元及属性二维线画图元及属性22中点画线法中点画线法n例：用中点画线法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)=6xiyid00110-3 2 1 3 31 -142 5 5 2 0 1 2 3 4 5321-二维线画图元及属性二维线画图元及属性23BresenhamBresenham画线算法画线算法nBresenham算法是最有效的直线生成的算法之一，也是计算机图形学领域使用最广泛的直线扫描转换算法。n令 k=y/x，就0k1的情况来说明Bresenham算法。-二维线画图元及属性二维线画图元及属性24BresenhamBresenham画线算法画线算法n设图中xi列上已用（xi,yi）作为表示直线的点，又设Q点是直线上的点，显然下一个表示直线的点只能从图中的P P1 1或者P P2 2点中去选。设M为P P1 1P P2 2的中点。若Q在M M点上面则应取P P1 1点（xi+1,yi+1），否则应取P P2 2点（xi+1,yi）。x xi ix xi+1i+1y yi iy yi+1i+1P P2 2P P1 1Q QMM算法的几何意义i-二维线画图元及属性二维线画图元及属性25BresenhamBresenham画线算法画线算法n为了确定Q在M点上面或下面，令判别式：nwi=i-0.5=k(xi+1)+b-yi-0.5 n如果wi0，说明i0.5，那么下一点取P P2 2（xi+1,yi)采用增量算法，则新的判别式为：nwi+1=k(xi+1+1)+b-yi+1-0.5=k(xi+1+1)+b-yi-0.5=wi+kx xi ix xi+1i+1y yi iy yi+1i+1P P2 2P P1 1Q QMM算法的几何意义i-二维线画图元及属性二维线画图元及属性26BresenhamBresenham画线算法画线算法n如果wi 0,说明i 0.5，那么下一点取P P1 1（xi+1,yi+1)采用增量算法，则新的判别式为：nwi+1=k(xi+1+1)+b-yi+1-0.5=k(xi+1+1)+b-(yi+1)-0.5=wi+k-1n初始时，令x=x0，y=y0，则有nw0=k(x0+1)+b-y0-0.5=（kx0+b-y0）+k-0.5=k-0.5x xi ix xi+1i+1y yi iy yi+1i+1P P2 2P P1 1Q QMM算法的几何意义i-二维线画图元及属性二维线画图元及属性27圆弧的扫描转换算法圆弧的扫描转换算法n根据圆的方程：(x2+y2)=R2用扫描线方式生成圆时，会出现x方向增量取1，则y=(R2-x2)1/2,这种方法，既增加了运算复杂性，又会产生点集疏密不均的现象：当x=0时，圆周上的切线斜率为零；当x接近R时，圆周上的切线斜率趋向无穷大，因此出现靠近y轴处点集较密集、平坦，但靠近x轴处间隔较大、陡直。yx-二维线画图元及属性二维线画图元及属性28圆弧的扫描转换算法圆弧的扫描转换算法n圆的八对称性n由圆的对称性，已知圆上一点(x,y)，可以得到其关于四条对称轴的七个对称点。n因此，只要扫描转换八分之一圆弧，就可以求出整个圆弧的象素集。-二维线画图元及属性二维线画图元及属性29圆弧的扫描转换圆弧的扫描转换-Bresenham-Bresenham法法n算法思想n每一步都选择一个距离理想圆周最近的点P(xi，yi)，使其误差项在每一步达到最小。n|D|D（P Pi i）|=|x|=|xi i2 2+y+yi i2 2-R-R2 2|n假设是第一象限1/8圆弧上已选中的一个像素点，根据圆弧走向，下一个像素点应从Hi或Li中选择。n引入判别式：ni=|D（i）|D（i）|ni，则选择ini，则选择iPHiLi应取应取H Hi i还是取还是取L Li i?yiyi-1xiXi+1-二维线画图元及属性二维线画图元及属性30圆弧的扫描转换圆弧的扫描转换-Bresenham-Bresenham法法n简化i的运算n i和i均在圆内（选取i）nD（i），D（i）n i在圆上，i在圆内（选取i）nD（i），D（i）n i在圆外，i在圆内nD（i），D（i）n i在圆外，i在圆上（选取i）nD（i），D（i）n i和i均在圆外（选取i）nD（i），D（i）n简化结果：i=D（i）D（i）PHiLi应取应取H Hi i还是取还是取L Li i?yiyi-1xiXi+1-二维线画图元及属性二维线画图元及属性31圆弧的扫描转换圆弧的扫描转换-Bresenham-Bresenham法法n进一步简化i的运算 i i=D=D（i i）D D（i i）=(x =(xi i+1)+1)2 2+y+yi i2 2-R-R2 2+(x+(xi i+1)+1)2 2+(y+(yi i-1)-1)2 2-R-R2 2 则则i i=(x=(xi i +1)+1)2 2+y+yi i 2 2-R-R2 2+(x+(xi i +1)+1)2 2+(y+(yi i -1)-1)2 2-R-R2 2n如果如果 i i，选取，选取i i，则，则x xi i x xi i+1+1，y yi i y yi i，得得ni i=i in如果如果 i i，选取，选取i i，则，则x xi i x xi i+1+1，y yi i y yi i，得得ni i=i i（）n对于，对于，则初值为，则初值为nPHiLiyiyi-1xiXi+1-二维线画图元及属性二维线画图元及属性32圆弧的扫描转换圆弧的扫描转换-中点法中点法n圆方程：F(x,y)=x2+y2-R2=0nD=F(M)=(xp+1)2+(yp-0.5)2-R2 0 取p2n再下一点的判别式为：nD=(xp+2)2+(yp-1.5)2-R2=D+2xp-2yp+5n起点（0，R）nD0=12+(R-0.5)2-R2=1.25-R演示：中点画圆算法演示：中点画圆算法 -二维线画图元及属性二维线画图元及属性33属性控制属性控制n直线的属性n线型、线宽、线色n线型控制n一般用一个位屏蔽器来实现-二维线画图元及属性二维线画图元及属性34属性控制属性控制n线宽处理n用像素复制方法产生宽图元n移动刷子产生宽图元n用填充图形表示宽图元水平刷水平刷水平刷水平刷垂直刷垂直刷垂直刷垂直刷方刷方刷方刷方刷-二维线画图元及属性二维线画图元及属性35字符生成字符生成n点阵字符:每个字符由一个位图表示n适合光栅显示器n矢量字符:记录字符的笔画信息n适合笔式绘图仪n特点：n点阵字符：存储量大，易于显示n矢量字符：存储量小，美观，变换方便，需要光栅化后才能显示。-二维线画图元及属性二维线画图元及属性36字符属性字符属性-二维线画图元及属性二维线画图元及属性37