1、计算机图形学 复习 0.绪论提出问题 1什么是计算机图形学？ 计算机图形学是研究怎样利用计算机来生成、处理和显示图形的原理、方法和技术的一门学科。 2计算机图形学研究的对象是什么？ 计算机图形学的研究对象图形 通常意义下的图形： 能够在人的视觉系统中形成视觉印象的客观对象都称为图形。 计算机图形学中所研究的图形 从客观世界物体中抽象出来的带有颜色及形状信息的图和形。 3计算机图形处理系统的构造？ 4计算机图形学的应用边缘性学科计算机图形学与传统理论 ： 交叉、界线模糊、相互渗透 CAGD（计算几何） 逼近论（计算数学） 微分几何 形态学图形的表示点阵法是用具有颜色信息的点阵来表示图形的一种方法
2、，它强调图形由哪些点组成，并具有什么灰度或色彩。 参数法是以计算机中所记录图形的形状参数与属性参数来表示图形的一种方法。 通常把参数法描述的图形叫做图形（Graphics）把点阵法描述的图形叫做图象（Image）v 与计算机图形学相关的学科计算机图形学试图从非图象形式的数据描述来生成（逼真的）图象。数字图象处理旨在对图象进行各种加工以改善图象的视觉效果。计算机视觉是研究用计算机来模拟生物外显或宏观视觉功能的科学和技术。 0.4.1 计算机图形系统的功能 第3章 基于光栅扫描的二维图元生成算法 提出问题 如何在指定的输出设备上根据坐标描述构造基本二维几何图形（点、直线、圆、椭圆、多边形域、字符串
3、及其相关属性等）。 图形的生成：是在指定的输出设备上，根据坐标描述构造二维几何图形。图形的扫描转换：在光栅显示器等数字设备上确定一个最佳逼近于图形的象素集的过程。 直线的绘制要求：v 1.直线要直v 2.直线的端点要准确v 3.直线的亮度、色泽要均匀v 4.画线的速度要快v 5.要求直线具有不同的色泽、亮度、线型等特点：v 增量算法 , 直观、易实现、误差小 , 不利于用硬件实现 二、直线的 Bresenham算法（中点Bresenham算法基本思想：每步一个坐标改变1，而另一个坐标要看当前点与直线上点的误差e,根据e的符号决定是否改变 显然有结论：当di0时，因T小，因此选择点Ti以逼近理想
4、直线，所以有: 当di0时，因S小，因此选择点Si以逼近理想直线，所以有: 当di=0时，因S=T，规定此时选择点Ti逼近理想直线，所以有: 3.3 区域填充实面积图形: 封闭图形（或有界表面），在其封闭的面积上（轮廓内）具有相同的亮度或色彩，这意味着要让计算机填充光栅扫描图形显示器（点阵图形显示器）中封闭面积上的每一个显示点（像素点）。 根据表示实面积图形的方法不同，实面积图形的生成可分为两大类：(1) 多边的填充：即实面积图形的轮廓用其封闭多边形的顶点坐标数据来描述定义（简称实面积图形的图形表示法），在其封闭的多边形内部填充用户指定的颜色；（2）种子填充：即用点阵方式描述定义实面积图形，这
5、个图形的实面积由用户指定的点阵颜色包围或组成（简称实面积图形的图像表示法），在图形的实面积上填充用户指定的颜色，其中这个指定的第一个填充点又称为种子。由于种子填充算法原则上属图像处理方法，故不在此讨论。 1. 多边形：是一个由折线段组成的封闭图形，它由有序顶点的点集及有向边的线集定义。n为多边形的顶点数或边数，且Ei=ViVi+1,i=1，2，n。这里Vn+1=V1，用以保证多边形的封闭性。应注意，当用多边形来表示有界平面或实面积图形的边界时，规定多边形每条有向边的左侧为实面积图形的实面积区域（或内部区域），因此它不允许多边形的边线自相交叉（见图3.3-1）。 2. 环 : 因为多边形的有向边
6、线左侧为其实面积区域，故沿实面积图形外轮廓线多边形的顶点方向顺序环行时，要求该多边形顶点的整个环行方向逆时针旋转；而沿其内轮廓线多边形的顶点方向顺序环行时，要求该多边形顶点的整个环行方向顺时针旋转。这种定义了环行方向的多边形称为环。前者为外环，后者为内环（见图3.3-2）。 3. 带孔多边形 由一个外环和数个内环组成的多边形称为带孔多边形，若多边形没有内环即为不带孔多边形。4. 凹、凸多边形的判别方法 当多边形的顶点数据按环的要求存放后，判断外环上凹、凸点的方法是： 定义其中，a的表达式见公式（3.3-2），向量k与Vi-1Vi， Vi Vi+1符合右手螺旋法则。v 若数值a0，则Vi点为凹点
7、，否则为凸点。v 具有凹点的多边形为凹多边形，只具有凸点的多边形为凸多边形。v 外环的凹点对应的内角一定大于180，凸点的内角小于180，人们一般利用这一性质直观地判别凹凸多边形，并有如下结论：任何一个多边形，其外形上凸点的个数总是多于其凹点的个数。这一结论用于三维空间的有界平面中，就能确定每个有界平面的朝向（见后述）。二、多边形的填充原理 找出所有位于封闭图形内的像素点，把这些点置换成所要求的像素值。 如果在显示屏中，采用从上到下、从左到右找出每一个显示点,然后通过多边形的边界函数（凸多边形有边界函数且表达方式简单）等方法,判断其是否位于封闭图形之内后再填充。这种方法原理虽然简单，但速度太慢
8、，特别不适合凹多边形与带孔多边形的填充需要。因此有必要寻找一种通用的（适用与凹、凸、带孔的多边形）快速判断像素点位于封闭图形之内的计算方法，这是多边形图形填充的关键。 射线的交点计数法：判断像素点位于封闭图形内外的方法如下： 从封闭图形外找一点，引一水平射线（称为扫描线）与封闭图形相交。当交点计数为奇数时，扫描线在封闭图形内（射线穿入封闭图形）；当交点计数为偶数时，扫描线在封闭图形外，该方法简称交点计数法则。如图3.3-3所示 因此在正确计算扫描线与封闭多边形的所有交点 之后，图形的填充就成了画直线的过程。这种逐个计算要显示的各点并显示的过程又称扫描转换三、多边形的（YX）填充算法（YX）填充
9、算法根据多边形填充算法的原理，先求出多边形各斜边与扫描线的所有交点并记录；然后按从上到下、从左到右的次序对所有的交点进行排序；最后利用这些交点总是成对出现并从上到下、从左到右排列的规律画直线，画完所有的直线即完成填充任务。对于图3.3-5（a）所示的多边形，其扫描线与多边形各斜边的交点的排序结果如图3.3-5（b）所示。根据这一结果，读者不难完成该多边形的填充。四、多边形的Y-X填充算法 （YX）填充算法虽然简单，v 但当多边形的形状复杂时，其交点表的容量非常大；v 而且对交点进行排序很费时，这极大地影响了该算法的使用效果；为了克服这两个缺点，可对该算法进行如下改进： v 改进存储方式。不存储
10、多边形上每个交点的坐标，而是存储其每条斜边。如果一条斜边用其2个顶点坐标变量（x1，y1），（x2，y2）来代替的话，这将比存储斜边上的每个交点坐标所需要的存储容量要少得多；v 改进交点的计算方法，并要求斜边上的每一交点与填充扫描线同步出现，以便画线填充多边形；v 因多边形的斜边总量远比其交点总量小，故对斜边的排序相对较快。3.6.2 图形的裁剪在二维观察中，需要在观察坐标系下对窗口进行裁剪，即只保留窗口内的那部分图形，去掉窗口外的图形。一、点与字符的裁剪 当图形系统的窗口确定之后，设被裁剪的点坐标为（x, y），则只有当该点的坐标满足下式该点才位于窗口之内，并经窗视变换送视区中显示，否则该点
11、位于窗口之外而被舍去。 二、 直线段的裁剪假定直线段用p1(x1,y1)p2(x2,y2)表示。v 直线段和剪裁窗口的可能关系： 完全落在窗口内 完全落在窗口外 与窗口边界相交v 实交点是直线段与窗口矩形边界的交点。v 虚交点则是直线段与窗口矩形边界延长线或直线段的延长线与窗口矩形边界的交点。1. 直线的编码裁剪算法基本思想：对每条直线段p1(x1,y1)p2(x2,y2)分三种情况处理：(1) 直线段完全可见，“简取”之。(2) 直线段完全不可见，“简弃”之。(3) 直线段既不满足“简取”的条件，也不满足“简弃”的条件，需要对直线段按交点进行分段，分段后重复上述处理。算法的步骤：(1)输入直
12、线段的两端点坐标：p1(x1,y1)、p2(x2,y2)，以及窗口的四条边界坐标：wyt、wyb、wxl和wxr。(2)对p1、p2进行编码：点p1的编码为code1，点p2的编码为code2。(3)若code1|code2=0000，对直线段应简取之，转(6)；否则，若code1&code20000，对直线段可简弃之，转(7)；当上述两条均不满足时，进行步骤(4)。(4)确保p1在窗口外部：若p1在窗口内，则交换p1和p2的坐标值和编码。(5)按左、右、上、下的顺序求出直线段与窗口边界的交点，并用该交点的坐标值替换p1的坐标值。也即在交点s处把线段一分为二，并去掉p1s这一段。考虑到p1是窗
13、口外的一点，因此可以去掉p1s。转(2)。(6)用直线扫描转换算法画出当前的直线段p1p2。(7)算法结束。特点：在两类裁剪场合非常高效：大窗口和特别小的窗口2. 中点分割算法基本思想： 当对直线段不能简取也不能简弃时，简单地把线段等分为二段，对两段重复上述测试处理，直至每条线段完全在窗口内或完全在窗口外。算法步骤：(1)输入直线段的两端点坐标：p1(x1,y1)、p2(x2,y2)，以及窗口的四条边界坐标：wyt、wyb、wxl和wxr。(2)对p1、p2进行编码：点p1的编码为code1，点p2的编码为code2。(3)若code1|code2=0000，对直线段应简取之，保留当前直线段的
14、端点坐标，转(5)；否则，若code1&code20000，对直线段可简弃之，转(5)；当上述两条均不满足时，进行步骤(4)。(4)求出直线段的中点M，将p1M、p2M入栈。(5)当栈不空时，从栈中弹出一条直线段，取为p1p2，转(2)进行处理。否则，继续(6)。(6)当栈为空时，合并保留的直线段端点，得到窗口内的直线段p1p2。用直线扫描转换算法画出当前的直线段p1p2，算法结束。 中点分割算法的核心思想是通过二分逼近来确定直线段与窗口的交点。 1.多边形的逐边裁剪算法算法实施策略：v 为窗口各边界裁剪的多边形存储输入与输出顶点表。在窗口的一条裁剪边界处理完所有顶点后，其输出顶点表将用窗口的
15、下一条边界继续裁剪。v 窗口的一条边以及延长线构成的裁剪线把平面分为两个区域，包含有窗口区域的一个域称为可见侧；不包含窗口区域的域为不可见侧。特点：适用于凸多边形和裁剪后仍连通的凹多边形，适于用硬件实现 当多边形的所有顶点都按这种情况处理完毕之后，所保存的顶点与交点就是所组成的数个新多边形的顶点。为使新多边形封闭，注意还要裁剪VnV1所组成的边（ V1,Vn分别是多边形的第一个顶点与最后一个顶点）。 在实现该算法时，如果保留每次裁剪之后的中间结果，这一中间结果会占用很大的存储空间，但如果能用递归的方式实现该算法，则不用保留每次裁剪的中间结果。 递归算法 :v 首先按多边形的顶点次序依次裁剪多边
16、形的每条边；v 而对多边形的每条边先用窗口的第一条边框去裁剪；v 当这条边通过窗口的第一条边框裁剪之后；v 再用窗口的第二条边框去裁剪；v 如果它通过第二条边框裁剪之后；v 再用窗口的第三、四条边框去裁剪；v 最后通过第四条边框裁剪输出的顶点与交点，就是被窗口裁剪之后新多边形的顶点。v 不能通过上述四步裁剪的边线，其顶点与交点自然被舍弃，因而对应的边线也被裁掉。 图形几何变换的目的：是用已有的简单图形构造复杂图形 5.1 图形的几何变换1齐次坐标v 齐次坐标表示就是用n+1维向量表示一个n维向量。 二维平面中的一个点P(x,y)，在齐次坐标系中可表示成P（wx,wy,w）其中w是一个不为0的常
17、量；反过来，只要能给定一个点的齐次坐标 ，我们就能得到这个点的二维直角坐标系 。 齐次坐标的不唯一性 规范化齐次坐标表示就是w=1的齐次坐标表示。v 如何从齐次坐标转换到规范化齐次坐标？2 几何变换图形的几何变换是指对图形的几何信息经过平移、比例、旋转等变换后产生新的图形，是图形在方向、尺寸和形状方面的变换。基本几何变换都是相对于坐标原点和坐标轴进行的几何变换1 平移变换平移是指将p点沿直线路径从一个坐标位置移到另一个坐标位置的重定位过程。平移是一种不产生变形而移动物体的刚体变换2 比例变换 比例变换是指对p点相对于坐标原点沿x方向放缩Sx倍，沿y方向放缩Sy倍。其中Sx和Sy称为比例系数。3
18、 旋转变换二维旋转是指将p点绕坐标原点转动某个角度（逆时针为正，顺时针为负）得到新的点p的重定位过程。4 对称变换对称变换后的图形是原图形关于某一轴线或原点的镜像。5 错切变换错切变换（主要用于三维图形变换），也称为剪切、错位变换，用于产生弹性物体的变形处理。(1)沿x方向错切 (2)沿y方向错切 (3)两个方向错切 二维图形几何变换的计算用点的齐次坐标及变换矩阵的组合方式，可表示一个图形连续的几何变换，以产生所需要的结果。几何变换均可表示成P=P*T的形式 1. 点的变换 2. 直线的变 换 3. 多边形的变换 4. 曲线的变换 注意:v 图形旋转一定是相对于某个参考点进行的。v 同样图形进
19、行比例变换，也是相对某个参考点进行的。在应用中如果不注意这点就会导致错误的结果。3.坐标系的变换 前面都是讨论在同一坐标系中把一组点变换成另一组点。实际上，把一组点变换成另一组点的另一种可选择的方法是改变坐标系。下面用两个例子来说明这种变换。 这一结论也适用于平移、比例、反射、错切等基本几何变换，即图形在坐标系中的变换等效于图形不变而让坐标系进行反向变换，这两者的变换效果与变换矩阵是一样的。 从而可归纳出如下结论：v 图形在坐标系中的放大等效于图形保持不变而让坐标系刻度尺寸缩小；v 图形在坐标系中沿坐标轴正向移动等效于图形保持不变而让坐标系沿坐标轴负向移动；v 图形在坐标系的正向旋转等效于图形保持不变而让坐标系负向旋转；v 图形相对X轴进行反射变换等效于该图形保持不变而让Y轴自身发生反射变换等。这一结论对计算机图形学分析非常有用。由此结论可知，表示坐标系变换所需要的矩阵就是在坐标系中反向变换这些点所需要的矩阵。 当用矩阵方法解决图形的连续几何变换时应注意：由于矩阵乘法一般不适用于交换律，所以图形在连续变换时，一般不能改变其变换的次序，否则不会得到正确结果。
