计算机图形学第三、四、五章1113new.ppt

计算机图形学第三、四、五章1113new.ppt1二维图元生成算法第三章第三章二维线画图元的生成二维线画图元的生成第四章第四章二维填充图元的生成二维填充图元的生成第五章第五章反混淆算法反混淆算法所谓图元的生成,是指完成图元的参数表示形式所谓图元的生成,是指完成图元的参数表示形式(由图形软件包的使用者指定)到点阵表示形式(由图形软件包的使用者指定)到点阵表示形式(光栅显示系统刷新时所需的表示形式)的转换。(光栅显示系统刷新时所需的表示形式)的转换。通常也称扫描转换图元。通常也称扫描转换图元。 2第三章第三章二维线画图元的生成二维线画图元的生成 扫描转换直线段 DDA 算法 中点画线法 圆弧、椭圆弧扫描转换 中点算法 内接多边形迫近法 等面积多边形逼近法 生成圆弧的正负法 线画图元的属性控制 3图形显示的几种方式图形显示前需要:扫描转换+裁剪●裁剪--- 〉扫描转换:最常用,节约计算时间。●扫描转换--- 〉裁剪:算法简单; ●扫描转换到画布--〉位块拷贝:算法简单,但耗时耗内存。常用于字符显示。设备级显示算法,考虑运算方式、时间、次数等细节。 4扫描转换直线段?扫描转换直线段?求与直线段充分接近的像素集?两点假设?直线段的宽度为 1 ?直线段的斜率: ]1,1[??m 像素间均匀网格整型坐标系 5扫描转换直线段? DDA ( digital differential analyzer )算法?条件: ?待扫描转换的直线段: ?斜率: ?直线方程: ?直接求交算法: ?划分区间[x0,x1]: ?计算纵坐标: ?取整: )1,1()0,0( 1 0yxPyxP01,01yyyxxx?????? xym???/Bxmy???1,,,, 1 10???iinxxxxx其中?Bxmy ii??? niiiyx 0 )}, {( ? niriiyx 0, )}, {( ?) (int)( )( ,??? iiriyy round y 6 扫描转换直线段?复杂度:乘法+加法+取整? DDA 算法(增量算法) ?复杂度:加法+取整?程序:见 45 页 mymBxm BxmBxmy ii iii???????????????)1( 11? Y=+1, 起点 p0(x0,y0)=(0,1), 终点 p1()=(5,3) X0=0,y0=1 X1=1, y ’ 1=, y1=1 X2=2, y ’ 2=, y2=2 X3=3, y ’ 3=, y3=2 X4=4, y ’ 4=, y4=3 X5=5, y ’ 5=3, y5=3 78扫描转换直线段?中点算法?目标:消除 DDA 算法中的浮点运算(浮点数取整运算,不利于硬件实现; DDA 算法,效率低) ?条件: ?同DDA 算法?斜率: ?直线段的隐式方程( (x0,y0)(x1,y1) 两端点) F(x,y)=ax+by+c=0 式中 a=y0-y1,b=x1-x0,c=X0Y1-X1Y0 ]1,0[?m9扫描转换直线段?直线的正负划分性直线上方点: F(X , Y) >0 直线下方的点 F(X , Y) <0 10扫描转换直线段?问题:判断距直线最近的下一个象素点构造判别式: d=F(M)=F(Xp+1,Yp+) 由d> =0 ,< 0可判定下一个象素, d>0 , y i+1 =y i,右方的像素 d< = 0, y i+1 =y i +1 ,右上方的像素 P P2 P1