计算机图形学课程

《计算机图形学课程》由会员分享，可在线阅读，更多相关《计算机图形学课程（154页珍藏版）》请在金锄头文库上搜索。

1、计算机图形学计算机图形学计算机图形学计算机图形学东北大学机械工程与自动化学院东北大学机械工程与自动化学院东北大学机械工程与自动化学院东北大学机械工程与自动化学院工程图学教学与研究中心工程图学教学与研究中心工程图学教学与研究中心工程图学教学与研究中心肖平阳肖平阳肖平阳肖平阳 计算机图形学计算机图形学计算机图形学计算机图形学计算机图形学计算机图形学计算机图形学计算机图形学绪 论 随着计算机软、硬件的发展，计算机图形学已成为一门成熟的学科，在计算机应用领域占有重要内容地位。计算机图形学的定义ISO(国际标准化组织)对其定义为：计算机图形学是研究通过计算机将数据转换为图形，并在专用显示设备上显示的原理

2、、方法和技术的学科。计算机图形学的IEEE定义Computer graphics is the art or science of producing graphical images with the aid of computer.注：注：InstituteofElectricalandElectronicsEngineers(IEEE)美国电子和电气工程师协会计算机图形学计算机图形学计算机图形学计算机图形学计算机图形学发展简史计算机图形学发展简史 1950年年第一台图形显示器作为美国麻省理工学院（第一台图形显示器作为美国麻省理工学院（MIT）旋风）旋风I号号（WhirlwindI）计算机

3、的附件诞生了。该显示器用一个类似于示）计算机的附件诞生了。该显示器用一个类似于示波器的阴极射线管（波器的阴极射线管（CRT）来显示一些简单的图形。）来显示一些简单的图形。1958年年美国美国Calcomp公司由联机的数字记录仪发展成滚筒式绘图仪，公司由联机的数字记录仪发展成滚筒式绘图仪，GerBer公司把数控机床发展成为平板式绘图仪。公司把数控机床发展成为平板式绘图仪。50年代末期年代末期MIT的林肯实验室在的林肯实验室在“旋风旋风”计算机上开发计算机上开发SAGE空中防御空中防御体系，第一次使用了具有指挥和控制功能的体系，第一次使用了具有指挥和控制功能的CRT显示器，操作者显示器，操作者可以

4、用笔在屏幕上指出被确定的目标。可以用笔在屏幕上指出被确定的目标。计算机图形学计算机图形学计算机图形学计算机图形学1962年年MIT林肯实验室的林肯实验室的IvanE.Sutherland发表了一篇题为发表了一篇题为“Sketchpad：一个人机交互通信的图形系统：一个人机交互通信的图形系统”的博士论文，首次的博士论文，首次使用使用“ComputerGraphics”这个术语，证明了交互计算机图形学这个术语，证明了交互计算机图形学是一个可行的、有用的研究领域，从而确定了计算机图形学作为是一个可行的、有用的研究领域，从而确定了计算机图形学作为一个崭新的科学分支的独立地位。一个崭新的科学分支的独立地

5、位。1964年年MIT的教授的教授StevenA.Coons提出了被后人称为超限插值的提出了被后人称为超限插值的新思想，通过插值四条任意的边界曲线来构造曲面。同在新思想，通过插值四条任意的边界曲线来构造曲面。同在60年代年代早期，法国雷诺汽车公司的工程师早期，法国雷诺汽车公司的工程师PierreBzier发展了一套发展了一套Bzier曲线、曲面的理论，成功地用于几何外形设计。曲线、曲面的理论，成功地用于几何外形设计。计算机图形学计算机图形学计算机图形学计算机图形学70年代是计算机图形学发展过程中一个重要的历史时期。光年代是计算机图形学发展过程中一个重要的历史时期。光栅显示器的产生，图形学进入了

6、第一个兴盛的时期，并开始出现栅显示器的产生，图形学进入了第一个兴盛的时期，并开始出现实用的实用的CAD图形系统。图形系统。70年代，计算机图形学另外两个重要进展年代，计算机图形学另外两个重要进展是真实感图形学和实体造型技术的产生。是真实感图形学和实体造型技术的产生。从从80年代中期以来，超大规模集成电路的发展，为图形学的年代中期以来，超大规模集成电路的发展，为图形学的飞速发展奠定了物质基础。计算机的运算能力的提高，图形处理飞速发展奠定了物质基础。计算机的运算能力的提高，图形处理速度的加快，使得图形学的各个研究方向得到充分发展，图形学速度的加快，使得图形学的各个研究方向得到充分发展，图形学已广泛

7、应用于动画、科学计算可视化、已广泛应用于动画、科学计算可视化、CAD/CAM、影视娱乐等、影视娱乐等各个领域。各个领域。计算机图形学计算机图形学计算机图形学计算机图形学计算机图形学研究的基本内容计算机图形学研究的基本内容 图形通常由点、图形通常由点、线、面、体等几何元素和灰度、色彩、线型、线、面、体等几何元素和灰度、色彩、线型、线宽等非几何属性组成。线宽等非几何属性组成。另一类是明暗图另一类是明暗图(Shading)，是，是以位图以位图(Bitmap)形式存在的灰形式存在的灰度信息度信息，也就是通常所说的真实感图形。也就是通常所说的真实感图形。从处理技术上来看，图形主要分为两类从处理技术上来看

8、，图形主要分为两类:一类是基于线条信息表示的，如工程图、等高线地图、曲面一类是基于线条信息表示的，如工程图、等高线地图、曲面的线框图等的线框图等，含有几何属性，或者说更强调场景的几何表示，是含有几何属性，或者说更强调场景的几何表示，是由场景的几何模型和景物的物理属性共同组成的。由场景的几何模型和景物的物理属性共同组成的。计算机图形学计算机图形学计算机图形学计算机图形学在用计算机处理图形数据方面，主要分为三个领域：在用计算机处理图形数据方面，主要分为三个领域：图形显图形显示、示、图像（图像（image）处理和处理和图像图像模式识别。模式识别。一、图形显示一、图形显示图形描述图形描述点、线、面等点

9、、线、面等及其拓扑信息。及其拓扑信息。图形变换图形变换二、三维变换、三维到二维、几何变换二、三维变换、三维到二维、几何变换和非几何变换和非几何变换等等。图形运算图形运算基本几何间的计算、裁剪、布尔运算等。基本几何间的计算、裁剪、布尔运算等。图形显示图形显示/输出输出基本图形生成算法、消隐、绘图、光照模型等基本图形生成算法、消隐、绘图、光照模型等。图形输入图形输入交互技术、参数化设计、造型技术等。交互技术、参数化设计、造型技术等。算法和算法复杂性分析算法和算法复杂性分析空间和时间等。空间和时间等。计算机图形学计算机图形学计算机图形学计算机图形学二、二、图像处理图像处理对直观图像（以具有颜色信息的

10、点阵来表示的图形），按图对直观图像（以具有颜色信息的点阵来表示的图形），按图形由哪些点组成、点的灰度及色彩进行处理，增强其清晰度。形由哪些点组成、点的灰度及色彩进行处理，增强其清晰度。三、 图象模式识别图象模式识别在算法研究方面，不单要求从数学上能够处理，还要求必须在在算法研究方面，不单要求从数学上能够处理，还要求必须在计算机容量允许的条件下和用户能够容忍的时间内完成这些处理。计算机容量允许的条件下和用户能够容忍的时间内完成这些处理。因此，强调要研究占用机时少、占用存储量小的图形处理方法。因此，强调要研究占用机时少、占用存储量小的图形处理方法。计算机图形学计算机图形学计算机图形学计算机图形学本

11、课程的设置内容本课程的设置内容作为一门主要面向机械专业研究生的课程，着重讨论与图形作为一门主要面向机械专业研究生的课程，着重讨论与图形变换、图案填充和隐线消除相关的原理与算法。变换、图案填充和隐线消除相关的原理与算法。为使学生具备以下几个方面的能力打下基础：掌握图形生成、为使学生具备以下几个方面的能力打下基础：掌握图形生成、图形变换、图案填充和隐线消除的一般原理、方法和技术；编制图形变换、图案填充和隐线消除的一般原理、方法和技术；编制计算机绘图程序；处理图形数据；进行更深入的计算机图形学研计算机绘图程序；处理图形数据；进行更深入的计算机图形学研究。究。授课中主要侧重软件方面，对硬件知识作一些必

12、要的介绍。授课中主要侧重软件方面，对硬件知识作一些必要的介绍。第第第第1 1章章章章 计算机图形系统计算机图形系统计算机图形系统计算机图形系统第第1章章计算机图形系统计算机图形系统 计算机图形系统的功能计算机图形系统的功能(1)计算功能计算功能(2)存储功能存储功能(3)交互功能交互功能(4)输入功能输入功能(5)输出功能输出功能第第第第1 1章章章章 计算机图形系统计算机图形系统计算机图形系统计算机图形系统一、一、硬件硬件1计算机计算机2输入设备：键盘、鼠标、图形输入板、扫描输入设备：键盘、鼠标、图形输入板、扫描仪仪等等数字化仪是一种把图形转变成计算机能接收的数字形式专用数字化仪是一种把图形

13、转变成计算机能接收的数字形式专用设备。现在非常流行的汉字手写系统就是一种数字化仪。设备。现在非常流行的汉字手写系统就是一种数字化仪。三坐标测量仪，用于真实物体的三维信息的输入。三坐标测量仪，用于真实物体的三维信息的输入。此外还有跟踪球、空间球、数据手套、光笔、触摸屏等。此外还有跟踪球、空间球、数据手套、光笔、触摸屏等。3输出设备输出设备图形输出包括图形的显示和图形的绘制，图形显示指的是图形输出包括图形的显示和图形的绘制，图形显示指的是在屏幕上输出图形，图形绘制通常指把图形画在纸上，也称硬在屏幕上输出图形，图形绘制通常指把图形画在纸上，也称硬拷贝，打印机和绘图仪是两种最常用的硬拷贝设备。拷贝，打

14、印机和绘图仪是两种最常用的硬拷贝设备。第第第第1 1章章章章 计算机图形系统计算机图形系统计算机图形系统计算机图形系统光栅扫描式光栅扫描式CRT监视器监视器阴极射线管（阴极射线管（CRTCathodeRayTube）的工作原理：高）的工作原理：高速的电子束由电子枪发出，经过聚焦系统、加速系统和磁偏转速的电子束由电子枪发出，经过聚焦系统、加速系统和磁偏转系统就会到达荧光屏的特定位置。荧光物质在高速电子的轰击系统就会到达荧光屏的特定位置。荧光物质在高速电子的轰击下，将发出荧光。为保持显示一幅稳定的画面，必须不断地发下，将发出荧光。为保持显示一幅稳定的画面，必须不断地发射电子束。射电子束。第第第第1

15、 1章章章章 计算机图形系统计算机图形系统计算机图形系统计算机图形系统刷新一次指电子束从上到下将荧光屏扫描一次，其扫描过刷新一次指电子束从上到下将荧光屏扫描一次，其扫描过程如下图所示。只有刷新频率高到一定值后，图象才能稳定显程如下图所示。只有刷新频率高到一定值后，图象才能稳定显示。大约达到每秒示。大约达到每秒60帧即帧即60Hz时，人眼才能感觉到屏幕不闪烁，时，人眼才能感觉到屏幕不闪烁，要使人眼觉得舒服，一般必须有要使人眼觉得舒服，一般必须有85Hz以上的刷新频率。以上的刷新频率。有些扫描速度较慢的显示器，为了能得到好的显示效果，有些扫描速度较慢的显示器，为了能得到好的显示效果，采用一种叫隔行

16、扫描的技术。当然这样的技术和真正逐行扫描采用一种叫隔行扫描的技术。当然这样的技术和真正逐行扫描的效果还是有差距的。的效果还是有差距的。彩色彩色CRT显示器的荧光屏上涂有三种荧光物质，它们分别显示器的荧光屏上涂有三种荧光物质，它们分别能发红、绿、兰三种颜色的光。而电子枪也发出三束电子来激能发红、绿、兰三种颜色的光。而电子枪也发出三束电子来激发这三种物质。如果每一个电子枪都有发这三种物质。如果每一个电子枪都有256级（级（8位）的强度控位）的强度控制，那么这个显象管所能产生的颜色就是我们平时所说的制，那么这个显象管所能产生的颜色就是我们平时所说的24位位真彩色了。真彩色了。第第第第1 1章章章章

17、计算机图形系统计算机图形系统计算机图形系统计算机图形系统点距和分辨率点距和分辨率点距是两个像素（光点）之间的距离，一般为点距是两个像素（光点）之间的距离，一般为0.280.32mm。分辨率是指屏幕上能有多少像素。比如分辨率是指屏幕上能有多少像素。比如1024768的含义就的含义就是一行有是一行有1024个像素，一列有个像素，一列有768个像素。个像素。第第第第1 1章章章章 计算机图形系统计算机图形系统计算机图形系统计算机图形系统LCD液晶显示器液晶显示器LCD（LiquidCrystalDisplay）液晶显示器。）液晶显示器。基本原理基本原理:液晶是一种介于液体和固体之间的特殊物质，它具有

18、液体液晶是一种介于液体和固体之间的特殊物质，它具有液体的流态性质和固体的光学性质。当液晶受到电压的影响时，就的流态性质和固体的光学性质。当液晶受到电压的影响时，就会改变它的物理性质而发生形变，此时通过它的光的折射角度会改变它的物理性质而发生形变，此时通过它的光的折射角度就会发生变化，而产生色彩。就会发生变化，而产生色彩。液晶屏幕后面有一个背光，这个光源射出的光线先穿过第液晶屏幕后面有一个背光，这个光源射出的光线先穿过第一层偏光板，再来到液晶体上，而当光线透过液晶体时，就会一层偏光板，再来到液晶体上，而当光线透过液晶体时，就会产生光线的色泽改变，从液晶体射出来的光线，还必得须经过产生光线的色泽改

19、变，从液晶体射出来的光线，还必得须经过一块彩色滤光片以及第二块偏光板。由于两块偏光板的偏振方一块彩色滤光片以及第二块偏光板。由于两块偏光板的偏振方向成向成90度，再加上电压的变化和一些其他的装置，液晶显示器度，再加上电压的变化和一些其他的装置，液晶显示器就能显示我们想要的颜色了。就能显示我们想要的颜色了。第第第第1 1章章章章 计算机图形系统计算机图形系统计算机图形系统计算机图形系统点距和分辨率点距和分辨率液晶屏幕的点距就是两个液晶颗粒（光点）之间的距离。液晶屏幕的点距就是两个液晶颗粒（光点）之间的距离。分辨率在液晶显示器中的含义并不和分辨率在液晶显示器中的含义并不和CRT中的完全一样。中的完

20、全一样。通常所说的液晶显示器的分辨率是指其真实分辨率，比如通常所说的液晶显示器的分辨率是指其真实分辨率，比如1024768的含义就是指该液晶显示器含有的含义就是指该液晶显示器含有1024768个液晶颗个液晶颗粒。只有在真实分辨率下液晶显示器才能得到最佳的显示效果。粒。只有在真实分辨率下液晶显示器才能得到最佳的显示效果。其它较低的分辨率只能通过缩放仿真来显示，效果并不好。而其它较低的分辨率只能通过缩放仿真来显示，效果并不好。而CRT显示器如果能在显示器如果能在1024768的分辨率下能清晰显示的话，那的分辨率下能清晰显示的话，那么其它如么其它如800600，640480都能很好地显示。都能很好地

21、显示。第第第第1 1章章章章 计算机图形系统计算机图形系统计算机图形系统计算机图形系统二、二、软件软件1基本子程序驱动基本子程序驱动设备的设备的程序程序2功能子程序完成通用绘图功能。如画线等功能子程序完成通用绘图功能。如画线等3应用子程序应用子程序为用户专门设计的子程序，用于特定专业，往往是用户自为用户专门设计的子程序，用于特定专业，往往是用户自行开发。行开发。第第2章章图形变换图形变换 图形变换的基本原理是：（1）图形的拓扑关系不变；）图形的拓扑关系不变；（2）图形的几何关系可以改变。）图形的几何关系可以改变。所谓图形拓扑关系不变是指图形的连边规则不变，即原来是所谓图形拓扑关系不变是指图形的

22、连边规则不变，即原来是相邻的点变换后依然相邻，原来不相交的线变换后依然不相交。相邻的点变换后依然相邻，原来不相交的线变换后依然不相交。所谓图形的几何关系可以改变是指图形的点与点之间的位置所谓图形的几何关系可以改变是指图形的点与点之间的位置和距离可以改变。和距离可以改变。第第2 2章章 图形变换图形变换用线模型描述物体的图形。图形由直线和曲线来表述。计算用线模型描述物体的图形。图形由直线和曲线来表述。计算机图形中的曲线是由短直线表示的。直线可由两点完全确定。因机图形中的曲线是由短直线表示的。直线可由两点完全确定。因此，图形的几何信息构成所有直线的点集的坐标。此，图形的几何信息构成所有直线的点集的

23、坐标。所有的变换均基于点的变换。所有的变换均基于点的变换。注意：变换前后都是在同一个坐标系内。用注意：变换前后都是在同一个坐标系内。用x、y、z表示变换表示变换前的点坐标，用前的点坐标，用X、Y、Z表示变换后的点坐标。表示变换后的点坐标。第第2 2章章 图形变换图形变换2 21 1二维图形变换二维图形变换二维图形变换二维图形变换 点用行向量（点用行向量（点用行向量（点用行向量（x,yx,y）来表示。）来表示。）来表示。）来表示。一、平移变换一、平移变换一、平移变换一、平移变换点点点点 p(p(x,yx,y) )沿坐标轴方向移动一定距离沿坐标轴方向移动一定距离沿坐标轴方向移动一定距离沿坐标轴方向

24、移动一定距离xw,ywxw,yw2-12-1二维二维二维二维变换变换数学表示：数学表示：数学表示：数学表示：X=x+xwX=x+xwY=y+ywY=y+yw其中其中其中其中xwxw, ,ywyw 称为平移常称为平移常称为平移常称为平移常数。数。数。数。若用二维矩阵表示，则有若用二维矩阵表示，则有若用二维矩阵表示，则有若用二维矩阵表示，则有X,Y=x,yX,Y=x,y=ax+cyax+cy,bx+dybx+dy ax+cyax+cyx+xwx+xwbx+dybx+dyy+ywy+yw无法用二维矩阵表示。无法用二维矩阵表示。无法用二维矩阵表示。无法用二维矩阵表示。2-12-1二维二维二维二维变换变

25、换abcd2-12-1二维二维二维二维变换变换 为了能统一描述图形变换，在计算机图形学中常采用齐次为了能统一描述图形变换，在计算机图形学中常采用齐次为了能统一描述图形变换，在计算机图形学中常采用齐次为了能统一描述图形变换，在计算机图形学中常采用齐次变换矩阵进行变换。变换矩阵进行变换。变换矩阵进行变换。变换矩阵进行变换。一般地，用一个一般地，用一个一般地，用一个一般地，用一个n+1n+1维坐标表示一个维坐标表示一个维坐标表示一个维坐标表示一个n n维的点的方法称为齐维的点的方法称为齐维的点的方法称为齐维的点的方法称为齐次坐标法。次坐标法。次坐标法。次坐标法。用齐次坐标法，将点向量表示为用齐次坐标

26、法，将点向量表示为用齐次坐标法，将点向量表示为用齐次坐标法，将点向量表示为xxyy1 1 XXY Y1=x1=x y y11 100010xwyw1变换矩阵变换矩阵变换矩阵变换矩阵2-12-1二维二维二维二维变换变换二、比例变换二、比例变换二、比例变换二、比例变换通过变换图形中两点间的距离，得到放大、缩小、拉伸或通过变换图形中两点间的距离，得到放大、缩小、拉伸或通过变换图形中两点间的距离，得到放大、缩小、拉伸或通过变换图形中两点间的距离，得到放大、缩小、拉伸或压缩图形的效果。压缩图形的效果。压缩图形的效果。压缩图形的效果。变换前后两点与基准点间的距离的长度之比称为比例因子。变换前后两点与基准点

27、间的距离的长度之比称为比例因子。变换前后两点与基准点间的距离的长度之比称为比例因子。变换前后两点与基准点间的距离的长度之比称为比例因子。沿沿沿沿X X、Y Y轴方向分别定义为轴方向分别定义为轴方向分别定义为轴方向分别定义为SxSx，SySy。以原点为基准点，则数学表示为以原点为基准点，则数学表示为以原点为基准点，则数学表示为以原点为基准点，则数学表示为（X0X0）/ /（xx0 0）=SxSx X=xX=xSxSx同样：同样：同样：同样： Y=yY=ySySy2-12-1二维二维二维二维变换变换SxSx1X1X向距离增大向距离增大向距离增大向距离增大SxSx 1X1X向距离减小向距离减小向距离

28、减小向距离减小SxSx 1X1X向距离保持不变向距离保持不变向距离保持不变向距离保持不变SxSx SySy等比例变换，图形放大或缩小等比例变换，图形放大或缩小等比例变换，图形放大或缩小等比例变换，图形放大或缩小SxSx SySy 1 1恒等变换恒等变换恒等变换恒等变换SxSxSySy SxSx00SySy00图形产生拉伸或压缩变形图形产生拉伸或压缩变形图形产生拉伸或压缩变形图形产生拉伸或压缩变形矩阵方法表示有两种形式：矩阵方法表示有两种形式：矩阵方法表示有两种形式：矩阵方法表示有两种形式：变换矩阵变换矩阵变换矩阵变换矩阵Ts1=Ts1=XY1=xy1Ts1=xXY1=xy1Ts1=xSxSxy

29、ySySy11变换矩阵变换矩阵变换矩阵变换矩阵Ts2=Ts2=XYH=xy1XYH=xy1Ts2=xysTs2=xys其中：其中：其中：其中：H=H=s s2-12-1二维二维二维二维变换变换Sx000Sy000110001000S2-12-1二维二维二维二维变换变换对第二种变换，要其结果进行处理，使第三个元素为对第二种变换，要其结果进行处理，使第三个元素为对第二种变换，要其结果进行处理，使第三个元素为对第二种变换，要其结果进行处理，使第三个元素为1 1。处。处。处。处理的方法是用理的方法是用理的方法是用理的方法是用1/s1/s乘以各元素，从而得到乘以各元素，从而得到乘以各元素，从而得到乘以各

30、元素，从而得到XXY Y1=x1=x/s/s,y/s,1,y/s,1这种方法称为齐次坐标的正常化。这种方法称为齐次坐标的正常化。这种方法称为齐次坐标的正常化。这种方法称为齐次坐标的正常化。 10001000S1/S0001/S0001= =1/S1/S 正常化处理后，成为比例因子为正常化处理后，成为比例因子为正常化处理后，成为比例因子为正常化处理后，成为比例因子为1/S1/S的等比例变换矩阵的等比例变换矩阵的等比例变换矩阵的等比例变换矩阵2-12-1二维二维二维二维变换变换几何含义：几何含义：几何含义：几何含义：2-12-1二维二维二维二维变换变换比例变换不动点比例变换前后位置不动的点称为比例

31、变换不动点，一般在原点，但它可以是任意点(xp, yp)。2-12-1二维二维二维二维变换变换以任意点作为比例变换不动点进行比例变换步骤：（1）平移P点至原点。平移常数为xp, yp。（2）相对于原点进行比例变换。（3）反平移P点。平移常数为xp, yp。变换矩阵变换矩阵变换矩阵变换矩阵2-12-1二维二维二维二维变换变换三、旋转变换三、旋转变换数学方法数学方法数学方法数学方法：x=rcos,y=rsinx=rcos,y=rsinX=rcos(X=rcos( +)+)=rcoscos=rcoscos -rsinsin-rsinsin =xcos=xcos -ysin-ysin Y=rsin(+

32、)Y=rsin(+)=r=rcoscossin+rsinsin+rsincoscos=xsin+y=xsin+ycoscos2-12-1二维二维二维二维变换变换矩阵方法：矩阵方法：矩阵方法：矩阵方法：2-12-1二维二维二维二维变换变换绕任意点绕任意点P P（xp,ypxp,yp）旋转）旋转 角角步骤：（步骤：（步骤：（步骤：（1 1）平移）平移）平移）平移P P点至原点。平移常数为点至原点。平移常数为点至原点。平移常数为点至原点。平移常数为xpxp, , ypyp。（2 2）绕原点）绕原点）绕原点）绕原点旋转旋转旋转旋转 角角角角。（3 3）反平移）反平移）反平移）反平移P P点。平移常数为

33、点。平移常数为点。平移常数为点。平移常数为xpxp, ,ypyp。变换矩阵变换矩阵变换矩阵变换矩阵2-12-1二维二维二维二维变换变换四、四、对称变换（镜像变换）对称变换（镜像变换）相对于一点或一直线。相对于一点或一直线。相对于一点或一直线。相对于一点或一直线。2-12-1二维二维二维二维变换变换数学方法数学方法数学方法数学方法：相对于相对于相对于相对于x x轴轴轴轴XX xx YY y y相对于相对于相对于相对于y y轴轴轴轴XX xxYY y y相对于坐标原点相对于坐标原点相对于坐标原点相对于坐标原点XX xxYY yy2-12-1二维二维二维二维变换变换矩阵方法：矩阵方法：矩阵方法：矩阵

34、方法：相对于相对于相对于相对于x x轴轴轴轴相对于相对于相对于相对于y y轴轴轴轴相对于坐标原点相对于坐标原点相对于坐标原点相对于坐标原点2-12-1二维二维二维二维变换变换相相对于任意直线的对称变换对于任意直线的对称变换我们用对称轴我们用对称轴我们用对称轴我们用对称轴的一个端点的一个端点的一个端点的一个端点P P的坐的坐的坐的坐标和该对称轴与标和该对称轴与标和该对称轴与标和该对称轴与X X轴的夹角轴的夹角轴的夹角轴的夹角 来表示来表示来表示来表示这根对称轴这根对称轴这根对称轴这根对称轴PSPS。要将图形中的要将图形中的要将图形中的要将图形中的MM点相对于点相对于点相对于点相对于PSPS轴对轴

35、对轴对轴对称变换到称变换到称变换到称变换到N N点。点。点。点。2-12-1二维二维二维二维变换变换步骤：步骤：步骤：步骤：（1 1）平移）平移）平移）平移P P点至点至点至点至P1P1点，点，点，点，与原点重合。平移常数为与原点重合。平移常数为与原点重合。平移常数为与原点重合。平移常数为xpxp, ,ypyp。（2 2）绕原点顺时针旋转）绕原点顺时针旋转）绕原点顺时针旋转）绕原点顺时针旋转角，使角，使角，使角，使P2S2P2S2与与与与X X轴重合。轴重合。轴重合。轴重合。（3 3）将）将）将）将M2M2点相对于点相对于点相对于点相对于X X轴轴轴轴进行对称变换，得到进行对称变换，得到进行对

36、称变换，得到进行对称变换，得到N2N2点。点。点。点。（4 4）将）将）将）将N2N2点绕原点逆时点绕原点逆时点绕原点逆时点绕原点逆时针旋转针旋转针旋转针旋转角，得到角，得到角，得到角，得到N1N1点。点。点。点。（5 5）反平移）反平移）反平移）反平移P2P2点，与点，与点，与点，与P P点重合。平移常数为点重合。平移常数为点重合。平移常数为点重合。平移常数为xpxp, ,ypyp。得到得到得到得到N N点。点。点。点。 2-12-1二维二维二维二维变换变换五、错移变换五、错移变换错移变换使图形产生扭变。错移变换使图形产生扭变。错移变换使图形产生扭变。错移变换使图形产生扭变。1 1沿沿沿沿x

37、 x轴错移轴错移轴错移轴错移这种变换使点的这种变换使点的这种变换使点的这种变换使点的X X向坐标产生与其向坐标产生与其向坐标产生与其向坐标产生与其Y Y坐标相关的错移。坐标相关的错移。坐标相关的错移。坐标相关的错移。2-12-1二维二维二维二维变换变换数学方法：数学方法：数学方法：数学方法：XX x+shxyx+shxyYY y y其中其中其中其中shxshx00为为为为x x轴方向错移系数轴方向错移系数轴方向错移系数轴方向错移系数例：例：例：例： shxshx1 1点错移前错移后x坐标y坐标X坐标x + shxyx + shxyY坐标P1111 + 11=21P2121 + 12=32P32

38、22 + 12=42P4212 + 11=312-12-1二维二维二维二维变换变换矩阵方法：矩阵方法：矩阵方法：矩阵方法：2 2沿沿沿沿y y轴错移轴错移轴错移轴错移这种变换使点的这种变换使点的这种变换使点的这种变换使点的Y Y向坐标产生与其向坐标产生与其向坐标产生与其向坐标产生与其X X坐标相关的错移。坐标相关的错移。坐标相关的错移。坐标相关的错移。数学方法：数学方法：数学方法：数学方法：XX xxYY shyxshyx+ + yyshyshy00为为为为y y轴方向错移系数轴方向错移系数轴方向错移系数轴方向错移系数2-12-1二维二维二维二维变换变换2-12-1二维二维二维二维变换变换矩阵

39、方法：矩阵方法：矩阵方法：矩阵方法：矩阵级联矩阵级联矩阵级联矩阵级联多个变换可以组合成新的变换，用矩阵相乘（矩阵的级联）而多个变换可以组合成新的变换，用矩阵相乘（矩阵的级联）而多个变换可以组合成新的变换，用矩阵相乘（矩阵的级联）而多个变换可以组合成新的变换，用矩阵相乘（矩阵的级联）而产生一个具有新的功效的单一变换矩阵。产生一个具有新的功效的单一变换矩阵。产生一个具有新的功效的单一变换矩阵。产生一个具有新的功效的单一变换矩阵。 矩阵级联是有序的。例如一个变换是平移和旋转，先平移后旋矩阵级联是有序的。例如一个变换是平移和旋转，先平移后旋矩阵级联是有序的。例如一个变换是平移和旋转，先平移后旋矩阵级联

40、是有序的。例如一个变换是平移和旋转，先平移后旋转的效果和先旋转后平移的效果，一般情况下是不同的。转的效果和先旋转后平移的效果，一般情况下是不同的。转的效果和先旋转后平移的效果，一般情况下是不同的。转的效果和先旋转后平移的效果，一般情况下是不同的。2-22-2三维三维三维三维变换变换22三维图形变换三维图形变换用右手系。用右手系。用右手系。用右手系。变换前后都是在同一个坐标系内。变换前后都是在同一个坐标系内。变换前后都是在同一个坐标系内。变换前后都是在同一个坐标系内。一、三维平移变换一、三维平移变换数学方法：数学方法：数学方法：数学方法：X=x+XwX=x+XwY=y+YwY=y+YwZ=z+Z

41、=z+ZwZw矩阵方法：矩阵方法：矩阵方法：矩阵方法：2-22-2三维三维三维三维变换变换二、三维比例变换二、三维比例变换与二维比例变换类似。与二维比例变换类似。与二维比例变换类似。与二维比例变换类似。数学方法：数学方法：数学方法：数学方法：一般以原点为基准点，则有一般以原点为基准点，则有一般以原点为基准点，则有一般以原点为基准点，则有X=SxxX=SxxY=SyyY=SyyZ=SzzZ=Szz矩阵方法表示有两种形式：矩阵方法表示有两种形式：矩阵方法表示有两种形式：矩阵方法表示有两种形式：2-22-2三维三维三维三维变换变换比例变换不动点比例变换不动点比例变换不动点比例变换不动点以任意点以任意

42、点以任意点以任意点( (xpxp, ,ypyp, ,zpzp) )作为比例变换不动点进行比例变换作为比例变换不动点进行比例变换作为比例变换不动点进行比例变换作为比例变换不动点进行比例变换步骤：（步骤：（步骤：（步骤：（1 1）平移）平移）平移）平移P P点至原点。平移常数为点至原点。平移常数为点至原点。平移常数为点至原点。平移常数为xpxp, ,ypyp, ,zpzp。（2 2）相对于原点进行比例变换。）相对于原点进行比例变换。）相对于原点进行比例变换。）相对于原点进行比例变换。（3 3）反平移）反平移）反平移）反平移P P点。平移常数为点。平移常数为点。平移常数为点。平移常数为xp,yp,z

43、pxp,yp,zp。变换矩阵变换矩阵变换矩阵变换矩阵2-22-2三维三维三维三维变换变换三、三维旋转变换三、三维旋转变换三维旋转是绕空间一直线的旋转。三维旋转是绕空间一直线的旋转。三维旋转是绕空间一直线的旋转。三维旋转是绕空间一直线的旋转。旋转方向：沿坐标轴正方向朝原点看去，逆时针为正。旋转方向：沿坐标轴正方向朝原点看去，逆时针为正。旋转方向：沿坐标轴正方向朝原点看去，逆时针为正。旋转方向：沿坐标轴正方向朝原点看去，逆时针为正。数学方法：数学方法：数学方法：数学方法：绕绕绕绕X X轴轴轴轴X=xX=xY=ycosY=ycos -zsin-zsin Z=ysin+zcosZ=ysin+zcos绕

44、绕绕绕Y Y轴轴轴轴X=xcosX=xcos +zsin+zsin Y=yY=yZ=-xsinZ=-xsin +zcos+zcos 绕绕绕绕Z Z轴轴轴轴X=X=xcosxcos -ysin-ysin Y=xsinY=xsin +ycos+ycos Z=zZ=z2-22-2三维三维三维三维变换变换矩阵方法：矩阵方法：矩阵方法：矩阵方法：绕绕绕绕X X轴轴轴轴绕绕绕绕Y Y轴轴轴轴绕绕绕绕Z Z轴轴轴轴2-22-2三维三维三维三维变换变换三维绕任意三维绕任意直线直线旋转旋转 角角设任意直线由设任意直线由设任意直线由设任意直线由P1P1（x1,y1,z1x1,y1,z1），），），），P2P2（x

45、2,y2,z2x2,y2,z2）两点确定。两点确定。两点确定。两点确定。思路：先将直线变换到与某思路：先将直线变换到与某思路：先将直线变换到与某思路：先将直线变换到与某坐标轴重合，然后绕坐标轴坐标轴重合，然后绕坐标轴坐标轴重合，然后绕坐标轴坐标轴重合，然后绕坐标轴旋转旋转旋转旋转 角，最后将直线再变换角，最后将直线再变换角，最后将直线再变换角，最后将直线再变换回初始位置。回初始位置。回初始位置。回初始位置。为叙述简便，为叙述简便，为叙述简便，为叙述简便，令令令令a=x2a=x2x1x1b=y2b=y2y1y1c=z2c=z2z1z12-22-2三维三维三维三维变换变换用矩阵方法步骤：用矩阵方法

46、步骤：用矩阵方法步骤：用矩阵方法步骤：7 7步步步步 （1 1） 平移平移平移平移P1P1点至原点点至原点点至原点点至原点(P1)(P1)，移常数为，移常数为，移常数为，移常数为x1,x1,y1,y1,z1z1。则有则有则有则有 P2P2（a,b,ca,b,c）（2 2）绕）绕）绕）绕X X轴轴轴轴旋转旋转旋转旋转11角，使直线转角，使直线转角，使直线转角，使直线转到到到到X XZ Z平面上平面上平面上平面上。2-22-2三维三维三维三维变换变换为确定为确定为确定为确定sin1sin1和和和和cos1cos1，先将直线投影到，先将直线投影到，先将直线投影到，先将直线投影到Y YZ Z平面上，其

47、平面上，其平面上，其平面上，其投影长度为投影长度为投影长度为投影长度为 l1l1。则有。则有。则有。则有 P2”P2”（0,b,c0,b,c）。）。）。）。2-22-2三维三维三维三维变换变换2-22-2三维三维三维三维变换变换直线转到直线转到直线转到直线转到X XZ Z平面上，平面上，平面上，平面上，此时有：此时有：此时有：此时有：P2(a,0,l1)P2(a,0,l1)2-22-2三维三维三维三维变换变换（3 3）绕）绕）绕）绕Y Y轴轴轴轴旋转旋转旋转旋转22角角角角。2-22-2三维三维三维三维变换变换（4 4）绕）绕）绕）绕Z Z轴轴轴轴旋转旋转旋转旋转 角角角角。（5 5）绕）绕）

48、绕）绕Y Y轴轴轴轴旋转旋转旋转旋转22角角角角。（6 6）绕）绕）绕）绕X X轴轴轴轴旋转旋转旋转旋转11角角角角。（7 7）反平移）反平移）反平移）反平移P P点至初始位置，平移常数为点至初始位置，平移常数为点至初始位置，平移常数为点至初始位置，平移常数为x1,y1x1,y1，z1z1。2-22-2三维三维三维三维变换变换四、三维对称（镜像）变换四、三维对称（镜像）变换相对于相对于相对于相对于xoyxoy平面平面平面平面相对于相对于相对于相对于xozxoz平面平面平面平面相对于相对于相对于相对于yozyoz平面平面平面平面2-22-2三维三维三维三维变换变换相对于相对于相对于相对于X X轴

49、轴轴轴相对于相对于相对于相对于Y Y轴轴轴轴相对于相对于相对于相对于Z Z轴轴轴轴相对于任意平面相对于任意平面相对于任意平面相对于任意平面S S：思路：先将思路：先将思路：先将思路：先将S S面上任意面上任意面上任意面上任意点平移至原点；点平移至原点；点平移至原点；点平移至原点；用用用用S S面内过此点的、面内过此点的、面内过此点的、面内过此点的、与某坐标面的交线作为与某坐标面的交线作为与某坐标面的交线作为与某坐标面的交线作为任意旋转轴，将任意旋转轴，将任意旋转轴，将任意旋转轴，将S S面旋面旋面旋面旋转到与某坐标面重合；转到与某坐标面重合；转到与某坐标面重合；转到与某坐标面重合；相对于此坐标

50、面进相对于此坐标面进相对于此坐标面进相对于此坐标面进行对称变换；行对称变换；行对称变换；行对称变换；然后反旋转，反平然后反旋转，反平然后反旋转，反平然后反旋转，反平移，将移，将移，将移，将S S面再变换回初面再变换回初面再变换回初面再变换回初始位置。始位置。始位置。始位置。2-22-2三维三维三维三维变换变换五、三维错移变换五、三维错移变换设有一设有一设有一设有一矩阵为矩阵为矩阵为矩阵为三维错移变换矩阵，三维错移变换矩阵，三维错移变换矩阵，三维错移变换矩阵，a,b,c,d,e,fa,b,c,d,e,f为错移系数。为错移系数。为错移系数。为错移系数。3X33X3子矩阵中的第一列元素使物体产生轴方

51、向的错切；子矩阵中的第一列元素使物体产生轴方向的错切；子矩阵中的第一列元素使物体产生轴方向的错切；子矩阵中的第一列元素使物体产生轴方向的错切；第二列元素使物体产生轴方向的错切；第三列元素使物体产第二列元素使物体产生轴方向的错切；第三列元素使物体产第二列元素使物体产生轴方向的错切；第三列元素使物体产第二列元素使物体产生轴方向的错切；第三列元素使物体产生轴方向的错切。生轴方向的错切。生轴方向的错切。生轴方向的错切。沿每个坐标方向的错移都可分为三种情况。沿每个坐标方向的错移都可分为三种情况。沿每个坐标方向的错移都可分为三种情况。沿每个坐标方向的错移都可分为三种情况。2-22-2三维三维三维三维变换变

52、换沿沿沿沿x x轴方向轴方向轴方向轴方向1 1沿沿沿沿x x轴方向含轴方向含轴方向含轴方向含y y错移错移错移错移, ,变换矩阵为变换矩阵为变换矩阵为变换矩阵为X=x+c*yY=y,Z=zX=x+c*yY=y,Z=z2-22-2三维三维三维三维变换变换点错移前错移后x+c*yx坐标y坐标z坐标X坐标P11001 + 10=1P21101 + 11=2P31111 + 11=2P41011 + 10=1P50000P60100 + 11=1P70110 + 11=1P80010 + 10=02-22-2三维三维三维三维变换变换22沿沿沿沿x x轴含轴含轴含轴含z z错移错移错移错移, ,变换矩阵

53、为变换矩阵为变换矩阵为变换矩阵为 X=x+e*z,Y=y,Z=zX=x+e*z,Y=y,Z=z2-22-2三维三维三维三维变换变换点错移前错移后x+e*zx坐标y坐标z坐标X坐标P11001 + 10=1P21101 + 10=1P31111 + 11=2P41011 + 11=2P50000P60100 + 10=0P70110 + 11=1P80010 + 11=12-22-2三维三维三维三维变换变换33沿沿沿沿x x轴含轴含轴含轴含y,y,z z错移错移错移错移, ,变换矩阵为变换矩阵为变换矩阵为变换矩阵为X=x+c*y+e*z,X=x+c*y+e*z,Y=yY=yZ=zZ=z2-22-

54、2三维三维三维三维变换变换点错移前错移后x+c*y+e*zx坐标y坐标z坐标X坐标P11001 + 10 + 10=1P21101 + 11 + 10=2P31111 + 11 + 11=3P41011 + 10 + 11=2P50000P60100 + 11 + 10=1P70110 + 11 + 11=2P80010 + 10 + 11=12-22-2三维三维三维三维变换变换沿其它方向与之类似。沿其它方向与之类似。沿其它方向与之类似。沿其它方向与之类似。2-22-2三维三维三维三维变换变换点错移前错移后x+c*y错移后x+e*z错移后x+c*y+e*zx坐标y坐标z坐标X坐标X坐标X坐标P

55、11001 + 10=11 + 10=11 + 10 + 10=1P21101 + 11=21 + 10=11 + 11 + 10=2P31111 + 11=21 + 11=21 + 11 + 11=3P41011 + 10=11 + 11=21 + 10 + 11=2P5000000P60100 + 11=10 + 10=00 + 11 + 10=1P70110 + 11=10 + 11=10 + 11 + 11=2P80010 + 10=00 + 11=10 + 10 + 11=12-32-3投影变换投影变换23投影变换投影变换一、正投影变换一、正投影变换工程制图中常用的三视图，是由空间中

56、一个立体向工程制图中常用的三视图，是由空间中一个立体向工程制图中常用的三视图，是由空间中一个立体向工程制图中常用的三视图，是由空间中一个立体向3 3个互相垂个互相垂个互相垂个互相垂直的投影面作正投影得到的。这三个投影面分别称为：正投影直的投影面作正投影得到的。这三个投影面分别称为：正投影直的投影面作正投影得到的。这三个投影面分别称为：正投影直的投影面作正投影得到的。这三个投影面分别称为：正投影面（面（面（面（V V面）、侧投影面（面）、侧投影面（面）、侧投影面（面）、侧投影面（WW面）、水平投影面（面）、水平投影面（面）、水平投影面（面）、水平投影面（H H面）。面）。面）。面）。2-32-3

57、投影变换投影变换使用用户坐标使用用户坐标使用用户坐标使用用户坐标系（系（系（系（XX，YY，ZZ）描述物体。一）描述物体。一）描述物体。一）描述物体。一般情况下用户坐标般情况下用户坐标般情况下用户坐标般情况下用户坐标系的原点不在世界系的原点不在世界系的原点不在世界系的原点不在世界坐标系的原点上，坐标系的原点上，坐标系的原点上，坐标系的原点上，首先要用平移变换首先要用平移变换首先要用平移变换首先要用平移变换将用户坐标变换成将用户坐标变换成将用户坐标变换成将用户坐标变换成世界坐标世界坐标世界坐标世界坐标，然后向，然后向，然后向，然后向坐标面进行投影，坐标面进行投影，坐标面进行投影，坐标面进行投影，

58、再展开到一个平面。再展开到一个平面。再展开到一个平面。再展开到一个平面。2-32-3投影变换投影变换投影到坐标面投影到坐标面压缩点集的某个坐标压缩点集的某个坐标压缩点集的某个坐标压缩点集的某个坐标正面投影正面投影正面投影正面投影-压缩压缩压缩压缩到到到到X-X-Z Z坐标面坐标面坐标面坐标面 Xv=xXv=xYvYv=0=0ZvZv=z=z 侧面投影侧面投影侧面投影侧面投影-压缩压缩压缩压缩到到到到Y-Y-Z Z坐标面坐标面坐标面坐标面XwXw=0=0YwYw=y=yZwZw=z=z 水平投影水平投影水平投影水平投影-压缩压缩压缩压缩到到到到X-X-Y Y坐标面坐标面坐标面坐标面 XhXh=x

59、=xYhYh=y=yZhZh=0=02-32-3投影变换投影变换矩阵方法：矩阵方法：矩阵方法：矩阵方法： 正面投影：正面投影：正面投影：正面投影：侧面投影：侧面投影：侧面投影：侧面投影：水平投影：水平投影：水平投影：水平投影：2-32-3投影变换投影变换22展开到一个平面展开到一个平面展开到一个平面展开到一个平面使各投影都处于正面投影面内。使各投影都处于正面投影面内。使各投影都处于正面投影面内。使各投影都处于正面投影面内。正面投影正面投影正面投影正面投影-不动不动不动不动 XX XvY=0Z=XvY=0Z=ZvZv侧面投影侧面投影侧面投影侧面投影-绕绕绕绕Z Z轴逆时针转动轴逆时针转动轴逆时针

60、转动轴逆时针转动9090XX YwYwY=0Z=Y=0Z=ZwZw水平投影水平投影水平投影水平投影-绕绕绕绕X X轴顺时针转动轴顺时针转动轴顺时针转动轴顺时针转动9090XX XhXhY=0Z=Y=0Z=YhYh最后，还要投影到投影坐标系中。最后，还要投影到投影坐标系中。最后，还要投影到投影坐标系中。最后，还要投影到投影坐标系中。2-32-3投影变换投影变换展开到一个平面展开到一个平面展开到一个平面展开到一个平面使各投影都处于正面投影面内。使各投影都处于正面投影面内。使各投影都处于正面投影面内。使各投影都处于正面投影面内。正面投影正面投影正面投影正面投影-不动不动不动不动 XX XvY=0Z=

61、XvY=0Z=ZvZv侧面投影侧面投影侧面投影侧面投影-绕绕绕绕Z Z轴逆时针转动轴逆时针转动轴逆时针转动轴逆时针转动9090XX YwYwY=0Z=Y=0Z=ZwZw水平投影水平投影水平投影水平投影-绕绕绕绕X X轴顺时针转动轴顺时针转动轴顺时针转动轴顺时针转动9090XX XhXhY=0Z=Y=0Z=YhYh第第3章章数据结构数据结构第第第第3 3章章章章数据结构数据结构数据结构数据结构 随着计算机技术的迅速发展，计算机的应用领域已从以数值计算为中心转移到以数据处理为中心。处理的数据也不再只是简单的数值，而是还有图形、图像等复杂的数据。为了使计算机更快速、更有效地处理数据，就必须用有效的、

62、合理的数据结构来组织、存储数据。 数据结构是在一定规则下数据的组织形式。研究数据结构，主要是研究数据之间的逻辑结构（数据之间的关系）和物理结构（数据在计算机中的存储结构）以及这两种结构之间的相互关系，并利用这些关系设计相应的算法。 第第第第3 3章章章章数据结构数据结构数据结构数据结构 数据的逻辑结构是指从具体问题中抽象出来的数据之间的内在关系。逻辑结构可分为以下三类：1线性结构该结构中的数据元素之间存在着一对一的顺序关系。2树形结构该结构中的数据元素之间存在着一对多的关系。3网状结构该结构中的数据元素之间存在着多对多的关系。 后两类又称为非线性结构。第第第第3 3章章章章数据结构数据结构数据

63、结构数据结构 数据的物理结构是指数据在存储器中的存储方式，主要有以下两种不同的存储结构1顺序存储 把逻辑上相邻的数据元素存储在物理位置上相邻的存储单元中，数据间的逻辑关系由存储单元的邻接关系来表示。2链状存储 可以将数据元素存储在任意位置的存储单元中。通过指针来表示数据元素之间逻辑关系。第第第第3 3章章章章数据结构数据结构数据结构数据结构 在计算机图形学中，需要处理大量的图形信息。图形信息主要分为两种：一种是图形的几何信息，指的是形体在空间中的位置、大小尺寸。另一种是拓扑信息，指的是各形体要素（点、线、面等）的数量及其相互间的连接关系。如何组织这些信息，使计算机处理这些信息时可以节省存储单元

64、，加快存取和处理速度，是图形数据结构所要解决的问题。 对于图形数据结构，主要有以下的基本要求： 能够记录图形的几何信息和拓扑信息。 管理方便，即便于查找、增删和修改数据。 较少占用存储单元。 可以快速处理数据。第第第第3 3章章章章数据结构数据结构数据结构数据结构常用数据结构1 线性表结构 线性表是一种最简单、最基本的线性数据结构。所谓线性是指数据元素之间存在“一对一”的关系，具有不多于一个的前趋和后继。线性表是由一组类型相同的数据元素按线性次序排列而成的。它的逻辑结构可以表示为a1,a2,a3an。数据的逻辑结构的下标与物理结构中的存储单元的地址存在着一一对应的关系。它是一种静态结构。 顺序

65、表存储结构的运算 对线性表的数据元素不仅可以进行访问，还可以进行插入、删除等运算，但这些运算是定义在逻辑结构上的，通过存储结构具体实现。第第第第3 3章章章章数据结构数据结构数据结构数据结构 表示数据元素的单元称为结点。把线性表的结点按逻辑次序依次存放在一组按顺序连续排列的存储单元中。用这种方法存储的线性表称为顺序表。 顺序表中相邻的元素在计算机中的存储位置也相邻, 每个结点占用的存储空间的大小也相同。由此可以很容易地确定线性表中的某个结点在存储单元中与初始地址的相对位置。 只要知道表中初始结点的内存地址ad和每个结点在计算机中占用存储单元的长度 c，则可计算出第 i 个结点 ai 的地址 L

66、OC( ai ) = ad + (i-1)c也就是说，结点 ai 的存储地址是该结点在表中的位置 i 的线性函数，可以在相同时间内求出任一结点的存储地址，因此顺序表是一种随机存取结构。第第第第3 3章章章章数据结构数据结构数据结构数据结构插入运算 顺序表插入运算实际上是指在顺序表下标为i-1 和i 的结点之间插入一个值为x 的新结点，使长度为n 的顺序表变成长度为n1 的顺序表该运算的步骤如下：（1）将ai an 之间的所有结点依次后移，为新元素空出第 i 个位置。（2）将新结点x 插入到第 i 个位置。 顺序表上的插入运算，时间主要消耗在结点的移动上。所以当n 较大时，算法的效率较低。删除运

67、算 顺序表结点删除运算是指在顺序表中删除下标为i 的结点，使得长度为n 的顺序表变成长度为n-1 的顺序表。顺序表删除结点运算的步骤如下： 将ai+1 an之间的结点顺序依次向前移动。 在线性表的顺序存储结构中，其特点是存取表方便。但也有其缺点。例如，进行插入和删除运算时需移动大量的结点、效率较低等。 数组结构是线性表结构，常采用顺序存储结构，也有线性表的优、缺点。第第第第3 3章章章章数据结构数据结构数据结构数据结构第第第第3 3章章章章数据结构数据结构数据结构数据结构链式存储结构。 线性表的链式存储结构，也称为链表。其存储方式是：在计算机内存中利用存储单元（不要求连续）来存放结点的值及它在

68、内存中的地址，各个结点的存放顺序及位置可以以任意顺序进行，原来相邻的结点在计算机内存中的存储位置不一定相邻，从一个元素查找下一个元素必须通过地址（指针）才能实现，因此它不能像顺序表那样随机访问，而只能按顺序访问。第第第第3 3章章章章数据结构数据结构数据结构数据结构单链表结构 链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址信息，这个信息称为指针。这两部分信息就组成了链表中的结点结构：其中：data 称为数据域，用来存放结点的值；link 称为指针域，用来存放结点的直接后继的地址。利用每个结点的指针域就可以将n 个

69、结点按其逻辑次序连成一个链表，由于这种链表中每个结点只含有一个指针域，故称为单链表。datalink第第第第3 3章章章章数据结构数据结构数据结构数据结构 由于单链表中每个结点的存储地址是存放在其直接前趋的指针域中，又整个链表应从第一个结点开始，但第一个结点没有直接前趋，故设一个头指针（head）指向开始结点；而最后一个结点没有直接后继，故终端结点的指针域应为空，即NULL（在图中可用符号“”来表示）。第第第第3 3章章章章数据结构数据结构数据结构数据结构单链表的基本运算 单链表与顺序表不同。顺序表在建立时，已定义好此顺序表的界限，并分配给它一块连续的存储单元，而单链表的结点数在定义前是不确定

70、的，单链表中的元素也不是顺序安排的，任意两个结点的存储位置之间没有固定的联系，而是由指针域来表示各结点的前后邻接关系。因此，在单链表中，若要找下标为i 的结点，就必须从第一个结点开始，顺着指针域往下查找。对链表进行插入、删除等运算时，通常也需要经过查找才能确定其存储位置。第第第第3 3章章章章数据结构数据结构数据结构数据结构建立单链表无论对单链表进行何种运算，首先必须建立该链表。链表的建立步骤为：（1）通过某种程序语言提供的函数建立第一个结点所需的存储空间，使指针变量p指向该结点，且将该结点的指针域置为空。（2）将表头指针head 和表尾指针r 指向第一个结点p。从而建立了头结点（3）申请另一

71、个结点，将指针变量p 指向该结点，并对其数据域赋值，置其指针域为空。（4）链接新结点，并修改表尾指针，从而在链表中建立了一个新结点。（5）重复执行步骤（2）、（3）、（4），即可创建整个单链表。第第第第3 3章章章章数据结构数据结构数据结构数据结构单链表中结点的删除设删除运算要将单链表中删除第 i 个结点。只要将第i结点的指针域中的内容（指向第i1 结点）置于第i1结点的指针域中。i1L i1iL ii+1i1L iiL ii+1删除前删除后第第第第3 3章章章章数据结构数据结构数据结构数据结构单链表中结点的插入设插入运算要将值为x 的新结点插入到表的第 i 个位置上，即插入到第i1结点与第i

72、 结点之间。首先从备用存储空间中取出一个结点，指向这个结点的指针为Lx。将第i1结点的指针域中的内容（指向第i 结点）置于新结点的指针域中，再将Lx置于第i1结点的指针域中。i1L i1ii1L xiL iL i1插入前插入后Lx第第第第3 3章章章章数据结构数据结构数据结构数据结构循环链表单链表结点之间是用一个指针域链接，其终端结点的指针域的值为Nil，表示单链表的结束。若将单链表的终端结点的指针域指向头结点，则整个链表头尾结点相链形成一个环，从而就构成了循环链表。循环链表的主要优点是从表中任一结点出发，都能通过后移操作来扫描整个链表（对单链表而言，则只能从头结点开始）。循环链表上的操作与前

73、面讨论的单链表的操作基本一致，差别仅仅在于算法中控制循环中止的条件不是判断指针是否为空，而是判断指针是否指向头指针。双向链表在循环链表中，每个结点只含有一个指向其后继的指针域。若想快速确定一个结点的前趋，则可以在单链表的基础上，每个结点再加上一个指针域，存储其前趋的地址，这样就构成了双向链表。 链表中所有结点通过LL和RL两个指针链接在一起，加上头结点，构成一个双向链表。由于双向链表是一种对称结构，每个结点既有指向其前趋的指针域，又有指向其后继的指针域，因此与单链表相比，要在双向链表中查找一个已知结点的前趋和后继要方便得多。第第第第3 3章章章章数据结构数据结构数据结构数据结构LLDataRL

74、第第第第3 3章章章章数据结构数据结构数据结构数据结构树树的定义树是由n(n 0) 个结点组成的有限集合T，当T 非空时满足如下两个条件：(1)有且仅有一个特定的称为根(Root)的结点；(2) 其余的结点可分为 i ( i 0) 个互不相交的有限集合T1,Ti,这些集合中的每一个又都是一棵树，称为根的子树。树的每个结点都是此树的某个子树的根。树形结构描述的是层次关系，树的结点之间存在一对多的关系。第第第第3 3章章章章数据结构数据结构数据结构数据结构基本术语1父结点、子结点、边若结点y 是结点x 的一棵子树的根，则x 称为y 的父结点，y 称为x 的子结点。2兄弟结点具有同一父结点的子结点之

75、间互称为兄弟结点。3结点的层规定根结点的层数为1，其它结点的层数等于其父结点的层数加1。树中结点的最大层数称为树的高度或树的深度。第第第第3 3章章章章数据结构数据结构数据结构数据结构4结点的度数、树的度数一结点所具有的子结点的个数称为该结点的度数。树中度数最大的结点的度数称为树的度数。5叶结点度数为0 的结点称为叶结点第第第第3 3章章章章数据结构数据结构数据结构数据结构二叉树二叉树是树形结构的一种最常见的类型，许多实际问题抽象出来的数据结构往往就是二叉树。二叉树的定义二叉树是n个结点 ( n 0) 的有限集合,其结点度数最大为2。子结点有序，分为左和右子结点。第第第第3 3章章章章数据结构

76、数据结构数据结构数据结构一般的树能转化为二叉树。其方法是：在各兄弟结点之间加一连线，再把各结点与其子结点（除了最左的子结点外）的连线去掉。左指针指向下一层的首结点，右指针指向同层的下一结点。第第第第3 3章章章章数据结构数据结构数据结构数据结构由于树形结构比线性结构更强调灵活的变化，所以一般情况下二叉树采用双向链表存储结构。第第第第3 3章章章章数据结构数据结构数据结构数据结构作业：作出事件的二叉树，画出描述它的结点指针图结构。一装配体，零件，面，线，点。第第4章章窗口与裁剪窗口与裁剪 第第第第4 4章章章章窗口与裁剪窗口与裁剪窗口与裁剪窗口与裁剪定义定义定义定义投影坐标系：投影图所在平面的坐

77、标系，一般是直角坐标系，投影坐标系：投影图所在平面的坐标系，一般是直角坐标系，投影坐标系：投影图所在平面的坐标系，一般是直角坐标系，投影坐标系：投影图所在平面的坐标系，一般是直角坐标系，无限大。无限大。无限大。无限大。窗口：投影坐标系中限定图形范围的界限，一般取矩形。窗口：投影坐标系中限定图形范围的界限，一般取矩形。窗口：投影坐标系中限定图形范围的界限，一般取矩形。窗口：投影坐标系中限定图形范围的界限，一般取矩形。设备坐标系：图形输出设备输出图形区域的坐标系，一般是设备坐标系：图形输出设备输出图形区域的坐标系，一般是设备坐标系：图形输出设备输出图形区域的坐标系，一般是设备坐标系：图形输出设备输

78、出图形区域的坐标系，一般是直角坐标系，其大小和单位与具体设备有关。直角坐标系，其大小和单位与具体设备有关。直角坐标系，其大小和单位与具体设备有关。直角坐标系，其大小和单位与具体设备有关。视区：设备输出图形区域中用以再现窗口内容的区域，一般视区：设备输出图形区域中用以再现窗口内容的区域，一般视区：设备输出图形区域中用以再现窗口内容的区域，一般视区：设备输出图形区域中用以再现窗口内容的区域，一般与窗口是类似形。与窗口是类似形。与窗口是类似形。与窗口是类似形。纵横比纵横比纵横比纵横比：显示器的象素间距在纵横方向上并不一致。象素纵：显示器的象素间距在纵横方向上并不一致。象素纵：显示器的象素间距在纵横方

79、向上并不一致。象素纵：显示器的象素间距在纵横方向上并不一致。象素纵向间距与横向间距长度之比称为向间距与横向间距长度之比称为向间距与横向间距长度之比称为向间距与横向间距长度之比称为纵横比。纵横比。纵横比。纵横比。SLSL纵向间距纵向间距纵向间距纵向间距 / /横向间距横向间距横向间距横向间距第第第第4 4章章章章窗口与裁剪窗口与裁剪窗口与裁剪窗口与裁剪窗口到视区的窗口到视区的窗口到视区的窗口到视区的变变变变换换换换设在投影坐标系中定义一个窗口，其左下角坐标为设在投影坐标系中定义一个窗口，其左下角坐标为设在投影坐标系中定义一个窗口，其左下角坐标为设在投影坐标系中定义一个窗口，其左下角坐标为(xw1

80、,yw1)(xw1,yw1)，右上角坐标为，右上角坐标为，右上角坐标为，右上角坐标为(xw2,yw2)(xw2,yw2)，窗口窗口窗口窗口内任意点内任意点内任意点内任意点PP(xp,yp)(xp,yp)；在设备坐标系中定义一个视区，其左下角坐标为在设备坐标系中定义一个视区，其左下角坐标为在设备坐标系中定义一个视区，其左下角坐标为在设备坐标系中定义一个视区，其左下角坐标为(xv1,yv1)(xv1,yv1)，右上角坐标为右上角坐标为右上角坐标为右上角坐标为(xv2,yv2)(xv2,yv2)，视区视区视区视区内对应点内对应点内对应点内对应点PP(xp(xp ,yp,yp ) )。为了保证窗口为了

81、保证窗口为了保证窗口为了保证窗口内点相对于内点相对于内点相对于内点相对于窗口窗口窗口窗口与与与与视视视视区区区区内对应点相对于内对应点相对于内对应点相对于内对应点相对于视区视区视区视区的比例关系，的比例关系，的比例关系，的比例关系，坐标之间应当满足下列关系坐标之间应当满足下列关系坐标之间应当满足下列关系坐标之间应当满足下列关系：窗口窗口窗口窗口内点到内点到内点到内点到窗口左边界的距离与窗窗口左边界的距离与窗窗口左边界的距离与窗窗口左边界的距离与窗口长度之比等于视区口长度之比等于视区口长度之比等于视区口长度之比等于视区内点到内点到内点到内点到视区左边视区左边视区左边视区左边界的距离与视区长度之比

82、；界的距离与视区长度之比；界的距离与视区长度之比；界的距离与视区长度之比；窗口窗口窗口窗口内点到内点到内点到内点到窗口下边界的距离与窗窗口下边界的距离与窗窗口下边界的距离与窗窗口下边界的距离与窗口高度之比等于视区口高度之比等于视区口高度之比等于视区口高度之比等于视区内点到内点到内点到内点到视区下边视区下边视区下边视区下边界的距离与视区高度之比。界的距离与视区高度之比。界的距离与视区高度之比。界的距离与视区高度之比。第第第第4 4章章章章窗口与裁剪窗口与裁剪窗口与裁剪窗口与裁剪第第第第4 4章章章章窗口与裁剪窗口与裁剪窗口与裁剪窗口与裁剪其中：其中：其中：其中：l-l-视区视区视区视区长长长长l

83、-l-窗口长窗口长窗口长窗口长h-h-视区高视区高视区高视区高h-h-窗口高窗口高窗口高窗口高SxSx、SySy 分别是由的分别是由的分别是由的分别是由的X X方向和方向和方向和方向和Y Y方向的比例变换因子。方向的比例变换因子。方向的比例变换因子。方向的比例变换因子。经整理，有经整理，有经整理，有经整理，有xp=Sx(xpxw1)+xv1xp=Sx(xpxw1)+xv1ypyp=SySy(ypypyw1)+yv1yw1)+yv1第第第第4 4章章章章窗口与裁剪窗口与裁剪窗口与裁剪窗口与裁剪用矩阵方法表示这个变换：用矩阵方法表示这个变换：用矩阵方法表示这个变换：用矩阵方法表示这个变换：令令令令

84、投影坐标系投影坐标系投影坐标系投影坐标系原点与原点与原点与原点与坐标系坐标系坐标系坐标系原点重合，首先将原点重合，首先将原点重合，首先将原点重合，首先将窗口左下窗口左下窗口左下窗口左下角点角点角点角点平移至原点，然后进行比例变换，使窗口变平移至原点，然后进行比例变换，使窗口变平移至原点，然后进行比例变换，使窗口变平移至原点，然后进行比例变换，使窗口变到与视区到与视区到与视区到与视区同样大小，再将同样大小，再将同样大小，再将同样大小，再将其左下角点其左下角点其左下角点其左下角点平移至平移至平移至平移至视区视区视区视区原始原始原始原始左下角点处左下角点处左下角点处左下角点处。第第第第4 4章章章章

85、窗口与裁剪窗口与裁剪窗口与裁剪窗口与裁剪第第第第4 4章章章章窗口与裁剪窗口与裁剪窗口与裁剪窗口与裁剪一般情况下，一般情况下，一般情况下，一般情况下，SxSySxSy，变换后会产生拉压变形。为了保持，变换后会产生拉压变形。为了保持，变换后会产生拉压变形。为了保持，变换后会产生拉压变形。为了保持原形，应当使原形，应当使原形，应当使原形，应当使Sx1Sx1Sy1Sy1S S。为了在视区内能够把窗口内。为了在视区内能够把窗口内。为了在视区内能够把窗口内。为了在视区内能够把窗口内容完全显示出来，应当有容完全显示出来，应当有容完全显示出来，应当有容完全显示出来，应当有 S=min(S=min(SxSx,

86、 ,SySy) )。第第第第4 4章章章章窗口与裁剪窗口与裁剪窗口与裁剪窗口与裁剪如果设备坐标系的如果设备坐标系的如果设备坐标系的如果设备坐标系的X X，Y Y轴单位长度不相等，还要考虑轴单位长度不相等，还要考虑轴单位长度不相等，还要考虑轴单位长度不相等，还要考虑纵横比处理。纵横比处理。纵横比处理。纵横比处理。X=xSLX=xSLY=yY=y第第第第4 4章章章章窗口与裁剪窗口与裁剪窗口与裁剪窗口与裁剪作业作业作业作业1:1:编程：在用户坐标系中描述五棱柱，将用户坐标系原编程：在用户坐标系中描述五棱柱，将用户坐标系原编程：在用户坐标系中描述五棱柱，将用户坐标系原编程：在用户坐标系中描述五棱柱，

87、将用户坐标系原点平移到世界坐标系的点（点平移到世界坐标系的点（点平移到世界坐标系的点（点平移到世界坐标系的点（10,1010,10，1010）处，在世界坐标系）处，在世界坐标系）处，在世界坐标系）处，在世界坐标系下投影成三视图。再以三视图原点为圆心，画一个圆（下投影成三视图。再以三视图原点为圆心，画一个圆（下投影成三视图。再以三视图原点为圆心，画一个圆（下投影成三视图。再以三视图原点为圆心，画一个圆（R R150150）和十字线。）和十字线。）和十字线。）和十字线。第第第第4 4章章章章窗口与裁剪窗口与裁剪窗口与裁剪窗口与裁剪三、裁剪三、裁剪三、裁剪三、裁剪确定图形在显示区之内部分的过程称为裁

88、剪。确定图形在显示区之内部分的过程称为裁剪。确定图形在显示区之内部分的过程称为裁剪。确定图形在显示区之内部分的过程称为裁剪。裁剪裁剪裁剪裁剪(Clipping)(Clipping)问题是计算机图形学的基本问题之一。问题是计算机图形学的基本问题之一。问题是计算机图形学的基本问题之一。问题是计算机图形学的基本问题之一。裁剪的边界可以是任意多边形，但常用的裁剪边界是矩形。裁剪的边界可以是任意多边形，但常用的裁剪边界是矩形。裁剪的边界可以是任意多边形，但常用的裁剪边界是矩形。裁剪的边界可以是任意多边形，但常用的裁剪边界是矩形。11直线段裁剪直线段裁剪直线段裁剪直线段裁剪因为任何图形都可以用直线段来描述

89、，从而直线段的裁因为任何图形都可以用直线段来描述，从而直线段的裁因为任何图形都可以用直线段来描述，从而直线段的裁因为任何图形都可以用直线段来描述，从而直线段的裁剪问题就成为裁剪的基础。剪问题就成为裁剪的基础。剪问题就成为裁剪的基础。剪问题就成为裁剪的基础。直线两端点相对窗口的位置与线段可见性的关系直线两端点相对窗口的位置与线段可见性的关系直线两端点相对窗口的位置与线段可见性的关系直线两端点相对窗口的位置与线段可见性的关系凸多边形定义：若连接多边形内的任意两点的直线完全凸多边形定义：若连接多边形内的任意两点的直线完全凸多边形定义：若连接多边形内的任意两点的直线完全凸多边形定义：若连接多边形内的任

90、意两点的直线完全处于多边形内，则此多边形称为凸多边形。处于多边形内，则此多边形称为凸多边形。处于多边形内，则此多边形称为凸多边形。处于多边形内，则此多边形称为凸多边形。第第第第4 4章章章章窗口与裁剪窗口与裁剪窗口与裁剪窗口与裁剪由于窗口是一个凸多边形，因此，直线在窗口内部最多为一由于窗口是一个凸多边形，因此，直线在窗口内部最多为一由于窗口是一个凸多边形，因此，直线在窗口内部最多为一由于窗口是一个凸多边形，因此，直线在窗口内部最多为一段。直线段的可见部分可简单地由决定两个端点的方法确定。段。直线段的可见部分可简单地由决定两个端点的方法确定。段。直线段的可见部分可简单地由决定两个端点的方法确定。

91、段。直线段的可见部分可简单地由决定两个端点的方法确定。（1 1）若直线两个端点完全在窗口内，则直线完全在窗口内，完）若直线两个端点完全在窗口内，则直线完全在窗口内，完）若直线两个端点完全在窗口内，则直线完全在窗口内，完）若直线两个端点完全在窗口内，则直线完全在窗口内，完全可见全可见全可见全可见（2 2）若直线两个端点完全在窗口外，有四种可能：）若直线两个端点完全在窗口外，有四种可能：）若直线两个端点完全在窗口外，有四种可能：）若直线两个端点完全在窗口外，有四种可能：直线完全在窗口外直线完全在窗口外直线完全在窗口外直线完全在窗口外不可见不可见不可见不可见直线与窗口相交于窗口角点直线与窗口相交于窗

92、口角点直线与窗口相交于窗口角点直线与窗口相交于窗口角点不可见不可见不可见不可见直线与窗口边线相交直线与窗口边线相交直线与窗口边线相交直线与窗口边线相交有一可见段有一可见段有一可见段有一可见段直线与窗口边线重合直线与窗口边线重合直线与窗口边线重合直线与窗口边线重合有一可见段有一可见段有一可见段有一可见段（3 3）若直线只有一个端点在窗口内，有两）若直线只有一个端点在窗口内，有两）若直线只有一个端点在窗口内，有两）若直线只有一个端点在窗口内，有两种可能：种可能：种可能：种可能：直线与窗口边线相交直线与窗口边线相交直线与窗口边线相交直线与窗口边线相交有一可见段有一可见段有一可见段有一可见段直线与窗口

93、边线重合直线与窗口边线重合直线与窗口边线重合直线与窗口边线重合有一可见段有一可见段有一可见段有一可见段第第第第4 4章章章章窗口与裁剪窗口与裁剪窗口与裁剪窗口与裁剪Cohen-SutherlandCohen-Sutherland裁剪算法裁剪算法裁剪算法裁剪算法编码裁剪法编码裁剪法编码裁剪法编码裁剪法算法思想：扩展窗口的边线，将图算法思想：扩展窗口的边线，将图算法思想：扩展窗口的边线，将图算法思想：扩展窗口的边线，将图形平面分成九个区域。对窗口形平面分成九个区域。对窗口形平面分成九个区域。对窗口形平面分成九个区域。对窗口外每个区域赋予编码。根据线外每个区域赋予编码。根据线外每个区域赋予编码。根据

94、线外每个区域赋予编码。根据线段端点坐标判断其所在区域并段端点坐标判断其所在区域并段端点坐标判断其所在区域并段端点坐标判断其所在区域并赋予相应的编码。如果端点位赋予相应的编码。如果端点位赋予相应的编码。如果端点位赋予相应的编码。如果端点位于窗口边线上，则认为点在靠于窗口边线上，则认为点在靠于窗口边线上，则认为点在靠于窗口边线上，则认为点在靠近窗口的那个区域中。对部分近窗口的那个区域中。对部分近窗口的那个区域中。对部分近窗口的那个区域中。对部分可见的线段，求其与窗口边线可见的线段，求其与窗口边线可见的线段，求其与窗口边线可见的线段，求其与窗口边线的交点，去掉不可见部分。的交点，去掉不可见部分。的交

95、点，去掉不可见部分。的交点，去掉不可见部分。第第第第4 4章章章章窗口与裁剪窗口与裁剪窗口与裁剪窗口与裁剪裁剪一条线段时，若直线两个端裁剪一条线段时，若直线两个端裁剪一条线段时，若直线两个端裁剪一条线段时，若直线两个端点完全在窗口内（编码为空），则线点完全在窗口内（编码为空），则线点完全在窗口内（编码为空），则线点完全在窗口内（编码为空），则线段完全可见；若直线两个端点的编码段完全可见；若直线两个端点的编码段完全可见；若直线两个端点的编码段完全可见；若直线两个端点的编码至少有一个相同的方向（例如至少有一个相同的方向（例如至少有一个相同的方向（例如至少有一个相同的方向（例如ABAB直线直线直线直

96、线都有下方向），则线段完全不可见。都有下方向），则线段完全不可见。都有下方向），则线段完全不可见。都有下方向），则线段完全不可见。否则，按第三种情况处理。求出否则，按第三种情况处理。求出否则，按第三种情况处理。求出否则，按第三种情况处理。求出线段与窗口一条边线的交点。此窗口线段与窗口一条边线的交点。此窗口线段与窗口一条边线的交点。此窗口线段与窗口一条边线的交点。此窗口边线把平面分成两个区域，一个区域边线把平面分成两个区域，一个区域边线把平面分成两个区域，一个区域边线把平面分成两个区域，一个区域包含窗口，我们把它广义地称为窗口包含窗口，我们把它广义地称为窗口包含窗口，我们把它广义地称为窗口包含窗

97、口，我们把它广义地称为窗口内部区域，把另一个区域广义地称为内部区域，把另一个区域广义地称为内部区域，把另一个区域广义地称为内部区域，把另一个区域广义地称为窗口外部区域。求交后，把线段在窗窗口外部区域。求交后，把线段在窗窗口外部区域。求交后，把线段在窗窗口外部区域。求交后，把线段在窗口外的部分去掉。对剩余部分重复上口外的部分去掉。对剩余部分重复上口外的部分去掉。对剩余部分重复上口外的部分去掉。对剩余部分重复上述处理，直至剩余线段完全可见或完述处理，直至剩余线段完全可见或完述处理，直至剩余线段完全可见或完述处理，直至剩余线段完全可见或完全不可见。如图所示，全不可见。如图所示，全不可见。如图所示，全

98、不可见。如图所示，CDCD直线若用窗直线若用窗直线若用窗直线若用窗口左边线求交，交点为口左边线求交，交点为口左边线求交，交点为口左边线求交，交点为E E，则，则，则，则CECE被认被认被认被认为是在窗口外。为是在窗口外。为是在窗口外。为是在窗口外。第第第第4 4章章章章窗口与裁剪窗口与裁剪窗口与裁剪窗口与裁剪求交时，利用直线的点斜式方程。先用两端点坐标求交时，利用直线的点斜式方程。先用两端点坐标求交时，利用直线的点斜式方程。先用两端点坐标求交时，利用直线的点斜式方程。先用两端点坐标(x1,(x1,y1)y1)，(x2,y2)(x2,y2)求出直线的斜率求出直线的斜率求出直线的斜率求出直线的斜率

99、mm。设设设设x1x2x1x2，则，则，则，则m=(y2-y1)/(x2-x1)m=(y2-y1)/(x2-x1)交点坐标为（交点坐标为（交点坐标为（交点坐标为（x,yx,y）m=(y-y1)/(x-x1)m=(y-y1)/(x-x1)与窗口左、右边线相交，则与窗口左、右边线相交，则与窗口左、右边线相交，则与窗口左、右边线相交，则x x已知，其已知，其已知，其已知，其y y值为值为值为值为y=m(x-x1)+y1y=m(x-x1)+y1若与窗口上、下边线相交，则若与窗口上、下边线相交，则若与窗口上、下边线相交，则若与窗口上、下边线相交，则y y已知，其已知，其已知，其已知，其x x值为值为值为

100、值为x=(y-y1)/m+x1x=(y-y1)/m+x1其中其中其中其中m0m0即即即即y1y2y1y2 若若若若m=0m=0，不予处理，直线会被其它窗口边线裁剪。，不予处理，直线会被其它窗口边线裁剪。，不予处理，直线会被其它窗口边线裁剪。，不予处理，直线会被其它窗口边线裁剪。第第第第4 4章章章章窗口与裁剪窗口与裁剪窗口与裁剪窗口与裁剪编程作业：线段裁剪编程作业：线段裁剪编程作业：线段裁剪编程作业：线段裁剪将如图所将如图所将如图所将如图所示线段裁剪示线段裁剪示线段裁剪示线段裁剪后在屏幕上后在屏幕上后在屏幕上后在屏幕上显示出来。显示出来。显示出来。显示出来。第第第第4 4章章章章窗口与裁剪窗口

101、与裁剪窗口与裁剪窗口与裁剪多边形裁剪多边形裁剪多边形裁剪多边形裁剪要求裁剪后多边形是封闭图形。要求裁剪后多边形是封闭图形。要求裁剪后多边形是封闭图形。要求裁剪后多边形是封闭图形。一般情况下，多边形被裁剪后不再是封闭的，因此需要用一般情况下，多边形被裁剪后不再是封闭的，因此需要用一般情况下，多边形被裁剪后不再是封闭的，因此需要用一般情况下，多边形被裁剪后不再是封闭的，因此需要用窗口边线的适当部分来封闭它。窗口边线的适当部分来封闭它。窗口边线的适当部分来封闭它。窗口边线的适当部分来封闭它。SutherlandSutherlandH Hodgmanodgman 逐边裁剪算法逐边裁剪算法逐边裁剪算法逐

102、边裁剪算法算法思想：每次用扩展窗口边线对多边形裁剪，形成一个新的算法思想：每次用扩展窗口边线对多边形裁剪，形成一个新的算法思想：每次用扩展窗口边线对多边形裁剪，形成一个新的算法思想：每次用扩展窗口边线对多边形裁剪，形成一个新的多边形，作为下次裁剪的初始图形，用窗口边依次对多边形裁多边形，作为下次裁剪的初始图形，用窗口边依次对多边形裁多边形，作为下次裁剪的初始图形，用窗口边依次对多边形裁多边形，作为下次裁剪的初始图形，用窗口边依次对多边形裁剪，经四次完成。剪，经四次完成。剪，经四次完成。剪，经四次完成。第第第第4 4章章章章窗口与裁剪窗口与裁剪窗口与裁剪窗口与裁剪步骤：步骤：步骤：步骤：(1)(

103、1)将待裁剪多边形的各顶点按照一定的方向有次序将待裁剪多边形的各顶点按照一定的方向有次序将待裁剪多边形的各顶点按照一定的方向有次序将待裁剪多边形的各顶点按照一定的方向有次序地组成输入顶点表。地组成输入顶点表。地组成输入顶点表。地组成输入顶点表。(2)(2)对输入的顶点进行处理，处理的结果产生一个新对输入的顶点进行处理，处理的结果产生一个新对输入的顶点进行处理，处理的结果产生一个新对输入的顶点进行处理，处理的结果产生一个新的输出顶点表。的输出顶点表。的输出顶点表。的输出顶点表。(3)(3)把输出顶点表作为新的输入顶点表，再次进行算把输出顶点表作为新的输入顶点表，再次进行算把输出顶点表作为新的输入

104、顶点表，再次进行算把输出顶点表作为新的输入顶点表，再次进行算法中的第法中的第法中的第法中的第(2)(2)步。如此重复步。如此重复步。如此重复步。如此重复3 3次。次。次。次。第第第第4 4章章章章窗口与裁剪窗口与裁剪窗口与裁剪窗口与裁剪处理多边形的边线时，一条直线与一条窗处理多边形的边线时，一条直线与一条窗处理多边形的边线时，一条直线与一条窗处理多边形的边线时，一条直线与一条窗口边线的位置关系只有四种。以窗口左边线为口边线的位置关系只有四种。以窗口左边线为口边线的位置关系只有四种。以窗口左边线为口边线的位置关系只有四种。以窗口左边线为例，处理如下：例，处理如下：例，处理如下：例，处理如下： 起

105、点起点起点起点V1V1、终点、终点、终点、终点V2V2都在窗口内，直线可见。都在窗口内，直线可见。都在窗口内，直线可见。都在窗口内，直线可见。将终点送入输出顶点表。将终点送入输出顶点表。将终点送入输出顶点表。将终点送入输出顶点表。 起点起点起点起点V2V2在窗口内，终点在窗口内，终点在窗口内，终点在窗口内，终点V3V3在窗口外，直在窗口外，直在窗口外，直在窗口外，直线部分可见。求出直线与窗口边的交点线部分可见。求出直线与窗口边的交点线部分可见。求出直线与窗口边的交点线部分可见。求出直线与窗口边的交点i1i1，将，将，将，将其送入输出顶点表。其送入输出顶点表。其送入输出顶点表。其送入输出顶点表。

106、 起点起点起点起点V3V3、终点、终点、终点、终点V4V4都在窗口外，直线不可见。没有顶点送入都在窗口外，直线不可见。没有顶点送入都在窗口外，直线不可见。没有顶点送入都在窗口外，直线不可见。没有顶点送入输出顶点表。输出顶点表。输出顶点表。输出顶点表。 起点起点起点起点V4V4在窗口外，终点在窗口外，终点在窗口外，终点在窗口外，终点V1V1在窗口内，直线部分可见。求出在窗口内，直线部分可见。求出在窗口内，直线部分可见。求出在窗口内，直线部分可见。求出直线与窗口边的交点直线与窗口边的交点直线与窗口边的交点直线与窗口边的交点i2i2，将，将，将，将i2i2和终点和终点和终点和终点V1V1送入输出顶点

107、表。送入输出顶点表。送入输出顶点表。送入输出顶点表。按以上处理方法，本例的输入顶点表为按以上处理方法，本例的输入顶点表为按以上处理方法，本例的输入顶点表为按以上处理方法，本例的输入顶点表为V1V1，V2V2，V3V3，V4V4，输出顶点表为，输出顶点表为，输出顶点表为，输出顶点表为V2V2，i1i1，i2i2，V1V1。第第第第4 4章章章章窗口与裁剪窗口与裁剪窗口与裁剪窗口与裁剪作业：作业：作业：作业：已知一平面矩形充满屏幕，长为已知一平面矩形充满屏幕，长为已知一平面矩形充满屏幕，长为已知一平面矩形充满屏幕，长为L L，高为，高为，高为，高为H H，欲将此，欲将此，欲将此，欲将此图形逆时针转

108、动图形逆时针转动图形逆时针转动图形逆时针转动3030度，尽量大地重新显示在屏幕上。请度，尽量大地重新显示在屏幕上。请度，尽量大地重新显示在屏幕上。请度，尽量大地重新显示在屏幕上。请写出变换方法（用等比例变换）、步骤及变换参数。写出变换方法（用等比例变换）、步骤及变换参数。写出变换方法（用等比例变换）、步骤及变换参数。写出变换方法（用等比例变换）、步骤及变换参数。屏幕坐标系如下图所示。屏幕坐标系如下图所示。屏幕坐标系如下图所示。屏幕坐标系如下图所示。xY第第第第5 5章章章章 多边形多边形多边形多边形填充填充填充填充第第5章章多边形多边形填充填充在图形处理中，经常需要在一个封闭图形中进行填充，在

109、图形处理中，经常需要在一个封闭图形中进行填充，例如工程图中的剖面线，木纹等。例如工程图中的剖面线，木纹等。封闭图形都可以用多边形近似表示。封闭图形都可以用多边形近似表示。多边形分为凸多边形、凹多边形、含内环的多边形。多边形分为凸多边形、凹多边形、含内环的多边形。凸多边形：任意两顶点间的连线均在多边形内。凸多边形：任意两顶点间的连线均在多边形内。凹多边形：任意两顶点间的连线有不在多边形内的部分。凹多边形：任意两顶点间的连线有不在多边形内的部分。第第第第5 5章章章章 多边形多边形多边形多边形填充填充填充填充假定我们用水平扫描线对一般多边形（不论凸多边形、假定我们用水平扫描线对一般多边形（不论凸多

110、边形、凹多边形）进行填充。凹多边形）进行填充。对多边形填充的过程可分为四个步骤：对多边形填充的过程可分为四个步骤：a.求扫描线与各边界的交点求扫描线与各边界的交点b.对各交点按对各交点按x由小到大排序由小到大排序c.把边界交点按对分组把边界交点按对分组d.用线段对每对交点之间进行填充用线段对每对交点之间进行填充考查右图，一个多边形的边界两侧必然考查右图，一个多边形的边界两侧必然是多边形的内、外侧；一条扫描线与多边形是多边形的内、外侧；一条扫描线与多边形边界的交点（不含顶点处）必为偶数，且相边界的交点（不含顶点处）必为偶数，且相邻交点间的连线必在多边形内、外交替，即邻交点间的连线必在多边形内、外

111、交替，即扫描线上一段是在多边形内，一段是在多边扫描线上一段是在多边形内，一段是在多边形外，依次交替，没有重迭。形外，依次交替，没有重迭。第第第第5 5章章章章 多边形多边形多边形多边形填充填充填充填充1边界表边界表首先要确定当前扫描线与多边形哪条边界相交。首先要确定当前扫描线与多边形哪条边界相交。假定求交点时是按扫描线的假定求交点时是按扫描线的Y值从小到大顺序进行的。值从小到大顺序进行的。高效方法是将边界分成三种类型：高效方法是将边界分成三种类型：正在求交边：与当前扫描线相交。正在求交边：与当前扫描线相交。退出求交边：当前扫描线的退出求交边：当前扫描线的Y值已经大于边界的最大值已经大于边界的最

112、大Y值。值。等待求交边：当前扫描线的等待求交边：当前扫描线的Y值小于边界的最小值小于边界的最小Y值。值。只对正在求交边进行求交计算。只对正在求交边进行求交计算。设有一条非水平边界，端点坐标为（设有一条非水平边界，端点坐标为（x1,y1）,（x2,y2），），斜率为斜率为m。x=(yy1)/m+x1对应对应y=y1的扫描线，交点的的扫描线，交点的x值为值为x=x1向上移动一条扫描线，向上移动一条扫描线，y=y1+1则有则有xnext=x=(yy1)/m+x1=1/m+x1第第第第5 5章章章章 多边形多边形多边形多边形填充填充填充填充用边界表记录各条用边界表记录各条边界的供判断是否相交和求交计算

113、的信息。边界的供判断是否相交和求交计算的信息。边界表由若干个单向链表组成。表头采用指针数组，每个数边界表由若干个单向链表组成。表头采用指针数组，每个数组元素对应一条扫描线，其中储存一个指针。指针或为空，或指组元素对应一条扫描线，其中储存一个指针。指针或为空，或指向对应单向链表的第一个边界结点。向对应单向链表的第一个边界结点。边界结点如下所示，有四个字段边界结点如下所示，有四个字段YTOP：边界的最大：边界的最大Y值值XMIN：最小：最小Y值值点的点的x坐标坐标MINVERSE：斜率倒数斜率倒数。EXT：指向具有相同指向具有相同最小最小Y值值的下一条边界的指针的下一条边界的指针。YTOPXMIN

114、MINVERSENEXTe2第第第第5 5章章章章 多边形多边形多边形多边形填充填充填充填充边界表由若干个单向链表组成。表头采用指针数组，每个数边界表由若干个单向链表组成。表头采用指针数组，每个数组元素对应一条扫描线，其中储存一个指针。组元素对应一条扫描线，其中储存一个指针。指针或为空，指针或为空，123456xY54321e4e3e2e1e5543210e3e1e5e4或指向对应单向链表的第一个边界结点。或指向对应单向链表的第一个边界结点。e2第第第第5 5章章章章 多边形多边形多边形多边形填充填充填充填充2顶点条件顶点条件当两条边界都在扫描线的同侧时，这个顶点称为极点。当两条边界都在扫描线

115、的同侧时，这个顶点称为极点。当两条边界分别在扫描线的两侧时，若把这个顶点按两个交当两条边界分别在扫描线的两侧时，若把这个顶点按两个交点计算，将引起不正确的填充。点计算，将引起不正确的填充。解决算法：在扫描线上方的边界，按缩短处理。解决算法：在扫描线上方的边界，按缩短处理。12xY4321e25432101.5e1e112xY4321e2e1e25432101e1baa第第第第5 5章章章章 多边形多边形多边形多边形填充填充填充填充3扫描线表扫描线表扫描线与各边界的交点，是一个单向链表，扫描线与各边界的交点，是一个单向链表，其结点结构与边界表中的相同。不同的是在扫描其结点结构与边界表中的相同。不

116、同的是在扫描线表的线表的XMIN字段中，存的是当前扫描线与某边字段中，存的是当前扫描线与某边界交点的界交点的X坐标。坐标。第第第第5 5章章章章 多边形多边形多边形多边形填充填充填充填充4算法算法（1）建立边界表。）建立边界表。（2）把扫描线表指针初始化，令其为）把扫描线表指针初始化，令其为NIL。（3）从边界表表头数组的非空元素开始，直到当前扫描线的）从边界表表头数组的非空元素开始，直到当前扫描线的Y值值超过多边形的最大超过多边形的最大Y值为止，重复进行以下步骤：值为止，重复进行以下步骤：a根据当前根据当前Y值，把边界表中对应的链表与当前扫描线表合并值，把边界表中对应的链表与当前扫描线表合并

117、成新的扫描线表，其结点按成新的扫描线表，其结点按XMIN值递增排序。值递增排序。b对扫描线表中的每对结点之间进行填充。对扫描线表中的每对结点之间进行填充。c从扫描线表中把从扫描线表中把YTOP值等于当前值等于当前Y值的边界删除。值的边界删除。d对于在扫描线表中保留下来的每一条边界，求出它们与下对于在扫描线表中保留下来的每一条边界，求出它们与下一扫描线的交点的一扫描线的交点的X坐标，送入坐标，送入XMIN。e按新的按新的XMIN值将扫描线表重新按递增排序。值将扫描线表重新按递增排序。f把当前把当前Y值加值加1，进行下一扫描线的运算。，进行下一扫描线的运算。第第第第5 5章章章章 多边形多边形多边

118、形多边形填充填充填充填充算法举例算法举例12345678910xY87654321e4e3e2e1e5e6e7543210e33 1e2e5e64 87e77 5 -1e48 58第第第第5 5章章章章 多边形多边形多边形多边形填充填充填充填充算法举例算法举例12345678910xY87654321e4e3e2e1e5e6e7543210e33 1e2e5e64 87e77 5 -1e48 58第第第第5 5章章章章 多边形多边形多边形多边形填充填充填充填充12345678910xY87654321e4e3e2e1e5e6e7当前扫描线表当前扫描线表3 1e24 8e713 1e24 8e7

119、合并后的新扫描线表合并后的新扫描线表1的的边界表边界表3e24e7第第第第5 5章章章章 多边形多边形多边形多边形填充填充填充填充12345678910xY87654321e4e3e2e1e5e6e7当前扫描线表当前扫描线表3e24e723e24e7合并后的新扫描线表合并后的新扫描线表2的的边界表边界表3e24e72第第第第5 5章章章章 多边形多边形多边形多边形填充填充填充填充12345678910xY87654321e4e3e2e1e5e6e7当前扫描线表当前扫描线表3e24e733e24e7合并后的新扫描线表合并后的新扫描线表3的的边界表边界表4e7e2第第第第5 5章章章章 多边形多边

120、形多边形多边形填充填充填充填充12345678910xY87654321e4e3e2e1e5e6e7当前扫描线表当前扫描线表4e747e34e7合并后的新扫描线表合并后的新扫描线表4的的边界表边界表7e3e37e7第第第第5 5章章章章 多边形多边形多边形多边形填充填充填充填充12345678910xY87654321e4e3e2e1e5e6e7当前扫描线表当前扫描线表57e3合并后的新扫描线表合并后的新扫描线表5的的边界表边界表7e3e5e67 5 -1e48 58e5e675-1e48 587e3e5e67-1e488第第第第5 5章章章章 多边形多边形多边形多边形填充填充填充填充1234

121、5678910xY87654321e4e3e2e1e5e6e7当前扫描线表当前扫描线表6合并后的新扫描线表与当前扫描线表相同合并后的新扫描线表与当前扫描线表相同6的的边界表边界表7e3e5e67 4 -1e4887e3e5e67-1e488第第第第5 5章章章章 多边形多边形多边形多边形填充填充填充填充12345678910xY87654321e4e3e2e1e5e6e7当前扫描线表当前扫描线表77的的边界表边界表7e3e5e67 3 -1e488e3e5e6e488合并后的新扫描线表与当前扫描线表相同合并后的新扫描线表与当前扫描线表相同第第第第5 5章章章章 多边形多边形多边形多边形填充填充

122、填充填充12345678910xY87654321e4e3e2e1e5e6e7当前扫描线表当前扫描线表88的的边界表边界表e5e688e5e6合并后的新扫描线表与当前扫描线表相同合并后的新扫描线表与当前扫描线表相同第第第第6 6章章章章隐线消除隐线消除隐线消除隐线消除第6章 隐线消除一、一、概述概述人们从一个方向观察不透明物体时，物体总可以分为可见部人们从一个方向观察不透明物体时，物体总可以分为可见部分和不可见部分。计算机无法自动区分物体的可见部分和不可见分和不可见部分。计算机无法自动区分物体的可见部分和不可见部分。如果把所有线条都画出来，则立体的图形就缺乏真实感，部分。如果把所有线条都画出来

123、，则立体的图形就缺乏真实感，往往导致图形的二义性（位置或形状不确定）。往往导致图形的二义性（位置或形状不确定）。第第第第6 6章章章章隐线消除隐线消除隐线消除隐线消除要消除二义性，绘出确定的、有真实感的立体图形，要消除二义性，绘出确定的、有真实感的立体图形，就必须消去表示形体中的不可见部分的线条或面。这就是就必须消去表示形体中的不可见部分的线条或面。这就是计算机图形学中的消隐问题。计算机图形学中的消隐问题。消隐从原理上讲并不复杂。只要把被考察元素（线、消隐从原理上讲并不复杂。只要把被考察元素（线、面）与其它元素比较，即可判断出哪些元素被遮挡。面）与其它元素比较，即可判断出哪些元素被遮挡。在消隐

124、过程中，最基本的运算是判断面对线的遮挡关在消隐过程中，最基本的运算是判断面对线的遮挡关系。在判断中，需要地进行大量的线线、线面之间的求交系。在判断中，需要地进行大量的线线、线面之间的求交运算。因此，需要研究出高效的算法。对算法的要求首先运算。因此，需要研究出高效的算法。对算法的要求首先是正确，然后是计算量小，占用存储空间小。是正确，然后是计算量小，占用存储空间小。第第第第6 6章章章章隐线消除隐线消除隐线消除隐线消除二基本计算方法二基本计算方法1平面内直线段相交平面内直线段相交平面内两直线（无限长）不平行则相交。但在两相交直线上平面内两直线（无限长）不平行则相交。但在两相交直线上的线段却可能不

125、相交。的线段却可能不相交。a用两点式方程表示的直线，求有效交点用两点式方程表示的直线，求有效交点xx1=(x2x1)(yy1)/(y2y1)xx3=(x4x3)(yy3)/(y4y3)令令Ea(x2x1)F=(x4x3)G(y2y1)H(y4y3)代入上式代入上式有有第第第第6 6章章章章隐线消除隐线消除隐线消除隐线消除若若GFEH0即即E/GF/H两直线斜率相等，它们平行或重合。两直线斜率相等，它们平行或重合。两相交直线上的交点有效性是指点两相交直线上的交点有效性是指点P（x,y）同时位于两直线段的端点范围之）同时位于两直线段的端点范围之内。内。考察右图，可以看出，有效交点的坐考察右图，可以

126、看出，有效交点的坐标必须满足下式：标必须满足下式：(xx1)(xx2)0(xx3)(xx4)0xYp4p3p2p1p5p6b用参数方程表示的直线，求有效交点用参数方程表示的直线，求有效交点Llx=x1(x2x1)y=y1(y2y1)第第第第6 6章章章章隐线消除隐线消除隐线消除隐线消除xYp4p3p2p1p5p6其中其中是线段上任意点是线段上任意点P到线段端到线段端点点P1的距离与线段长度之比。若的距离与线段长度之比。若0，P在在P1处；处；1，P在在P2处；处；01时，时，P点一定在线段范围内。点一定在线段范围内。L2x=x3(x4x3)y=y3(y4y3)若若P点是点是L1与与L2的交点，

127、必同时满足其的参数方程，则有：的交点，必同时满足其的参数方程，则有：x1(x2x1)=x3(x4x3)y1(y2y1)=y3(y4y3)从而求得从而求得第第第第6 6章章章章隐线消除隐线消除隐线消除隐线消除可以看出，有效交点的坐标必须满足下式：可以看出，有效交点的坐标必须满足下式：0101若若(x4x3)(y2y1)(x2x1)(y4y3)0，则两线平行。则两线平行。2最小投影矩形检验最小投影矩形检验可以包含平面多边形投影的最小矩形称为此多边形的最小可以包含平面多边形投影的最小矩形称为此多边形的最小投影矩形。投影矩形。两平面的最小投影矩形若不发生重叠，则从投影方向观察两平面的最小投影矩形若不发

128、生重叠，则从投影方向观察它们，必定不会发生相互遮挡。因此可以利用最小投影矩形来它们，必定不会发生相互遮挡。因此可以利用最小投影矩形来迅速判断，排除互不遮挡的面，从而避免进行进一步的检验，迅速判断，排除互不遮挡的面，从而避免进行进一步的检验，减少计算量，加快处理速度。减少计算量，加快处理速度。最小投影矩形的位置和大小用最小投影矩形的位置和大小用Xmin、Ymin、Xmax和和Ymax表示。若两个最小投影矩形表示。若两个最小投影矩形A、B不发生重叠，必定满足不发生重叠，必定满足下面的四个不等式之一下面的四个不等式之一：XaminXbmaxYaminYbmaxXamaxXbminYamaxYbmin

129、若上述四个不等式得不到满足，表明这两个最小投影矩形若上述四个不等式得不到满足，表明这两个最小投影矩形相互重叠。为了确定其中的多边形投影是否重叠，还需要进行相互重叠。为了确定其中的多边形投影是否重叠，还需要进行进一步的检验和判断。进一步的检验和判断。第第第第6 6章章章章隐线消除隐线消除隐线消除隐线消除第第第第6 6章章章章隐线消除隐线消除隐线消除隐线消除3平面体表面外法线与可见性平面体表面外法线与可见性由立体的内部指向立体外部的平面法线称为外由立体的内部指向立体外部的平面法线称为外法线法线。用。用N表示。表示。我们可以把平面的一个表面假想为正面和背面。我们可以把平面的一个表面假想为正面和背面。

130、背面处在物体的内部，看不见。背面处在物体的内部，看不见。第第第第6 6章章章章隐线消除隐线消除隐线消除隐线消除设物体放在三维直角坐标系中，取视轴设物体放在三维直角坐标系中，取视轴E平行于一个坐标轴，平行于一个坐标轴，由物体指向观察由物体指向观察者。者。E与与N的夹角为的夹角为。N NE EN NE EN NE E若若00，观察者可以看到平面的正面，观察者可以看到平面的正面。若若90，则，则Cos 0，平面积聚为一条直线，平面积聚为一条直线。若若90180，则，则Cos 0，则，则Cos 0，平面可见，平面可见。B0，则，则Cos 0，平面积聚为一条直线，与其它，平面积聚为一条直线，与其它可见面

131、的边线重合，可不予处理可见面的边线重合，可不予处理。B0，则，则Cos 0，即，即ysyp，则，则P在平面之后，被平面遮挡。在平面之后，被平面遮挡。若若ts=0，则，则P在平面上。在平面上。若若ts0，则，则P在平面之前，在平面之前，不被平面遮挡。不被平面遮挡。第第第第6 6章章章章隐线消除隐线消除隐线消除隐线消除三平面描述及数据结构三平面描述及数据结构1平面描述平面描述平面多边形由边围成，其上可能还有孔。我们把平面多边平面多边形由边围成，其上可能还有孔。我们把平面多边形的边框定义为外环和内环。外环由一平面的外轮廓上的边构形的边框定义为外环和内环。外环由一平面的外轮廓上的边构成，其顶点按逆时针

132、方向顺次排列；内环由平面内的孔的轮廓成，其顶点按逆时针方向顺次排列；内环由平面内的孔的轮廓边围成，其顶点按顺时针方向顺次排列。一个平面只有一个外边围成，其顶点按顺时针方向顺次排列。一个平面只有一个外环，可以有若干个内环。环，可以有若干个内环。第第第第6 6章章章章隐线消除隐线消除隐线消除隐线消除2数据结构数据结构1）体表表中记录一个体的信息，如体的最小盒子参）体表表中记录一个体的信息，如体的最小盒子参数，体上表面数，下一体地址指针，首面地址指针，首点地址数，体上表面数，下一体地址指针，首面地址指针，首点地址指针等。指针等。2）面表表中记录一个面的信息，如面的最小投影矩）面表表中记录一个面的信息

133、，如面的最小投影矩形参数，面上环数，下一面地址指针，首环地址指针，面方程形参数，面上环数，下一面地址指针，首环地址指针，面方程系数系数A、B、C、D等。等。3）环表表中记录一个环的信息，如环上边数，（有）环表表中记录一个环的信息，如环上边数，（有时也可直接记录组成环的顶点序号，这样就隐含了边的信息，时也可直接记录组成环的顶点序号，这样就隐含了边的信息，从而省去了边表），下一环地址指针。从而省去了边表），下一环地址指针。4）边表表中记录边的两端点的序号。）边表表中记录边的两端点的序号。5）点表表中记录各顶点的坐标。）点表表中记录各顶点的坐标。第第第第6 6章章章章隐线消除隐线消除隐线消除隐线消除

134、四任意平面体的消隐算法四任意平面体的消隐算法首先计算各表面的首先计算各表面的B值，根据值，根据B值去除所有朝后面和积聚值去除所有朝后面和积聚面。这样，对一个复杂的立体，可能能去除一半的表面，从而面。这样，对一个复杂的立体，可能能去除一半的表面，从而大大减少求交计算量。剩下的朝前面，我们不妨称它为可能可大大减少求交计算量。剩下的朝前面，我们不妨称它为可能可见面。见面。对于凸多面体，所有朝前面都是可见面，消隐处理至此结对于凸多面体，所有朝前面都是可见面，消隐处理至此结束。束。对于凹多面体，朝前面之间还可能互相遮挡，所以还要对对于凹多面体，朝前面之间还可能互相遮挡，所以还要对可能可见面进行处理。可能

135、可见面进行处理。第第第第6 6章章章章隐线消除隐线消除隐线消除隐线消除1任意拿出一个可能可见面任意拿出一个可能可见面A，用面的最小投影矩形检验，用面的最小投影矩形检验，去除不可能遮挡它的面。去除不可能遮挡它的面。2拿出拿出A面上的一条边面上的一条边Ea，用，用Ea的最小投影矩形与剩下的的最小投影矩形与剩下的面的最小投影矩形进行比较，去除不可能遮挡面的最小投影矩形进行比较，去除不可能遮挡Ea的面。的面。3用用Ea的最小投影矩形与可能遮挡的最小投影矩形与可能遮挡Ea的面的面B上的各边上的各边Eb的的最小投影矩形进行比较，去除此面上不可能遮挡最小投影矩形进行比较，去除此面上不可能遮挡Ea的边。的边。

136、4用用Ea与此面上剩余的边进行求交计算，记下与此面上剩余的边进行求交计算，记下Ea与各边与各边Eb的有效交点，把这些交点按其参数的大小排序。的有效交点，把这些交点按其参数的大小排序。EaAAAEaEbBBB第第第第6 6章章章章隐线消除隐线消除隐线消除隐线消除5以两交点间线段为一子段，依次取各子段的中点，用以两交点间线段为一子段，依次取各子段的中点，用包含性检验法判断此子段是否在此可能遮挡面多边形范围内，包含性检验法判断此子段是否在此可能遮挡面多边形范围内，用深度检验确定此面是否遮挡此子段，从而确定用深度检验确定此面是否遮挡此子段，从而确定(对于此面而对于此面而言言)Ea上的可见子段和不可见子段。上的可见子段和不可见子段。最后，对求出的最后，对求出的Ea边相对于各可能遮边相对于各可能遮挡面的可见子段进行集合求交计算，以确定挡面的可见子段进行集合求交计算，以确定最后输出的可见子段。最后输出的可见子段。11121314151621221112212210-210-2图形变换图形变换结束结束谢谢谢谢