计算机图形学课程

单击此处编辑节标题,计算机图形学,计算机图形学,工程图学教学与研究中心,肖平阳,计算机图形学,第1章 计算机图形系统,第2章 图形变换,绪 论,下 页,总目录,上 页,结 束,第3章 数据结构,第4章 窗口与裁剪,计算机图形学,第5章 图案填充,第6章 隐线消除,计算机图形学,下 页,上 页,结 束,绪 论,随着计算机软、硬件的发展，计算机图形学已成为一门成熟的学科，在计算机应用领域占有重要内容地位。,总目录,计算机图形学的定义,ISO(国际标准化组织)对其定义为：计算机图形学是研究通过计算机将数据转换为图形，并在专用显示设备上显示的原理、方法和技术的学科。,计算机图形学的,IEEE,定义,Computer graphics is the art or science of producing graphical images with the aid of computer.,注：Institute of Electrical and Electronics Engineers (IEEE),美国电子和电气工程师协会,计算机图形学,下 页,上 页,结 束,计算机图形学发展简史,1950年,第一台图形显示器作为美国麻省理工学院（,MIT,）旋风,I,号（,Whirlwind I,）计算机的附件诞生了。该显示器用一个类似于示波器的阴极射线管（,CRT,）来显示一些简单的图形。,总目录,1958年,美国,Calcomp,公司由联机的数字记录仪发展成滚筒式绘图仪，,GerBer,公司把数控机床发展成为平板式绘图仪。,50年代末期,MIT,的林肯实验室在“旋风”计算机上开发,SAGE,空中防御体系，第一次使用了具有指挥和控制功能的,CRT,显示器，操作者可以用笔在屏幕上指出被确定的目标。,计算机图形学,下 页,上 页,结 束,1962年,MIT,林肯实验室的,Ivan E.Sutherland,发表了一篇题为“,Sketchpad,：一个人机交互通信的图形系统”的博士论文，首次使用“,Computer Graphics”,这个术语，证明了交互计算机图形学是一个可行的、有用的研究领域，从而确定了计算机图形学作为一个崭新的科学分支的独立地位。,总目录,1964年,MIT,的教授,Steven A. Coons,提出了被后人称为超限插值的新思想，通过插值四条任意的边界曲线来构造曲面。同在,60,年代早期，法国雷诺汽车公司的工程师,Pierre Bzier,发展了一套,Bzier,曲线、曲面的理论，成功地用于几何外形设计。,计算机图形学,下 页,上 页,结 束,70,年代是计算机图形学发展过程中一个重要的历史时期。光栅显示器的产生，图形学进入了第一个兴盛的时期，并开始出现实用的,CAD,图形系统。,70,年代，计算机图形学另外两个重要进展是真实感图形学和实体造型技术的产生。,总目录,从,80,年代中期以来，超大规模集成电路的发展，为图形学的飞速发展奠定了物质基础。计算机的运算能力的提高，图形处理速度的加快，使得图形学的各个研究方向得到充分发展，图形学已广泛应用于动画、科学计算可视化、,CAD/CAM,、影视娱乐等各个领域。,计算机图形学,下 页,上 页,结 束,计算机图形学研究的基本内容,图形通常由点、 线、面、体等几何元素和灰度、色彩、线型、线宽等非几何属性组成。,总目录,另一类是明暗图(Shading)，是以位图(Bitmap)形式存在的灰度信息，也就是通常所说的真实感图形。,从处理技术上来看，图形主要分为两类:,一类是基于线条信息表示的，如工程图、等高线地图、曲面的线框图等，含有几何属性，或者说更强调场景的几何表示，是由场景的几何模型和景物的物理属性共同组成的。,计算机图形学,下 页,上 页,结 束,在用计算机处理图形数据方面，主要分为三个领域：,图形显示、图像（,image,）,处理和图像模式识别。,总目录,一、图形显示,图形描述 点、线、面等 及其拓扑信息。,图形变换,二、三维变换、三维到二维、几何变换,和非几何变换等 。,图形运算 基本几何间的计算、裁剪、布尔运算等。,图形显示/输出 基本图形生成算法、消隐、绘图、光照模型等 。,图形输入 交互技术、参数化设计、造型技术等。,算法和算法复杂性分析 空间和时间等。,计算机图形学,下 页,上 页,结 束,二、,图像处理,对直观图像（以具有颜色信息的点阵来表示的图形），按图形由哪些点组成、点的灰度及色彩进行处理，增强其清晰度。,三、,图象模式识别,总目录,在算法研究方面，不单要求从数学上能够处理，还要求必须在计算机容量允许的条件下和用户能够容忍的时间内完成这些处理。因此，强调要研究占用机时少、占用存储量小的图形处理方法。,计算机图形学,下 页,上 页,结 束,本课程的设置内容,作为一门主要面向机械专业研究生的课程，着重讨论与图形变换、图案填充和隐线消除相关的原理与算法。,总目录,为使学生具备以下几个方面的能力打下基础：掌握图形生成、图形变换、图案填充和隐线消除的一般原理、方法和技术；编制计算机绘图程序；处理图形数据；进行更深入的计算机图形学研究。,授课中主要侧重软件方面，对硬件知识作一些必要的介绍。,第1章 计算机图形系统,第1章 计算机图形系统,下 页,章目录,上 页,结 束,计算机图形系统的功能,(1),计算功能,(2),存储功能,(3),交互功能,(4),输入功能,(5),输出功能,第1章 计算机图形系统,下 页,章目录,上 页,结 束,一、,硬件,1,计算机,2,输入设备：键盘、鼠标、图形输入板、扫描仪等,数字化仪是一种把图形转变成计算机能接收的数字形式专用设备。现在非常流行的汉字手写系统就是一种数字化仪。,三坐标测量仪，用于真实物体的三维信息的输入。,此外还有跟踪球、空间球、数据手套、光笔、触摸屏等。,3,输出设备,图形输出包括图形的显示和图形的绘制，图形显示指的是在屏幕上输出图形，图形绘制通常指把图形画在纸上，也称硬拷贝，打印机和绘图仪是两种最常用的硬拷贝设备。,第1章 计算机图形系统,下 页,章目录,上 页,结 束,光栅扫描式,CRT,监视器,阴极射线管（,CRT Cathode,RayTube,）的工作原理：高速的电子束由电子枪发出，经过聚焦系统、加速系统和磁偏转系统就会到达荧光屏的特定位置。荧光物质在高速电子的轰击下，将发出荧光。为保持显示一幅稳定的画面，必须不断地发射电子束。,第1章 计算机图形系统,下 页,章目录,上 页,结 束,刷新一次指电子束从上到下将荧光屏扫描一次，其扫描过程如下图所示。只有刷新频率高到一定值后，图象才能稳定显示。大约达到每秒,60,帧即,60Hz,时，人眼才能感觉到屏幕不闪烁，要使人眼觉得舒服，一般必须有,85Hz,以上的刷新频率。,有些扫描速度较慢的显示器，为了能得到好的显示效果，采用一种叫隔行扫描的技术。当然这样的技术和真正逐行扫描的效果还是有差距的。,彩色,CRT,显示器的荧光屏上涂有三种荧光物质，它们分别能发红、绿、兰三种颜色的光。而电子枪也发出三束电子来激发这三种物质。如果每一个电子枪都有,256,级（,8,位）的强度控制，那么这个显象管所能产生的颜色就是我们平时所说的,24,位真彩色了。,第1章 计算机图形系统,下 页,章目录,上 页,结 束,点距和分辨率,点距是两个像素（光点）之间的距离，一般为,0.28,0.32mm,。,分辨率是指屏幕上能有多少像素。比如,1024768,的含义就是一行有,1024,个像素，一列有,768,个像素。,第1章 计算机图形系统,下 页,章目录,上 页,结 束,LCD,液晶显示器,LCD,（,Liquid Crystal Display,）液晶显示器。,基本原理,:,液晶是一种介于液体和固体之间的特殊物质，它具有液体的流态性质和固体的光学性质。当液晶受到电压的影响时，就会改变它的物理性质而发生形变，此时通过它的光的折射角度就会发生变化，而产生色彩。,液晶屏幕后面有一个背光，这个光源射出的光线先穿过第一层偏光板，再来到液晶体上，而当光线透过液晶体时，就会产生光线的色泽改变，从液晶体射出来的光线，还必得须经过一块彩色滤光片以及第二块偏光板。由于两块偏光板的偏振方向成,90,度，再加上电压的变化和一些其他的装置，液晶显示器就能显示我们想要的颜色了。,第1章 计算机图形系统,下 页,章目录,上 页,结 束,点距和分辨率,液晶屏幕的点距就是两个液晶颗粒（光点）之间的距离。,分辨率在液晶显示器中的含义并不和,CRT,中的完全一样。通常所说的液晶显示器的分辨率是指其真实分辨率，比如,1024768,的含义就是指该液晶显示器含有,1024768,个液晶颗粒。只有在真实分辨率下液晶显示器才能得到最佳的显示效果。其它较低的分辨率只能通过缩放仿真来显示，效果并不好。而,CRT,显示器如果能在,1024768,的分辨率下能清晰显示的话，那么其它如,800600,，,640480,都能很好地显示。,第1章 计算机图形系统,下 页,章目录,上 页,结 束,二、,软件,1,基本子程序驱动设备的程序,2,功能子程序完成通用绘图功能。如画线等,3,应用子程序,为用户专门设计的子程序，用于特定专业，往往是用户自行开发。,下 页,章目录,上 页,结 束,第2章 图形变换,图形变换的基本原理是：,（,1,）图形的拓扑关系不变；,（,2,）图形的几何关系可以改变。,所谓图形拓扑关系不变是指图形的连边规则不变，即原来是相邻的点变换后依然相邻，原来不相交的线变换后依然不相交。,所谓图形的几何关系可以改变是指图形的点与点之间的位置和距离可以改变。,第2章,图形变换,下 页,章目录,上 页,结 束,用线模型描述物体的图形。图形由直线和曲线来表述。计算机图形中的曲线是由短直线表示的。直线可由两点完全确定。因此，图形的几何信息构成所有直线的点集的坐标。,所有的变换均基于点的变换。,注意：变换前后都是在同一个坐标系内。用 x、y、z 表示变换前的点坐标，用 X、Y、Z 表示变换后的点坐标。,第2章,图形变换,21二维图形变换,点用行向量（x,y）来表示。,一、平移变换,点 p (x,y) 沿坐标轴方向移动一定距离,xw, yw, 2-1 二维,变换,下 页,章目录,上 页,结 束,数学表示：X = x + xw,Y = y + yw 其中xw, yw 称为平移常数。,若用二维矩阵表示，则有, X, Y = x, y,= ax+cy, bx+dy ,ax+cy x + xw bx+dy y + yw,无法用二维矩阵表示。, 2-1 二维,变换,下 页,章目录,上 页,结 束, 2-1 二维,变换,为了能统一描述图形变换，在计算机图形学中常采用齐次变换矩阵进行变换。,一般地，用一个n+1维坐标表示一个n维的点的方法称为齐次坐标法。,用齐次坐标法，将点向量表示为x y 1, XY1 = x y1 ,下 页,章目录,上 页,结 束,变换矩阵, 2-1 二维,变换,二、比例变换,通过变换图形中两点间的距离，得到放大、缩小、拉伸或压缩图形的效果。,变换前后两点与基准点间的距离的长度之比称为比例因子。沿X、Y轴方向分别定义为Sx，Sy。,以原点为基准点，则数学表示为,（,X 0 ）/（x ,0,）,= Sx,X = x Sx,同样： Y = y Sy,下 页,章目录,上 页,结 束, 2-1 二维,变换,Sx 1 X向距离增大,Sx 1 X向距离减小,Sx 1 X向距离保持不变,Sx Sy 等比例变换，图形放大或缩小,Sx Sy 1恒等变换,Sx Sy Sx 0Sy 0图形产生拉伸或压缩变形,下 页,章目录,上 页,结 束,矩阵方法表示有两种形式：,变换矩阵Ts1 =,X Y 1 = x y 1 Ts1 = x Sx y Sy 1 ,变换矩阵Ts2 =,X Y H = x y 1 ,Ts2 = x y s ,其中：,H = s, 2-1 二维,变换,下 页,章目录,上 页,结 束, 2-1 二维,变换,对第二种变换，要其结果进行处理，使第三个元素为,1,。处理的方法是用,1/s,乘以各元素，从而得到,X,Y,1 = x/s , y/s, 1 ,这种方法称为齐次坐标的正常化。,下 页,章目录,上 页,结 束,=,1 / S,正常化处理后，成为比例因子为,1 / S的等比例变换矩阵, 2-1 二维,变换,下 页,章目录,上 页,结 束,几何含义：, 2-1 二维,变换,下 页,章目录,上 页,结 束,比例变换不动点,比例变换前后位置不动的点称为比例变换不动点，一般在原点，但它可以是任意点(xp, yp)。, 2-1 二维,变换,下 页,章目录,上 页,结 束,以任意点作为比例变换不动点进行比例变换,步骤：（1）平移P点至原点。平移常数为,xp,yp。,（2）相对于原点进行比例变换。,（3）反平移P点。平移常数为xp, yp。,变换矩阵, 2-1 二维,变换,下 页,章目录,上 页,结 束,三、旋转变换,数学方法：,x = r cos , y= r sin ,X = r cos (+ ),= r cos cos - r sin sin ,= x cos - y sin ,Y = r sin (+ ),= r cos sin + r sin cos = x sin + y cos , 2-1 二维,变换,下 页,章目录,上 页,结 束,矩阵方法：, 2-1 二维,变换,下 页,章目录,上 页,结 束,绕任意点,P,（,xp,yp,）旋转,角,步骤：（1）平移P点至原点。平移常数为xp,yp。,（2）绕原点,旋转角。,（3）反平移P点。平移常数为xp,yp。,变换矩阵, 2-1 二维,变换,下 页,章目录,上 页,结 束,四、,对称变换（镜像变换）,相对于一点或一直线。, 2-1 二维,变换,下 页,章目录,上 页,结 束,数学方法,：,相对于,x,轴,X,x,Y,y,相对于,y,轴,X,x,Y,y,相对于坐标原点,X,x,Y,y, 2-1 二维,变换,下 页,章目录,上 页,结 束,矩阵方法：,相对于,x,轴,相对于,y,轴,相对于坐标原点, 2-1 二维,变换,下 页,章目录,上 页,结 束,相,对于任意直线的对称变换,我们用对称轴的一个端点,P,的坐标和该对称轴与,X,轴的夹角,来表示这根对称轴,PS,。,要将图形中的,M,点相对于,PS,轴对称变换到,N,点。, 2-1 二维,变换,下 页,章目录,上 页,结 束,步骤：,（1）平移P点至P1点，与原点重合。平移常数为xp,yp。,（2）绕原点顺时针旋转,角，使P2S2与X轴重合。,（3）将M2点相对于X轴进行对称变换，得到N2点。,（4）将N2点绕原点逆时针旋转,角，得到N1点。,（5）反平移P2点，与P点重合。平移常数为xp,yp。,得到N点。, 2-1 二维,变换,下 页,章目录,上 页,结 束,五、错移变换,错移变换使图形产生扭变。,1,沿,x,轴错移,这种变换使点的,X,向坐标产生与其,Y,坐标相关的错移。, 2-1 二维,变换,下 页,章目录,上 页,结 束,数学方法：,X,x + shxy,Y,y,其中,shx 0为x,轴方向错移系数,例：,shx,1,点,错移前,错移后,x坐标,y坐标,X坐标,x + shxy,Y坐标,P1,1,1,1 + 1,1=2,1,P2,1,2,1 + 1,2=3,2,P3,2,2,2 + 1,2=4,2,P4,2,1,2 + 1,1=3,1, 2-1 二维,变换,下 页,章目录,上 页,结 束,矩阵方法：,2,沿,y,轴错移,这种变换使点的,Y,向坐标产生与其,X,坐标相关的错移。,数学方法：,X,x,Y,shy x,+,y,shy 0为y,轴方向错移系数, 2-1 二维,变换,下 页,章目录,上 页,结 束, 2-1 二维,变换,下 页,章目录,上 页,结 束,矩阵方法：,矩阵级联,多个变换可以组合成新的变换，用矩阵相乘（矩阵的级联）而产生一个具有新的功效的单一变换矩阵。,矩阵级联是有序的。例如一个变换是平移和旋转，先平移后旋转的效果和先旋转后平移的效果，一般情况下是不同的。, 2-2 三维,变换,下 页,章目录,上 页,结 束,22三维图形变换,用右手系。变换前后都是在同一个坐标系内。,一、三维平移变换,数学方法：X = x + Xw,Y= y + Yw,Z= z + Zw,矩阵方法：, 2-2 三维,变换,下 页,章目录,上 页,结 束,二、三维比例变换,与二维比例变换类似。,数学方法：,一般以原点为基准点，则有,X = Sx x,Y= Sy y,Z= Sz z,矩阵方法表示有两种形式：, 2-2 三维,变换,下 页,章目录,上 页,结 束,比例变换不动点,以任意点(xp, yp, zp)作为比例变换不动点进行比例变换,步骤：（1）平移P点至原点。平移常数为xp,yp,zp。,（2）相对于原点进行比例变换。,（3）反平移P点。平移常数为xp,yp,zp。,变换矩阵, 2-2 三维,变换,下 页,章目录,上 页,结 束,三、三维旋转变换,三维旋转是绕空间一直线的旋转。,旋转方向：沿坐标轴正方向朝原点看去，逆时针为正。,数学方法：,绕X轴,X = x,Y = y cos - z sin ,Z = y sin + z cos ,绕Y轴,X = x cos + z sin ,Y = y,Z = -x sin + z cos ,绕Z轴,X = x cos - y sin ,Y = x sin + y cos ,Z = z, 2-2 三维,变换,下 页,章目录,上 页,结 束,矩阵方法：,绕X轴,绕Y轴,绕Z轴, 2-2 三维,变换,下 页,章目录,上 页,结 束,三维绕任意直线旋转,角,设任意直线由,P1（x1, y1, z1），,P2（x2, y2, z2）,两点确定。,思路：先将直线变换到与某坐标轴重合，然后绕坐标轴旋转角，最后将直线再变换回初始位置。,为叙述简便，,令a = x2x1,b = y2,y1,c = z2,z1, 2-2 三维,变换,下 页,章目录,上 页,结 束,用矩阵方法步骤：7,步,（,1,） 平移,P1点至原点(P1)，移常数为x1,y1,z1。,则有 P2（a, b, c）,（2）绕X轴旋转,1角，使直线转,到,X,Z,平面上。, 2-2 三维,变换,下 页,章目录,上 页,结 束,为确定sin1和cos1，先将直线投影到YZ平面上，其投影长度为 l 1。则有 P2”（0, b, c）。, 2-2 三维,变换,下 页,章目录,上 页,结 束, 2-2 三维,变换,下 页,章目录,上 页,结 束,直线转到,X,Z,平面上，此时有：P2(a, 0, l1), 2-2 三维,变换,下 页,章目录,上 页,结 束,（3）绕Y轴,旋转2角。, 2-2 三维,变换,下 页,章目录,上 页,结 束,（4）绕Z轴,旋转角。,（5）绕Y轴旋转2角。,（6）绕X轴旋转1角。,（7）反平移P点至初始位置，平移常数为x1, y1，z1。, 2-2 三维,变换,下 页,章目录,上 页,结 束,四、三维对称（镜像）变换,相对于,xoy,平面,相对于,xoz,平面,相对于,yoz,平面, 2-2 三维,变换,下 页,章目录,上 页,结 束,相对于,X,轴,相对于,Y,轴,相对于,Z,轴,相对于任意平面,S,：,思路：先将S面上任意点平移至原点；,用S面内过此点的、与某坐标面的交线作为任意旋转轴，将S面旋转到与某坐标面重合；,相对于此坐标面进行对称变换；,然后反旋转，反平移，将S面再变换回初始位置。, 2-2 三维,变换,下 页,章目录,上 页,结 束,五、三维错移变换,设有一矩阵为,三维错移变换矩阵，,a,b,c,d,e,f,为错移系数。,3X3子矩阵中的第一列元素使物体产生轴方向的错切；第二列元素使物体产生轴方向的错切；第三列元素使物体产生轴方向的错切。,沿每个坐标方向的错移都可分为三种情况。, 2-2 三维,变换,下 页,章目录,上 页,结 束,沿,x,轴方向,1,沿,x,轴方向含,y,错移,变换矩阵为,X = x + c * y Y = y, Z = z, 2-2 三维,变换,下 页,章目录,上 页,结 束,点,错移前,错移后,x+c*y,x坐标,y坐标,z坐标,X坐标,P1,1,0,0,1 + 1,0=1,P2,1,1,0,1 + 1,1=2,P3,1,1,1,1 + 1,1=2,P4,1,0,1,1 + 1,0=1,P5,0,0,0,0,P6,0,1,0,0 + 1,1=1,P7,0,1,1,0 + 1,1=1,P8,0,0,1,0 + 1,0=0, 2-2 三维,变换,下 页,章目录,上 页,结 束,2,沿,x,轴含,z,错移,变换矩阵为,X = x + e * z, Y = y, Z = z, 2-2 三维,变换,下 页,章目录,上 页,结 束,点,错移前,错移后,x+e*z,x坐标,y坐标,z坐标,X坐标,P1,1,0,0,1 + 1,0=1,P2,1,1,0,1 + 1,0=1,P3,1,1,1,1 + 1,1=2,P4,1,0,1,1 + 1,1=2,P5,0,0,0,0,P6,0,1,0,0 + 1,0=0,P7,0,1,1,0 + 1,1=1,P8,0,0,1,0 + 1,1=1, 2-2 三维,变换,下 页,章目录,上 页,结 束,3,沿,x,轴含y,z,错移,变换矩阵为,X = x + c * y + e * z ,Y = y,Z = z, 2-2 三维,变换,下 页,章目录,上 页,结 束,点,错移前,错移后,x+c*y+e*z,x坐标,y坐标,z坐标,X坐标,P1,1,0,0,1 + 1,0,+,1,0=1,P2,1,1,0,1 + 1,1,+,1,0=2,P3,1,1,1,1 + 1,1,+,1,1=3,P4,1,0,1,1 + 1,0,+,1,1=2,P5,0,0,0,0,P6,0,1,0,0 + 1,1,+ 1,0=1,P7,0,1,1,0 + 1,1,+ 1,1=2,P8,0,0,1,0 + 1,0,+ 1,1=1, 2-2 三维,变换,下 页,章目录,上 页,结 束,沿其它方向与之类似。, 2-2 三维,变换,下 页,章目录,上 页,结 束,点,错移前,错移后,x+c*y,错移后,x+e*z,错移后,x+c*y+e*z,x坐标,y坐标,z坐标,X坐标,X坐标,X坐标,P1,1,0,0,1 + 1,0=1,1 + 1,0=1,1 + 1,0,+,1,0=1,P2,1,1,0,1 + 1,1=2,1 + 1,0=1,1 + 1,1,+,1,0=2,P3,1,1,1,1 + 1,1=2,1 + 1,1=2,1 + 1,1,+,1,1=3,P4,1,0,1,1 + 1,0=1,1 + 1,1=2,1 + 1,0,+,1,1=2,P5,0,0,0,0,0,0,P6,0,1,0,0 + 1,1=1,0 + 1,0=0,0 + 1,1,+ 1,0=1,P7,0,1,1,0 + 1,1=1,0 + 1,1=1,0 + 1,1,+ 1,1=2,P8,0,0,1,0 + 1,0=0,0 + 1,1=1,0 + 1,0,+ 1,1=1, 2-3,投影变换,下 页,章目录,上 页,结 束,23投影变换,一、正投影变换,工程制图中常用的三视图，是由空间中一个立体向,3,个互相垂直的投影面作正投影得到的。这三个投影面分别称为：正投影面（,V,面）、侧投影面（,W,面）、水平投影面（,H,面）。, 2-3,投影变换,下 页,章目录,上 页,结 束,使用用户坐标系（X，Y，Z）描述物体。一般情况下用户坐标系的原点不在世界坐标系的原点上，首先要用平移变换将用户坐标变换成世界坐标,，然后向坐标面进行投影，再展开到一个平面。, 2-3,投影变换,下 页,章目录,上 页,结 束,投影到坐标面,压缩点集的某个坐标,正面投影-压缩到X-Z坐标面,Xv= x Yv= 0 Zv= z,侧面投影-压缩到Y-Z坐标面,Xw= 0 Yw= y Zw= z,水平投影-压缩到X-Y坐标面,Xh= x Yh= y Zh= 0, 2-3,投影变换,下 页,章目录,上 页,结 束,矩阵方法：,正面投影：,侧面投影：,水平投影：, 2-3,投影变换,下 页,章目录,上 页,结 束,2,展开到一个平面,使各投影都处于正面投影面内。,正面投影-不动,X Xv Y = 0 Z = Zv,侧面投影-绕Z轴逆时针转动90,X Yw Y = 0 Z = Zw,水平投影-绕X轴顺时针转动90,X Xh Y = 0 Z = Yh,最后，还要投影到投影坐标系中。, 2-3,投影变换,下 页,章目录,上 页,结 束,展开到一个平面,使各投影都处于正面投影面内。,正面投影-不动,X Xv Y = 0 Z = Zv,侧面投影-绕Z轴逆时针转动90,X Yw Y = 0 Z = Zw,水平投影-绕X轴顺时针转动90,X Xh Y = 0 Z = Yh,第3章 数据结构,第3章 数据结构,下 页,章目录,上 页,结 束,随着计算机技术的迅速发展，计算机的应用领域已从以数值计算为中心转移到以数据处理为中心。处理的数据也不再只是简单的数值，而是还有图形、图像等复杂的数据。为了使计算机更快速、更有效地处理数据，就必须用有效的、合理的数据结构来组织、存储数据。,数据结构是在一定规则下数据的组织形式。研究数据结构，主要是研究数据之间的逻辑结构（数据之间的关系）和物理结构（数据在计算机中的存储结构）以及这两种结构之间的相互关系，并利用这些关系设计相应的算法。,第3章 数据结构,章目录,结 束,数据的逻辑结构是指从具体问题中抽象出来的数据之间的内在关系。,逻辑结构可分为以下三类：,1线性结构,该结构中的数据元素之间存在着一对一的顺序关系。,2树形结构,该结构中的数据元素之间存在着一对多的关系。,3网状结构,该结构中的数据元素之间存在着多对多的关系。,后两类又称为非线性结构。,下 页,上 页,第3章 数据结构,章目录,结 束,数据的物理结构是指数据在存储器中的存储方式，主要有以下两种不同的存储结构,1顺序存储,把逻辑上相邻的数据元素存储在物理位置上相邻的存储单元中，数据间的逻辑关系由存储单元的邻接关系来表示。,2链状存储,可以将数据元素存储在任意位置的存储单元中。通过指针来表示数据元素之间逻辑关系。,下 页,上 页,第3章 数据结构,章目录,结 束,在计算机图形学中，需要处理大量的图形信息。图形信息主要分为两种：一种是图形的几何信息，指的是形体在空间中的位置、大小尺寸。另一种是拓扑信息，指的是各形体要素（点、线、面等）的数量及其相互间的连接关系。如何组织这些信息，使计算机处理这些信息时可以节省存储单元，加快存取和处理速度，是图形数据结构所要解决的问题。,对于图形数据结构，主要有以下的基本要求：,能够记录图形的几何信息和拓扑信息。,管理方便，即便于查找、增删和修改数据。,较少占用存储单元。,可以快速处理数据。,下 页,上 页,第3章 数据结构,章目录,结 束,常用数据结构,1 线性表结构,线性表是一种最简单、最基本的线性数据结构。所谓线性是指数据元素之间存在“一对一”的关系，具有不多于一个的前趋和后继。线性表是由一组类型相同的数据元素按线性次序排列而成的。它的逻辑结构可以表示为a1,a2,a3an。数据的逻辑结构的下标与物理结构中的存储单元的地址存在着一一对应的关系。它是一种静态结构。,顺序表存储结构的运算,对线性表的数据元素不仅可以进行访问，还可以进行插入、删除等运算，但这些运算是定义在逻辑结构上的，通过存储结构具体实现。,下 页,上 页,第3章 数据结构,章目录,结 束,表示数据元素的单元称为结点。把线性表的结点按逻辑次序依次存放在一组按顺序连续排列的存储单元中。用这种方法存储的线性表称为顺序表。,顺序表中相邻的元素在计算机中的存储位置也相邻, 每个结点占用的存储空间的大小也相同。由此可以很容易地确定线性表中的某个结点在存储单元中与初始地址的相对位置。,只要知道表中初始结点的内存地址ad和每个结点在计算机中占用存储单元的长度 c，则可计算出第 i 个结点,ai,的地址,LOC,(,ai,) = ad + (i-1)c,也就是说，结点,ai,的存储地址是该结点在表中的位置,i,的线性函数，可以在相同时间内求出任一结点的存储地址，因此顺序表是一种随机存取结构。,下 页,上 页,第3章 数据结构,章目录,结 束,插入运算,顺序表插入运算实际上是指在顺序表下标为i-1 和i 的结点之间插入一个值为x 的新结点，使长度为n 的顺序表变成长度为n1 的顺序表,该运算的步骤如下：,（1）将,ai,an,之间的所有结点依次后移，为新元素空出第 i 个位置。,（2）将新结点x 插入到第 i 个位置。,顺序表上的插入运算，时间主要消耗在结点的移动上。所以当,n,较大时，算法的效率较低。,下 页,上 页,删除运算,顺序表结点删除运算是指在顺序表中删除下标为i 的结点，使得长度为n 的顺序表变成长度为n-1 的顺序表。,顺序表删除结点运算的步骤如下：,将,ai,+1,an,之间的结点顺序依次向前移动。,在线性表的顺序存储结构中，其特点是存取表方便。但也有其缺点。例如，进行插入和删除运算时需移动大量的结点、效率较低等。,数组结构是线性表结构，常采用顺序存储结构，也有线性表的优、缺点。,第3章 数据结构,章目录,结 束,下 页,上 页,第3章 数据结构,结 束,链式存储结构。,线性表的链式存储结构，也称为链表。其存储方式是：在计算机内存中利用存储单元（不要求连续）来存放结点的值及它在内存中的地址，各个结点的存放顺序及位置可以以任意顺序进行，原来相邻的结点在计算机内存中的存储位置不一定相邻，从一个元素查找下一个元素必须通过地址（指针）才能实现，因此它不能像顺序表那样随机访问，而只能按顺序访问。,章目录,下 页,上 页,第3章 数据结构,结 束,单链表结构,链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址信息，这个信息称为指针。这两部分信息就组成了链表中的结点结构：,其中：,data,称为数据域，用来存放结点的值；,link,称为指针域，用来存放结点的直接后继的地址。利用每个结点的指针域就可以将,n,个结点按其逻辑次序连成一个链表，由于这种链表中每个结点只含有一个指针域，故称为单链表。,data,link,章目录,下 页,上 页,第3章 数据结构,结 束,由于单链表中每个结点的存储地址是存放在其直接前趋的指针域中，又整个链表应从第一个结点开始，但第一个结点没有直接前趋，故设一个头指针（head）指向开始结点；而最后一个结点没有直接后继，故终端结点的指针域应为空，即NULL（在图中可用符号“”来表示）。,章目录,下 页,上 页,第3章 数据结构,结 束,单链表的基本运算,单链表与顺序表不同。顺序表在建立时，已定义好此顺序表的界限，并分配给它一块连续的存储单元，而单链表的结点数在定义前是不确定的，单链表中的元素也不是顺序安排的，任意两个结点的存储位置之间没有固定的联系，而是由指针域来表示各结点的前后邻接关系。因此，在单链表中，若要找下标为i 的结点，就必须从第一个结点开始，顺着指针域往下查找。对链表进行插入、删除等运算时，通常也需要经过查找才能确定其存储位置。,章目录,下 页,上 页,第3章 数据结构,结 束,建立单链表,无论对单链表进行何种运算，首先必须建立该链表。链表的建立步骤为：,（1）通过某种程序语言提供的函数建立第一个结点所需的存储空间，使指针变量p指向该结点，且将该结点的指针域置为空。,（2）将表头指针head 和表尾指针r 指向第一个结点p。从而建立了头结点,（3）申请另一个结点，将指针变量p 指向该结点，并对其数据域赋值，置其指针域为空。,（4）链接新结点，并修改表尾指针，从而在链表中建立了一个新结点。,（5）重复执行步骤（2）、（3）、（4），即可创建整个单链表。,章目录,下 页,上 页,第3章 数据结构,结 束,单链表中结点的删除,设删除运算要将单链表中删除第 i 个结点。,只要将第i结点的指针域中的内容（指向第i1 结点）置于第i1结点的指针域中。,i1,L,i1,i,L,i,i1,L,i,i,L,i,删除前,删除后,章目录,下 页,上 页,第3章 数据结构,结 束,单链表中结点的插入,设插入运算要将值为x 的新结点插入到表的第 i 个位置上，即插入到,第,i1结点与,第,i 结点之间。,首先从备用存储空间中取出一个结点，指向这个结点的指针为Lx。将第i1结点的指针域中的内容（指向第i 结点）置于新结点的指针域中，再将Lx置于第i1结点的指针域中。,i1,L,i1,i1,L,x,i,L,i,插入前,插入后,Lx,章目录,下 页,上 页,第3章 数据结构,结 束,循环链表,单链表结点之间是用一个指针域链接，其终端结点的指针域的值为Nil，表示单链表的结束。若将单链表的终端结点的指针域指向头结点，则整个链表头尾结点相链形成一个环，从而就构成了循环链表。,循环链表的主要优点是从表中任一结点出发，都能通过后移操作来扫描整个链表（对单链表而言，则只能从头结点开始）。,循环链表上的操作与前面讨论的单链表的操作基本一致，差别仅仅在于算法中控制循环中止的条件不是判断指针是否为空，而是判断指针是否指向头指针。,章目录,下 页,上 页,双向链表,在循环链表中，每个结点只含有一个指向其后继的指针域。若想快速确定一个结点的前趋，则可以在单链表的基础上，每个结点再加上一个指针域，存储其前趋的地址，这样就构成了双向链表。,链表中所有结点通过LL和RL两个指针链接在一起，加上头结点，构成一个双向链表。,由于双向链表是一种对称结构，每个结点既有指向其前趋的指针域，又有指向其后继的指针域，因此与单链表相比，要在双向链表中查找一个已知结点的前趋和后继要方便得多。,第3章 数据结构,结 束,LL,Data,RL,章目录,下 页,上 页,第3章 数据结构,结 束,树,树的定义,树是由,n,(,n, 0) 个结点组成的有限集合T，当T 非空时满足如下两个条件：,(1)有且仅有一个特定的称为根(Root)的结点；,(2) 其余的结点可分为,i,(,i, 0) 个互不相交的有限集合T1,Ti,这些集合中的每一个又都是一棵树，称为根的子树。,树的每个结点都是此树的某个子树的根。,树形结构描述的是层次关系，树的结点之间存在一对多的关系。,章目录,下 页,上 页,第3章 数据结构,结 束,基本术语,1,父结点、子结点、边,若结点y 是结点x 的一棵子树的根，则x 称为y 的父结点，y 称为x 的子结点。,2,兄弟结点,具有同一父结点的子结点之间互称为兄弟结点。,3,结点的层,规定根结点的层数为1，其它结点的层数等于其父结点的层数加1。树中结点的最大层数称为树的高度或树的深度。,章目录,下 页,上 页,第3章 数据结构,结 束,4,结点的度数、树的度数,一结点所具有的子结点的个数称为该结点的度数。树中度数最大的结点的度数称为树的度数。,5,叶结点,度数为0 的结点称为叶结点,章目录,下 页,上 页,第3章 数据结构,结 束,二叉树,二叉树是树形结构的一种最常见的类型，许多实际问题抽象出来的数据结构往往就是二叉树。,二叉树的定义,二叉树是n个结点,(,n, 0) 的有限集合,其结点度数最大为2。子结点有序，分为左和右子结点。,章目录,下 页,上 页,第3章 数据结构,结 束,一般的树能转化为二叉树。其方法是：在各兄弟结点之间加一连线，再把各结点与其子结点（除了最左的子结点外）的连线去掉。左指针指向下一层的首结点，右指针指向同层的下一结点。,章目录,下 页,上 页,第3章 数据结构,结 束,由于树形结构比线性结构更强调灵活的变化，所以一般情况下二叉树采用双向链表存储结构。,章目录,下 页,上 页,第3章 数据结构,结 束,作业：,作出事件的二叉树，画出描述它的结点指针图结构。,一装配体，零件，面，线，点。,章目录,下 页,上 页,第4章,窗口与裁剪,第4章,窗口与裁剪,定义,投影坐标系：投影图所在平面的坐标系，一般是直角坐标系，无限大。,窗口：投影坐标系中限定图形范围的界限，一般取矩形。,设备坐标系：图形输出设备输出图形区域的坐标系，一般是直角坐标系，其大小和单位与具体设备有关。,视区：设备输出图形区域中用以再现窗口内容的区域，一般与窗口是类似形。,纵横比,：显示器的象素间距在纵横方向上并不一致。象素纵向间距与横向间距长度之比称为纵横比。,SL,纵向间距 / 横向间距,结 束,章目录,下 页,上 页,第4章,窗口与裁剪,窗口到视区的变换,设在投影坐标系中定义一个窗口，其左下角坐标为,(xw1, yw1),，右上角坐标为,(xw2, yw2),，,窗口内任意点P,(xp, yp),；,在设备坐标系中定义一个视区，其左下角坐标为,(xv1, yv1),，,右上角坐标为,(xv2, yv2),，,视区内对应点P,(xp, yp),。,结 束,章目录,下 页,上 页,为了保证窗口内点相对于窗口与视区内对应点相对于视区的比例关系，坐标之间应当满足下列关系：,窗口内点到窗口左边界的距离与窗口长度之比等于视区内点到视区左边界的距离与视区长度之比；,窗口内点到窗口下边界的距离与窗口高度之比等于视区内点到视区下边界的距离与视区高度之比。,第4章,窗口与裁剪,结 束,章目录,下 页,上 页,第4章,窗口与裁剪,其中：,l-,视区长l- 窗口长,h- 视区高h- 窗口高,Sx、Sy 分别是由的X方向和Y方向的比例变换因子。,经整理，有,xp = Sx ( xp xw1 ) + xv1,yp = Sy ( yp yw1 ) + yv1,结 束,章目录,下 页,上 页,第4章,窗口与裁剪,用矩阵方法表示这个变换：,令,投影坐标系原点与坐标系原点重合，首先将窗口左下角点平移至原点，然后进行比例变换，使窗口变到与视区同样大小，再将其左下角点平移至视区原始左下角点处。,结 束,章目录,下 页,上 页,第4章,窗口与裁剪,结 束,章目录,下 页,上 页,第4章,窗口与裁剪,一般情况下，SxSy，变换后会产生拉压变形。为了保持原形，应当使Sx1Sy1S。为了在视区内能够把窗口内容完全显示出来，应当有 S = min ( Sx, Sy)。,结 束,章目录,下 页,上 页,第4章,窗口与裁剪,如果设备坐标系的X，Y轴单位长度不相等，还要考虑纵横比处理。,X = x SL,Y = y,结 束,章目录,下 页,上 页,第4章,窗口与裁剪,作业1: 编程：在用户坐标系中描述五棱柱，将用户坐标系原点平移到世界坐标系的点（10,10，10）处，在世界坐标系下投影成三视图。再以三视图原点为圆心，画一个圆（R150）和十字线。,结 束,章目录,下 页,上 页,第4章,窗口与裁剪,三、裁剪,确定图形在显示区之内部分的过程称为裁剪。,裁剪(Clipping)问题是计算机图形学的基本问题之一。,裁剪的边界可以是任意多边形，但常用的裁剪边界是矩形。,1,直线段裁剪,因为任何图形都可以用直线段来描述，从而直线段的裁剪问题就成为裁剪的基础。,直线两端点相对窗口的位置与线段可见性的关系,凸多边形定义：若连接多边形内的任意两点的直线完全处于多边形内，则此多边形称为凸多边形。,结 束,章目录,下 页,上 页,第4章,窗口与裁剪,由于窗口是一个凸多边形，因此，直线在窗口内部最多为一段。直线段的可见部分可简单地由决定两个端点的方法确定。,（,1,）若直线两个端点完全在窗口内，则直线完全在窗口内，完全可见,（,2,）若直线两个端点完全在窗口外，有四种可能：,直线完全在窗口外,不可见,直线与窗口相交于窗口角点,不可见,结 束,直线与窗口边线相交,有一可见段,直线与窗口边线重合,有一可见段,（,3,）若直线只有一个端点在窗口内，有两种可能：,直线与窗口边线相交,有一可见段,直线与窗口边线重合,有一可见段,章目录,下 页,上 页,第4章,窗口与裁剪,Cohen-Sutherland,裁剪算法编码裁剪法,算法思想：扩展窗口的边线，将图形平面分成九个区域。对窗口外每个区域赋予编码。根据线段端点坐标判断其所在区域并赋予相应的编码。如果端点位于窗口边线上，则认为点在靠近窗口的那个区域中。对部分可见的线段，求其与窗口边线的交点，去掉不可见部分。,结 束,章目录,下 页,上 页,第4章,窗口与裁剪,裁剪一条线段时，若直线两个端点完全在窗口内（编码为空），则线段完全可见；若直线两个端点的编码至少有一个相同的方向（例如,AB,直线都有下方向），则线段完全不可见。,否则，按第三种情况处理。求出线段与窗口一条边线的交点。此窗口边线把平面分成两个区域，一个区域包含窗口，我们把它广义地称为窗口内部区域，把另一个区域广义地称为窗口外部区域。求交后，把线段在窗口外的部分去掉。对剩余部分重复上述处理，直至剩余线段完全可见或完全不可见。如图所示，CD直线若用窗口左边线求交，交点为E，则CE被认为是在窗口外。,结 束,章目录,下 页,上 页,第4章,窗口与裁剪,求交时，利用直线的点斜式方程。先用两端点坐标(x1, y1)，(x2, y2)求出直线的斜率m。,设x1x2，则 m = ( y2 - y1) / ( x2 - x1),交点坐标为（x, y） m = ( y - y1) / ( x - x1),与窗口左、右边线相交，则x已知，其y值为,y = m ( x - x1) + y1,若与窗口上、下边线相交，则y已知，其x值为,x = ( y - y1) / m + x1,其中 m0即y1y2,若m=0，不予处理，直线会被其它窗口边线裁剪。,结 束,章目录,下 页,上 页,第4章,窗口与裁剪,编程作业：线段裁剪,结 束,章目录,下 页,上 页,将如图所示线段裁剪后在屏幕上显示出来。,第4章,窗口与裁剪,多边形裁剪,要求裁剪后多边形是封闭图形。,一般情况下，多边形被裁剪后不再是封闭的，因此需要用窗口边线的适当部分来封闭它。,Sutherland,Hodgman,逐边裁剪算法,算法思想：每次用扩展窗口边线对多边形裁剪，形成一个新的多边形，作为下次裁剪的初始图形，用窗口边依次对多边形裁剪，经四次完成。,结 束,章目录,下 页,上 页,第4章,窗口与裁剪,步骤：,(1),将待裁剪多边形的各顶点按照一定的方向有次序地组成输入顶点表。,(2),对输入的顶点进行处理，处理的结果产生一个新的输出顶点表。,(3),把输出顶点表作为新的输入顶点表，再次进行算法中的第,(2),步。如此重复,3,次。,结 束,章目录,下 页,上 页,第4章,窗口与裁剪,处理多边形的边线时，一条直线与一条窗口边线的位置关系只有四种。以窗口左边线为例，处理如下：,起点,V1,、终点,V2,都在窗口内，直线可见。将终点送入输出顶点表。,起点,V2,在窗口内，终点,V3,在窗口外，直线部分可见。求出直线与窗口边的交点,i1,，将其送入输出顶点表。,结 束,起点,V3,、终点,V4,都在窗口外，直线不可见。没有顶点送入输出顶点表。,起点,V4,在窗口外，终点,V1,在窗口内，直线部分可见。求出直线与窗口边的交点,i2,，将,i2,和终点,V1,送入输出顶点表。,按以上处理方法，本例的输入顶点表为,V1,，,V2,，,V3,，,V4,，输出顶点表为,V2,，,i1,，,i2,，,V1,。,章目录,下 页,上 页,第4章,窗口与裁剪,作业：,已知一平面矩形充满屏幕，长为,L,，高为,H,，欲将此图形逆时针转动,30,度，尽量大地重新显示在屏幕上。请写出变换方法（用等比例变换）、步骤及变换参数。屏幕坐标系如下图所示。,结 束,章目录,下 页,上 页,x,Y,第5章,多边形填充,第5章,多边形填充,下 页,章目录,上 页,结 束,在图形处理中，经常需要在一个封闭图形中进行填充，例如工程图