计算机图形学3-2.ppt

1、第三章 基本光栅图形的生成,3.1 直线的生成算法 3.2 圆的生成算法 3.3 区域填充算法 3.4 字符的生成,Xuhai college,假定直线斜率0K1， 且已确定当前象素点P( xi , yi）,则下一个与直线最接近的像素只能是P1点或P2点。设M为中点，Q为交点，现需确定下一个需要点亮的象素。,3.中点画线算法,3.2 线的生成算法,Xuhai college, 当M在Q的下方, P2离直线更近, 取P2 。 当M在Q的上方, P1离直线更近, 取P1 当M与Q重合，P1、P2任取一点。 问题关键：如何判断M与Q点的关系？,Xuhai college,假设直线方程为：F(x,y)

2、= ax+by+c=0 其中a=y0 - y1, b=x1-x0, c=x0y1-x1y0 该直线方程将平面分为三个区域： * 对于直线上的点，F(x,y)=0； * 对于直线上方的点，F(x,y)0； * 对于直线下方的点，F(x,y)0。,欲判断M 点是在Q点上方还是在Q点下方，只需把M代入F(x,y),并检查它的符号。,Xuhai college,构造递推式： di=F(Mi)=F(xi+1,yi+0.5) =a(xi+1)+b(yi +0.5)+c 当d0，M在直线(Q点)上方，取右方P1； 当d0，M在直线(Q点)下方，取右上方P2； 当d=0，选P1或P2均可，约定取P1； 能否采

3、用增量算法呢？,Xuhai college,假设若d0, 中间点M在直线上方, 则取P1; 那么此时再下一个象素的递推式为 di+1= F(xi+2, yi+0.5)=a(xi+2)+b(yi +0.5)+c = a(xi+1)+b(yi+0.5)+c +a =di+a； 增量为a,Xuhai college,假设若d0，中间点M在直线下方，则取P2; 那么此时再下一个象素的递推式为 di+1= F(xi+2, yi+1.5)=a(xi+2)+b(yi+1.5)+c = a(xi+1)+b(yi+0.5)+c +a +b =di+a+b ； 增量为ab,Xuhai college,画线从(x0

4、, y0)开始，d的初值 d =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来摆脱小数，提高效率。,Xuhai college,总结,Xuhai college,例：用中点画线法P0(0,0) P1(5,2) a=y0-y1=-2 b=x1-x0=5 d0 =2(a+0.5b) d0=2a+b=1 d1=2a=-4 d2=2(a+b)=6 若d0，增量为2a d3=2a=-4 d4= 2(a+b)=6 若d0，增量为2(ab) xi yi d 0

5、 0 1 1 0 -3 (1 - 4) 2 1 3 (-3 +6) 3 1 -1 (3 - 4) 4 2 5 (-1 +6) 5 2,Xuhai college,void MidpointLine (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; setpixel(x, y, color); while (x=x1) if (d0) x+; y+; d+=d2; else x+; d+=

6、d1; setpixel (x, y, color); /* mid PointLine */,Xuhai college,3.2.1 基础知识,给出圆心坐标(xc, yc)和半径r，逐点画出一个圆周的公式有下列两种： 直角坐标法 (xxc)2 + (yyc)2 = r2 由上式导出：,当xxc从r到r作加1递增。 但是这样求出的圆周上的点是不均匀的，所生成的圆不美观。同时计算量很大。,3.3 圆的生成算法,Xuhai college, 极坐标法 x = xc + r cos，y = yc + r sin 当从0到作递增时，由此式便可求出圆周上均匀分布的 360个点的(x, y)坐标。,利用圆

7、周坐标的对称性，此 算法还可以简化。将圆周分为8个象限，只要将第1a象限中的圆周光栅点求出，其余7部分圆周就可以通过对称法则计算出来。,缺点：三角函数和浮点运算，运算速度慢,Xuhai college,3.2.2 中点圆生成算法,若Pk0，则 yk+1取yk+1=yk， 否则yk+1取yk-1。,若当前点y坐标为yk，则下一点yk+1只能是yk或yk-1,Xuhai college,设M为P1，P2的中点，M=(xk+1,yk-0.5) 构造判别式pk,有如下结论： 当f(M) = 0 ，M在圆外，则取P2,Xuhai college,假设若pk0, 则P1 为下一个象素，那么再下一个象素的递

8、推式为：,即pk的增量为2xk+3,Xuhai college,假设若pk=0, 则P2 为下一个象素，那么再下一个象素的递推式为：,即pk的增量为2(xk-yk)+5,Xuhai college,为了避免浮点运算，取,总结,Xuhai college,中点画圆算法步骤： 1、输入圆半径r； 2、 求误差初值，p0=5/4r，画点(0, r)； 3、求下一个光栅位置，其中xi+1=xi+1，如果pi0则 yi+1=yi，否则yi+1=yi1； 3. 画点(xi+1, yi+1)； 4. 计算下一个误差，如果pi0则pi+1=pi+2xi+3，否则 pi+1=pi+2xi2yi+5； 5. 确定

9、其他七个八分圆中的对称点。 6. i=i+1，如果x=y则结束，否则返回步骤3。,Xuhai college,例：使用中点画圆算法绘制圆：半径r=10，圆心在原点。p0=1-r=-9。,Xuhai college,y=x,x,y,Xuhai college,3.2.3 圆的Bresenham算法,即:xi+1 = xi + 1 相应的yi+1则在两种可能中选择： yi+1 = yi或者yi+1 = yi1,设圆的半径为r。考虑圆心在(0, 0)，并从x=0、y=r 开始的顺时针方向的1/8圆周的生成过程。在这种情况下， x每步增加1，从x=0开始，到x=y结束。,Xuhai college,计

10、算式为 y2 = r2(xi+1)2 d1 = yi2 +(xi+1)2 r2 d2 = r2(xi+1)2+(yi1)2) 令pi=d1d2，并代入d1、d2，则有 pi = 2(xi+1)2 + yi2 + (yi1)22r2 (2.6) pi称为误差。如果pi0则yi+1=yi，否则yi+1=yi1。 pi的递归式为 pi+1 = pi + 4xi +6+2(y2i+1 yi2) 2(yi+1yi) (2.7) pi的初值由式(2.6)代入xi=0，yi=r而得 p1 = 32r (2.8),Xuhai college,总结,Xuhai college,Bresenham圆周生成算法思想

11、如下： 求误差初值，p1=32r，i=1，画点(0, r)； 求下一个光栅位置，其中xi+1=xi+1，如果pi0则 yi+1=yi，否则yi+1=yi1； 画点(xi+1, yi+1)； 计算下一个误差，如果pi0则pi+1=pi+4xi+6，否则 pi+1=pi+4(xiyi)+10； i=i+1，如果x=y则结束，否则返回步骤2。,Xuhai college,圆的Bresenham算法的程序实现如下： circle(xc, yc, radius, c) int xc, yc, radius, c; int x, y, p;x=0;y=radius;p=32*radius； while(xy) plot_circle_points(xc,yc,x,y,c); if(p0) p=p+4*x+6; else p=p+4*(xy)+10; y=1; x+=1; if(x=y) plot_circle_points(xc,yc,x,y,c); ,Xuhai college,plot_circle_points(xc, yc, x, y, c) int xc, yc, x, y, c; set_pixel(xc+x, yc+y, c); set_pixel(xcx, yc+y, c); set_pixel(xc+x, ycy, c);