数值微分(DDA)法 缺点:在此算法中,y、k必须是foat,且每 步都必须对y进行舍入取整,不利于硬件实 现。 2021/1/21 浙江大学计算机图形学
2021/1/21 浙江大学计算机图形学 11 数值微分(DDA)法 ◼ 缺点： 在此算法中，y、k必须是float，且每 一步都必须对y进行舍入取整，不利于硬件实 现
中点画线法 原理: 假定直线斜率0<K<1,且已 P2 确定点亮象素点P(X,,Y。) 则下一个与直线最接近的像 素只能是P1点或P2点。设M 为中点,Q为交点 P=(XpL yp, )IP1 现需确定下一个点亮的象素。 2021/1/21 浙江大学计算机图形学 12
2021/1/21 浙江大学计算机图形学 12 中点画线法 ◼ 原理： 假定直线斜率0<K<1，且已 确定点亮象素点P（Xp ,Yp ）, 则下一个与直线最接近的像 素只能是P1点或P2点。设M 为中点，Q为交点 现需确定下一个点亮的象素。 P=(xp,yp) Q P2 P1
中点画线法 n当M在Q的下方>P2离直线更近更近>取P2。 aM在Q的上方->P1离直线更近更近→>取P1 aM与Q重合,P1、P2任取一点 P2 P=(xpy yp)Ipl 问题:如何判断M与Q点的关系? 2021/1/21 浙江大学计算机图形学 13
2021/1/21 浙江大学计算机图形学 13 中点画线法 ◼ 当M在Q的下方-> P2离直线更近更近->取P2 。 ◼ M在Q的上方-> P1离直线更近更近->取P1 ◼ M与Q重合， P1、P2任取一点。 ◼ 问题：如何判断M与Q点的关系？ P=(xp,yp) Q P2 P1
中点画线法 假设直线方程为:ax+by+C=0 其中a=yy1,b=Xx,C=XyXy0 由常识知: F(xy)=0点在直线上面 F(x,y)>0点在直线上方 F(x,y)<0点在直线下方 Ⅹpyp)|P1 欲判断中点M点是在Q点上方还是在Q点下 方,只需把M代入x并检查它的符号。 2021/1/21 浙江大学计算机图形学 14
2021/1/21 浙江大学计算机图形学 14 中点画线法 假设直线方程为：ax+by+c=0 其中a=y0 -y1 , b=x1 -x0 , c=x0y1 -x1y0 由常识知： ∴欲判断中点M点是在Q点上方还是在Q点下 方，只需把M代入F(x,y),并检查它的符号。 ( ) ( ) ( ) = 点在直线下方 点在直线上方 点在直线上面 , 0 , 0 , 0 F x y F x y F x y P=(xp,yp) Q P2 P1
中点画线法 构造判别式: d=F(M)=F(x+1y+0 P2 5 =a(×+1)+b(y+0.5)c 当d<0,M在直线(Q点)下P(y 方,取右上方P; 当d>0,M在直线(Q点)上 方,取右方P1; 当d=0,选P或P2均可, 约定取P1; 能否采用增量算法呢? 2021/1/21 浙江大学计算机图形学 15
2021/1/21 浙江大学计算机图形学 15 中点画线法 构造判别式： d=F(M)=F(x p+1,y p+0. 5) =a(x p+1)+b(y p+0.5)+c 当d<0 ， M在直线(Q 点 ) 下 方，取右上方 P 2 ； 当d>0 ， M在直线(Q 点 ) 上 方，取右方 P 1 ； 当d=0，选 P 1 或 P 2均可， 约定取 P 1 ； 能否采用增量算法呢？ P=( x p , y p ) Q P2 P1