计算机图形学(教案)

1、徐光伟一、本课程的性质、地位和作用二、本课程的教学基本要求 1了解图形系统的框架及其涉及的软件、硬件技术； 2了解图形学基本问题，掌握基本概念、方法与算法； 3掌握基本图形（二维）和几何实体（三维）生成技术； 4. 具有一定实践体会和相关的编程能力。三、教材及参考书目 1Donald Hearn, M. Pauline Baker ,“Computer Graphics (C Version)”, Prentice Hall , 1997. 2计算机图形学（新版） 孙家广编 清华大学出版社 3计算机图形学基础 唐泽圣等著清华大学出版社 4. 计算机图形学（Computer Graphics）.

2、 Donald Hearn et al. 蔡士杰译. 电子工业出版社 5. Fundamentals of Computer Graphics, Peter Shirley, second edition, AK Peters四、基础知识要求 熟练的编程能力，数据结构和算法五、每日课堂练习和作业提交 计算机图形学是研究用计算机表示、生成、处理和显示图形的学科。它涉及将几何模型和数据转变为图形的各种算法和技术。 11l图形通常由点、线、面、体等几何元素和灰度、色彩、线型、线宽等非几何属性组成。从处理技术上来看，图形主要分为两类，一类是由线条组成的图形，如工程图、等高线地图、曲面的线框图等，另一类

3、是类似于照片的明暗图(Shading)，也就是通常所说的真实感图形。13.7尺68.5尺9.5尺13.7尺9.5尺9.5尺9.5尺9.5尺13.7尺13.7尺13.7尺l计算机图形产生的方法(1)矢量法(短折线法)任何曲线用许多首尾相连的短直线(矢量)逼近.(2)描点法(相临像素串接法)曲线由发亮的相素点串接起来.l图形与图像两个概念间的区别越来越模糊，但还是有区别的：图像纯指计算机内以位图(Bitmap)形式存在的灰度信息，而图形含有几何属性，或者说更强调场景的几何表示，是由场景的几何模型和景物的物理属性共同组成的。 1950年，第一台图形显示器作为美国麻省理工学院（MIT）旋风I号（Whi

4、rlwind I）计算机的附件诞生了。该显示器用一个类似于示波器的阴极射线管（CRT）来显示一些简单的图形。 1958年美国Calcomp公司由联机的数字记录仪发展成滚筒式绘图仪，GerBer公司把数控机床发展成为平板式绘图仪。在整个50年代，只有电子管计算机，用机器语言编程，主要应用于科学计算，为这些计算机配置的图形设备仅具有输出功能。计算机图形学处于准备和酝酿时期，并称之为：“被动式”图形学 1950年代初到1960年代中，MIT开始计算机辅助设计/计算机辅助制造（CAD/CAM）的研究； 1964年MIT的教授Steven A. Coons提出了插值四条任意的边界曲线的Coons曲面；

5、1966年，法国雷诺汽车公司的工程师Pierre Bzier发展了一套自由曲线和曲面的方法； 1975年Versprille提出有理B样条的理论。 1974年，美国国家标准化局（ANSI）在ACM SIGGRAPH的一个与“与机器无关的图形技术”的工作会议上，提出了制定有关标准的基本规则。 CGI(Computer Graphics Interface) ； CGM（Computer Graphics Metafile） ； GKS(Graphics Kernel system) ； PHIGS(Programmers Hierarchical Interactive Graphics Sta

6、ndard) ； 1992年，美国SGI(Silicon Graphics, Inc.)推出了OpenGL 。l最后，我们以SIGGRAPH会议的情况，来结束计算机图形学的历史回顾。ACM SIGGRAPH会议是计算机图形学最权威的国际会议，每年在美国召开，参加会议的人在50,000人左右。世界上没有第二个领域每年召开如此规模巨大的专业会议，SIGGRAPH会议很大程度上促进了图形学的发展。因为每年只录取大约50篇论文，在Computer Graphics杂志上发表，因此论文的学术水平较高，基本上代表了图形学的主流方向。 三维景物的表示； 三维场景的显示； 基于图象和图形的的混合绘制技术； 自

7、然景物仿真； 图形用户接口； 虚拟现实； 动画技术； 可视化技术； 几何和图形数据的存储，包括数据压缩和解压缩； 图形硬件、图形标准、图形交互技术。 l计算机辅助设计计算机辅助设计 l图示图形学图示图形学 如如wordword中的各种报表中的各种报表l计算机艺术计算机艺术 l娱乐娱乐 l教学与培训教学与培训 l可视化可视化 l图像处理图像处理 l图形用户界面图形用户界面 lCAD/CAM是计算机图形学在工业界最广泛、最活跃的应用领域 ,美国波音飞机公司已用有关的CAD系统实现波音777飞机的整体设计和模拟。l随着计算机网络技术的发展，在网络环境下进行异地异构系统的协同设计，已经成为CAD领域最

8、热门的课题之一。 l三维几何造型系统具有许多优点，例如，可以进行装配件的干涉检查，可以用于有限元分析、仿真、数控加工等后续操作，它基本上代表了CAD技术的发展方向。l目前科学计算可视化广泛应用于医学、流体力学、有限元分析、气象分析当中。尤其在医学领域，可视化有着广阔的发展前途。机械人和医学专家配合做远程手术是目前医学上很热门的课题，而这些技术的实现的基础则是可视化。 l北京海军总医院远程会诊中心，专家正通过电脑监视延安大学附属医院手术室内的手术过程。l在计算机中重现真实世界场景的过程叫做真实感绘制。真实感绘制的主要任务是要模拟真实物体的物理属性，即物体的形状、光学性质、表面的纹理和粗糙程度，以

9、及物体间的相对位置、遮挡关系等等。 日本Yoshinori Dobashi等人绘制的真实感云（Siggraph2000） l基于图像的建模技术和绘制技术 l艺术重构l早期的计算机动画灵感来源于传统的卡通片，在生成几幅被称做“关键帧”的画面后，由计算机对两幅关键帧进行插值生成若干“中间帧”，连续播放时两个关键帧就被有机地结合起来了。 l20世纪90年代是计算机动画应用辉煌的十年。Disney公司每年都要出一部制作精美的卡通动画片，好莱坞的大片屡屡大量运用计算机生成各种各样精彩绝伦的动画特技效果，广告设计、电脑游戏也频频运用计算机动画。计算机动画也因这些商业应用的大力推动而有了极大的发展。 l基于

10、特征的图象变形（猫变虎）l三维FFD得到的鱼变形图 lGEORGE BORSHUKOV在“基于图像的脸部动画在Matrix中的应用” lGEORGE BORSHUKOV在matrix中的真实人脸渲染论文 lGEORGE BORSHUKOV在生成真实头发的技术论文 l目前几个大的软件公司都在研究下一代用户界面，开发面向主流应用的自然、高效多通道的用户界面。研究多通道语义模型、多通道整合算法及其软件结构和界面范式是当前用户界面和接口方面研究的主流方向，而图形学在其中起主导作用。 l现在的美术人员、尤其是商业艺术人员都热衷于用计算机软件从事艺术创作。可用于美术创作的软件很多，如二维平面的画笔程序(如

11、CorelDraw，Photoshop， PaintShop)、专门的图表绘制软件(如Visio)、三维建模和渲染软件包(如3DMAX，Maya)、以及一些专门生成动画的软(如 Alias，Softimage)等，可以说是数不胜数。这些软件不仅提供多种风格的画笔画刷，而且提供多种多样的纹理贴图，甚至能对图象进行雾化变形等操作。很多功能是一个传统的艺术家无法实现也不可想象的。 Georges Winkenblach绘制的壶和碗（Siggraph96） Salisbury绘制的茶壶（Siggraph97） S a l i s b u r y 绘 制 的 熊 （Siggraph97） Oliver

12、Deussen绘制的素描树（Siggraph2000） （1）、刷新式CRT 在CRT结构中，灯丝、阴极、控制栅、加速电极以及聚焦系统组成了电子枪。黑白CRT中仅有一支电子枪，而在彩色CRT中有三支电子枪，其发射的电子束分别轰击荧光粉层上的红、绿、蓝荧光点。灯丝 阴极控制栅聚焦系统偏转系统荧光层加速电极CRT结构示意图 电子束轰击荧光屏的荧光层产生亮点，通过快速控制电子束反复重画图象来维持荧光的亮度。 分辨率（resolution）：水平和垂直方向上每厘米可绘制的点数。 问题：这里的分辨率与通常说的一个显示器件的分辨率为1024*768有什么差异？ 纵横比（aspect ratio）：在屏幕的

13、水平和垂直两个方向生成同等长度的线段所需要的垂直点数对水平点数的比值。通常的纵横比为3/4。 帧缓冲存储器(也叫视频存储器)，简称帧缓存，用来存放图形信息。 帧缓存的地址和屏幕地址是一一对应的， 其中所存的信息就是屏幕上对应位置的图形信息，这些信息在存储器内的分布完全和屏幕上所显示图形的形状及颜色、 明暗程度相对应。要在屏幕上显示图形，首先要将图形信息写入帧缓存器中，然后显示系统访问帧缓存器，再把其中的内容显示在屏幕上， 这就是我们看到的图形。l1、光栅扫描显示器 在光栅扫描系统中，电子束横向扫描屏幕，一次一行，从顶到底依次进行。每个屏幕点作为一个像素（pixel）。每个像素一位，又称为位图。

14、 2、随机扫描显示器 CRT的电子束只在屏幕的图形部分移动。随机扫描显示器生成光滑线条，而光栅系统生成锯齿状线条。l3、彩色CRT监视器 利用能发射不同颜色光的荧光层的组合来显示彩色图形。l4、平板显示器 平板显示器包括两类：发射显示器和非发射显示器。 1键盘2鼠标3操纵杆 手 柄按 钮4数据手套5数字化仪6图象扫描仪7. 光笔 光笔是一种能检测出屏幕上亮光的笔, 它具有拾取功能。 光笔的形状和大小像一支圆珠笔，笔尖处开有一个圆孔，让荧光屏上的光通过这个孔进入光笔。SPL4001.3.4Y 向 电 机X 向 电 机导 轨台 面图 纸横 梁笔笔 架XY (1)打印机 图形打印机按其记录原理分类，

15、有点阵针式打印机、喷墨打印机、激光打印机、热敏打印机、热转印打印机等。目前应用较广的是前三种打印机。l点阵针式打印机点阵针式打印机 点阵针式打印机技术成熟，价格低，使用费用低(普通纸即可， 色带耐用且便宜)， 特别是Epson LQ-1600 系列打印机， 用量极大，几乎垄断了点阵针式打印机市场。对于出图质量要求不是很高或出草图时用此打印机合算。 l(2). 绘图仪压辊笔控制面板笔架图纸控制装置计算机 Z Z Y Y X XY 向电机X向电机YX抬笔落笔笔笔架滚筒图纸总结： 计算机图形学怎么学，能学到什么知识l基本的直线、圆弧和曲线生成图形基本的直线、圆弧和曲线生成图形算法算法l区域填充区域填

16、充l字符生成字符生成 l输出图元的属性输出图元的属性 (线型、宽度和颜色线型、宽度和颜色)l光栅图形反走样光栅图形反走样 l二维几何变换、投影变换二维几何变换、投影变换l二维观察、裁剪二维观察、裁剪l三维物体表示与真实感图形显示三维物体表示与真实感图形显示l高中级别的代数和三角学 高中级别的代数和三角学也许是开始学计算机图形学中最重要的数学领域了。经常需要进行简单的三角运算诸如从一些几何图形的边长和角度推导出某些边长。代数和三角学是两门可以解决图形学日常问题的学科。 推荐书籍：推荐书籍：Computer Graphics: Principles and Practice James Foley

17、, Andries van Dam, Steven Feiner, John Hughes Addison-WesleylLinear Algebra 线代的思想贯穿整个图形学。事实上，任何跟几何数值表示相关的领域通常把数字如x,y,z集中到一个叫做向量vector的数学对象中。向量和一个相关的叫做矩阵的数学对象在图形学中一直使用。向量和矩阵是一门用于描述一个对象旋转转移变大变小的一种优雅的方式。 推荐书籍：推荐书籍： Linear Algebra and Its Applications Gilbert Strang Academic Press lCalculus 微积分的知识。如果你打算

18、在图形学里进行研究，强烈推荐你有个微积分的基础。不仅仅是因为需要用到相关知识，而且因为许多研究者用微积分的语言描述他们的问题和解法。而且许多数学领域也将微积分作为先行要求。这是除了基本代数以外的一个能作为你未来的数学理解的敲门砖的数学领域。 lDifferential Geometry微分几何 这部分数学研究了那些控制平滑曲线和表面的几何的方程。如果你试图研究出什么方向是垂直于平滑曲面，那么你应该使用微分几何。以一个速度沿着曲线进行机械运动也是微分几何。在图形学中有一种普遍的技巧叫做凹凸映射，让一个平滑的表面看起来粗糙；这种方法也是依赖于微分几何。如果你打算和用来生成形状的曲线和表面（也就是建

19、模）打交道的话，那么你至少得学一些微分几何的基础。多变量的微积分是这个方面的先行要求。 推荐书籍：推荐书籍： - Elementary Differential Geometry Barrett ONeill Academic Press lNumerical Methods数值方法 几乎每次我们表示或操作计算机中的数字时，我们都是使用了近似值。正因为此，总有错误的可能性出现。而且，对于一个给定的数学问题，有许多方法可以解决。一些更快更准确或者需要更少的内存。研究这些问题通常涉及到“数值方法”和“科学计算”（numerical methods and scientific computing）

20、。这是一个非常广的领域，包括了取样理论（sampling theory）, 矩阵方程（matrix equations）, 微分方程的数值解法（numerical solution of differential equations）, 还有优化问题（optimization）. 推荐书籍：推荐书籍：Numerical Recipes in C: The Art of Scientific Computing William Press, Saul Teukolsky, William Vetterling and Brian Flannery Cambridge University Pre

21、ss lSampling Theory and Signal Processing 在计算机图形学，我们将一些对象如图形或几何表面表达为存储在二维数组的数字集合。无论什么时候，我们都是生成一个取样后的对象。如果我们要控制某些几何表达方法的质量，抽样理论的理解是非常重要的。抽样中一个普遍的运用到图形中问题是当显示在屏幕上时边缘锯齿会出现在一个对象的黑色剪影上。这些锯齿边缘的外形（就是“走样”）非常没有吸引力，但这可以通过抽样理论很好理解的技巧最小化。这个理论的核心是一些卷积，傅立叶变换和空间频率表达的方程的概念。这些在图像和声音处理中同样很重要。 推荐书籍：推荐书籍： The Fourier T

22、ransform and Its Applications Ronald N. Bracewell McGraw Hill lMatrix Equations 矩阵方程的数值解法。这些问题包括：找到最佳位置和朝向使一个矩阵匹配另一个( “最小方阵”问题), 生成一个覆盖给定点集的表面, 和模拟某些材料如水或者衣服。 推荐书籍：推荐书籍： Matrix Computations Gene Golub and Charles Van Loan Johns Hopkins University Press lPhysics 物理很明显是自成一体的学科而非数学的子类。然而物理和数学在图形学中却紧紧相连

23、。涉及物理的图形学例子包括光如何和对象表面作用，光在一个复杂环境如何反弹，动物和人怎么运动，水和风的运动。物理知识对模拟这些现象非常重要。这和下面要提到的解微分方程密切相关。lNumerical Solutions of Differential Equations 解微分方程对图形学是极端重要的。一些图形学致力于模拟真实世界的物理系统。波纹在水中是如何形成和动物如何走过是两个物理模拟的例子。物理系统的模拟通常引导向一个微分方程的解法。计算机符号解法是准确的答案且通常作为非常简单的方程组所建立。 在物理模拟中，在物理模拟中，世界被分解为一些小片，这些小片是由大向量来世界被分解为一些小片，这些小

24、片是由大向量来表示。然后世界各部分的关系通过矩阵获得。解表示。然后世界各部分的关系通过矩阵获得。解决形成的矩阵方程通常不会准确地进行计算而是决形成的矩阵方程通常不会准确地进行计算而是通过一系列近似计算得到。这就是微分方程的数通过一系列近似计算得到。这就是微分方程的数值解法。值解法。lOptimization 计算机图形学中经常寻求一个或一堆对象的描述，以达到某些目标。例子包括给你某些特定的“感觉”房间会怎样被光线照亮，让你寻找光的位置；解决一个动画人物在执行某个特别的动作时是怎么移动它的四肢的；以及放置形状和文字在一个页面里结果看起来不显得杂乱。每个例子都可以从一个优化问题出发。十年前图形学著

25、作中很少涉及到优化技巧的使用，但现在领域愈发频繁地在现在的实践中使用优化。lProbability and Statistics 图形学中有些领域利用概率论或者统计学。当研究者使用人类对象进行研究的时候，当然会需要用统计方法进行数据的分析。相关领域包括虚拟现实和人机交互。而且许多描述真实世界的计算机技术涉及某种动作发生的多种概率（various probilities）。一棵树的树枝在生长中会如何生成的概率或者一个虚构的动物如何决定在某个特定方向行走的概率是这其中的两个例子。最后，一些解决困难方程的技巧利用随机数字估计解。重要的例子是一类技巧叫做蒙特卡洛方法通常用于确定光线如何传播。 lCom

26、putational Geometry 计算几何是研究操作几何图形的有效方法的学科。典型的问题包括测试两个物体是否会碰撞，确定怎么将一个多边形分解成三角形，寻找一些点中的最近邻点。这个领域综合了算法，数据结构和数学。研究建模学者们非常依赖于这个领域。 推荐书籍：推荐书籍： Computational Geometry in C Joseph ORourke Cambridge University Press Computational Geometry: An Introduction Franco Preparata and Michael Shamos Springer-Verlag 光

27、栅图形显示器可以看成是由许多可发光的离散点（即像素）组成的矩阵，它需要专门的算法来生成直线、圆弧和曲线等等图形。 22 当在光栅图形设备上显示一条直线时，我们当在光栅图形设备上显示一条直线时，我们只能在显示器所给定的有限个像素组成的矩阵中，只能在显示器所给定的有限个像素组成的矩阵中，按扫描线顺序，依次确定最佳逼近于该直线的一按扫描线顺序，依次确定最佳逼近于该直线的一组像素，并且对这些像素进行写操作。这个过程组像素，并且对这些像素进行写操作。这个过程称为直线的扫描转换。称为直线的扫描转换。 在点阵设备中，直线是用一系列靠近直线的像素点来逼近的。下图是像素点逼近直线的几个例子(用小圆点代表逼近的像

28、素点)。从图中可见，只有当直线是水平的(如AB)、垂直的(如AC)或与水平线成45(如AD)时，由像素点拼成的图形才是真正的直线，其他位置的直线(如AE)都呈阶梯形，这种现象称为阶梯效应。研究直线的生成就要减少这种阶梯效应。DCABAE 画直线的基本要求：直线必须有精确的起点和终点，外观要直(即逼近程度好) ，线宽应当均匀一致、且与直线的长度和方向无关，最后，算法速度要快(与直线生成算法和计算机速度均有关) 。 DDA法即数字微分分析法(Digital Differential Analyzer)。我们知道，直线笛卡儿斜率截距方程为： 其中，k为直线的斜率，b为y轴的截距。给定线段的两个端点

29、和 。则:bxky),(11yx),(22yx)/()(1212xxyyk11xkyb【例】用DDA法在起点A(2，1)和终点B(12，7)之间生成一段直线。 求解的第一步是计算初值x, y, K和b。 第二步按递推公式循环计算点的坐标，并取整显示。bxky11bxky22bxkynnAB753124681012算法中加 0.5 是为减少误差而采用的“四舍五入法”思考上图中：y=y+k的来历。 DDA算法采用在一个坐标轴上以单位间隔对线段取样，从而确定另一个坐标轴上最靠近线路径的对应整数值。 (1)正斜率（ ）l（ ）以单位x间隔（ ）取样，逐个计算l（ ）以单位y间隔（ ）取样，逐个计算 (

30、2)负斜率（ ）上述的方程也可以用来计算负斜率的线段的像素位置。 1k0k1xkyyii11k1ykxxii110k 斜率在0到1之间，直线在x方向增加一个单位，则y方向上的增量只能在0到1之间。 若P（XP,YP)点已经确定，那么下一个与直线最近的像素点只能在正右方的P1(Xp+1,Yp)或右上方的P2（Xp+1,Yp+1）之间选择。令M为P1和P2的中点，易知M的坐标为（Xp+1,Yp+0.5）。关于直线和点之间的位置关系有下列几种情况: F(MX,MY)=0, M点在直线上，取P点； F(MX,MY)0，M点在直线上方，取P1点； F(MX,MY)0，M点在直线下方，取P点。0),(cb

31、yaxyxF“增量的计算方法”: 令a=y0-y1，b=x1-x0，c=x0y1-x1y0。 构造判别式： d=a(xp+1)+b(yp+0.5)+c d的初始值d0 = a+0.5b 在d0的情况下，取正右方像素P1， d1=a(xp+2)+b(yp+0.5)+c =d+a 在d0的情况下，取右上方像素P2， d2=a(xp+2)+b(yp+1.5)+c = d+a+b【例】用中点画线法在起点A(2，1)和终点B(12，7)之间生成一段直线。 求解的第一步是计算初值。 第二步按递推公式循环计算点的坐标，并取整显示。 过各行各列像素中心构造一组虚拟网格线，按直线从起点到终点的顺序计算直线与各垂

32、直网格线的交点，然后确定该列像素中与此交点最近的像素。 由图不难看出：若st，则Si比较靠近理想直线，应选Si;若st，则Ti比较靠近理想直线，应选Ti。3 算法原理如下：过各个像素的中心构造一组虚拟网格线，首先按直线从起点到终点的顺序计算直线与各垂直网格线的交点，然后，采用增量计算，使得对于每一列，只要检查一个误差项的符号，就可以确定该列像素中与此交点最近的像素。 首先考虑: 斜率k=dy/dx1的直线设直线 L方程为: ，其中，k = dy/dx。 假设当前像素的x坐标已经确定为xi，其y坐标为yi，由于坐标（xi，yi）（i=0,1,）只能取整数，那么下一个像素的x坐标 ，而yi1的坐标

33、有两种可能： (1) 保持不变，即yi1 yi；或者 (2) y坐标递增1，即yi1 yi1。 (1) 初始误差：d0=0(2) x每增加1，y的值相应 递增直线的斜率值k，即di+1=di+k(3) 一旦di+11，就将它减去1，这样始终保证di+1在01之间。令 y坐标是否增加1取决于误差项d i的值 1) 当d i+10.5时，直线 与xxi1的垂线的交点最接近于当前像素（xi，yi）的右上方像素（xi1，yi1）； 2) 当d i+10.5时，其交点更接近于（xi，yi）右边的像素（xi1，yi）。 【例】用BresenhamBresenham画线画线法在起点A(0，0)和终点B(5，

34、2)之间生成一段直线。(1) 初始误差：d0=? ,k=?(2) x每增加1，y的值相应 递增直线的斜率值k，即di+1=di+k d1=? (=) 0.5 取(0+1,0)=(1,0)或（1，1）？ d2=? (=) 0.5 取？ d3=？ 。 (1) 初始误差：d0=0,k=2/5=0.4(2) x每增加1，y的值相应 递增直线的斜率值k，即di+1=di+k d1=0+0.4=0.40.5 取(2,1) d3=0.8+0.4=1.2 因di+11,所以d3-1 =0.20.5 取(4,2) d5=0.6+0.4=1.0 因di+11,所以d5-1 =0.00,H在圆外,那么有、情形；H0

35、,H在圆内,那么有情形；D0,D在圆外,那么有 、情形；D0,V在圆外,那么有情形；V0,V在圆内,那么有、情形；如D0，这时的最佳逼近只可能是H或D中的一个 若 HD0, 下一像素取D； HD=0,约定下一像素取正右方H。 |DHHD练习 分析D0时的下一个像素的选取。椭圆的非参数化方程一般形式为： 上式可用隐式方程表示为： 利用极坐标和，可以按照参数化方程的形式来描述椭圆为： 1)()(220220byyaxx0),(222222bayaxbyxFsincos00byyaxx椭圆弧上斜率为1的点将椭圆弧分为上、下部分。 椭圆弧对成性 在区域2，设当前位置为P点，下一个可能的点是像素点H和D

36、，这时可构造判别式： di0，取D为下一个像素点。)5 . 0, 1(iiiyxFd练习在区域1，设当前位置为P点，下一个可能的点是像素点?这时如何构造判别式以及如何判定点的选取？二次曲线的一般方程为： 令 我们可以对二次曲线进行分类： 椭圆或圆弧； 抛物线； 双曲线 样条曲线：利用多项式曲线段形成的连续曲线。 顶点表示：也称为几何表示，是用区域的顶点序列来表示区域。 点阵表示：也称为像素表示，是用位于多边形内的像素集合来刻画多边形。 内点表示：区域内的所有像素着同一颜色，而区域外的所有像素具有另一种颜色； 边界表示：区域边界上的所有像素点具有特定的颜色（可以是填充色），在区域内的所有像素均不

37、能具有这一特定色，而且边界外的像素不能具有与边界相同的颜色。4 由一系列首尾相连的直线段构成的图形称为多边形。如果在多边形内任意选取不相同的两点，其连线上的所有点均在该多边形内，这样的多边形称为凸多边形；否则，称为凹多边形。 扫描线的确定有四个步骤： l求交 ：扫描线与多边形各边的交点； l排序 ：交点按递增顺序进行排序； l交点配对 ：第一个与第二个，第三个与第四个等等 ；l区间填色 ：相交区间内的象素置成多边形颜色，区间外的象素置成背景色 。 常用的填充方法是按扫描线顺序，计算扫描线与多边形的相交区间，再用要求的颜色显示这些区间的相素，完成填充。 扫描线XYe3e4e5e6e1e23561

38、2abcd24681012O24681012143.3.14需要解决的两个特殊问题： l扫描线与多边形顶点相交时的交点取舍 扫 描 线XYe3e4e5e6e1e235612abcd24681012O24681012143.3.14l多边形边界上象素的取舍 对左下角为（1，1），右上角为（3，3）的正方形填充。 “左闭右开”、“下闭上开”活性边表的结构内容： lx: 当前扫描线与边的交点； l x：从当前扫描线到下一条扫描线之间的x增量； lYmax：边所交的最高扫描线号。 练习 写出扫描线2的活性边表。l基本思想：对于每一条扫描线和每条多边形边的交点，将该扫描线上交点右方的所有象素取补。对多边

39、形的每条边作此处理，多边形的顺序随意。 5缺点：对多边形的每条边作上述处理时，会对某些区域进行反复填充。 l 栅栏指的是一条与扫描线垂直的直线，栅栏位置通常取过多边形顶点、且把多边形分为左右两半。 栅栏填充算法的基本思想是：对于每个扫描线与多边形边的交点，就将交点与栅栏之间的象素取补。若交点位于栅栏的左边，就将交点之右，栅栏之左的所有象素取补；若交点位于栅栏的右边，就将交点之左，栅栏之右的所有象素取补。 l边标志算法分为两步： （1）对多边形的每条边进行直线扫描转换，亦即对多边形边界所经过的象素打上边标志； （2）填充。对每条与多边形相交的扫描线，依次从左到右顺序，逐个访问该扫描线上象素。设置

40、一个布尔量来表明当前点是在多边形内还是在多边形外，通过遇到边标志变换状态（取反）来填充。 种子填充算法又称为边界填充算法。其基本思想是：从多边形区域的一个内点开始，由内向外用给定的颜色画点直到边界为止。 种子填充算法常用四连通域和八连通域技术进行填充操作。 （1）四连通域，从区域内任意一点出发，通过上、下、左、右四个方向到达区域内的任意像素。这种填充方法称为四向连通算法。 （2）八连通域，从区域内任意一点出发，通过上、下、左、右、左上、左下、右上和右下八个方向到达区域内的任意像素。这种填充方法称为八向连通算法。5l一般来说，八向连通算法可以填充四向连通区域，而四向连通算法有时不能填充八向连通区

41、域。 l四向连通填充算法： a） 种子像素压入栈中； b） 如果栈为空，则转e)；否则转c)； c） 弹出一个像素，并将该像素置成填充色；并判断该像素相邻的左、上、右、下四连通像素是否为边界色或已经置成多边形的填充色，若不是，则将该像素压入栈； d） 转b）； e） 结束。 2974 83974 93974 4974 2 8 9 3 4 7 6 5重复入堆栈 上述算法需要大量栈空间来存储相邻的点。一个改进的方法：通过沿扫描线填充水平像素段，来处理四连通或八连通相邻点，这样就仅仅只需要将每个水平像素段的起始位置压入栈，而不需要将当前位置周围尚未处理的相邻像素都压入栈，从而可以节省大量的栈空间。这

42、种算法称为扫描线填充法，其原理为，种子象素入栈；当栈非空时作如下。l四步操作： 1） 栈顶象素出栈； 2） 沿扫描线对出栈象素的左右象素进行填充，直到遇见边界象素为止，既每出栈一个象素，就对包含该象素的整个区间进行填充； 3） 上述区间内最左和最右的象素分别记为Xl和Xr； 4）在区间Xl ,Xr中检查与当前扫描线相临的上下两条扫描线的有关象素是否全为边界象素或已填充的象素，若存在非边界、未填充的象素，则把每一个区间的最右象素取做种子象素入栈。l进行图案填充时，在不考虑图案旋转的情况下，必须确定区域与图案之间的位置关系。这可以通过把图案原点与图形区某点对齐的办法来实现。对齐的方法有：把图案原点

43、与填充区域边界或内部的某点对齐。 l对于圆和椭圆这样的具有光滑边界的区域，则最好取区域内部某一点，如中心，对应图案原点。 l在具体填充图案时，用简单的透明或不透明方式不能得到理想的结果，需要进行多次的AND运算得到理想的结果。l字符指计算机在文本方式下能够在屏幕上显示的数字、字母、音标、标点符号、数学符号、汉字等符号。l计算机中的字符由一个数字编码唯一标识。l最流行的字符集是“美国信息交换用标准代码集”简称ASCII码。它用7位二进制编码 。规定了129个字符.l我国除采用ASCII码外，还另外制定了汉字编码的国家标准字符集，如：“信息交换用汉字编码字符集基本集”GB231280。该字符集分为

44、94个区，94个位，每个符号由一个区码和一个位码共同标识。为了能够区分ASCII码与汉字编码，采用字节的最高位来标识：最高位为0表示ASCII码；最高位为1表示汉字编码。lUnicode字符集编码（Universal Multiple-Octet Coded Character Set） 通用多八位编码字符集的简称 ,为每种语言中的每个字符设定了统一并且唯一的二进制编码。使用16 bits(两个字节)来表示一个字符 。 l字库分为点阵字库和矢量字库两种，用于存储每个字符的形状信息。点阵字库中，每个字符用二值点阵信息表示每个字符，矢量字库则用直线和曲线（如三次B样条曲线/Bezier曲线）来描述

45、每个字符的轮廓形状。 l在点阵字库中，每个字符由一个位图表示（如下图所示），并把它用一个称为字符掩膜的矩阵来表示，其中的每个元素都是一位二进制数，如果该位为1表示字符的笔画经过此位，该像素置为字符颜色；如果该位为0，表示字符的笔画不经过此位，该像素置为背景颜色。 l点阵字符的显示分为两步:首先从字符中将位图检索出来,然后将检索到的位图写到帧缓冲器中。l为避免存储空间占用过大,常要采用压缩技术。l矢量字符记录字符的笔画信息而不是整个位图，具有存储空间小，美观、变换方便等优点。例如：在AutoCAD中使用图形实体-形（Shape）-来定义矢量字符，其中，采用了直线和圆弧作为基本的笔画来对矢量字符进

46、行描述。 l对于字符的旋转、放大、缩小等几何变换，点阵字符需要对其位图中的每个象素进行变换，而矢量字符则只需要对其几何图素进行变换就可以了，例如：对直线笔画的两个端点进行变换，对圆弧的起点、终点、半径和圆心进行变换等等。l轮廓字形法是当今国际上最流行的一种字符表示方法，其压缩比大，且能保证字符质量。轮廓线构成一个或若干个封闭的平面区域。轮廓线定义加上一些指示横宽、竖宽、基点、基线等等控制信息就构成了字符的压缩数据。 作业：初始种子点选在的各点填充顺序6l线段的基本属性有线型、宽度和颜色。 l线型属性包括：实线、虚线和点线等。 生成虚线和点线的方法是在实线中插入空白段实现的。 l在监视器上的粗线

47、可以用相邻的平行线进行显示；而在绘图仪上则可能需要更换画笔。 l加粗线的方式：l一是移动一把具有一定宽度的“刷子”来获得；二是采用区域填充的办法间接产生。 cl生成具有宽度的线条还可以采用区域填充的算法，先算出线条的曲线的内、外边界，然后调用多边形填充算法把所有的四边形进行填色，即得到具有宽度的线条。 l可以如下图所示选择画笔或画刷。 l当系统提供颜色（或亮度）选择时，给出当前颜色索引的参数则包含在系统属性表中。 l颜色采用0到某一正整数之间的整数值进行编码。RGB组合编码 lRGB（R，G，B）组合编码的表。 l使用0到1范围内的数值来指定灰度级别，然后将其转换成为适当的二进制码存储在光栅中

48、。 l区域显示有三种基本填充模式：具有颜色边界的空心区域、使用纯色填充的实心区域、使用指定图案或设计填充的区域。 l空心区域通过仅显示边界轮廓并保持其内部颜色与背景色相同而实现。l实心区域以单一颜色对区域内部进行填充，也可以包含其边界。 l图案和背景色可以使用布尔操作进行组合，或者简单地使用图案颜色替代背景色。 l显示的字符外观由字体、大小、颜色和方向这些属性控制。 l字体： Times New Roman、宋体、仿宋等。l附加风格：下划线风格（实线（ ）、点线（ ）、双线（ ）、黑体、斜体、轮廓或影线风格。 l标记符号是一种单一字符，它以不同的颜色和不同的大小进行显示。标记类型的类型码是1到

49、5的整数，分别指定点（.）、垂直交叉（+）、星号（*）和对角交叉（）。 l Bresenham直线算法生成的直线图形一般都呈阶梯状（见下图），实际上，这是光栅图形的一种走样现象。这种走样现象是由于采用离散量表示连续量引起的。通常，我们把由离散量表示连续量引起的失真称为走样；把减少或克服走样效果的技术称为反走样技术，简称反走样。 l光栅图形的走样有如下几种：la) 产生阶梯或锯齿形；b) 细节或纹理绘制失真；c) 狭小图形遗失；d) 实时动画忽隐忽现、闪烁跳跃。 lb) 细节或纹理绘制失真 l 造成走样的原因是由于采样频率太低造成的欠采样。根据采样定理，为了避免走样，采样频率至少应是信号最高频率

50、的2倍。lc) 狭小图形遗失l 对于小于像素尺寸的图形对象，一方面，如果它未能覆盖像素中用于计算其属性的像素中点，则这个对象将不会显示出来；另一方面，如果它覆盖了像素中用于计算其属性的那一点，它将不恰当地代表整个像素的属性。 ld) 实时动画忽隐忽现、闪烁跳跃l 下图是一个小卡通动画序列中的三幅画。如果像素的属性由其中心决定，则在第一帧中，这个小卡通人是不可见的，在第二帧小卡通人可见，但第三帧又不可见。这样，小卡通人给人的感觉不是在缓慢地连续前进，而是一明一暗地在闪烁。 运动图形闪烁l光栅图形的反走样方法主要有两类： l第一类是超采样或称后置滤波。这类算法的基本思想着眼于提高分辨率即增加采样点

51、。 l第二类方法称为前置滤波。即：把像素作为一个有限区域而不是一个面积为零的点来处理，从而对区域采样。 6l其基本思想在于提高分辨率即增加采样点，虽然采用高分辨率的光栅图形显示器也是一个选择，但它受到客观条件的限制，而且也不经济。 分辨率提高一倍，阶梯状程度减小一倍 l 采用软件实现的方法，即：将低分辨率的图形像素划分为许多子像素，在较高分辨率上对各子像素的颜色值或灰度值进行计算，然后采用某种平均算法，将原像素内的各子像素的颜色值或灰度值的平均值作为该像素显示的颜色值或灰度值，在较低分辨率的光栅图形设备上进行显示。l当在一个多灰度级的显示器上显示一条黑线，若一个象素落在线条上，则将它置成黑色；

52、若一个象素与线条部分相交，根据相交部分的大小来选择不同的灰度。相交部分大的象素更黑一些，相交部分小的象素更白一些，这种方法将产生模糊的边界，以此来减轻锯齿效应。 重叠区域面积的计算。精确起点，则可以得到图中的D的值，利用D和直线斜率k可以得到重叠区域的面积为： 图形变换一般是指将物体的几何信息经过放大、缩小、平移和旋转等几何变换后产生新的图形。 它总是与相关的坐标系紧密相连的。从相对运动的观点来看，图形变换既可以看作是图形相对于坐标系的变动，即：坐标系固定不动，物体的图形在坐标系中的坐标值发生变化；也可以看作是图形不动，但是坐标系相对于图形发生了变动，从而使得物体在新的坐标系下具有新的坐标值。

53、 通常图形变换只改变物体的几何形状和大小，但是不改变其拓扑结构。 7l两矢量和的和、点积、长度、叉积。 两个矢量分别为： （x1,y1,z1)和（x2,y2,z2）lm行n列矩阵A，mn矩阵： l矩阵的加法、乘、逆、转置 mnmmnnaaaaaaaaaA.212222111211l平移变换是将图形对象沿直线路径从一个坐标位置(x, y)移到另一个坐标位置(x，y)的重定位。 l它只改变物体的位置，不改变物体的大小和形状。 l平移变换的公式为：l矩阵表示法： yxttyxyxl练习有个三角形的三个顶点的坐标分别为（，），（，），（，），现沿x轴方向平移3个单位，沿y轴方向平移4个单位后的各坐标点

54、的新坐标l缩放（比例）变换改变对象的尺寸。缩放（比例）变换是使图形按在x和y坐标轴方向分别按比例因子Sx和Sy放大或缩小的变换。 l计算公式为： xxSx yySy 矩阵的形式 (1)当Sx= Sy=1时，为恒等比例变换，即图形不变；(2)当Sx= Sy1时，图形沿两个坐标轴方向等比例放大；(3)当Sx= Sy0）到达P点。旋转角的正值定义为绕基点逆时针旋转，负值则以顺时针方向旋转对象。旋转基准点l其计算公式为： x xcosysin yxsinycos l矩阵运算的表达为：l练习有个三角形的三个顶点的坐标分别为（，），（，），（，），现绕坐标原点逆时针旋转度，计算旋转后的各坐标点的新坐标l对

55、称（反射）是产生对象的镜像的一种变换。 l其计算公式为：l表示成矩阵变换的形式为： eydxybyaxxyxedbayxl(1) 当b=d=0，a=-1,e=1时，有x=-x, y=y，产生与y轴对称的反射图形，如图f；l（2）当b=d=0，a=1,e=-1时，有x=x, y=-y ，产生与x轴对称的反射图形，如图g；l（3）当b=d=0，a=-1,e=-1时，有x=-x, y=-y ，产生与原点对称的反射图形，如图h；l（4）当b=d=1，a=0,e=0时，有x=y, y=x ，产生与直线y=x对称的反射图形，如图I；l(5) 当b=d=-1，a=0,e=0时，有x=-y, y=-x ，产生

56、与直线y=-x对称的反射图形，如图j。eydxybyaxxl练习有个三角形的三个顶点的坐标分别为（，），（，），（，），现分别关于x轴，坐标原点，y=x直线做对称变换，计算变换后的各坐标点的新坐标l错切是一种使对象形状发生变化的变换。常用的错切变换有两种：改变x坐标值和改变y坐标值。 87l变换方程为：l表示成矩阵变换的形式为： ydxybyxxyxdbyx11(1) 当d=0时，x=x+by, y=y,此时，图形的y坐标不变，x坐标随初值（x,y）及变换系数b而作线性变化；l 如b0，图形沿+x方向作错切位移；l 如b0，图形沿+y方向作错切位移； 如d0 时，表示 ax+by=0 的直线，

57、即在 y=-(a/b)/x 上的连续点x,y逐渐趋近于无穷远，但其斜率不变。 l平移变换矩阵 : yxttyxyxl于是得到平移变化：110010011YXTTYXYX10010011001001100100121211122YYXXYXYXTTTTTTTTl连续两次平移后的平移变换矩阵l练习有个三角形的三个顶点的坐标分别为（，），（，），（，），现进行连续的两次平移，第一次沿X轴方向移动2个单位，再沿Y轴方向移动3个单位，计算变换后的各坐标点的新坐标思考: 复合平移与平移的关系l变换矩阵为：l于是得到有： 1000000YXSSST110000001YXSSYXYXyxSSST00l两个连续

58、缩放操作的复合缩放的变换矩阵： 10000001000000100000021211122YYXXYXYXSSSSSSSSl练习有个三角形的三个顶点的坐标分别为（，），（，），（，），现沿x轴方向放大3倍，沿y轴方向放大1倍，然后再沿x轴方向放大1/2倍，沿y轴方向放大2倍后的各坐标点的新坐标l旋转变换矩阵Tr： l于是得到有： 1000cossin0sincosrT11000cossin0sincos1YXYXl两个连续旋转操作的复合旋转的变换矩阵： 1000cossin0sincos*1000cossin0sincos11112222l练习证明连续的两次旋转可以交换次序。l绕图中的固定点旋

59、转l通过完成平移-旋转-平移操作序列，来实现绕任意选择的基准点（x,y）的旋转： l（1）平移对象使基准点位置移动到坐标原点；l（2）绕坐标原点旋转；l（3）平移对象使基准点回到原始位置。l绕固定点缩放l前述的算法只能相对于坐标原点缩放的缩放功能，产生关于所选择的固定位置（x,y）缩放的变换顺序为：l平移对象使固定点与坐标原点重合；l对于坐标原点的缩放； l使用步骤1的反向平移将对象返回到原始位置。 l将上述三步的矩阵连接，得到下面的所需矩阵： 对称变换的奇次矩阵：l关于y轴对称 关于x轴对称l关于原点对称 关于y=x轴对称l关于y=-x轴对称1000100011000010101000100

60、011000100011000010109l从变化功能上，矩阵可把T2D分为四个子矩阵，其中：l 是对图形进行缩放、旋转、对称、错切等变换；l 是对图形进行平移变换； l 对图形作投影变换，c的作用是在x轴上的1/c处产生一个灭点，f的作用是在y轴的1/f处产生一个灭点；l 是对整体图形作伸缩变换。 ifchebgdaTD2ebdafchgi8l将三维空间中的物体变为二维图形表示的过程称为投影变换。l投影变换的分类：l投影的要素包括投影对象、投影中心、投影平面、投影线和投影。l要作投影变换的物体称为投影对象；在三维空间中，选择一个点，记这个点为投影中心；不经过这个点再定义一个平面，记这个平面为