数值微分(DDA)法 ■基本思想 已知过端点P0(xO,y0),P1(X1,y1)的直线段L y=kx+b 直线斜率为 令x=x0→>x;x=x+ stepx v=kx+b (x, round()) 这种方法直观,但效率太低,因为每一步需要一次浮点乘法 和一次舍入运算。 2021/1/21 浙江大学计算机图形学
2021/1/21 浙江大学计算机图形学 6 数值微分(DDA)法 ◼基本思想 已知过端点P0 (x0, y0), P1(x1, y1)的直线段L y=kx+b 直线斜率为 这种方法直观，但效率太低，因为每一步需要一次浮点乘法 和一次舍入运算。 1 0 1 0 x x y y k − − = ( , ( )) ; 0 1 x round y y k x b x x x x x stepx = + 令 = → = +
数值微分(DDA法 计算y1=kx1+b =kx+b+k△X =yi+kAX 当AX=1;y1=y+k 即:当x每递增1,y递增k(即直线斜率) ■注意上述分析的算法仅适用于k≤1的情形。 在这种情况下,ⅹ每增加1,y最多增加1。 n当k>1时,必须把X,y地位互换 2021/1/21 浙江大学计算机图形学 7
2021/1/21 浙江大学计算机图形学 7 数值微分(DDA)法 计算yi+1= kxi+1+b = kxi+b+kx = yi+kx 当x =1; yi+1 = yi+k ◼ 即：当x每递增1，y递增k(即直线斜率)； ◼ 注意上述分析的算法仅适用于k ≤1的情形。 在这种情况下，x每增加1,y最多增加1。 ◼ 当 k 1时，必须把x，y地位互换
数值微分(DDA)法 ■增量算法:在一个迭代算法中,如果每 一步的ⅹ、y值是用前一步的值加上一个 增量来获得,则称为增量算法。 ■DDA算法就是一个增量算法。 2021/1/21 浙江大学计算机图形学
2021/1/21 浙江大学计算机图形学 8 数值微分(DDA)法 ◼ 增量算法：在一个迭代算法中，如果每 一步的x、y值是用前一步的值加上一个 增量来获得，则称为增量算法。 ◼ DDA算法就是一个增量算法
数值微分(DDA)法 void ddaline (int xo int yo, int x,, int yu,int color) fint X: float dx, dy, y, k dx,=X-Xo, dy=y1-yoi k=dy/dx, y=yo for(X=X6;X≤X1,X++) i drawpixel ( x, int(y+0.5),color y=y+k; 2021/1/21 浙江大学计算机图形学
2021/1/21 浙江大学计算机图形学 9 数值微分(DDA)法 void DDALine(int x0 ,int y0 ,int x1 ,int y1 ,int color) int x； float dx, dy, y, k; dx, = x1 -x0 , dy=y1 -y0 ; k=dy/dx, y=y0 ; for (x=x0 ; xx1 , x++) drawpixel (x, int(y+0.5), color); y=y+k;
数值微分(DDA)法 例:画直线段PO,0)-P(5,2) nt(y+05)y+0.51ine:P0(0,0)-p1(,2) 0 0+0.5 0 0.4+0.5 0.8+0.5 12+0.5 1.6+0.5 012345 52 2.0+0.5 2021/1/21 浙江大学计算机图形学
2021/1/21 浙江大学计算机图形学 10 数值微分(DDA)法 ◼ 例：画直线段P0(0,0)--P1(5,2) x int(y+0.5) y+0.5 0 0 0+0.5 1 0 0.4+0.5 2 1 0.8+0.5 3 1 1.2+0.5 4 2 1.6+0.5 5 2 2.0+0.5 0 1 2 3 4 5 3 2 1 Line: P0(0, 0)-- P1(5, 2)