计算机图形学-课件

1、 余 敦 辉湖北大学 数计学院计算机图形学1 余 敦 辉计算机图形学1第五章 基本图形生成算法光栅扫描图形系统的结构光柵扫描特点： * 数据量大 快的要求 * 显示的离散化 准的要求 * 独立的图形显示处理器 快速，实时硬件处理的扫描转换CPU系统总线显示处理器系统存储器显示处理器存储器帧缓存视频控制器I/O设备监视器2第五章 基本图形生成算法光栅扫描图形系统的结构光柵扫描特第五章 基本图形生成算法图形显示处理器 (加速引擎)任务：进行扫描转换(Scan Conversion)扫描转换：将应用程序给出的图形定义数字化为一组像素强度值，并放到帧缓存器扫描转换的工作内容：基本图形的生成字符的生成填

2、充、裁剪线型的处理彩色处理某些变换和管理3第五章 基本图形生成算法图形显示处理器 (加速引擎)任务第五章 基本图形生成算法坐标系统为描述对象、构造场景或完成图形变换，需要不同的坐标系！建模坐标系定义对象2. 世界坐标系定义对象与外界环境的关系3. 设备坐标系 定义图形显示的位置、大小4. 规范化坐标 为保证互换性（与设备无关）而定义的辅助坐标4第五章 基本图形生成算法坐标系统为描述对象、构造场景或完第五章 基本图形生成算法坐标系统建模坐标Modeling CoordinateLocal CoordinateMaster Coordinate世界坐标World Coordinate绘图仪其它输出

3、设备设备坐标Device CoordinateScreen Coordinate111规范化坐标NormalizedCoordinate5第五章 基本图形生成算法坐标系统建模坐标Modelin第五章 基本图形生成算法5.1 直线的扫描转换光栅扫描显示下画直线存在的问题：(1) 显示速度问题： 例：分辨率：1024768， 24Bit 彩色， 帧存容量：10247683 2,359,296 Byte 刷新率 85Hz: 85 2,359,296 200,540,160 (Byte / S) 存储器读出时间：5nS(2) 显示质量问题：阶梯状线的粗细不一线的亮度差异6第五章 基本图形生成算法5.1

4、 直线的扫描转换光栅扫描显第五章 基本图形生成算法5.1 直线的扫描转换直线的绘制要求：1.直线要直2.直线的端点要准确，即无定向性和断裂情况3.直线的亮度、色泽要均匀4.画线的速度要快5.要求直线具有不同的色泽、亮度、线型等解决的问题：给定直线两端点P0(x0,y0)和P1(x1,y1)，画出该直线。7第五章 基本图形生成算法5.1 直线的扫描转换直线的绘第五章 基本图形生成算法5.1 直线的扫描转换5.1.1 数值微分法(DDA法)直线的微分方程：DDA算法原理： =1/max(|x|,|y|) 8第五章 基本图形生成算法5.1 直线的扫描转换5.1.第五章 基本图形生成算法5.1 直线的

5、扫描转换5.1.1 数值微分法(DDA法)max(|x|,|y|)=|x|，即|k|1的情况：max(|x|,|y|)=|y|，此时|k|1：9第五章 基本图形生成算法5.1 直线的扫描转换5.1.第五章 基本图形生成算法5.1 直线的扫描转换5.1.1 数值微分法(DDA法)注意：round(x)=(int)(x+0.5)10第五章 基本图形生成算法5.1 直线的扫描转换5.1.第五章 基本图形生成算法5.1 直线的扫描转换5.1.1 数值微分法(DDA法)Void DDAline(int x0,int y0,int x1,int y1) int dx,dy,eps1,k; float x,

6、y,xIncre,yIncre; dx=x1-x0; dy=y1-y0; x=x0; y=y0; If (abs(dx)abs(dy) eps1=abs(dx); else eps1=abs(dy); xIncre=(float)dy/(float)eps1; yIncre=(float)dy/(float)eps1; for (k=0;k=eps1;k+) putpixel(int)(x+0.5),(int)(y+0.5); x+=xIncre; y+=yIncre; 11第五章 基本图形生成算法5.1 直线的扫描转换5.1.第五章 基本图形生成算法5.1 直线的扫描转换 5.1.1 数值微

7、分法(DDA法)特点：增量算法直观、易实现缺点：浮点运算、取整废时，且不利于硬件实现。不利于用硬件实现 。12第五章 基本图形生成算法5.1 直线的扫描转换 5.1第五章 基本图形生成算法5.1 直线的扫描转换 5.1.2 中点画线法算法5.1.2 中点画线法算法原理：假定直线斜率K1，且已确定点亮象素点P（Xp ,Yp ）M为中点，Q为交点现需确定下一个点亮的象素。显然可得出如下结论：若M在Q的下方，选Pu，否则选Pd13第五章 基本图形生成算法5.1 直线的扫描转换 5.1第五章 基本图形生成算法5.1 直线的扫描转换 5.1.2 中点画线法算法算法实现： 假设直线的起点、终点分别为：（X

8、0,Y0),(X1,Y1) 该直线方程可表示为： F(x,y)=a*x+b*y+c （1） 其中： a=Y0-Y1, b=X1-X0, c=X0*Y1-X1*Y0 当： F(Xt,Yt) = 0 (Xt,Yt) 在直线上 F(Xt,Yt) 0 (Xt,Yt) 在直线上方14第五章 基本图形生成算法5.1 直线的扫描转换 5.1第五章 基本图形生成算法5.1 直线的扫描转换5.1.2 中点画线法算法15第五章 基本图形生成算法5.1 直线的扫描转换5.1.第五章 基本图形生成算法5.1 直线的扫描转换5.1.2 中点画线法算法 因此：将中点M坐标代入（1）式，并判断其符号即可确定象素点的选取。构

9、造如下判别式： d = F(M) =F(Xp+1,Yp+0.5) =a(Xp+1)+b(Yp+0.5)+c 由上式可看出，d是x,y线性函数，可推导d的增量公式16第五章 基本图形生成算法5.1 直线的扫描转换5.1.第五章 基本图形生成算法5.1 直线的扫描转换5.1.2 中点画线法算法当d 0 时， 取象素Pu，此时再下一个象素的判别式为：d= 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;误差项的递推d= 0时，取象素Pd，此时再下一个象素的判别式为：d= F(Xp+2,Yp+0.

10、5) = a(Xp+2)+b(Yp+0.5)+c = a(Xp+1)+b(Yp+0.5)+c +a = d + a;误差项的递推d0：18第五章 基本图形生成算法5.1 直线的扫描转换5.1.第五章 基本图形生成算法5.1 直线的扫描转换5.1.2 中点画线法算法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，这样可得如下中点算法程序：19第五章 基本图形生成算法5.1 直线的扫描转换5.1.第五章 基本图形生成算

11、法5.1 直线的扫描转换5.1.2 中点画线法算法 MidpointLine(X0,Y0,X1,Y1,Color) int X0,Y0,X1,Y1,Color; int a,b,d1,d2,d,x,y; a=Y0-Y1; b=X1-X0; d=a+a+b; d1=a+a; d2=a+b+a+b; x=X0; y=Y0; drawpixle(x,y,Color); while(xX1) if(d0) x+; y+; d+=d2; 20第五章 基本图形生成算法5.1 直线的扫描转换5.1.第五章 基本图形生成算法5.1 直线的扫描转换5.1.2 中点画线法算法 else x+; d += d1;

12、drawpixle(x,y,Color); /*while*/ /*MidPointLine*/ 习题： 按照中点划线算法，确定直线（0，0）（5，3）的点亮象素。列出计算过程，并列出所选象素坐标。 21第五章 基本图形生成算法5.1 直线的扫描转换5.1.第五章 基本图形生成算法5.1 直线的扫描转换5.1.3 Bresenham画线算法5.1.3 改进的Bresenham算法基本原理：(假定直线段的0k1)22第五章 基本图形生成算法5.1 直线的扫描转换5.1.第五章 基本图形生成算法5.1 直线的扫描转换5.1.3 Bresenham画线算法假定直线斜率,0k1 时 d=d-1 ;当d

13、0.5，则(x,y)更新为(x+1,y+1)，同时将d更新为d-1；否则(x,y)更新为(x+1,y)。5.当直线没有画完时，重复步骤3和4。否则结束。24第五章 基本图形生成算法5.1 直线的扫描转换5.1.第五章 基本图形生成算法5.1 直线的扫描转换5.1.3 Bresenham画线算法改进1：令e=d-0.5e初= -0.5，每走一步有e=e+k。if (e0) then e=e-125第五章 基本图形生成算法5.1 直线的扫描转换5.1.第五章 基本图形生成算法5.1 直线的扫描转换5.1.3 Bresenham画线算法算法步骤为：1.输入直线的两端点P0(x0,y0)和P1(x1,

14、y1)。2.计算初始值x、y、e=-0.5、x=x0、y=y0。3.绘制点(x,y)。4.e更新为e+k，判断e的符号。若e0，则(x,y)更新为(x+1,y+1)，同时将e更新为e-1；否则(x,y)更新为(x+1,y)。5.当直线没有画完时，重复步骤3和4。否则结束。26第五章 基本图形生成算法5.1 直线的扫描转换5.1.第五章 基本图形生成算法5.1 直线的扫描转换5.1.3 Bresenham画线算法改进2：用2ex来替换ee初= -x，每走一步有e=e+2y。if (e0) then e=e-2x27第五章 基本图形生成算法5.1 直线的扫描转换5.1.第五章 基本图形生成算法5.

15、1 直线的扫描转换5.1.3 Bresenham画线算法算法步骤：1. 输入直线的两端点P0(x0,y0)和P1(x1,y1)。2. 计算初始值x、y、e=-x、x=x0、y=y0。3. 绘制点(x,y)。4. e更新为e+2y，判断e的符号。若e0，则(x,y)更新为(x+1,y+1)，同时将e更新为e-2x；否则(x,y)更新为(x+1,y)。5. 当直线没有画完时，重复步骤3和4。否则结束。28第五章 基本图形生成算法5.1 直线的扫描转换5.1.程序如下： BresenhamLine(x0,y0,x1,y1,color) int x0,y0,x1,y1,color; int x,y,d

16、x,dy; float k,e; int e; dx = x1-x0; dy = y1-y0; k = dy/dx; e = -0.5; x=x0; y=y0; e = -dx; for( i=0; i 0) e = e - 1; e = e - 2*dx; if(e =0) y+; 29程序如下： BresenhamLine(x0,y0, Bresenham 画线例直线端点为(20,10)和（30,18), 用 Bresenham 法画线解： Dx 10， Dy 8， k = Dy / Dx = 0.8， 2 Dy 16， 2Dx 20 e0 Dx 10 画初始点(20, 10), 并根据判

17、别式确定沿线段路径的后续像素位置如下表：29212223242526202827101817161513141211193030 Bresenham 画线例29212223242526第五章 基本图形生成算法5.2 圆的扫描转换5.2.1 圆的对称性利用八分圆的对称性特点，可以简化圆的扫描转换算法。如果圆的圆心在原点，则可以由其中某个八分圆的圆周上的某点（x，y）计算出其他七个八分圆圆周上对应的点的坐标。由此可构造相应算法，由图中阴影的圆周复制生成整个圆周。31第五章 基本图形生成算法5.2 圆的扫描转换5.2.1第五章 基本图形生成算法5.2 圆的扫描转换5.2.1 圆的对称性算法如下：in

18、t Circle_Points(x,y,value)int x,y,value; drawpixel(x,y,value); drawpixel(x,-y,value); drawpixel(-x,y,value); drawpixel(-x,-y,value); drawpixel(y, x, value); drawpixel(-y, x, value); drawpixel(y, -x, value); drawpixel(-y, -x, value);32第五章 基本图形生成算法5.2 圆的扫描转换5.2.1第五章 基本图形生成算法5.2 圆的扫描转换5.2.2 角度DDA画圆算法1、

19、角度DDA法若已知圆的方程： x = x0 + Rcos y = y0 + Rsin dx =- Rsind dy = Rcosd xn+1 =x n + dx y n+1 =y n + dy xn+1 =x n - (y n - y 0 )d y n+1 =y n + (x n - x 0 )d33第五章 基本图形生成算法5.2 圆的扫描转换5.2.2第五章 基本图形生成算法5.2 圆的扫描转换5.2.2 角度DDA画圆算法角增量(弧度)的选取：d /(n-1)n越大，点越多，速度越慢。所以在不同的精度下，对于不同的半径给定不同的d：使 max(|x|， |y|) 1因： x = - ( y

20、n y0) d y = ( xn x0) d即 max(| ( yn y0) d |， | ( xn x0) d |) 1又因为 | yn y0 |， | xn x0 | 最大是R所以：R| d | 1 | d | 1/R绝对值表示画圆弧有顺时针和逆时针之别，为精度计，取 | d | 1/(R+1)34第五章 基本图形生成算法5.2 圆的扫描转换5.2.2第五章 基本图形生成算法5.2 圆的扫描转换5.2.2 角度DDA画圆算法算法：Arcdda（xc，yc，r，a1，a2，color）int xc，yc，r，color；double a1，a2； int i,steps,x,y； doubl

21、e da,radin; da = 1/(r1）； radin a2 - a1; steps = radin/da; x = r*cos(a1); y = r * Sin(a1); for(i = 0;i steps;i+) drawpixel( x+xc , y+ yc , color ); x = x y*da ; y = y+ x*da ; 35第五章 基本图形生成算法5.2 圆的扫描转换5.2.2第五章 基本图形生成算法5.2 圆的扫描转换5.2.3 中点画圆法利用圆的对称性，只须讨论1/8圆(第一象限中的第二个八分圆)。解决问题：36第五章 基本图形生成算法5.2 圆的扫描转换5.2.

22、3第五章 基本图形生成算法5.2 圆的扫描转换5.2.3 中点画圆法基本原理：假设P（Xp+1，Yp）为当前点亮象素，那么，下一个点亮的象素可能是P1（Xp+1，Yp）或P2（Xp +1，Yp +1)。37第五章 基本图形生成算法5.2 圆的扫描转换5.2.3第五章 基本图形生成算法5.2 圆的扫描转换5.2.3 中点画圆法 2)推导过程： 构造一函数： F（X，Y）=X2 + Y2 - R2 F（X，Y）= 0 （X，Y）在圆上； F（X，Y） 0 （X，Y）在圆外。 M为P1、P2间的中点，M=(Xp+1,Yp-0.5) 有如下结论： F（M）= 0 取P238第五章 基本图形生成算法5.

23、2 圆的扫描转换5.2.3第五章 基本图形生成算法5.2 圆的扫描转换5.2.3 中点画圆法 构造判别式 d = F(M)= F(xp + 1, yp - 0.5) =(xp + 1)2 + (yp - 0.5) 2 - R2 若d=0, 则P2 为下一个象素，那么再下一个象素的判别式为： d = F(xp + 2, yp - 1.5) = (xp + 2)2 + (yp - 1.5) 2 - R2 = d + 2(xp - yp) + 5 即d 的增量为 2 (xp - yp) +5.40第五章 基本图形生成算法5.2 圆的扫描转换5.2.3第五章 基本图形生成算法5.2 圆的扫描转换5.2

24、.3 中点画圆法算法步骤：1.输入圆的半径R。2.计算初始值d=1.25-R、x=0、y=R。3.绘制点(x,y)及其在八分圆中的另外七个对称点。4.判断d的符号。若d0，则先将d更新为d+2x+3，再将(x,y)更新为(x+1,y)；否则先将d更新为d+2(x-y)+5，再将(x,y)更新为(x+1,y-1)。5.当xy时，重复步骤3和4。否则结束。41第五章 基本图形生成算法5.2 圆的扫描转换5.2.3第五章 基本图形生成算法5.2 圆的扫描转换5.2.3 中点画圆法MidpointCircle(r, color) int r, color; int x,y; float d; x=0;

25、 y=r; d=1.25-r; drawpixel(x,y,color); while(xy) if(d0) d+ = 2*x+3; x+； else d+ = 2*(x-y) + 5; x+;y-; 42第五章 基本图形生成算法5.2 圆的扫描转换5.2.3第五章 基本图形生成算法5.2 圆的扫描转换5.2.3 中点画圆法改进1：用d-0.25代替d算法步骤：1.输入圆的半径R。2.计算初始值d=1-R、x=0、y=R。3.绘制点(x,y)及其在八分圆中的另外七个对称点。4.判断d的符号。若d0，则先将d更新为d+2x+3，再将(x,y)更新为(x+1,y)；否则先将d更新为d+2(x-y)

26、+5，再将(x,y)更新为(x+1,y-1)。5.当xy时，重复步骤3和4。否则结束。令ed0.25 e1R则 d 0 e 0.25而e为整数，则e 0.25等价于e 0。再将e仍用d来表示43第五章 基本图形生成算法5.2 圆的扫描转换5.2.3第五章 基本图形生成算法5.2 圆的扫描转换5.2.3 中点画圆法改进2：因判别式d的增量是x，y的线性函数。 每当x递增1，d递增 x 2； 每当y递增1，d递减 y 2； 由于初始象素为（0，r），所以x 的初值为3， y 的初值为2r2。再注意到乘2运算可以改用加法实现，至此我们可写出不含乘法，仅用整数实现的中点画圆算法。44第五章 基本图形生

27、成算法5.2 圆的扫描转换5.2.3第五章 基本图形生成算法5.2 圆的扫描转换5.2.3 中点画圆法MidpointCircle(r, color) int r, color; int x,y，deltax，deltay，d; x=0; y=r; d=1-r; deltax=3; deltay=2-r-r; drawpixel(x,y,color); while(xy) if(d0) d+ = deltax; deltax+=2; x+； else d+ = (deltax+deltay); deltax+=2;deltay+=2; x+; y-; 45第五章 基本图形生成算法5.2 圆的扫

28、描转换5.2.3例题：画第一象限中，半径 R10， 圆心在原点的圆弧解：起点为(x0, y0) (0, 10) e0 1R 9； (x1, y1)(1, 10) e1 e0 2x0 +3 6； (x2, y2)(2, 10) e2 e1 2x1 +3 1； (x3, y3)(3, 10) e3 e2 2x2 +3 6； (x4, y4)(4, 9) e4 e3 2(x3 y3 ) + 5 3；(x5, y5)(5, 9) e5 e4 2x4 + 3 8； (x6, y6)(6, 8) e6 e5 2(x5 y5 ) + 5 5； (x7, y7)(7, 7)912345608719876453

29、21010若 ei ei1 ei + 2xi + 3ei=0, ei1 ei + 2(xi yi ) + 546例题：画第一象限中，半径 R10， 圆心在原点的圆弧解：起第五章 基本图形生成算法5.2 圆的扫描转换5.2.3 Bresenham画圆法5.2.3. Bresenham画圆算法 为讨论方便，仅考虑圆心在原点，半径为R的第一象限上的一段圆弧。且取（0，R）为起点，按顺时针方向绘制该1/4圆弧。47第五章 基本图形生成算法5.2 圆的扫描转换5.2.3第五章 基本图形生成算法5.2 圆的扫描转换5.2.3 Bresenham画圆法原理 ： 如图1-3所示，从当前点亮象素出发，按顺时针方

30、向生成圆时，最佳逼近该圆的下一个象素只可能为H、D、V三象素之一。H、D、V中距圆周边界距离最小者，即为所求的象素点。48第五章 基本图形生成算法5.2 圆的扫描转换5.2.3第五章 基本图形生成算法5.2 圆的扫描转换5.2.3 Bresenham画圆法算法： H、D、V三点到圆心的距离平方与圆的半径平方差，即为H、D、V到圆弧距离的一种度量： H = (x+1)2 + y2 - R2; D = (x+1)2 + (y-1)2 - R2; V = x2 + (y-1)2 - R2;49第五章 基本图形生成算法5.2 圆的扫描转换5.2.3第五章 基本图形生成算法5.2 圆的扫描转换5.2.3

31、 Bresenham画圆法为了根据这些度量值可确定最佳象素点，首先，将H、D、V与理想圆弧的关系进行分类。存在以下五种情况： 1）H、D、V全在圆内； 2）H在圆外，D、V在圆内； 3）D在圆上，H在圆外，V在圆内； 4）H、D在圆外，V在圆内； 5）H、D、V全在圆外。与Bresenham画线算法一样，按照上述不同类型，找出误差度量的递推公式，然后判别它的正、负性即可确定最佳逼近的象素点。50第五章 基本图形生成算法5.2 圆的扫描转换5.2.3第五章 基本图形生成算法5.2 圆的扫描转换5.2.3 Bresenham画圆法当D 0 , 只可能为1或2种情况。为了确定是H还是D，可用如下判别

32、式： HD = | H | - | D | HD 0 则应选H，否则选D。51第五章 基本图形生成算法5.2 圆的扫描转换5.2.3第五章 基本图形生成算法5.2 圆的扫描转换5.2.3 Bresenham画圆法对于第2种情况： HD = H + D = (x+1)2 + y2 - R2 + (x+1)2 + (y-1)2 - R2 =2 D + 2y - 1 对于第1种情况： y是x的单调递减函数H为下一点亮象素。 另，此时H 0 和 D 0 H + D = 2 D + 2y - 1 =0) drawpixel(x,y,color); if(delta 0) d1 = 2* (delta +

33、 y) -1; if(d1 0) d2 = 2*(delta-x)-1; if(d2 0；对于椭圆内的点，F(x,y) x分量y分量 0，取Pd(xi+1,yi-1)66第五章 基本图形生成算法5.3 椭圆的扫描转换5.3.第五章 基本图形生成算法5.3 椭圆的扫描转换5.3.1 椭圆的中点Bresenham算法误差项的递推情况一：d10：67第五章 基本图形生成算法5.3 椭圆的扫描转换5.3.第五章 基本图形生成算法5.3 椭圆的扫描转换5.3.1 椭圆的中点Bresenham算法误差项的递推情况二： d10：68第五章 基本图形生成算法5.3 椭圆的扫描转换5.3.第五章 基本图形生成算法5.3 椭圆的扫描转换5.3.1 椭圆的中点Bresenham算法上半部判别式的初始值： 初始点（0，b）候选点（1，b-1）（1，b）中 点 （1，b-0.5）69第五章 基本图形生成算法5.3 椭圆的扫描转换5.3.第五章 基本图形生成算法5.3 椭圆的扫描转换5.3.1 椭圆的中点Bresenham算法再来推导椭圆弧下半部分的绘制公式判别式 误差项的递推 判别式的初值70第五章 基本图形生成算法5.3 椭圆的扫描转换5.3.第五章 基本图形生成算法5.3 椭圆的扫描转换5.3.