第四讲二维图元生成算法 4.1二维线画图元的生成 4,2二维填充图元的生成 4.3反混淆算法 所谓图元的生成,是指完成图元的参数表示形式(由图形软 件包的使用者指定)到点阵表示形式(光栅显示系统刷新时所 需的表示形式)的转换。通常也称扫描转换图元 北大计算机系多媒体与人机交互
北大计算机系多媒体与人机交互 1 第四讲 二维图元生成算法 4.1 二维线画图元的生成 4.2 二维填充图元的生成 4.3 反混淆算法 所谓 图元的生成，是指完成图元的参数表示形式 （由图形软 件包的使用者指定）到点阵表示形式（光栅显示系统刷新时所 需的表示形式）的转换。通常也称扫描转换图元
4.1二维线画图元的生成 ?扫描转换直线段 DDA算法 中点画线法 ?圆弧、椭圆弧扫描转换 中点算法 内接多边形迫近法 等面积多边形逼近法 生成圆弧的正负法 ?线画图元的属性控制 北大计算机系多媒体与人机交互 2
北大计算机系多媒体与人机交互 2 4.1 二维线画图元的生成 ？扫描转换直线段 DDA算法 中点画线法 ？圆弧、椭圆弧扫描转换 中点算法 内接多边形迫近法 等面积多边形逼近法 ？生成圆弧的正负法 ？线画图元的属性控制
图形显示的几种方式 图形显 ●裁剪图元二维 扫描 ●扫描 裁剪 转换 ●扫描 存。 设备级显示算法,考虑运算方式、时间、 次数等细节。 北大计算机系多媒体与人机交互
北大计算机系多媒体与人机交互 3 图形显示的几种方式 图形显示前需要：扫描转换+裁剪 ●裁剪---〉扫描转换：最常用，节约计算时间。 ●扫描转换---〉裁剪：算法简单； ●扫描转换到画布--〉位块拷贝：算法简单，但耗时耗内 存。常用于字符显示。 • 设备级显示算法，考虑运算方式、时间、 次数等细节
扫描转换直线段 扫描转换直线段 求与直线段充分接近的像素集 像素间均匀网格 整型坐标系 两点假设 直线段的宽度为1 直线段的斜率:m∈[1,1 北大计算机系多媒体与人机交互
北大计算机系多媒体与人机交互 4 扫描转换直线段 • 扫描转换直线段 – 求与直线段充分接近的像素集 • 两点假设 – 直线段的宽度为1 – 直线段的斜率: m[−1,1] 像素间均匀网格 整型坐标系
扫描转换直线段 DDA( digital differential analyzer)算法 条件: 待扫描转换的直线段:P0(x0,y0)B(x,y) 斜率:m=y/△x 1-x0,△y=y1-y0 直线方程:y=mx+B 直接求交算法: 划分区间x0,x1:x,x2…,xn,其中x+1=x1+1 计算纵坐标:y=m·x1+B 取整:{(x,y)}→(x,y,)} yr=round (i)=(int (y,+0.5) 北大计算机系多媒体与人机交互
北大计算机系多媒体与人机交互 5 扫描转换直线段 • DDA（ digital differential analyzer）算法 – 条件： • 待扫描转换的直线段： • 斜率： • 直线方程： – 直接求交算法： • 划分区间[x0,x1]: • 计算纵坐标： • 取整： ( 0, 0) ( 1, 1) 0 1 P x y P x y x = x1− x0,y = y1− y0 m = y / x y = m• x + B x0 , x1 , , xn ,其中xi+1 = xi +1 yi = m• xi + B n i i i x y 0 {( , )} = n i i r i x y , 0 {( , )} = ( ) (int)( 0.5) yi,r = round yi = yi +
扫描转换直线段 y X0=x ·复杂度:乘法+加法+取整 DDA算法(增量算法) mox,+B (x+1)+B =m·x1+B+m=y2+m (xj+1, round (i + m)) 复杂度:加法+取整 程序:见45页 北大计算机系多媒体与 (x, round o) (x+1,y2+m)
北大计算机系多媒体与人机交互 6 扫描转换直线段 • 复杂度：乘法+加法+取整 – DDA算法（增量算法） • 复杂度：加法+取整 • 程序：见45页 m x B m y m y m x B m x B i i i i i = • + + = + +1 = • +1 + = • ( +1) +
扫描转换直线段 中点算法 目标:消除DDA算法中的浮点运算(浮点数取整 运算,不利于硬件实现;DDA算法,效率低) 条件: 同DDA算法 斜率:m∈[0,1] 直线段的隐式方程((yoyl)两端点) F(X,y)=ax+by+c=0 式中ay0-y1,b=x1-x0,c=X0Y1X1Y0 北大计算机系多媒体与人机交互
北大计算机系多媒体与人机交互 7 扫描转换直线段 • 中点算法 – 目标：消除DDA算法中的浮点运算（浮点数取整 运算，不利于硬件实现； DDA算法，效率低） – 条件： • 同DDA算法 • 斜 率： – 直线段的隐式方程（(x0,y0)(x1,y1)两端点） F(x,y)=ax+by+c=0 式中 a=y0-y1,b=x1-x0,c=X0Y1-X1Y0 m[0,1]
扫描转换直线段 直线的正负划分性 F(x,y=0 F(x,y)>0 F(x,Y0 直线下方的点F(X,Y)<0 北大计算机系多媒体与人机交互
北大计算机系多媒体与人机交互 8 扫描转换直线段 – 直线的正负划分性 直线上方点：F(X，Y)＞0 直线下方的点F(X，Y)＜0
扫描转换直线段 题:判断距直线最近的下一个象素点 构造判别式:d=F(M=F(Xp+1,Yp+0.5) 由d>0,<0可判定下一个象素, x=x;x=x;+1 NEPa -(x1+1,y+ y1) 北大计算机系多媒体与人机交互
北大计算机系多媒体与人机交互 9 扫描转换直线段 • 问题：判断距直线最近的下一个象素点 构造判别式：d=F(M)=F(Xp+1,Yp+0.5) 由d＞0，＜0可判定下一个象素， P P2 P1
扫描转换直线段 要判定再下一个象素,分两种情形考虑 1)若d>0,取正右方象素P1,再下一个象素判定, 由:dl=F(Xp+2,Yp+0.5)=a(Xp+2)+b(Yp+0.5)+c=d+a, d的增量是a 2)若d<0,取右上方象素P2,再下一个象素, H: d2=F(Xp+2, Yp+1.5)=d+a+b d的增量为a+b x=万2x=+ NEP2 (x,,)P 北大计算机系多媒体与人机交互
北大计算机系多媒体与人机交互 10 • 要判定再下一个象素，分两种情形考虑： 1）若d≥0，取正右方象素P1，再下一个象素判定， 由：d1=F(Xp+2,Yp+0.5)=a(Xp+2)+b(Yp+0.5)+c = d+a， d的增量是a 2）若d＜0，取右上方象素P2，再下一个象素， 由：d2=F(Xp+2,Yp+1.5)=d+a+b d的增量为a+b P2 P P1 扫描转换直线段
