维基本图形元素生成算法

《维基本图形元素生成算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章二维基本图形元素生成算法1基本概念所谓图元的生成，是指完成图元的参数表示形式（由图形软件包的使用者指定）到点阵表示形式（光栅显示系统刷新时所需的表示形式）的转换。通常也称扫描转换图元2课程内容§3.1简单的二维图形显示流程§3.2直线段的扫描转换§3.3圆弧的扫描转换§3.4易画曲线的正负法§3.5线画图元的属性控制33.1简单的二维图形显示流程裁剪和扫描显示图元图3-1-1二维图形显示流程裁剪和扫描图形显示前需要进行扫描转换+裁剪，这一过程有三种方法：●裁剪---〉扫描转换：最常用，节约计算时间。●扫描转换---〉裁剪：算法简单；●扫描转换到画布--〉位块拷贝：算法简单，但耗时耗内

2、存。常用于字符显示。53.2直线段的扫描转换目标：求与直线段充分接近的像素集两点假设1.直线段的宽度为12.直线段的斜率:像素间均匀网格整型坐标系图3-2-16描绘线条图形的要求直线段要显得笔直线段端点位置要准确线段的亮度要均匀转换算法速度要快73.2.1DDA（digitaldifferentialanalyzer）算法条件：待扫描转换的直线段：斜率：，其中直线方程：83.2.1DDA算法直接求交算法：划分区间[x,x1]:计算纵坐标：取整：复杂度：乘法+加法+取整图3-2-293.2.1DDA算法DDA算法（增量算法）复杂度：加法+取整算法图3-2-3103.2.1DDA算法DDA算法

3、程序：voidLineDDA(intx0,inty0,intx1,inty1,intcolor)/*假定x0

4、   1.6+0.5图3-2-4123.2.1DDA算法特点1注意上述分析的算法仅适用于

5、k

6、≤1的情形。在这种情况下，x每增加1,y最多增加1。当

7、k

8、>1时，必须把x，y地位互换，y每增加1，x相应增加1/k。特点2在这个算法中，y与k必须用浮点数表示，而且每一步都要对y进行四舍五入后取整。这使得它不利于硬件实现。133.2.1DDA算法改进算法（增量DDA）优化点：增加斜率判断并改变循环参数143.2.1DDA算法DDA画线算法程序（改进）voidLineDDA(intx0,inty0,intx1,inty1,intcolor){intx,y；floatdx,dy,k,l,m;dx=

9、float(x1-x0);dy=float(y1-y0);k=dy/dx;if(abs(k)<1){for(x=x0;x<=x1,x++){Putpixel(x,int(y+0.5),color);y+=k;}}else{for(y=y0;y<=y1,y++){Putpixel(int(x+0.5),y,color);x+=1/k;}}?如果x0>x1怎么办？153.2.2画线中点算法目标：消除DDA算法中的浮点运算（浮点数取整运算，不利于硬件实现；DDA算法，效率低）条件：同DDA算法斜率：直线段的隐式方程（(x0,y0)(x1,y1)两端点）F(x,y)=ax+by+c=0式中a=y0

10、-y1,b=x1-x0,c=x0y1-x1y016基本原理：画直线段的过程中，当前象素点为(xp,yp)，一个象素点有两种可选择点p1(xp+1,yp)或p2(xp+1,yp+1)。若M=(xp+1,yp+0.5)为p1与p2之中点，Q为理想直线与x=xp+1垂线的交点。当M在Q的下方，则P2应为下一个象素点；M在Q的上方，应取P1为下一点。图3-2-5173.2.2画线中点算法3.2.2画线中点算法点与直线的关系：on:F(x,y)=0;up:F(x,y)>0;down:F(x,y)<0;图3-2-6直线的正负划分性183.2.2画线中点算法欲判断中M在Q点的上方还是下方，只要把M代F(

11、x,y)并判断它的符号。构造判别式:d=F(M)=F(xp+1,yp+0.5)=a(xp+1)+b(yp+0.5)+c当d<0，M在Q点下方，取P2为下一个象素；当d>0，M在Q点上方，取P1为下一个象素；当d=0，选P1或P2均可，约定取P1为下一个象素19问题：判断距直线最近的下一个象素点构造判别式：d=F(M)=F(xp+1,yp+0.5)由d＞0，d＜0可判定下一个象素，PP2P1图3-2-7203.2.2画线中