212中点画线法 画直线段的过程中,当前象素点为(X,y),一个象素点有两种可选择点p1(x+1,y)或p2(x+1,y+1)。若 M=(x+1,y+0.5),为p与p2之中点,Q为理想直线与x=xp+1垂线的交点。当M在Q的下方,则P2应为下 个象素点:M在Q的上方,应取P1为下一点。就是中点画线法的基本原理 P2 P 图212中点画线法每步迭代涉及的象素和中点示意图 下面讨论中点画线法的实现。令直线段L(p(xyo),p(X1,y),其方程式F(x,y)=ax+by+c=0。其中 a=yoy,b=X-X,c=xy-Xy;点与L的关系:on:F(xy)=0;up:F(x,y)>0;down:F(x,y)<0:因此,欲判断 中M在Q点的上方还是下方,只要把M代入F(X,y),并判断它的符号。构造判别式 d=F(M)=F(x+1,y+0.5)=a(X+1)+by+0.5)+c 当d<0,M在L(Q点)下方,取P2为下一个象素 当d>0,M在L(Q点)上方,取P为下一个象素 当d=0,选P1或P2均可,约定取P1为下一个象素 注意到d是xpyp的线性函数,可采用增量计算,提高运算效率, 若当前象素处于￠≥0情况,则取正右方象素P1(X+1,yp),要判下一个象素位置,应计算d=F(x+2 y+0.5)=a(x+2)+b(y+0.5)=d+a:增量为a 若d<0时,则取右上方象素P2(x+1,yp+1)。要判断再下一象素,则要计算 d=F(x+2,y+15)=a(X+2)+by+15)+c=d+a+b;增量为a+b 画线从(X,y)开始,d的初值d=F(x+1,y+0.5)=F(X,y)+a+0.5b因F(x,yo)=0,则d=a+0.5b 由于我们使用的只是d的符号,而且d的增量都是整数,只是初始值包含小数。因此,我们可以用2d 代替d来摆脱小数,写出仅包含整数运算的算法。 中点画线算法程序 void Midpoint Line(int Xo, int yo, int XI, int yi, int color) i int a, b, dL,d2, d, x,y, a=yo-y1, b=X -Xo, d=2*a+b: d=2*a,d=2*(a+b) X-Xo, y=yo drawpixel(x, y, color) if(d<0)(X++,y++,d+=da;} else X++, d+di; 1 0 drawpixel (x, y, color) 1/* while */ 图2.1.3用中点画线法对连接两点的直线进行光栅化 3/mid Point Line*/ 举例用中点画线方法扫描转换连接两点P0(0,0)和P1(52)的直线段 a=y0y1=2;b=x1-X0=5;d0=2a+b=1;d1=2*a=4d2=2a+b)=6 xy d 00 10-3 31-1 425 52 问题1:若上述算法往下取二步(Δj=2),则算法和象素的取法将变成怎样? 213 Bresenham算法 Bresenham算法是计算机图形学领域使用最广泛的直线扫描转换算法。该方法类似于中点法,由误差项 符号决定下一个象素取右边点还是右上点 计算机图形学第二章第19页共27页计算机图形学 第二章 第 19 页 共 27 页 2.1.2 中点画线法 画直线段的过程中，当前象素点为(xp, yp)，一个象素点有两种可选择点 p1(xp+1, yp)或 p2(xp+1, yp+1)。若 M=(xp+1, yp+0.5)，为 p1与 p2之中点，Q 为理想直线与 x=xp+1 垂线的交点。当 M 在 Q 的下方，则 P2 应为下 一个象素点；M 在 Q 的上方，应取 P1 为下一点。就是中点画线法的基本原理。 图 2.1.2 中点画线法每步迭代涉及的象素和中点示意图 下面讨论中点画线法的实现。令直线段 L(p0(x0,y0), p1(x1, y1)), 其方程式 F(x, y)=ax+by+c=0。其中， a=y0-y1, b=x1-x0, c=x0y1-x1y0; 点与 L 的关系：on: F(x,y)=0; up: F(x, y)>0; down: F(x, y)<0; 因此，欲判断 中 M 在 Q 点的上方还是下方，只要把 M 代入 F（x，y），并判断它的符号。构造判别式: d=F(M)=F(xp+1, yp+0.5)=a(xp+1)+b(yp+0.5)+c 当 d<0，M 在 L(Q 点)下方，取 P2为下一个象素； 当 d>0，M 在 L(Q 点)上方，取 P1为下一个象素； 当 d=0，选 P1或 P2均可，约定取 P1为下一个象素； 注意到 d 是 xp, yp的线性函数，可采用增量计算，提高运算效率。 若当前象素处于 d 0 情况，则取正右方象素 P1（xp+1, yp）,要判下一个象素位置，应计算 d1=F(xp+2, yp+0.5)=a(xp+2)+b(yp+0.5)=d+a； 增量为 a 若 d<0 时，则取右上方象素 P2（xp+1, yp+1）。要判断再下一象素，则要计算 d2= F(xp+2, yp+1.5)=a(xp+2)+b(yp+1.5)+c=d+a+b ；增量为 a＋b 画线从(x0, y0)开始，d 的初值 d0=F(x0+1, y0+0.5)=F(x0, y0)+a+0.5b 因 F(x0, y0)=0，则 d0=a+0.5b。 由于我们使用的只是 d 的符号，而且 d 的增量都是整数，只是初始值包含小数。因此，我们可以用 2d 代替 d 来摆脱小数，写出仅包含整数运算的算法。 中点画线算法程序 void Midpoint Line (int x0,int y0,int x1, int y1,int color) { int a, b, d1, d2, d, x, y; a=y0-y1, b=x1-x0, d=2*a+b; d1=2*a, d2=2* (a+b); x=x0, y=y0; drawpixel(x, y, color); while (x<x1) { if (d<0) {x++, y++, d+=d2; } else {x++, d+=d1;} drawpixel (x, y, color); } /* while */ } /* mid PointLine */ 举例 用中点画线方法扫描转换连接两点 P0（0,0）和 P1（5,2）的直线段。 a=y0-y1=-2; b=x1-x0=5; d0=2*a+b=1;d1=2*a=-4;d2=2*(a+b)=6 , x y d 0 0 1 1 0 -3 2 1 3 3 1 -1 4 2 5 5 2 15 问题 1：若上述算法往下取二步( i=2)，则算法和象素的取法将变成怎样？ 2.1.3 Bresenham 算法 Bresenham 算法是计算机图形学领域使用最广泛的直线扫描转换算法。该方法类似于中点法，由误差项 符号决定下一个象素取右边点还是右上点。 图 2.1.3 用中点画线法对连接两点的直线进行光栅化