洛阳师范学院信息技术
计算机科学与技术专业
课程教案
课 程 名 称 计算机图形学 授 课 人
一、 课程名称 ： 计算机图形学
二、 学 时 数：周学时4，共15周（60），3.5 学分 三、 课程开设：选修课 四、 课程类型：专业课
五、 使用教材：罗笑南主编，《计算机图形学》第三版，中山大学出版社 六、 教学参考文献：
1. 唐泽圣，周嘉玉，李新友.计算机图形学基础[M].北京:清华大学出版社,1995
2. 彭群生，鲍虎军，金小刚.计算机真实感图形的算法基础[M].北京:
科学出版社,1999
3. 孙家广等.计算机图形学(第三版)[M].北京:清华大学出版社,1998 4. 王汝传，邹北骥.计算机图形学[M].北京:人民邮电出版社,2002 七、 教学方法与手段：讲授与范例相结合，运用多媒体教学。 八、 教学要求：通过教学和实验，使学生
1.了解图形系统的框架及其涉及的软件、硬件技术；
2.了解图形学的基本问题，掌握图形学的基本概念、方法与算法； 3.对与图形相关的应用及当前的研究热点有一个初步认识； 4.具有一定实践体会和相关的编程能力。 九、 考核方式：平时成绩与实验程序。
第1章 绪论
教学学时：4课时
教学目的与要求：使学生了解计算机图形学的基本研究内容，基础概念，了
解计算机图形学的发展，应用层次，了解图形学与我们日常生活的关系，了解常用的图形输入输出设备，了解目前国际上的一些图形标准。
教学重点：计算机图形学的概念、发展和应用，图形输出设备光栅显示器。 教学内容：
1.1 计算机图形学概念、发展和应用 1.1.1 什么是计算机图形学 1.1.2 计算机图形学的发展 1.1.3 计算机图形学的应用 1.1.4 计算机图形学研究动态 1.1.5 计算机图形学的基本术语
1.1.6 交互式计算机图形系统的组成与功能 1.2常用的图形输入/输出设备 1.2.1 图形输入设备 1.2.2 图形输出设备 1.3 计算机图形标准
1.1 计算机图形学概念、发展和应用 1.1.1什么是计算机图形学
问题：计算机发展的下一个热潮是什么？
纵观计算机发展的历程，按时间先后的顺序，先后出现的热潮是操作系统、数据库、网络。那么下一个热潮是什么？从计算机是人的工作工具出发，我们不难得到结论：下一个热潮是包括图形图像在内的加强信息利用和沟通的方向。
计算机是人的工具，研究计算机的各个方面就是要使这种工具好用。下一个热潮是什么呢？因为计算机中的数据的最终目的是要为人处理各种事情服务的，所以这些数据所蕴涵的信息如何能高效地让人自适应地、高效地获得就成了计算机发展历程中新的、下一个瓶颈。那么下一个热潮就在这里。其中，由于视觉是人类最快捷的信息获知途径，图形图像将是下一个热潮中的主要内容。目前，网络的发展很快，人们对使用网络的各种要求也大多能基本满足，所以，下一个热潮的到来将很快。目前，
在欧美等发达国家，关于图形图像的研究和应用正处于一种爆炸式的发展阶段。
图形这个概念很早就有，距今几十万年的原始人就用各种图形表达意思，人类的语言很早的象形字，甲骨文等，都是最早的使用图形的例子。可以说，现实世界中图形无处不在，婴儿感知世界，也从各种各样图形开始。
二十世纪最伟大的成就之一，计算机技术的诞生和飞速发展为计算机图形学提供了发展的契机。
计算机图形学（Computer Graphics）是近三十年来发展迅速，应用广泛的新兴学科，它主要研究怎样用数字计算机生成、处理和显示图形。
图形的具体应用范围很广，但是从基本的处理技术看只有两类，一类是线条，如工程图、地图、曲线图表等；另一类是明暗图，与照片相似。为了生成图形，首先要有原始数据或数学模型，如工程人员构思的草图，地形航测的判读数据，飞机的总体方案模型，企业经营的月统计资料等等。这些数字化的输入经过计算机处理后变成图形输出。 计算机图形学是研究怎样用计算机生成、处理和显示图形的一门学科。
国际标准化组织(ISO)的定义：
计算机图形学是研究通过计算机将数据转换为图形，并在专门显示设备上显示的原理、方法和技术的学科。它是建立在传统的图学理论、应用数学和计算机科学基础上的一门边缘学科。
图形学和其它学科的关系
在许多论述中，经常将图形和图像统称为“图形图像”，这使得图形和图像的含义在使用上大大地模糊了，虽然它们都使用数字化的物体形态来表示，但它们的存储结构和表示方法是有根本区别的。
图形是矢量结构的画面存储形式。矢量结构显式地表现画面内容的位置（坐标值），用一系列的线段或其它造型来描述对象；而画面内容的颜色或亮度是较隐含地统一描述的，它记录的内容主要是坐标值或坐标值序列。
图像是栅格结构的画面存储形式。栅格结构将图像划分为均匀分布的栅格(像素)，显式地记录每一像素的光度值（亮度/彩色）；而像素的坐标值是规则地隐含的，其位置规则排列（如最常见的矩形排列）。 图像处理：（image process)——对图像采用增强、变换、去噪等技术进行
处理
增强(对比度)：对暴光过度或不足，以及模糊的图象进行处理。
变换：一幅亮度范围宽的图象—>两种亮度的图象—>线条状图形 去噪：通过算法去除图像中的噪音干扰。
目前市场上最著名的图像处理软件就是大名鼎鼎的 photoshop
模式识别： (pattern recognition)——这里特别指对图像进行模式识别，就
是对图像提取特征、予以分类和描述关系，再进行模式匹配。
计算机图形学的特点：
b) 计算机产生的图形纯净美观、无噪声干扰
c) 计算机产生的图形不仅能描绘客观世界的各种对象，也能描绘纯粹是想像的主观世界中的各种对象
d) 交互式计算机图形显示可由用户控制，产生的图形可修改性强，且速度快、差错少
1.1.2计算机图形学的发展
准备阶段（50年代） 发展阶段（60年代） 推广应用阶段（ 70年代） 系统实用化阶段（80年代） 标准化智能化阶段（90年代）
a) 计算机产生的图形有规律、光滑
1.1.3计算机图形学的应用
1.计算机辅助设计与制造——工业领域 2.系统环境模拟
3.计算机动画——商业领域 4.计算机艺术——艺术领域
5.非真实感绘制(NPR Non-Photorealistic Rendering) 6.过程控制
7.事务和商务数据的图形显示 8.地形地貌和自然资源的图形显示 9.科学计算的可视化 10.多媒体应用
1.1.4计算机图形学研究动态
基于图形设备的基本图形元素的生成算法 图形的变换和裁剪
自由曲线和曲面——计算几何 几何造型技术 真实感图形的生成算法 自然景物的生成——分形几何 颜色科学及其应用 计算机动画技术
虚拟现实技术——实时交互式三维图形处理
1.1.5计算机图形学的基本术语 一、光点（Point） 二、像素（Pixel）
三、图形分辨率（Resolution） 四、文本方式（Text Mode） 五、图形方式
六、颜色调色板(Palette) 七、视频缓冲区(Video Buffer)
1.1.6交互式计算机图形系统的组成与功能
1.2常用的图形输入与输出设备
高质量的计算机图形离不开高性能的计算机图形硬件设备。一个图形系统通常由图形处理器，图形输出设备和输入设备构成。这一节我们将逐个探讨这些图形硬件设备。 1.2.1图形输入设备 图形输入设备的发展
? 第一阶段：
控制开关、穿孔纸等
? 第二阶段：
键盘、光笔
? 第三阶段：
二维定位设备，如鼠标、坐标数字化仪、跟踪球、触摸屏、操纵杆、扫描仪等
? 第四阶段：
三维输入设备（如三维鼠标、空间球、数据手套、数据衣）
智能人机接口：用户的手势、表情、语音等
1.2.2图形输出设备(教学重点)
下面重点介绍图形显示设备的各种显示器
1.阴极射线管（CRT）,按颜色分类有单色和彩色二种。按刷新方式分类，分直视存储管式和刷新式二种。重点是彩色光栅扫描显示器。 2. LCD显示器 3. LCOS显示器 4.等离子体显示器 5.未来显示器
1.3 计算机图形标准
原则：与计算机硬件无关，实现程序的可移植性； 通用的与设备无关的标准包括：
核心图形系统CGS(Core Graphics System)，1977年美国计算机协会公布 计算机图形接口CGI(Computer Graphics Interface),ISO公布； 计算机图形元标准CGM(Computer Graphics Metafile); 计算机图形核心系统GKS(Graphics Kernel System);
程序员层次交互式图形系统PHIGS(Programmer’s Herarchical Interactive Graphics System);
初始图形交换规范IGES(Initial Graphics Exchange Specification),1983年，美国国家标准局；等等。
一些非官方图形软件，广泛应用于工业界，成为事实上的标准。包括： DirectX (MS) Xlib (X-Window系统) OpenGL (SGI) Adobe公司Postscript
开放式、高效率的发展趋势
思考题：
1、名词解释：图形、图象、点阵法、参数法？
2、图形包括哪两方面的要素，在计算机中如何表示它们？
3、什么叫计算机图形学？分析计算机图形学、数字图象处理和计算机视觉学科间的关系？ 4、有关计算机图形学的软件标准有哪些？
5、试从科学历史发展的角度分析计算机图形学以及硬设备的发展过程？
6、试发挥你的想象力，举例说明计算机图形学有哪些应用范围，解决的问题是什么？ 7、一个交互性计算机图形系统必须具有哪几种功能？其结构如何？ 8、名词解释：
鼠标、光笔、触摸屏、操纵杆、跟踪球、空间球、数据手套、数字化仪、图象扫描仪、声频输入系统、视频输入系统、平板显示器、发射显示器、非发射显示器、等离子体显示板、薄片光电显示器、激光显示器、LCD、LED、随机扫描、光栅扫描、刷新、刷新频率、图形显示子系统、显示控制器、属性控制器、象素点、光点、屏幕分辨率、显示分辨率、存储分辨率、组合象素法、颜色位面法、位平面、颜色查找表、显示长宽比、屏幕坐标系、MDA、CGA、EGA、VGA、SVGA、TVGA、AVGA、AGP端口、刷新带宽、显示存储器带宽。 9、试列举出你所知道的图形输入与输出设备？
10、阴极射线管由哪几部分组成？它们的功能分别是什么？ 11、液晶显示器的原理是什么？适用于哪些方面？ 12、什么是象素点？什么是显示器的分辨率？
13、确定用你的系统中的视频显示器x和y方向的分辨率，确定其纵横比，并说明你的系统怎样保持图形对象的相对比例？ 14、如何根据显示器的指标计算显示存储器的容量和刷新带宽。 15、为什么说图形显示卡与系统总线的接口仍会成为系统瓶颈？ 15、图形的硬拷贝设备有哪些，简述其各自的特点。
补充上机实验章节：VC6快速入门
教学学时：2课时 教学目的与要求：
让学生初步掌握VC6编译器的集成开发环境和使用，熟悉VC框架结构，熟悉单文档/视结构的框架，熟悉类向导的使用，要求学习完毕后学生能快速的进行VC环境下的编程，能编写简单的对话框程序，能将菜单映射到函数，实现简单的VC框架编程。 定位：
不是VC专业教程，不讲VC具体知识，比如里面的字符，循环，消息映射，虚函数，多态，继承，重载等等概念。
是对具体编程步骤的一个简单指导，快速实质性学习VC的一个速成指南，一个快速上机操作的例子。具体用到哪些知识必要时候做些解释。
主要针对图形学编程，但是开发方法完全可以推广到其它方面编程，是对以前学习高级程序语言设计的提高与应用。 主要内容：
第一部分：创建简单的对话框应用程序 第二部分：创建简单的单文档视图文档结构 第三部分：在第二步的基础上创建一个对话框
教学重点：类向导的使用，从菜单到函数的映射，对话框类的使用和添加，
VC编程规范。
思考题：
1、什么是面向对象的编程语言？特点有哪些？
2、总结一下类向导的功能，思考一下如果使用类向导这个工具的逆过程，是不是可以一下子看清楚复杂程序的结构。 3、什么是继承，注意父类public同protect和private类型变量或成员函数被继承到子类的不同。
第二章 直线扫描转换算法
教学学时：8课时 教学目的与要求：
让学生初步掌握生成直线的几种算法，逐点绘制直线方法，dda绘制直线方法，Bresenham绘制直线方法，掌握算法的理论原理，学会从理论上的算法转换到编译程序中的代码实现这个思维过程，能够分析基本算法的优缺点，掌握算法的改良后适合计算机实现的算法，了解计算机计算和理论计算的差异。最后了解直线的线宽，其他线型的算法实现，了解VC语言中提供的简单绘制二维基本图形的各种函数。
教学重点：逐点绘制直线基本方法和改进，dda绘制直线基本方法和改进，
Bresenham绘制直线基本方法和改进，实现线宽线型的算法。
教学内容：
2.1 光栅图形学 2.2 逐点画线算法 2.3 DDA画线算法 2.4 BRESENHAM画线算法 2.5 关于线宽线型
2.6 Visual C++中基本绘图函数
2.1 光栅图形学
计算机图形学已成为计算机技术中发展最快的领域，计算机图形软件也相应得到快速发展。计算机绘图显示有屏幕显示、打印机打印图样和绘图机输出图样等方式，其中用屏幕显示图样是计算机绘图的重要内容。
计算机上常见的显示器为光栅图形显示器，光栅图形显示器可以看作像素的矩阵。像素是组成图形的基本元素，一般称为“点”。通过点亮一些像素，灭掉另一些像素，即在屏幕上产生图形。在光栅显示器上显示任何一种图形必须在显示器的相 应像素点上画上所需颜色，即具有一种或多种颜色的像素集合构成图形。确定最佳接近图形的像素集合，并用指定属性写像素的过程称为图形的扫描转换或光栅化。对于一维图形，在不考虑线宽时，用一个像素宽的直、曲线来显示图形。二维图形的光栅化必须确定区域对应的像素集，并用指定的属性或图案进行显示，即区域 填充。
图形光栅化和光栅化图形的处理就是光栅图形学的研究内容。 光栅图形学算法特点：
1.要充分考虑屏幕像素，光栅的特性，如何逼近真实图形，如何减小这个误差，如何提高图形处理速度是图形学算法的追求。
2.编写计算机图形学算法，最好还要具备计算方法的基础知识，了解计算机是如何求解方程，了解求解过程与实际人思维的不同，也就是把人思维的计算方法翻译到机器，这就是计算方法研究的内容。 光栅图形学的研究内容： ? ? ? ? ? ? ?
2.2 逐点画线算法
逐点比较法算法的基本思想是：在绘制直线的过程中，每绘制一个点就与原直线进行比较，根据比较的结果决定下一步的走向，这样一步一步逼近直线，逐点比较法的执行过程如下：
2.3 DDA画线算法
数值微分法（Digital Differential Analyzer）是一种基于直线微分方程来生成直线的方法。回顾一下数值微分的几何意义，一阶数值微分反应的是变化率，表达瞬时变化趋势和快慢的量。 简单的DDA绘制直线算法 对称的DDA绘制直线算法
2.4 BRESENHAM画线算法
直线段的扫描转换算法 圆弧的扫描转换算法
多边形的扫描转换与区域填充 字符 裁剪 反走样 消隐
Bresenham算法是计算机图形学领域中使用最广泛的直线扫描转换算法。该算法最初是为数字绘图仪设计的。由于它也适用于光栅图形显示器，所以后来被广泛用于直线的扫描转换与其他一些应用。为了讨论方便，学习的开始也假定直线的斜率在0、l之间。其他情况可类似处理。过各行、 各列像素中心构造一组虚拟网格线, 按直线从起点到终点的顺序计算直线与各垂直网格线的交点, 然后确定该列像素中与该交点最近的像素。
2.5 关于线宽线型
前面我们编程实现的画图算法都是一个像素宽度的连续的直线（逐点画线法画出来的线粗细步均匀），实际使用中我们经常还需要用到各种宽度不同的线，实线，还有虚线来表达不同的含义。常用商业软件都提供了类似的功能，比如word，autocad等等软件。
要产生具有宽度的线，可以顺着扫描所生成的单像素线条轨迹， 移动一把具有一定宽度的“刷子”来获得，“刷子”的形状可以是一条线段或一个正方形。也可以采用区域填充的办法间接地产生有宽度的线(如AutoCAD系统即是)。
垂直线刷子 水平线刷子 方形刷子
在绘图应用中常用到不同线型的线条，以便区分各种不同的意义。如采用实线表示立体线框图中可见的轮廓线，用虚线表示不可见的轮廓线， 用点划线表示中心线等等。
线型可以用一个布尔值的序列来存放。例如，用一个 32 位整数可以存放 32 个布尔值。用这样的整数存放线型定义时，线型必须以 32 个像素为周期进行重复。可按下述语句写像素：
if(位串［i2］)drawpixel(x, y,color)；
其中i为循环变量，在扫描转换算法的内循环中，每处理一个像素就递增 1，然后除以 32 取余。
在我们选用的教材上（P32），使用了一种最灵活的方式画虚线，通过定义实线和虚线的距离来选择绘图像素点。
这种方法有个缺点，那就是直线段的总长度可能不是实线部分加上虚线部分距离的整数倍，可能会造成绘制虚线二头端点为空的情况。还有个缺点，那就是大量的除法计算效果不太好。
2.6 Visual C++中基本绘图函数
实际利用Visual C++中编制图形程序，可以利用图形学算法自己动手编制基本图形程序，作为图形程序的基类，当然还可利用系统中已提供的图形基类。下面简单介绍Visual C++提供的常用绘制图形函数。 1．点
画点是最基本的绘图操作，在绘图中，画点是通过调用CDC::SetPixel()或CDC∷SetPixelV()函数来实现的。 2．画笔 3．画刷
4．绘制直线函数 MoveTo()函数 LineTo()函数 5．椭圆函数
6．函数绘制一段椭圆弧 7．矩形函数 8．连续画线函数 9．多边形绘制函数 10．填充函数 思考题：
1、写出适合任何情况下的逐点比较法算法。 2、写出用Bresenham算法绘制多边形的算法。 3、试分析几种常用画线算法的优缺点。
4、已知直线段起点坐标为(0,0), 终点为(-8,6),试用三种画线算法来描述生成直线描点的过程。 5、如何改造构造好的绘制直线算法为绘制虚线算法？请在VC环境中实现。
第三章 二次曲线
教学学时：8课时 教学目的与要求：
让学生初步掌握绘制圆的几种算法，逐点绘制圆的方法，中点画圆方法，Bresenham画圆的方法，掌握绘制椭圆的二种方法，逐点绘制法和中点绘制法，掌握抛物线的绘制方法逐点绘制法。了解一些其他绘制圆的方法思想，比如多边形逼近法，角度参数直接法等等。掌握这些算法的理论原理，学会从理论上的算法转换到编译程序中的代码实现这个思维过程，能够分析基本算法的优缺点，掌握算法的改良后适合计算机实现的算法，了解计算机计算和理论计算的差异。
教学重点：逐点绘制的算法思想总结及在绘制直线，圆，椭圆，抛物线上的
应用和改进算法的相似性对比。中点法画圆的思想推导出画椭圆的算法。
教学内容：
3.1 圆弧的逐点插补法 3.2 圆弧的Bresenham算法 3.3 绘制圆弧的其它几种方法 3.4 椭圆的生成算法 3.5 其它二次曲线绘制举例
3.1圆弧的逐点插补法
圆弧逐点插补法算法的基本思想是：在绘制圆弧的过程中，每绘制一个点就与圆弧进行比较，根据比较的结果决定下一步的走向，这样一步一步逼近圆弧，逐点比较法的执行过程如下：
设判决函数为：
Fk?x?y?R2k2k2
若画第一象限的圆弧AB，如上图所示，起点为A(xa, ya)， 终点为B(xb, yb)，圆心为O(0，0)，设绘图笔当前位置为K(xk, yk)，这里的坐标为局部坐标。
当K在AB上时，Fk=0; K在AB外侧时，Fk>0; K在AB内侧时，Fk<0。
加上圆周的八对称性质，绘制完整的圆其实只要绘制出八分之一圆弧部分就可以了，其它可以通过对称点判断得到。
3.2 圆弧的Bresenham算法
第一象限顺时针画第一象限四分圆，如图所示，下一步选择哪个点？
YB(xb , yb)K(xk , yk)RA(xa , ya)OX下一个候选点有三个，H点，D点，V点，注意区分这个方法同中点画圆方法的不同，中点绘制圆的方法如果是第一象限顺时针绘制，下一个候选点只考虑H点和D点，而不考虑V点，造成的后果就是当圆的半径偏大时候，绘制出来的圆的误差大一些。
教材上提到的是简化的BRESENHAM画圆算法，实际绘制圆的过程中，取V点的次数很少，一般取的都是D点或H点，完整的BRESENHAM绘制算法复杂性是简化算法的二倍以上。所以从运算速度上讲，简化的算法速度更快，判断更少。缺点是可能造成误差更大，实际应用中我们一般取个折衷，对速度性能要求很高，我们牺牲点精度取速度，对精度要求很严格，那就牺牲点速度取精度。如何取与舍看场合，根据实际应用。同学们大脑中要有这种算法分析的概念与思想。 3.3 绘制圆弧的其它几种方法
除了前二节介绍的逐点绘制圆弧的算法，bresenham绘制圆弧算法外，还有很多种算法可以绘制圆，比如直角坐标的方法，参数方程角度DDA法，中点画圆法，圆弧正负法，圆弧的角度法，DDA方法，内(外)接多边形法等方法，下面简要介绍这些绘制圆弧的算法。有兴趣同学可以根据这些算法思想提炼出程序，来锻炼自己思维的能力和编程的能力，这一点对以后工作或者科研非常有帮助。在大学里面同学们主要学到的是思维的能力和学习的能力。 角度DDA法产生圆弧
若已知圆心坐标为(xc, yc)，半径为R，则以角度t为参数的圆的参数方程可写为
?x?xc?Rcost??y?yc?Rsint当t从 0 变化到2π时，上述方程所表示的轨迹是一整圆； 当t从起始角ts变化到终止角te时，则产生一段圆弧。由于我们定义角度的正方向是逆时针方向，所以圆弧是由ts到te逆时针画圆得到的。 中点画圆法
假设圆方程 F(X,Y)=X2+Y2-R2=0
见下图，当前点位置，下二个候选点中点坐标为M=(Xp+1,Yp-0.5)：
d?F(M)?F(xp?1,yp?0.5)?(xp?1)2?(yp?0.5)2?R2
当F(M)＜0时，M在圆内，P1距离圆弧近，取P1 当F(M)＞0时，M在圆外，P2距离圆弧近，取P2 DDA画圆法
圆的内接正多边形逼近法 圆的等面积正多边形逼近法
3.4 椭圆的生成算法
中心在原点、轴对齐的椭圆的非参数化方程为：
上式可用隐式方程表示为：
由于椭圆的对称性，仅考虑在第一象限的椭圆弧即可。 逐点绘制法：
与逐点绘制圆类似，只是把判决函数换掉就可以了。 中点绘制法：
椭圆弧被分成二部分，分别使用中点法判断。
参数方程绘制法：
根据椭圆的参数方程，直接绘制。
3.5 其它二次曲线绘制举例
前面介绍了几种绘制圆和椭圆的一些方法，其中逐点法是我们的重点，本节再举一例子，以逐点绘制方法为指导思想，说明简单抛物线的绘制。
思考题：
1. 试给出逐点法绘制圆弧在第二象限内逆时针绘制的推导过程和源代码。
2. 试给出不在直线上的三点，如何绘制经过这三点的圆？请给出推导过程和源代码说明。
3. 请给出逐点法绘制椭圆的推导过程和源代码，要求逆时针绘制第一象限的椭圆弧。
4. 绘制出一段抛物线，给出推导过程和源代码。
5. 比较中点法绘制圆和完备的Bresenham方法绘制圆的一些不同点，主要是误差区别。
6. 请用参数形式绘制圆，椭圆，并给出源代码说明。
7. 本章介绍的都是绘制水平椭圆或竖直椭圆，请思考一下如何绘制任意的椭圆？请给出思路。
第四章 多边形
教学学时：4课时 教学目的与要求：
让学生初步掌握多边形的定义，掌握多边形扫描转换的一些算法，掌握区域填充的种子填充递归算法并编程实现，掌握算法的理论原理，学会从理论上的算法转换到编译程序中的代码实现这个思维过程，能够分析基本算法的优缺点，掌握算法的改良后适合计算机实现的算法，最后了解多边形图案区域填充，反走样方法原理。
教学重点：扫描线填充算法，边填充算法，栅栏填充算法，种子填充算法。 教学内容：
4.1 多边形的定义
定义：一系列首尾相连的线段构成的图形。 线段 -------- 边 端点 -------- 顶点
4.1 多边形的定义 4.2 多边形的扫描转换 4.3 区域填充(种子填充算法) 4.4 反走样
一般情况：多边形是封闭的
多边形分为凸多边形、凹多边形二种
凸多边形：连多边形内任意两点的线段,该线段上的点均在多边形内。
计算机生成的物体常常可以用若干多边形来描述，有些非多边形的
物体，也可以用多边形来逼近。比如上一章二次曲线的绘制我们了解了可以用多边形去逼近圆。在多边形生成以后，就可以利用光栅显示系统对其内部区域进行填充。
那么多边形是如何在系统中如何描述的呢？ 顶点表示 点阵表示
顶点表示：用多边形顶点的序列来刻划多边形。直观、几何意义强、
占内存少；缺点是不能直接用于面着色。
点阵表示：用位于多边形内的象素的集合来刻划多边形。便于运用
帧缓冲存储器表示图形，易于面着色。缺点是失去了许多重要的几何信息；
4.2多边形的扫描转换
什么是多边形的扫描转换？
从多边形顶点信息到该多边形点阵表示的转换——多边形的扫描转
换，也就是从多边形的给定边界出发，求出位于其内部的各个象素，并给帧缓冲器内的各个对应元素设置相应的灰度和颜色，通常称这种过程为多边形的扫描转换(又称多边形的填充)。
几种方法： 逐点判断法； 扫描线算法； 边填充法； 栅栏填充法； 边界标志法。 算法思想：
逐个象素点判别，确定它们是否在多边形内，从而来决
定是否进行着色。
如何判断点在多边形的内外关系？
逐点判断法：
1）累计角度法(转角和法)； 2）射线法； 3）符号法； 扫描线算法：
扫描线算法是多边形扫描转换的常用算法。与逐点判断算法相比，扫描线算法充分利用了相邻象素之间的连贯性，避免了对象素的逐点判断和反复求交的运算，达到了减少了计算量和提高速度的目的。
开发和利用相邻象素之间的连贯性是光栅图形算法研究的重要内容。扫描线算法综合利用了区域的连贯性、扫描线连贯性和边的连贯性等三种形式的连贯性
基本思想：
按扫描线顺序，计算扫描线与多边形的相交区间，再用要求的颜色显示这些区间的象素，即完成填充工作。 ?
对于一条扫描线填充过程可以分为四个步骤： 1. 求交 2. 排序
3. 配对 4. 填色
扫描线基础算法的核心是计算扫描线与多边形的交点，然后配对，着色。其实求解交点这一步工作量是非常大的，所以根据前面介绍的多边形边的连贯性，区域的连贯性规则，我们可以构造更简单的扫描线算法(有的书称为有序边表算法)。下面是其的数据结构实现，改进后的扫描线算法就是简化了不断求解交点这么一个复杂的工作。 边填充法:
基本思想：光栅图形中，如果某区域已着上值为M的颜色值做偶数次求余运算，该区域颜色不变；而做奇数次求余运算，则该区域颜色变为值为新的颜色。这一规律应用于多边形扫描转换，就为边填充算法。 栅栏填充算法:
实质：改进的边填充算法
引入栅栏，以减少填充算法访问象素的次数。
栅栏：与扫描线垂直的直线，通常过一顶点，且把多边形分为左右
二半。
优缺点：减少了象素重复访问数目，但不彻底。 边界标志算法：
引入边标志：以克服象素被重复访问的缺点。 算法思想：
1. 轮廓线：对多边形的每一条边进行扫描转换，即对多边形边界所经过
的象素作一个边界标志。
2.填充：对每条与多边形相交的扫描线，按从左到右的顺序，逐个访问该
扫描线上的象素。
实现细节：
取一个布尔变量inside来指示当前点的状态，Inside 的初始值为假，每当当前访问象素为被打上标志的点，就把inside取反。对未打标志的点，inside不变。
4.3区域填充(种子填充算法)
上一节我们讲述了多边形的扫描转换，在实际应用中，我们可能会遇到任意的区域。要求对任意封闭的区域进行填充，不该变多边形的表示，
若inside为真，则点在多边形内，着色。 若inside为假，则点在多边形外，着背景色
区别于多边形的扫描转换。
种子填充算法思想
进行着色，因为多边形的边是直线，是规则的，所以计算起来也比较容易，但是对于任何不规则区域，考虑到边的不规则性，使用扫描线类填充算法更麻烦。种子填充算法思想是只考虑边界的颜色结构，从被填充区域内部任意一点出发，通过判断周边像素是不是边界而进行填充，直到填充完毕。
区域填充的概念
4连通：从区域内任意一点出发，可通过上、下、左、右四个方向到
达区域内的任意象素；
8连通：从区域内任意一点出发，可通过上、下、左、右、左上、左
下、右上、右下八个方向到达区域内的任意象素；
区域填充图案
多边形扫描转换与区域填充方法联系
4.4反走样
思考题：
1．如何绘制多边形？请在第二章绘制直线的基础上写出绘制多边形的方法。
2．如何判断多边形为凸或凹多边形？
3．试描述多边形扫面转换和区域填充的异同，并给出例子。 4．给出多边形扫描线算法改进的邻接链表算法例子。 用离散量表示连续量引起的失真现象称之为走样(aliasing) 走样原因：
1）光栅图形的象素是离散的，是有面积的，而非数学中面积为零的
点。
2）线段、多边形的边界等都是连续的。
因此，用离散的象素表示连续的线段或多边形的边界时光滑的线段
就成了阶梯状或锯齿状。
用于减少或消除走样现象的技术称为反走样(antialiasing) 硬件方法———提高分辨率
软件方法———区域采样，加权区域采样，半色调技术
前面介绍的扫描线，边填充算法等都是直接考虑多边形的边，最后
第五章 裁剪
教学学时：4课时 教学目的与要求：
让学生初步了解裁剪的定义，掌握对直线段裁剪的一些基本算法，掌握简单的对多边形裁剪的算法，掌握算法的理论原理，能够分析基本算法的优缺点。
教学重点：Cohen-Sutherland算法，中点分割算法，梁友栋—Barsky算法，
参数化算法，Sutlerland_Hodgman算法。
教学内容：
5.1 裁剪概述 5.2 二维裁剪 5.2.1 直线段裁剪 5.2.2 多边形裁剪
5.1 裁剪概述
在使用计算机处理图形信息时，遇到的情况往往是计算机内部存储的图形比较大，而屏幕显示只是图的一部分。例如，虽然计算机内部可以存储全国地图，但是，如果把全国地图整幅显示在屏幕上，则不能看到各地局部的细节。这时，可以使用缩放技术，把地图中的局部区域放大显示。在放大显示一幅图形的一部分区域时，必须确定图形中哪些部分落在显示区之内，哪些部分落在显示区之外，以便显示落在显示区内的那部分图形。这个选择处理过程称为裁剪。在进行裁剪时，画面中对应于屏幕显示的那部分区域称为窗口。一般把窗口定义为矩形，由上、下、左、 右四条边围成。裁剪的实质就是决定图形中哪些点、线段、文字以及多边形在窗口之内。
裁剪可以在世界坐标系中进行，即相对于窗口进行；也可以把对象变换为设备坐标之后相对于视区进行。前者可以把不在窗口范围内的部分剪掉， 避免了不必要的变换处理；后者在设备坐标系中裁剪易于用硬件实现。裁剪处理的基础是：点在窗口区域内外的判断以及计算图形元素与窗口区域边界的交点。其原理虽然简单，但涉及的图形元素多， 提高裁剪速度是算法应考虑的重要问题。以下介绍直线段裁剪算法及多边形裁剪算法。
5.2 二维裁剪
裁剪算法有二维的和三维的，裁剪对象也可以是规则形体，也可以是不规则形体。本章重点介绍二维裁剪，三维裁剪涉及到后面章节三维消隐等内容，后面再简要介绍。 5.2.1 直线段裁剪
直线段裁剪算法是复杂图元裁剪的基础。复杂的曲线可以通过折线段来近似，从而裁剪问题也可以化为直线段的裁剪问题。所以本章重点讨论直线段的裁剪算法。算法一般取的裁剪多边形都是矩形，有些特殊的算法采用任意多边形裁剪。 直接求交算法
Cohen-Sutherland算法
基本思想：
对于每条被裁剪线段P1P2分为三种情况处理: 直线与窗口边都写成参数形式，求参数值。 设直线P0P1为被裁剪线段，裁剪过程如下：
（1）若P1P2完全在窗口内，则显示该线段P1P2 。 （2）若P1P2明显在窗口外，则丢弃该线段。
（3）若线段不满足（1）或（2）的条件，则在交点处把线段分为两
段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。
为快速判断，采用如下编码方法：
对直线段的端点进行编码后，执行下面步骤： ? ? ?
若P1P2完全在窗口内code1=0,且code2=0,则“取” 若P1P2明显在窗口外code1&code2≠0，则“弃”
在交点处把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。 中点分割算法
本质：是对上面Cohen-Sutherland算法的发展与改进。
算法思想：在Cohen-Sutherland 直线段裁剪算法中, 为了避免求直线段与窗口边界的交点, 用不断对分线段的方法排斥线段在窗口外的部分, 最后求出离线段端点最远的可见点(所谓可见点就是线段落在窗口内的点), 若这两点存在, 则这两点就是线段P1P2的可见线段端点。 梁友栋-Barskey算法
地位：写入图形学教科书的唯一中国人的算法。
基本思想：把二维裁剪化为一维裁剪问题，通过求始边终边问题，并向x（或y）方向投影以决定可见线段。 参数化裁剪算法
上面讲的几种裁剪直线段的算法的裁剪区域都是矩形区域，本算法将裁剪区域推广到了凸多边形区域。
算法思想：将被裁剪的线段使用参数化表示，任取凸多边形上一点，通过
凸多边形的参数化性质判断被裁剪直线段上点同裁剪多边形的关系。 5.2.2 多边形裁剪
用直线段裁剪法可以解决折线以及封闭折线(多边形)的裁剪问题。但对多边形区域(如需进行多边形区域填充时)的裁剪则不适用。多边形区域裁剪后剩余部分应该仍然是多边形区域，裁剪后的多边形区域的边界由原来多边形经裁剪的线段及窗口区域的若干段边界组成。 Sutherland-Hodgman算法
适用对象：对凹凸多边形裁剪，裁剪窗口为凸多边形,描述简单算法使用的是矩形裁剪窗口。
基本思想:是一次用裁剪窗口的一条边所在的直线来裁剪多边形，即将多边形关于裁剪窗口的裁剪分解为多边形关于窗口各边所在直线的裁剪。 Weiler-Atherton算法
Sutherland-Hodgman算法对凸多边形应用本算法可以得到正确的结果，但是对凹多边形的裁剪将可能显示出一条多余的直线。这种情况在裁剪后的多边形有两个或者多个分离部分的时候出现。因为只有一个输出顶点表，所以表中最后一个顶点总是连着第一个顶点。
解决这个问题有多种方法，一是把凹多边形分割成若干个凸多边形，然后分别处理各个凸多边形。二是修改本算法，沿着任何一个裁剪窗口边检查顶点表，正确的连接顶点对。这就是Weiler-Atherton算法。
思考题：
1. 直线段裁剪的算法可以推广到多边形裁剪吗？为什么？
2. 线段端点编码的含义是什么？如何简单的通过端点编码判断线段在窗口外？举例说明。
3. 给出一个在坐标系上的带坐标矩形区域(裁剪区域)，给出一条典型的带坐标的直线段(直线段二个端点不在矩形区域内，但有部分区间在矩形区域内)，试用中点分割的方法求出直线段的可见部分，写出每一次分割的步骤和中点变化情况直到求解条件满足为止。 4. 给出一个Sutherland-Hodgman算法裁剪多边形的例子，要求写出步骤。
第六章 自由曲线
教学学时：6课时 教学目的与要求：
让学生初步了解自由曲线的定义，了解插值和拟合这二种不同的计算方法，初步掌握基本的Bezier曲线和B样条曲线，能编程绘制出二、三次Bezier曲线和B样条曲线。
教学重点：最小二乘法，Bezier曲线的生成， B样条曲线的生成。 教学内容：
6.1 概述
6.2 Bezier曲线 6.3 B样条曲线
6.1 概述
曲线的分类
? ? ? ?
规则曲线 自由曲线 随机曲线 计算几何
?
研究内容
? ? ?
最小二乘原理
对几何外形信息的计算机表示 对几何外形信息的分析与综合 对几何外形信息的控制与显示
1969 Minsky, Papert提出 1972 A.R.Forrest给出正式定义
1974 Barnhill, Riesenfeld, 美国Utah大学的一次
研究分支
CAGD (Computer Aided Geometrical Design)
国际会议上提出
6.2 Bezier曲线
1962年，法国雷诺汽车公司 P.E.Bezier工程师 以“逼近”为基础 UNISURF系统
1972年雷诺汽车公司正式使用
Bezier曲线的定义和性质
二次Bezier曲线、三次Bezier曲线的拼接 Bezier曲线的优点：
? ?
形状控制直观 设计灵活
Bezier曲线的缺点：
? ? ? ? ?
所生成的曲线与特征多边形的外形相距较远
局部控制能力弱，因为曲线上任意一点都是所有给定顶控制顶点数增多时，生成曲线的阶数也增高 控制顶点数较多时，多边形对曲线的控制能力减弱 曲线拼接需要附加条件，不太灵活
点值的加权平均
6.3 B样条曲线
产生：
? 1946年，Schoenberg发表关于B样条函数的第1篇论文 ? 1973年前后，Gordon,Riesenfield,Forrest等人受到Bezier方法
的启发，将B样条函数拓广成参数形式的B样条曲线
优于Bezier曲线之处：
? 与控制多边形的外形更接近 ? 局部修改能力
? 任意形状，包括尖点、直线的曲线 ? 易于拼接
? 阶次低，与型值点数目无关，计算简便 B样条曲线优点：
? 与控制多边形的外形更接近 ? 局部修改能力
? 任意形状，包括尖点、直线的曲线 ? 易于拼接
? 阶次低，与型值点数目无关，计算简便 B样条曲线缺点：
? 不能精确表示圆
思考题：
1．分别写出二、三次样条曲线的定义，并论述样条曲线的局限性。
2．给定平面上的三个顶点，用其作为特征多边形来绘制一条二次Bezier曲线，再用其作为插值顶点绘制另一条插值二次Bezier曲线，并同时画出这二条二次Bezier曲线的特征多边形。
3．任意给定一组实验数据，试用二次多项式拟合中的最小二乘法来逼近这些最数据点。
4．给出四个顶点，采用二次B样条曲线分别绘出封闭的曲线和光滑封闭曲线图。
第七章 图形变换
教学学时：4课时 教学目的与要求：
了解各种坐标系的定义及其作用；熟悉二维观察流程；掌握二维三维坐标变换的基本方法。
教学重点：坐标变换，平移变换，伸缩变换，旋转变换，组合变换； 教学内容：
7.1 图形变换的数学基础
图形变换一般是指将物体的几何信息经过放大、缩小、平移和旋转等几何变换后产生新的图形。它总是与相关的坐标系紧密相连的。从相对运动的观点来看，图形变换既可以看作是图形相对于坐标系的变动，即：坐标系固定不动，物体的图形在坐标系中的坐标值发生变化；也可以看作是图形不动，但是坐标系相对于图形发生了变动，从而使得物体在新的坐标系下具有新的坐标值。通常图形变换只改变物体的几何形状和大小，但是不改变其拓扑结构。
数学基础主要研究矢量，矩阵的一些运算，略。
7.2窗口视图变换 窗口和视图区
用户坐标系（world coordinate system，简称WC） 设备坐标系（device coordinate system，简称DC） 窗口区（window）
视图区（viewport） a 世界坐标系：
通常世界坐标系是一个三维笛卡儿坐标系。它是一个全局坐标系统，一般为右手坐标系。该坐标系主要用于图形场景中的所有图形对象的空间定位、观察者（视点）的位置和视线的定义等等。计算机图形系统中所涉及的其它坐标系基本上都是参照它进行定义的。 b 局部坐标系：
为了几何造型和观察物体方便起见，独立于世界坐标系定义的二维或三维笛卡儿坐标系称为局部坐标系。在局部坐标系中定义的\局部\物体，通过指定局部坐标系在世界坐标系中的方位，利用几何变换，就可以将\局部\定义的物体变换到世界坐标系内，使之升级成为世界坐标系中的物体。 c 观察坐标系：
观察坐标系通常是以视点的位置为原点，通过用户指定的一个向上的观察向量来定义的一个坐标系，缺省为左手坐标系。观察坐标系主要用于从观察者的角度对整个世界坐标系内的图形对象进行观察，以便简化几何物
7.1 图形变换的数学基础 7.2 窗口视图变换 7.3 二维图形几何变换 7.4 三维图形几何变换
体在视平面（又成为成像面或投影面）的成像的数学演算。 d 视平面（成像面）坐标系：
它是一个二维直角坐标系统，主要用于计算物体在成像面上的投影。一般是通过指定视方向和视点到成像面之间的距离来定义成像面（投影面）。可进一步在投影面上定义一个称之为窗口的矩形区域来实现部分成像。 e 屏幕坐标系：
屏幕坐标系也称为设备坐标系，它主要用于某一特定的计算机图形显示设备(如光栅显示器)的表面的点的定义。在多数情况下，对于每一个具体的显示设备，都有一个单独的设备坐标系。
在定义了成像窗口的情况下，可进一步在屏幕坐标系统中定义称为视区的有界区域，视区中的成像即为实际所观察到的图形对象。换句话说，在世界坐标系中要显示的区域称为窗口，而显示器上相应的图形输出区域称为视区（或视口）。将世界坐标系中的一部分区域中的场景映射到设备坐标系的过程称为观察变换；将二维观察变换简单地称为窗口到视区的变换，简称为窗视变换。
7.3二维图形几何变换
图形变换：对图形的几何信息经过几何变换后产生新的图形。 图形变换的两种形式： 1.图形不变，坐标系改变； 2.图形改变，坐标系不变。
我们所讨论的是针对坐标系的改变而讲的。 7.3.1 二维图形几何变换的原理 二维图形由点或直线段组成 直线段可由其端点坐标定义
二维图形的几何变换：对点或对直线段端点的变换 7.3.2几种典型的二维图形几何变换 1.平移变换（translation） 2.比例变换（scale） 3.旋转变换（rotation）
7.3.3 齐次坐标（homogeneous coordinates）技术 1.齐次坐标技术的引入
平移、比例和旋转等变换的组合变换
处理形式不统一，将很难把它们级联在一起。 2.变换具有统一表示形式的优点 便于变换合成 便于硬件实现
3.齐次坐标技术的基本思想
把一个n维空间中的几何问题转换到n+1维空间中解决。 4.齐次坐标表示
5.基本几何变换的齐次坐标表示
?100?? 平移变换
?x?y?1???xy1???010????TxTy1???Sx00??y?1y1? 比例变换
?x???x???0Sy0???001????cos?sin?? 旋转变换： ?x?y?1???xy1????sin?cos???00逆时针为正
6. 无穷远点或无穷远区域的齐次坐标表示 7.3.4 二维组合变换
组合变换又称级联变换，指对图形做一次以上的几何变换。 注意：任何一个线性变换都可以分解为上述几类变换。 7.4三维图形几何变换 略。 思考题：
1.试推导把二维平面上任一条直线p1(x1,y1),p2(x2,y2)变换成与X坐标重合的变换矩阵。
2.在实验三中我们绘制出的椭圆，是垂直方向的或水平方向的，也就是坐标系是水平的。根据本章所学内容，试绘制出任意椭圆。 3.试证明下述几何变换的矩阵运算具有互换性： (1)二个连续的旋转变换 (2)二个连续的平移变换 (3)二个连续的变比例变换
(4)当比例系数相等时的旋转和比例变换 0?0?1???