ch3基本图形的生成与计算.ppt

直线和直线图形 1）绘制直线的要求 1）绘制直线的要求 实际绘制 直线的笛卡儿斜率截距方程 生成直线的常用算法 1、逐点比较法 2、 DDA－数值微分法 3、中点画线法 4、 Bresenham画线算法 1. 逐点比较法 绘制思路 计算偏差（确定X和Y的最大走向） 设 ?=tg?-tg? 偏差计算 绘制结果 偏差递推公式 偏差递推公式 终点判别 绘制直线 2. DDA－数值微分法(Digital Differential Analyzer) 数值微分法（ＤＤＡ） 假定直线的起点、终点分别为：（x0,y0), (x1,y1)，且都为整数。　 数值微分(DDA)法 基本思想 已知过端点P0 (x0, y0), P1(x1, y1)的直线段L y=kx+b 直线斜率为 数值微分(DDA)法 计算yi+1= kxi+1+b = kxi+b+k?x = yi+k?x 当?x =1; yi+1 = yi+k 即：当x每递增1，y递增k(即直线斜率)； 注意上述分析的算法仅适用于?k? ≤1的情形。在这种情况下，x每增加1,y最多增加1。 当 ?k? ?1时，必须把x，y地位互换 数值微分(DDA)法 增量算法：在一个迭代算法中，如果每一步的x、y值是用前一步的值加上一个增量来获得，则称为增量算法。 DDA算法就是一个增量算法。 数值微分(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; x?x1, x++) ? drawpixel (x, int(y+0.5), color); y=y+k; ? ? 数值微分(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 数值微分(DDA)法 缺点： 在此算法中，y、k必须是float，且每一步都必须对y进行舍入取整，不利于硬件实现。 中点画线法 原理： 中点画线法 当M在Q的下方?P2离直线更近?取P2 。 当M在Q的上方?P1离直线更近?取P1 。 M与Q重合， P1、P2任取一点。 问题：如何判断M与Q点的关系？ 中点画线法 假设直线方程为：ax+by+c=0 其中a=y0-y1, b=x1-x0, c=x0y1-x1y0 由数学知识知： ∴欲判断M点是在Q点上方还是在Q点下方，只需把M代入F(x,y),并检查它的符号。 中点画线法 构造判别式：d=F(M)=F(xp+1,yp+0.5) =a(xp+1)+b(yp+0.5)+c 当d0，M在直线(Q点)下方，取右上方P2； 当d0，M在直线(Q点)上方，取右方P1； 当d=0，选P1或P2均可，约定取P1； 能否采用增量算法呢？ 中点画线法 若d?0 －－M在直线上方 －－取P1; 此时再下一个象素的判别式为 d1=F(xp+2, yp+0.5)=a(xp+2)+b(yp+0.5)+c = a(xp +1)+b(yp +0.5)+c +a =d+a； 增量为a 中点画线法 若d0 －－M在直线下方 －－取P2; 此时再下一个象素的判别式为 d2= F(xp+2, yp+1.5)=a(xp+2)+b(yp+1.5)+c = a(xp +1)+b(yp +0.5)+c +a +b =d+a+b ； 增量为a＋b 中点画线法 画线从(x0, y0)开始，d的初值 d0=F(x0+1, y0+0.5)= a(x0 +1)+b(y0 +0.5)+c = F(x0, y0)+a+0.5b = a+0.5b 由于只用d 的符号作判断，为了只包含整数运算, 可以用2d代替d来摆脱小数，提高效率。 中点画线法 void Midpoint Line (int x0,int y0,int x1, int y1,int c