《计算机图形学教程一些算法》由会员分享，可在线阅读，更多相关《计算机图形学教程一些算法（25页珍藏版）》请在金锄头文库上搜索。
1、第四章 基本图形生成算法,4.1 直线段的扫描转换算法 4.2 圆弧的扫描转换算法 4.3 多边形的扫描转换与区域填充 4.6 裁剪 4.7 反走样,简单的二维图形显示流程图,扫描转换,简单的二维图形显示流程图,图形扫描转换：在光栅显示器等数字设备上 确定一个最佳逼近于图形的象素集的过程。,4.1 直线段的扫描转换算法,直线的扫描转换: 确定最佳逼近于该直线的一组象素，并且按扫描线顺序，对这些象素进行写操作。 三个常用算法： 4.1.1数值微分法（DDA） 4.1.2中点画线法 4.1.3Bresenham算法。,4.1.1 数值微分(DDA)法,基本思想 已知过端点P0 (x0, y0),
2、P1(x1, y1)的直线段L y=kx+b 直线斜率为 从x的左端点x0开始，向x右端点步进。步长=1(1个象素)，计算相应的y坐标y=kx+B；取象素点 (x, round(y)作为当前点的坐标。,计算yi+1= kxi+1+B = k1 xi+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算法核心代码,for (x=xa;xSetPixel (x,int(y+0.5),c); y=y+k; ,直线DD
3、A算法的VC代码,void CMyView: OnDDALine() CDC* pDC=GetDC(); /获得设备指针 int xa=100,ya=300,xb=300,yb=200,c=RGB(255,0,0); int x,y; float dx, dy, k; dx=(float)(xb-xa), dy=(float)(yb-ya); k=dy/dx, y=ya;,直线DDA算法VC代码,if (abs(k)SetPixel (x,int(y+0.5),c); y=y+k; if(abs(k)=1) /当k1的情形 for (y=ya; ySetPixel (int(x+0.5),y,
4、c); x=x+1/k; ReleaseDC(pDC); ,例：画直线段P 0(0,0)-P1(5,2) x int(y+0.5) y+0.5 0 0 0 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,缺点： 在此算法中，y、k必须是float，且每一步都必须对y进行舍入取整，不利于硬件实现。,4.1.2 中点画线法,基本思想 当前象素点为(xp, yp) 。下一个象素点为P1或P2。 设M=(xp+1, yp+0.5)，为p1与p2 之中点，Q为理想直线与x=xp+1 垂线的交点。将Q与M的y坐标进 行比较。 当M在Q
5、的下方，则P2 应为 下一个象素点； M在Q的上方，应取P1为下一点。,假设直线方程为：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点)上方，取右方P1； 当d=0，选P1或P2均可，约定取P1； 能否采用增量算法呢？,若d0 - M在直线上方 - 取P1; 此时再下一个象素的判别式为 d1=F(xp+2, yp+0.5)=a(xp+2)+b(y
6、p+0.5)+c = a(xp +1)+b(yp +0.5)+c +a =d+a； 增量为a,若d 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 ； 增量为ab,画线从(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
7、 MidpointLine (int x0,int y0,int x1, int y1, COLORREF 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; pDC-SetPixel(x, y, color); while (xSetPixel (x, y, color); /* while */ /* mid PointLine */,例：用中点画线法P0（0,0) P1（5,2) a=y0-y1=-2 b=x1-x0=5 d0=2a+b=1 d1=2a=
8、-4 d2=2(a+b)=6 i xi yi d 1 0 0 1 2 1 0 -3 3 2 1 3 4 3 1 -1 5 4 2 5,4.1.3 Bresenham算法,基本思想 过各行各列象素中心构造一组虚拟网格线。按直线从起点到终点的顺序计算直线与各垂直网格线的交点，然后根据误差项的符号确定该列象素中与此交点最近的象素。,设直线方程为： ， 其中k=dy/dx。 因为直线的起始点在象素中心，所以误差项d的初值d00。 X下标每增加1，d的值相应递增直线的斜率值k，即ddk。一旦d1，就把它减去1，这样保证d在0、1之间。 当d0.5时，最接近于当前象素的右上方象素(xi1，yi1)而当d0
9、.5时，更接近于右方象素（xi1，yi）。,为方便计算，令ed-0.5， e的初值为-0.5，增量为k。 当e0时，取当前象素（xi，yi）右上方象素（xi1，yi1）； 而当e0时，更接近于右方象素（xi1，yi）。,void Bresenhamline (int x0,int y0,int x1, int y1,COLORREF color) int x, y, dx, dy; double k, e; dx = x1-x0, dy = y1- y0, k=dy/dx; e=-0.5, x=x0, y=y0; for (i=0; idx; i+) pDC-SetPixel (x, y, color); x=x+1，e=e+k; if (e0) y+, e=e-1; ,可以改用整数以避免除法。由于算法中只用到误差项的符号，因此可作如下替换： 例：Line: P0(0, 0), P1(5,2) k=dy/dx=0.4 x y e 0 0 -0.5 1 0 -0.1 2 1 -0.7 3 1 -0.3 4 2 -0.9 5 2 -0.5,
