重点：基本图形（直线和圆）绘制，三种坐标系：教学难点：Bresenham算法的原理推导，坐标变换关系。重点难点PP544、5题讨论练习作业教材王德忠主编：包装计算机辅助设计，印刷工业出版社，1996。参考主要参考书：孙家广：计算机图形学（第三版），清华大学出版社，1999资料教研室主任审批意见对坐标变换和Bresenham算法的原理推导理解有点困难，建议学生继续课后化一定的时间进一步自行学习。基本完成教学任务。教学后记
教 学 重 点 难 点 重点：基本图形（直线和圆）绘制，三种坐标系； 难点：Bresenham 算法的原理推导，坐标变换关系。 讨 论 练 习 作 业 PP54 4、5 题 参 考 资 料 教材 王德忠主编：包装计算机辅助设计，印刷工业出版社，1996。 主要参考书： 孙家广：计算机图形学（第三版），清华大学出版社，1999 教研室 主任 审批意见 教 学 后 记 对坐标变换和 Bresenham 算法的原理推导理解有点困难，建议学生继续课后化一 定的时间进一步自行学习。 基本完成教学任务
第二章计算机绘图与程序设计第一节计算机图形学的概念一、图形的描述计算机图形学中研究的图形就是从客观世界的物体中抽象出来的带有灰度或色彩及形状的图或形：景物，照片、图片、工程图、设计图、美术画、数学方法描述的图形。计算机表述图形的方法点阵表示用具有灰度或色彩的点阵来表示图形（强调图形由点构成），简称为图像（数字图像）。参数表示由图形的形状参数（方程或分析表达式的系数，线段的端点坐标等)+属性参数（颜色、线型等)来表示图形，简称为图形。二、计算机图形学的研究内容如何在计算机中表示图形、以及利用计算机进行图形的计算、处理和显示的相关原理与算法，构成了计算机图形学的主要研究内容。图形通常由点、线、面、体等几何元素和灰度、色彩、线型、线宽等非几何属性组成。从处理技术上来看，图形主要分为两类，一类是基于线条信息表示的，如工程图、等高线地图、曲面的线框图等，另一类是明暗图（Shanding），也就是通常所说的真实感图形。可以说，计算机图形学一个主要的目的就是要利用计算机产生令人赏心悦目的真实感图形。为此，必须建立图形所描述的场景的儿何表示，再用某种光照模型，计算在假想的光源、纹理、材质属性下的光照明效果。所以计算机图形学与另一门学科计算机辅助几何设计有着密切的关系。事实上，图形学也把可以表示几何场景的曲线曲面造型技术和实体造型技术作为其主要的研究内容。同时，真实感图形计算的结果是以数字图象的方式提供的，计算机图形学也就和图象处理有着密切的关系。图形与图象两个概念间的区别越来越模糊，但我们认为还是有区别的；图象纯指计算机内以位图（Bitmap）形式存在的灰度信息，而图形含有几何属性，或者说更强调场景的几何表示，是由场景的几何模型和景物的物理属性共同组成的。计算机图形学的研究内容非常广泛，如图形硬件、图形标准、图形交互技术、光栅图形生成算法、曲线曲面造型、实体造型、真实感图形计算与显示算法，以及科学计算可视化、计算机动画、自然景物仿真、虚拟现实等。第二节坐标系一、用户坐标系用户原始应用的坐标系：极坐标、球坐标、直角坐标。二、设备坐标系(0,0-与设备有关的坐标系，一般是二维，有时是三维的。(a.s)例IBMPC机坐标系，左上角为原点（O，O），横坐标0，1，2319（639），纵坐标0，1，2199，即每一点对应一对整数表示的坐标三、规格化坐标系图2-1屏幕坐标与设备无关的图形系统，x、y轴取值范围[1.0，1.0]。四、四、三种坐标系间的关系用户坐标系中的一点（xy.）转变为规格化坐标系中的点（xa，y。）Jx, = (xw-Xw)/Ww[y, =(yw-ybw)/Hw
第二章 计算机绘图与程序设计 第一节 计算机图形学的概念 一、图形的描述 计算机图形学中研究的图形就是从客观世界的物体中抽象出来的带有灰度或色彩及形 状的图或形：景物，照片、图片、工程图、设计图、美术画、数学方法描述的图形。 计算机表述图形的方法 点阵表示 用具有灰度或色彩的点阵来表示图形(强调图形由点构成)，简称为图像（数字图像）。 参数表示 由图形的形状参数(方程或分析表达式的系数，线段的端点坐标等)+属性参数(颜色、 线型等)来表示图形，简称为图形。 二、计算机图形学的研究内容 如何在计算机中表示图形、以及利用计算机进行图形的计算、处理和显示的相关原理与 算法，构成了计算机图形学的主要研究内容。图形通常由点、 线、面、体等几何元素和灰 度、色彩、线型、线宽等非几何属性组成。 从处理技术上来看，图形主要分为两类，一类是基于线条信息表示的，如工程图、等高 线地图、曲面的线框图等，另一类是明暗图(Shanding)，也就是通常所说的真实感图形。可 以说，计算机图形学一个主要的目的就是要利用计算机产生令人赏心悦目的真实感图形。为 此，必须建立图形所描述的场景的几何表示，再用某种光照模型，计算在假想的光源、纹理、 材质属性下的光照明效果。所以计算机图形学与另一门学科计算机辅助几何设计有着密切的 关系。事实上，图形学也把可以表示几何场景的曲线曲面造型技术和实体造型技术作为其主 要的研究内容。同时，真实感图形计算的结果是以数字图象的方式提供的，计算机图形学也 就和图象处理有着密切的关系。图形与图象两个概念间的区别越来越模糊，但我们认为还是 有区别的；图象纯指计算机内以位图(Bitmap)形式存在的灰度信息，而图形含有几何属性， 或者说更强调场景的几何表示，是由场景的几何模型和景物的物理属性共同组成的。计算机 图形学的研究内容非常广泛，如图形硬件、图形标准、图形交互技术、光栅图形生成算法、 曲线曲面造型、实体造型、真实感图形计算与显示算法，以及科学计算可视化、计算机动画、 自然景物仿真、虚拟现实等。 第二节 坐标系 一、用户坐标系 用户原始应用的坐标系：极坐标、球坐标、直角坐标。 二、设备坐标系 与设备有关的坐标系，一般是二维，有时是三维的。 例 IBM PC机坐标系，左上角为原点（0，0），横坐标0， 1，2.319（639），纵坐标0，1，2.199，即每一点对应一对 整数表示的坐标 三、规格化坐标系 与设备无关的图形系统，x、y轴取值范围[1.0，1.0]。四、 四、三种坐标系间的关系 用户坐标系中的一点（xw, yw）转变为规格化坐标系中的点（xn, yn） ( ) ( ) = − = − n w bw w n w lw w y y y /H x x x /W
-o(r..y.)(r..y.)(Fw.yw)Ww设备坐标规格化设备坐标用户坐标图2-2三种坐标系的关系W.H为用户绘图空间的范围：Xi，Y.为用户原点坐标例如IBMPC/XT微机的显示器在高分辨模式下，分辨率为640*200，设备坐标系的取值范围是x：0-639；y：1-199。当（0，0）为用户坐标系原点时，规格化坐标为[x, =(xw)Ww[y, = (yw)/Hw变换到屏幕坐标系时[xa=639×x.=[639×xw/W.][y。=199×y.=[199×yw/H.]Ⅱ表示取整，由于屏幕的坐标原点在左上角，须经变换，才能以习惯的形式显示：1、原点平移到（0，199）；2、绕x轴旋转180°x,=[639×xw/W.]y,=[199×(1-yw/H.)]第三节基本图形的生成方法1、点点是构成图形的最基本元素，一般的软件都可以直接调用，对于其最底层的生成方法作了解，不需自己编程。2、直线段在数学上，理想的直线是没有宽度的，由无数个点构成的集合。当我们对直线进行光栅化时，只能在显示器所给定的有限个象素组成的矩阵中，确定最佳逼近于该直线的一组象素，并且按扫描线顺序，对这些象素进行写操作，这就是通常所说的用显示器绘制直线或直线的扫描转换。图2-1直线段的点生成a-理想像素分布h-实际像素分布
Ww,Hw为用户绘图空间的范围；Xlw,Ybw为用户原点坐标 例如 IBM PC/XT 微机的显示器在高分辨模式下，分辨率为640*200，设备坐标系的取 值范围是x：0-639；y：1-199。 当（0，0）为用户坐标系原点时，规格化坐标为 变换到屏幕坐标系时 []表示取整，由于屏幕的坐标原点在左上角，须经变换，才能以习惯的形式显示：1、原点 平移到（0，199）；2、绕 x 轴旋转 1800 第三节 基本图形的生成方法 1、点 点是构成图形的最基本元素，一般的软件都可以直接调用，对于其最底层的生成方法 作了解，不需自己编程。 2、直线段 在数学上，理想的直线是没有宽度的，由无数个点构成的集合。当我们对直线进行光 栅化时，只能在显示器所给定的有限个象素组成的矩阵中，确定最佳逼近于该直线的一组象 素，并且按扫描线顺序，对这些象素进行写操作，这就是通常所说的用显示器绘制直线或直 线的扫描转换。 ( ) ( ) = = n w w n w w y y /H x x /W = = = = a n w w a n w w y 199 y 199 y /H x 639 x 639 x /W = − = y 199 (1 y /H ) x 639 x /W b w w b w w
由于一个图中可以包含成千上万条直线，所以要求绘制算法应尽可能的快。本节我们介绍一个象素宽直线的三个常用算法：逐点法、数值微分法（DDA）和Bresenham算法。2.1逐点计算法假定直线的起点、终点分别为：PO（x0，yO），P1（x1，y1），且都为整数，则直线的方程为(y-y0)/ (x-x0)=(y1-y0)/(x1-x0)写成参数方程为X=x0+(x1-x0) tY=y0+ (yl-y0) t(0 ≤ t ≤ 1)令t=ti=i/nn=0,1n，可得到i点的方程：Xi=x0+(x1-x0)tiYi=y0+(yl-y0)ti(i=0, 1, n)(round(xi),round(yi))!则像素点为mi=（xi,yi）（即每画一个点就要作一次加法和乘法，存在工作量大的问题！！2.2数值微分(DDA)法已知过端点PO(xO，yO)，P1(x1，y1)的直线段L(PO，P1)，；直线斜率为画线过程从x的左端点x0开始，向x右端点步进，步长=1（个象素），计算相应的y坐标y=kx+B；取象素点（x，round（y)））作为当前点的坐标。计算yi+i = kxi+1+B= k.X;+B+kDx= y;+kDx当Dx =l; yi+i =y;+k即：当x每递增1，y递增k（即直线斜率）；Line:P0(0, 0)--P1(5,2)举例：用DDA方法扫描转换连接两点PO（O，O）和3P1（5,2）的直线段。x int(y+0. 5) y+0.5200011 00.4+0.5210.8+0.545311.2+0.50123421.6+0.5DDA算法小节1)增量算法：在一个选代算法中，如果每一步的x、y值是用前一步的值加上一个增量来获得，则称为增量算法。2）DDA算法就是一个增量算法。3）只要在开头做乘除法，每次只要做加法，计算量大大减小4）缺点：在此算法中，x或y必须是float，且每一步都必须对x或y进行舍入取整，不利于硬件实现2.3直线生成的Bresenham算法Bresenham算法是计算机图形学领域使用最广泛的直线扫描转换算法。该方法类似于中点法，由误差项符号决定下一个象素取右边点还是右上点。算法原理如下：过各行各列象素中心构造一组虚拟网格线。按直线从起点到终点的顺序计算直线与各垂直网格线的交点，然后确定该列象素中与此交点最近的象素。该算法的巧妙之处在于采用增量计算，使得对于每一列，只要检查一个误差项的符号，就可以确定该列的
由于一个图中可以包含成千上万条直线，所以要求绘制算法应尽可能的快。本节我们介 绍一个象素宽直线的三个常用算法：逐点法、数值微分法（DDA）和Bresenham算法。 2.1 逐点计算法 假定直线的起点、终点分别为：P0（x0,y0), P1(x1,y1)，且都为整数, 则直线的方程 为 (y-y0)/(x-x0)=(y1-y0)/(x1-x0) 写成参数方程为 X=x0+(x1-x0)t Y=y0+(y1-y0)t (0 ≤ t ≤ 1) 令t=ti=i/n n=0,1.n, 可得到i点的方程： Xi=x0+(x1-x0)ti Yi=y0+(y1-y0)ti (i=0, 1,.n) 则像素点为mi=（xi,yi） (round(xi), round(yi))! 即每画一个点就要作一次加法和乘法，存在工作量大的问题！！ 2.2 数值微分(DDA)法 已知过端点P0(x0, y0), P1(x1, y1)的直线段L(P0, P1),；直线斜率为画线过程从x的 左端点x0开始，向x右端点步进，步长=1(个象素)，计算相应的y坐标y=kx+B；取象素点(x, round(y))作为当前点的坐标。 计算yi+1 = kxi+1+B= k.xi+B+kDx = yi+kDx 当Dx =1; yi+1 = yi+k 即：当x每递增1，y递增k(即直线斜率)； 举例：用DDA方法扫描转换连接两点P0（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 DDA算法小节 1)增量算法：在一个迭代算法中，如果每一步的 x、y 值是用前一步的值加上一个增量 来获得，则称为增量算法。 2）DDA 算法就是一个增量算法。 3）只要在开头做乘除法，每次只要做加法，计算量大大减小 4）缺点：在此算法中，x 或 y 必须是 float，且每一步都必须对 x 或 y 进行舍入取整， 不利于硬件实现 2.3 直线生成的 Bresenham 算法 Bresenham算法是计算机图形学领域使用最广泛的直线扫描转换算法。该方法类似于中 点法，由误差项符号决定下一个象素取右边点还是右上点。 算法原理如下：过各行各列象素中心构造一组虚拟网格线。按直线从起点到终点的顺序 计算直线与各垂直网格线的交点，然后确定该列象素中与此交点最近的象素。该算法的巧妙 之处在于采用增量计算，使得对于每一列，只要检查一个误差项的符号，就可以确定该列的
所求象素。算法框架：根据直线的斜率选择变量在x方向或y方向上每次增加一个单位，另一个变量根据实际直线与像素点的距离最近来确定其增量为0或1。设直线过起点PA(XA,yA)，终点PB(XByB)，若xA<XB，则斜率m=(yB-yA)/(XB-XA)，且Pars0≤m≤1如果PA为原点（0，0），则v=mx确定（xi-1,yi-1）后，下一点（xi,yi-1）或（xi,yi）？取决于与直线的距离a=yi-mxi;b=mxi-yi-1b- a=mxi-yi-1- (yi-mx:)= 2mxi-2yi+1(IA.YA)若b-a>0，（xi,yi）像素点离直线近若b-a<0，（xi,yi-1）像素点离直线近图2-5Bresenham算法这样每点都要进行判断，由相应的乘法运算。改进算法将前式两边除以2，再加m-1得(b- a)/2+m-1=(2mxi-2yi+1)/2+m-1(1)= mxi-yi+m-1/2令ei'=(b-a)/2+m-1则 e'=mxi-yi+m-1/2(2)0 ≤yB-yA≤xB-XA,y的坐标y(x)=mxi将xo=XA，yo=yA代入（2）式：(3)eo’=y(xo)-yo+m-1/2=m-1/2当斜率m>1/2，eo≥0，下一个点应取为(xo+1,yo+1)当m<1/2，0>eo，下一个点应取为(xo+1,yo)同理对于(xi,yi)点e"≥0，下一个点应取为(xi+1,yi+1)e'<0，下一个点应取为(xi+1,y)根据（2）ei+1-e'=mxi+1-yi+I+m-1/2-(mxi-yi+m-1/2)=m-(yi+1-y)..ei+'=ei'+m-(yi+I-y.)即ei+'=ei'+m-1当ei'≥0(4)当ei<0Orei'+m两边乘2△x，即2△xei+1'=2△xei'+2y-2△x当ei≥0当ei<0(5)2△xei+2△y令2△xei=ei当ei≥0ei+1=ei+2△y-2△x当ei'<0(6)ei+2△y由（3）式得eo=2△y-△x，ei代替2△xe，避免了除法运算，用加法运算可提高运算速度。结论：Deg=2Ay-Ax,Xo=xA,yo=y,Ax=x-xA,Ay=yn-yA②对i=0到i=Ar-1，令×+1=x+1且Jyi+ = yi +1若e≥0，则(ei+1 =e +2 (Ay-Ax)[yi+I= yi若e<0,则ei+1 = e; +24y
所求象素。 算法框架:根据直线的斜率选择变量在x方向或y方向上每次增加一个单位，另一个变量 根据实际直线与像素点的距离最近来确定其增量为0或1。 设直线过起点PA (xA, yA), 终点PB(xB, yB)，若xA<xB, 则斜率m= (yB - yA)/(xB - xA), 且 0≤m≤1 如果PA 为原点（0，0），则y=mx 确定（xi-1,yi-1）后，下一点（xi, yi-1）或（xi, yi）？ 取决于与直线的距离a=yi-mxi ; b=mxi-yi-1 b - a=mxi-yi-1- (yi-mxi) = 2mxi-2yi+1 若b-a>0, （xi, yi）像素点离直线近 若b-a<0,（xi, yi-1）像素点离直线近 这样每点都要进行判断，由相应的乘法运算。 改进算法 将前式两边除以2，再加m-1得 (b – a)/2+m-1= (2mxi-2yi+1)/2+m-1 = mxi-yi+m-1/2 (1) 令 ei’=(b – a)/2+m-1 则 ei’ = mxi-yi+m-1/2 (2) 0 ≤ yB – yA ≤ xB - xA, y的坐标 y(xi)= mxi 将x0=xA, y0=yA 代入（2）式： e0’ = y(x0) – y0+m-1/2 = m-1/2 （3） 当斜率m>1/2， e0’ ≥0 ，下一个点应取为(x0+1, y0+1) 当m<1/2， 0 > e0’ ，下一个点应取为(x0+1, y0) 同理 对于(xi, yi)点 ei’ ≥0 ，下一个点应取为(xi+1, yi+1) ei’ < 0，下一个点应取为(xi+1, yi) 根据（2） ei+1’ - ei’ = mxi+1-yi+1+m-1/2 –( mxi-yi+m-1/2) =m- (yi+1-yi) ∴ei+1’ = ei’ + m- (yi+1-yi) 即ei+1’= ei’ + m- 1 当ei’ ≥0 Or ei’ + m 当ei’ < 0 （4） 两边乘 2△x， 即 2△xei+1’= 2△x ei’ + 2△y -2△x 当 ei’ ≥0 2△x ei’ + 2△y 当 ei’ < 0 （5） 令 2△x ei’ = ei ei+1= ei + 2△y -2△x 当 ei’ ≥0 ei + 2△y 当 ei’ < 0 （6） 由（3）式得 e0 = 2△y - △x ，ei 代替 2 △x ei’ ，避免了除法运算，用加法运算可提高运 算速度。 结论：