计算机图形学-第二章

1、计算机图形学计算机图形学长春师范大学-数学学院 nenu_ZhangK.2光栅图形学光栅图形学 直线段的扫描转换算法 圆弧的扫描转换算法 多边形的扫描转换与区域填充 字符 裁剪 反走样 消隐3 什么是光栅图形学？ 光栅显示器 图形光栅化、 光栅扫描图形显示器的构成: 帧缓冲存储器（Frame Buffer)，视频控制器（Video Controller)，显示处理器（Display Processor），CRT4较为典型的光栅扫描图形显示系统的结构 帧缓冲存储器：存储屏幕上像素的颜色值，简称帧缓冲器，俗称显存。 视频控制器作用：建立与屏幕像素之间的一一对应，负责刷新。视频控制器能够直接存取帧缓

2、存以刷新屏幕。5光栅扫描显示器的工作原理: 计算机将欲显示的图形、图象转换为位图，经接口电路送入帧缓存；视频控制器依次扫描帧缓存中的位图，把位图转换成亮度或色彩信号来控制电子束的强度；同时光栅扫描电路控制电子束从左到右、从上到下移动。6 光栅显示器是画点设备，可看做是一个点阵单元发生器（象素矩阵），并可控制每个点阵单元的亮度。显示器的任务就是确定最佳逼近图形的象素集合，并用指定属性写象素的过程，这个过程被称为扫描转换，或光栅化。光栅化将给定直线和其他几何对象的图形命令转换为一组与屏幕位置对应的离散点。例如：直线的光栅化7 OpenGL中指定的二维世界坐标系统 gluOrtho2D:设定一个二维

3、笛卡儿坐标系 gluOrtho2D（xmin,xmax,ymin,ymax）;Xmin XmaxYmaxYmin显示窗口显示窗口屏幕窗口屏幕窗口8 OpenGL画点函数glBegin(GL_POINTS); /变量用来指定要显示的输出图元类型 glVertex*( ); /该函数要有后缀码glEnd( ); *函数后缀码包括用来指明空间尺寸、用做坐标值的数据类型和可能的向量形式坐标的描述。of419第二章第二章 光栅图形学光栅图形学 什么是光栅图形学？ 光栅显示器 图形光栅化、 光栅化图形的处理 of4110 光栅图形学的研究内容n直线段的扫描转换算法n圆弧的扫描转换算法n多边形的扫描转换与区

4、域填充n字符n裁剪n反走样n消隐of41112.1 直线段的扫描转换算法直线段的扫描转换算法 直线的扫描转换直线的扫描转换: 确定最佳逼近于该直线的一组象素，并且按扫描线顺序，对这些象素进行写操作。 三个常用算法：数值微分法（DDA）中点画线法Bresenham算法。0 1 2 3 4 5321Line: P0(0, 0)- P1(5, 2)of41122.1.1 数值微分数值微分(DDA)法法 基本思想 已知过端点 的直线段L： 直线斜率为 从 的左端点 开始，向 右端点步进。步长=1(个象素)，计算相应的y坐标 ；取象素点(x, round(y)作为当前点的坐标。0101xxyyk),()

5、,(111000yxPyxPbkxyx0 xxbkxyof4113n作为最底层的光栅图形算法，在通常的CAD/图形系统中，会被大量应用，因此，哪怕节约一个加法或减法，也是很了不起的改进。n由此出发点，导致增量算法的思想。of4114计算当 时;即：当x每递增1，y递增k(即直线斜率)； xkyxkbkxbkxyiiii 111xkyyii1of4115例：画直线段x int(y+0.5) y+0.5000100.4+0.5210.8+0.5311.2+0.5421.6+0.5522.0+0.5注：网格点表示象素0 1 2 3 4 5321Line: P0(0, 0)- P1(5, 2)2 ,

6、5()0 ,0(10PPof4116void 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; xx1, x+) drawpixel (x, int(y+0.5), color); y=y+k; of4117 问题： 当 k 1时，会如何？of4118注意上述分析的算法仅适用于k 1的情形。在这种情况下，x每增加1, y最多增加1。当 k 1时，必须把x，y地位互换 k DDA算法采用点斜式，可否采用其他

7、的直线表示方式？of4120基本思想当前象素点为(xp, yp) 。下一个象素点为P1 或P2 。设M=(xp+1, yp+0.5)，为p1与p2之中点，Q为理想直线与x=xp+1垂线的交点。将Q与M的y坐标进行比较。n当M在Q的下方，则P2 应为 下一个象素点；nM在Q的上方，应取P1为下一点。P=(xp,yp)QP2P1of4121构造判别式:d=F(M)=F(xp+1,yp+0.5) =a(xp+1)+b(yp+0.5)+c 其中a=y0-y1, b=x1-x0, c=x0y1-x1y0当d0，M在L(Q点)上方，取右方P1为下一个象素；当d=0，选P1或P2均可，约定取P1为下一个象素

8、；of4122但这样做，每一个象素的计算量是4个加法，两个乘法。如果也采用增量算法呢？ d是xp, yp的线性函数，因此可采用增量计算，提高运算效率。of4123 若当前象素处于d0情况，则取正右方象素P1 (xp+1, yp), 要判下一个象素位置，应计算 d1=F(xp+2, yp+0.5)=a(xp+2)+b(yp+0.5)=d+a； 增量为a 若d0时，则取右上方象素P2 (xp+1, yp+1)。要判断再下一象素，则要计算 d2= F(xp+2, yp+1.5)=a(xp+2)+b(yp+1.5)+c=d+a+b ；增量为abof4124 至此，至少新算法可以和DDA算法一样好。 能

9、否再做改进？ 能否实现整数运算？of4125 画线从(x0, y0)开始，d的初值d0=F(x0+1, y0+0.5)=F(x0, y0)+a+0.5b =a+0.5b。可以用2d代替d来摆脱小数，提高效率。令 d0=2a+b, d1=2a, d2=2a+2b,我们有如下算法 。of4126void 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; drawpix

10、el(x, y, color); while (xx1) if (d0) x+, y+, d+=d2; else x+, d+=d1; drawpixel (x, y, color); /* while */ /* mid PointLine */of4127例：用中点画线法 i xiyid1 0012 10-33 2134 31-15 4250 1 2 3 4 5321)2, 5()0 ,0(10PP5,20110 xxbyya,6)(2,42, 12210badadbadof41282.1.3 Bresenham算法算法 基本思想nDDA算法采用点斜式，中点法采用隐式表示。n中点法可以有整

11、数算法。n其他表示可以推出整数算法吗？of4129n 过各行各列象素中心构造一组虚拟网格线。按直线从起点到终点的顺序计算直线与各垂直网格线的交点，然后根据误差项的符号确定该列象素中与此交点最近的象素。ddddof4130设直线方程为： ，其中k=dy/dx。 因为直线的起始点在象素中心，所以误差项d的初值d00。X下标每增加1，d的值相应递增直线的斜率值k，即ddk。一旦d1，就把它减去1，这样保证d在0、1之间。n当d0.5时，最接近于当前象素的右上方象素（ ）n而当d0.5时，更接近于右方象素（ ）。为方便计算，令ed-0.5，e的初值为-0.5，增量为k。n当e0时，取当前象素（xi，y

12、i）的右上方象素（ ）；n而当e0时，更接近于右方象素（ ）。kyxxkyyiiiii)(1111,iiyxiiyx,111,iiyxiiyx,1of4131可以改用整数以避免除法。由于算法中只用到误差项的符号，因此可作如下替换： 例：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.3 3 1 -0.3 4 2 0.1 5 2 -0.5 大于零，大于零，y加加1，小于零，不变，小于零，不变dxee*2 0 1 2 3 4 5321of4132void Bresenhamline (int x0,int y0,i

13、nt x1, int y1,int color) int x, y, dx, dy; float k, e; dx = x1-x0, dy = y1- y0, k=dy/dx; e=-0.5, x=x0, y=y0; for (i=0; idx; i+) drawpixel (x, y, color); x=x+1，e=e+k; if (e0) y+, e=e-1; of4133 最终，Bresenham算法也是每个象素，需一个整数算法，其优点是可以用于其他二次曲线。 至此，直线光栅化是否终结？of4134 设计光栅图形算法的依据： 确定最佳逼近图形的象素集合(寻优)of4135 算法评价指标

14、：n准确性n高效性of4136直线光栅化总结直线光栅化总结画线方法画线方法直线方程直线方程计算方法计算方法决策参数决策参数数值微分法（数值微分法（DDA）y=kx+b增量算法“四舍五入法”中点法中点法ax+by+c=0增量算法中点坐标Bresenham算法算法y=kx+b增量算法误差项of4137新方法：BRDC: binary representation of displacement code for lineMiao LF, Liu XG, Peng QS, Bao HJCOMPUTERS & GRAPHICS-UK 26 (3): 401-408 JUN 2002of4138

15、 其他图形 of41392.2 圆弧的扫描转换算法圆弧的扫描转换算法 常见的圆of41402.2 圆弧的扫描转换算法圆弧的扫描转换算法 思考？思考？ 圆C,原点为C(x,y),半径为r 如何进行圆扫描转换？of41412.2 圆弧的扫描转换算法圆弧的扫描转换算法 圆的方程 一般式： 利用方程，沿x轴从xc-r到xc+r以单位步长计算对应的y值，从而得到圆周上每点的位置： 222r)()(ccyyxx22)(yxxryccof4142 参数方程 x=xc+ rcos y= yc+ rsin 以固定角度为步长，利用圆周的 等距点来绘制圆。当设定角度间 隔为1/r时，可获得较连续的边界。 此时绘出的

16、像素位置大约间隔一 个单位。 ycxcr(x,y)of4143 圆的特征圆的特征xy y=x0of4144 圆的特征圆的特征:八对称性。只要扫描转换八分之一圆弧，就可以求出整个圆弧的象素集 决策参数？决策参数？of4145 点与圆的位置关系 圆函数: f=x2+y2-r2 对于任何一点(x,y),则： 0, (x,y)位于圆边界外 of4146 决策参数 当前点为xi, 下一个取样位置xi+1的两个候选点分别为P1 (xi+1,yi)及P2 (xi+1,yi-1)。圆函数在取样候选点的中点M(xi+1,yi-0.5)进行测试： Pk=f(xi+1,yi-0.5)=(xi+1)2+(yi-0.5

17、)2-r2 0, M位于圆边界外， P1、P2均可P=(xp,yp)P1P2Mof4147 若 Pk =0, 则应取P2为下一像素，而且下一象素的判别式为增量为 第 一个象素是（0,r）， 决策参数Pk的初始值为32px32)5 . 0()2()5 . 0, 2(k222kpppppxPryxyxFP5)(2)5 . 1()2()5 . 1, 2(k222kppppppyxPryxyxFPrrFP25.1)5 .0, 1 (05)(2ppyxkPof4148 注意！n第一象限，圆弧从x=0到x=y，曲线斜率从0变化到-1.x x方向步进方向步进n当圆心（xc , yc）不在坐标原点时，可以先使

18、用算法计算圆心在（0,0）的圆的像素位置，然后通过将xc加到x,且yc加到y，从而把计算出的每个位置移动到其相应的屏幕位置。n算法可实现整数运算： P0=1-r (r是整数)of4149 中点画圆算法步骤 1.输入圆半径r和圆心（xc , yc），并得到圆周（圆心在原点）上的第一点： （x0, y0）=（0，r） 2.计算决策参数初始值：P0=1.25-r 3.在每个xi位置（从i=0）开始，完成下列测试： 假如Pk0,下一个点在（ xi+1 , yk ）,且 否则，下一个点在（ xi+1 , yk-1 ）,且 4.确定在其他七个八分圆中的对称点 5.若原始圆圆心不在原点，则将每个计算出的像素

19、位置（x,y）移动到圆心（xc , yc）的圆路径上，并画坐标值x=x + xc,y=y + yc 6.重复步骤3-5，直至xy32kkixPP5)(2kkiiyxPPof4150 例题： 给定圆的圆心在坐标原点，半径r=10，使用中点画圆算法画图初始点：（x0 , y0）=(0,10)决策参数初始值：P0=1-r=-9决策参数初始增量：若P00,下一个点在( xi+1 , yk ),且P =2 x0 +3=3 若P0 0下一个点在(xi+1 , yk-1),且 P=2(x0 - y0)+5=-15iPk(xi+1,yi+1)2xi+12yi+1P0-9(1,10)22031-6(2,10)523456of4151关于y=x对称关于y轴对称关于x轴对称of4152算法算法MidPointCircle(int r int color)int x,y; float d; x=0; y=r; d=1.25-r; circlep