计算机图形学课件第3章二维图元生成技术.ppt

《计算机图形学课件第3章二维图元生成技术.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1所谓图元的生成，是指完成图元的参数表示形式(由图形软件包的使用者指定)到点阵表示形式(光栅显示系统刷新时所需的表示形式)的转换。通常也称扫描转换图元。第3章二维图元生成技术2象素线圆3简单的二维图形显示流程图图形显示前需要：扫描转换+裁剪●裁剪---〉扫描转换：最常用，节约计算时间。●扫描转换---〉裁剪：算法简单；●扫描转换到画布--〉位块拷贝：算法简单，但耗时耗内存。常用于字符显示。4求与直线段充分接近的像素集3.1直线的扫描转换算法像素间均匀网格整型坐标系5直线方程6让x坐标从x0变化到x1,每一

2、步递增1，这样可以保证x坐标落在对应的栅格上，进而计算对应的y坐标，并舍入取整。7voidDirectLine(intx0,inty0,intx1,inty1,intcolor){intx；floatdx,dy,y,k；dx=x1-x0；dy=y1-y0；k=dy/dx,；y=y0；for(x=x0；x

3、画线法Bresenham算法。10假定直线的起点、终点分别为：（x0,y0),(x1,y1)，且都为整数。(digitaldifferentialanalyzer)3.1.1DDA算法11计算yi+1=kxi+1+b=kxi+b+kx=yi+kx当x=1;yi+1=yi+k即：当x每递增1，y递增k(即直线斜率)；注意上述分析的算法仅适用于k≤1的情形。在这种情况下，x每增加1,y最多增加1。当k1时，必须把x，y地位互换1213数值微分(DDA)法DDA算法就是一个增量算法。增量算法：在

4、一个迭代算法中，如果每一步的x、y值是用前一步的值加上一个增量来获得，则称为增量算法。14数值微分(DDA)法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;xx1,x++)drawpixel(x,int(y+0.5),color);y=y+k;15数值微分(DDA)法缺点：在此算法中，y、k必须是float，且每一步都必须对y进行舍

5、入取整，不利于硬件实现。16DDA算法(增量算法)复杂度：加法+取整17目标：消除DDA算法中的浮点运算浮点数取整运算，不利于硬件实现；DDA算法，效率低条件：同DDA算法斜率：直线段的隐式方程((x0,y0)(x1,y1)两端点,其中x1≧x0)F(x,y)=ax+by+c=0式中a=y0-y1,b=x1-x0,c=x0y1-x1y03.2.2中点算法18直线的正负划分性直线上方的点：F(x,y)＞0直线下方的点：F(x,y)＜019PP2P1判断距直线最近的下一个象素点构造判别式：d=F(M)=F(x

6、p+1,yp+0.5)由d＞0，＜0可判定下一个象素问题：20PP2P1要判定下一个象素，分两种情形考虑：1)若d≥0，取正右方象素P1，再对下一个象素判定，由：d1=F(xp+2,yp+0.5)=a(xp+2)+b(yp+0.5)+c=d+a，d的增量是a2)若d＜0，取右上方象素P2，再对下一个象素判定，由：d2=F(xp+2,yp+1.5)=d+a+bd的增量为a+b21d的初始值d0=F(x0+1,y0+0.5)=F(x0,y0)+a+0.5b因(X0,Y0)在直线上，F(x0,y0)=0,所以，

7、d0=a+0.5bd的增量都是整数，只有初始值包含小数，可以用2d代替d,2a改写成a+a。算法中只有整数变量，不含乘除法，可用硬件实现。22voidMidpointline(x0,y0,x1,y1,color)intx0,y0,x1,y1,color;{inta,b,d1,d2,d,x,y;a=y0-y1;b=x1-x0;d=a+a+b;d1=a+a;d2=(a+b)+(a+b);x=x0;y=y0;PutPixel(x,y,color);while(x

8、2;}else{x++;d+=d1;}PutPixel(x,y,color);}}程序：演示23中点画线法原理：假定直线斜率0P2离直线更近更近->取P2。M在Q的上方->P1离直线更近更近->取P1M与Q重合，P1、P2任取一点