扫描转换直线段 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,Y<0 直线上方点:F(X,Y)>0 直线下方的点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 扫描转换直线段