计算机图形学基础知识重点整理

计算机图形学复习资料 第一章 1 图形学定义

ISO的定义：计算机图形学是研究怎样利用计算机表示、生成、处理和显示图形的原理、算法、方法和技术的一门学科。

通俗定义：计算机图形学以表达现实世界中的对象及景物为主要目标，其核心是解决如何用图形方式作为人和计算机之间传递信息的手段，即人机界面问题。

计算机图形学的研究对象——图形。图形是从客观世界物体中抽象出来的带有颜色及形状信息的图和形。

图形的构成要素：几何要素：点、线、面、体等描述对象的轮廓、形状。非几何要素：描述对象的颜色、材质等。

图形的表示方法：点阵法：枚举出图形中所有点(简称图像)。参数法：由图形的形状参数(简称图形)。 2 图形与图像

图像：狭义上又称为点阵图或位图图像。图像是指整个显示平面以二维矩阵表示，矩阵的每一点称为一个像素，由像素点所取亮度或颜色值不同所构成的二维画面。

特点：

A文件所占的空间大。

B位图放大到一定的倍数后会产生锯齿。

C位图图像在表现色彩、色调方面的效果比矢量图更加优越。

图形：狭义上又称为矢量图形或参数图形。按照数学方法定义的线条和曲线组成，含有几何属性。或者说更强调场景的几何表示，是由场景的几何模型和景物的物理属性共同组成的。

特点： A文件小。

B可采取高分辨印刷。 C图形可以无限缩放。 3 图形学过程

3D几何建模、3D动画设置、绘制（光照和纹理）、生成图像的存储和显示 4 与图像处理

计算机图形学：研究模型及数据的建立和由模型生成图像的过程和方法。（模型到图像）

图像处理：将客观景物数字化成图像，研究数字化图像的采集、去噪、压缩、增强、锐化、复原及重建等。（图像到特征）

对立统一的关系。 5 计算机图形信息的特点

图形信息表达直观，易于理解。 图形信息表达精确、精炼。

图形信息能“实时”的反映事物的分布和变化规律 6 计算机图形学的应用

计算机辅助设计及计算机辅助制造 科学计算可视化 地图制图与地理信息系统 计算机动画、游戏 用户接口 计算机艺术 7 计算机图形系统

作为一个图形系统，至少应具有计算、存储、输入、输出、对话等五个方面的基本功能。 计算机图形系统主要有三部分构成：人、图形软件包、图形硬件设备。 图像硬件设备通常由图形处理器、图形输入设备和输出设备构成。 第二章

1图形的扫描转换

确定一个像素集合及其颜色，用于显示一个图形的过程，称为图形的扫描转换。从本质上讲，图形的扫描转换是由参数表示形式到点阵表示形式的转换过程。

PS1：在输出设备上输出一个点，首先需要计算出最逼近该点的像素位置，其次需要把应用程序中的坐标信息转换成所用输出设备的相应指令

PS2：在显示器有限个像素中，确定最佳逼近该直线的一组像素，并且按扫描线顺序，对这些像素进行写操作，这个过程称为直线的扫描转换。 2 DDA算法

最基本思想：

从x的左端点x0开始，向x右端点步进，步长=1(个像素)。X步进后，用y=kx+b计算相应的y坐标。最后取像素点(x, 取整round(y))作为当前点的坐标。即当x每递增1，y递增k。

PS：实际代码时用Y+0.5替代取整。

PS2：当 |k|>1时，必须把x，y地位互换。按照从(x1, y1)到(x2, y2)方向不同，分8个象限。例如对于方向在第1a象限内的直线而言，取增量值Dx=1，Dy=k。对于方向在第1b象限内的直线而言，取增量值Dy=1，Dx=1/k。其余同理。

优点：

最简单，最直接的画线算法。采用增量的思想，每计算一个像素，只需计算一个加法。 缺点：

由于斜率很可能是小数（浮点数），因此每个加法都意味着是浮点运算，浮点运算不利于硬件实现；每次加法后还必须进行一次四舍五入后的取整运算。 3 中点画线法

假设当前像素点为P(xp, yp) ，则下一个像素点为P1（右） 或P2（右上） 。

设M=(xp+1, yp+0.5)，为p1与p2之中点，Q为理想直线与x=xp+1垂线的交点。将Q与M的y坐标进行比较。

当M在Q的下方，则P2应为下一个像素点；M在Q的上方，应取P1为下一点。 具体算式：

d=F(M)=F(xp+1,yp+0.5) =a(xp+1)+b(yp+0.5)+c （a=y0-y1， b=x1-x0，c=x0y1-x1y0）

当d<0，M在Q点下方，取右上方P2为下一个像素； 当d>0，M在Q点上方，取右方P1为下一个像素； 当d=0，选P1或P2均可，约定取P1为下一个像素；

改进1：根据前一点的判别式值d和整数增量即可得到后一点的判别式值d’。 因此可采用增量计算，只有加法，提高运算效率。若当前像素处于d>0情况，则取正右方像素P1 (xp+1, yp ), 要判下一个像素位置，应计算d’=d+a；若d<0时，则取右上方像素P2 (xp+1, yp+1)。要判断再下一像素，则要计算 d’= d+a+b

改进2：由于只判别d 的符号确定下一个像素位置，因此可以用2d来判别，化为整数算法。递推算法中只包含加、减运算，便于硬件实现。d’=d+2a；d’= d+2（a+b） 4 Bresenham算法

基本思想：过各行各列像素中心构造一组虚拟网格线。按直线从起点到终点的顺序计算直线与各垂直网格线的交点，然后根据误差项的符号确定该列像素中与此交点最近的像素。

算法：

假设起始位置像素落在直线上，d = 0；沿横坐标每前进一步，d 的值增加量为k, 即d = d + k；一旦d > 1，即令d = d－1， 保证 d 介于0与 1之间。

当d > = 0.5 时， 直线接近右上方像素，d < 0.5 时，直线接近右方像素。为便于判别，令 e = d － 0.5， 则当e >= 0， 取右上方像素，当 e < 0， 取右方像素。e 的初始值为 －0.5。y在递增时，e在取值范围一般介于-0.5与0.5之间。

改进：

由于只判别 e 的符号，确定像素的取舍，因此可令 e’ = 2 × e × dx，通过判别 e’ 的符号确定像素取舍，不但可以避免小数运算，还能避免除法。

优点：增量算法、避免了浮点运算、避免了乘除法运算，节省运算量，并适合硬件实现，使用最广泛 5 圆的扫描转换

若已知圆弧上一点P1＝C（x, y），利用其对称性便可以得到关于四条对称轴的其它7个点，即：P2＝C（x,－y），P3＝C（－x, y），P4＝C（－x,－y），P5＝C（y，x），P6＝C（－y，x），P7＝C（y，－x），P8＝C（－y，－x）。这种性质称为八对称性。因此，只要扫描转换八分之一圆弧，就可以通过圆弧的八对称性得到整个圆。 6 中点画圆法

函数（圆心在原点为例）： F(x,y)=x2＋ y2－R2，第一点为P（xp，yp） 圆上点： F(x,y)= 0；圆外点： F(x,y)> 0；圆内点： F(x,y)< 0 设M是待选像素P1，P2的中点, M坐标(xp+1,yp-0.5)，判断d=F(M)

若 d<0, 则取右侧P1( xp+1,yp)为下一像素，而且再下一像素的判别式为d’=d+2xp+3；若d>=0, 则应取右下P2(Xp+1,Yp-1)为下一像素，而且下一像素的判别式为d’=d+2（xp-yp）+5。

例：第一个像素是（0,R），第一个M的坐标为(1,R-0.5)，则判别式d的初始值为1.25-R。

改进：为了进一步提高算法的效率，可以将上面的算法中的浮点数改写成整数，将乘法运算改成加法运算，即仅用整数实现中点画圆法。即使用e=d-0.25代替d，即e0=1-R。则判别式 d < 0 对应于e < -0.25 ,由于 e0=1-R 的初值为整数， 且在运算中增量为整数，故 e < -0.25 等价于 e < 0 ! 7 Bresenham画圆法

基本思路：通过比较临近像素点到圆弧的距离，设法求出该距离的递推关系，并通过符号判别像素取舍。

设从点Pi(xi,yi)出发，顺时针画第一个四分圆。待选点与圆弧只可能有5种关系。下一像素有3种可能的选择：

ΔH=(xi+1)2+yi2-R2 ΔD=(xi+1)2+(yi-1)2-R2 ΔV=xi2 +(yi-1)2-R2

选择像素的原则：使其与实际圆弧的距离平方达到最小

具体算法：考察右下角像素D 与实际圆弧的近似程度：ΔD=(xi+1)2+(yi-1)2-R2 当ΔD<0时，D在圆内，情形①② 当ΔD=0时，D在圆上，情形③ 当ΔD>0时，D在圆外，情形④⑤ 结论： 当ΔD<0时,

若2 (ΔD+yi) -1 ≤0，选H 若2 (ΔD+yi) -1 >0，选D

当ΔD>0时,

若2 (ΔD -xi)-1 ≤0，选D 若2 (ΔD -xi)-1 >0，选V 当ΔD=0时，选D 完整流程：

(1) 初值:从(0, R)开始画圆， ΔD=(0+1)2+(0-1)2-R2 =2(1－R)； (2) 根据ΔD的符号判断，计算dHD或 dDV，确定选中D、H、V中某点； (3) 若下一像素为H(x’,y’) ＝(x＋1，y)，则 Δ’D＝ ΔD＋2x’＋1；

(4) 若下一像素为D(x’,y’) ＝(x＋1，y－1)，则 Δ’ D ＝ ΔD＋2x’－2y’＋2； (5) 若下一像素为V(x’,y’) ＝(x，y－1)，则 Δ’ D ＝ ΔD－2y’＋1； (6) 重复(2)～(5), 直至完成圆弧。 第三章

1多边形的表示方法

A顶点表示：用多边形的顶点序列来刻画多边形。

特点：表示方法直观，几何意义强，占内存空间少。但没指明哪些像素在多边形内，不能直接用于着色

B点阵表示：用位于多边形内部或边界上的像素集合来刻画多边形。会失去很多重要的几何信息，但它是光栅显示系统显示面着色时所需的图形表示形式。 2 扫描转换与区域填充的联系与区别

（1）定义

多边形的扫描转换：

从多边形顶点表示到点阵表示的转换，这种转换称为多边形的扫描转换。

这种转换就是给多边形包围的区域着色的过程。即从多边形的给定边界出发，求出位于其内部的各个像素，并将其灰度和颜色值写入帧缓存中相应单元。主要用来填充多边形区域以及由多边形拟合的其他简单曲线区域。

区域填充：

从给定的位置开始涂描直到指定的边界为止。

区域是指一组相邻而又相连的像素，且具有相同的属性。区域填充可用在具有复杂形状边界的多边形以及交互式绘图系统中。

（2）联系

都是光栅图形面着色，二者可相互转换。

当已知顶点表示的多边形内一点作为种子点，并用扫描转换直线段的算法将多边形的边界表示成八连通区域后，多边形扫描转换问题就可转化为区域填充问题；若已知给定区域是多边形区域，并且通过一定的方法求出它的顶点坐标，则区域填充问题便可以转化为多边形扫描转换问题。

（3）区别

A基本思想不同，各自应用的场合不同。

多边形扫描转换是指将多边形的顶点表示转换成点阵表示的方法，而区域填充只改编了区域的填充颜色，没有改变区域的表示方法。

B对边界的要求不同。

多边形扫描转换不要求多边形的边界封闭。而区域填充为了防止递归填充时跨越区域的边界，需设定边界。

C基于的条件不同。

多边形扫描转换是从多边形的边界信息出发，利用多种形式的连贯性进行填充；区域填充算法给定区域内一点作为种子点，从这点根据连通性将新的颜色扩散到整个区域。

3 矩形填充

填充从ymin到ymax每条扫描线位于xmin和xmax之间的区段就可以了。

共享边的处理方式：如果像素的中心落在矩形边界的左方或下方时，该像素属于矩形，否则不属于该矩形区域，也就是说，如果象素的中心落在矩形边界的右方或上方时，该象素不属于矩形区域。 4 扫描转换三种方法

逐点判断算法（射线法、弧长法）；扫描线填充算法；边缘填充算法 （1）射线法

由被测点向某方向做射线，计算此射线与多边形所有边的交点个数。若交点个数为奇数，则被测点在多边形内部；若交点个数为偶数(包括0)，则该点在多边形的外部。

规定射线过顶点时，计数为1；在射线左边的边与该射线相交时交点有效，应计数；而在射线右边的边与射线相交时交点无效，不计数 (左闭右开原则)。

（2）弧长法

前提：多边形由有向边组成, 即规定沿多边形各边的走向其左侧(或右侧)为多边形的内部。 方法：以被测点为圆心作单位圆，将全部有向边向单位圆作径向投影，并计算其在单位圆上弧长的代数和。若代数和为0，则被测点在多边形之外；若代数和为2Pi，则被测点在多边形之内。（效率低）

（3）扫描线填充算法

算法思想：按扫描线顺序，先计算出扫描线与多边形区域边界的交点，然后判断扫描线上的哪些部分在区域边界之内，最后用要求的颜色对边界内的像素填色。

实现方法：依次考察各条扫描线，一条扫描线从左至右与多边形的交点是成对出现的。即A、B点，C、D点之间的像素都位于多边形之内，则A、B为一个区段， C、D为一个区段。对这些区段内的像素用指定的颜色进行填充后，就完成了该扫描线的填充工作，再继续下一条扫描线。

实现步骤（四步）：

A求交点：计算扫描线与多边形各边的交点 B交点排序：把所有交点按递增顺序进行排序

C交点配对：第一个交点与第二个交点，第三个交点与第四个交点等,每对交点代表扫描线与多边形的一个相交区间((A、B) (C、D))

D区间填色：把这些相交区间内的象素置成多边形颜色，把相交区间外的象素置成背景色。

注1：如何保证交点正确配对？答：检查两相邻边在扫描线的哪一侧。若共享顶点的两条边：分别落在扫描线两边，取交点1次；均高于扫描线，取交点2次；均低于扫描线，取交点0次。（具体实现：检查顶点的两条边的另外两个端点的y值，按这两个y值中大于交点y值的个数是0、1、2来决定交点是取零个、一个、两个。）

注2：边界上像素的取舍问题？答：落在右/上边界的象素不予填充，而落在左/下边界的象素予以填充。（具体实现：对扫描线与多边形的相交区间，取“左闭右开”；而正确配对则保证了多边形的“下闭上开”。）

数据结构：

为了求出扫描线与多边形边的交点，最简单的方法是将多边形的所有边放在一个表中,称之为边表，在处理每条扫描线时，从表中顺序取出所有的边，分别求这些边与扫描线的交点。实际上在进行扫描线与多边形边求交点时，应只求那些与扫描线相交的边的交点。

把与当前扫描线相交的边称为活性边。并把它们按与扫描线交点 x 坐标递增的顺序存放在一个链表中，称此链表为活性边表。

边表(ET)构造：

先按端点的纵坐标值对所有边作总分组，再将同一组中的边按端点X坐标递增的顺序进行排序。 活性边表(AET) ：假设当前扫描线与多边形的某一条边的交点坐标为x，那么下一条扫描线与该边的

交点不必从头计算，只要加上一个增量即可。（设边AB的斜率为k，若其与扫描线yi的交点横坐标为xi，则与扫描线yi＋1的交点的横坐标为： xi＋1＝xi＋1/k ）

活性边表(AET)的结点中至少应为对应边保存如下内容： X: 边与当前扫描线的交点的X坐标； ΔX: 当前扫描线到下一扫描线之间x的增量 Ymax: 边所交的最高扫描线号； 算法步骤：

优点：

A数据结构和算法本身要比逐点判断算法复杂。 B速度比逐点判断算法快得多。 C利用边的连贯性来加速交点的计算 D利用AET以排除盲目求交

E利用扫描线的连贯性以避免逐点判别 缺点：对各种表的维持和排序开销大。

（4）边缘填充算法

基本思想：对于每一条扫描线和每条多边形边的交点(x1,y1)，将该扫描线上交点右方的所有像素取补。（对该区域内象素颜色作偶数次取补运算后，该区域内象素的颜色保持不变，而做奇数次取补运算后，该区域内象素的颜色变为M’。）

优点是算法简单，缺点是对于复杂图形，每一象素可能被访问多次，增加了运算量。

（5）(栅栏)边缘填充算法

栅栏：指的是一条与扫描线垂直的直线。栅栏位置通常取多边形的顶点，且把多边形分为左右两半。 基本思路：对于每个扫描线与多边形的交点，将交点与栅栏之间的象素用多边形的属性值取补。 算法特点：

A用求补运算代替排序 B数据结构和程序结构简单 C需要对帧缓存的大量象素反复赋值

D运行速度比扫描线算法慢

5 区域填充

区域：指已经表示成点阵形式的填充图形，它是象素的集合。 分类：

4连通内部表示区域：可以从任一象素出发，通过上、下、左、右等4个方向的移动，到达另一个象素；

8连通内部表示区域：从任一个象素出发，需要通过水平、垂直、对角线等8种方向的移动，到达另一个象素。

区域的特点:

A一条扫描线上的像素存在着相关性； B在多边形边处，像素性质才发生变化；

C将相邻像素放在一起测试，从而减少测试点的数目。

区域填充：指先将区域的一点赋予指定的颜色，然后将该颜色扩展到整个区域的过程。区域填充算法要求区域是连通的。

区域建立和定义的方式：

A1内定义区域：区域内部所有象素具有同一种颜色或亮度值，而区域外的所有象素具有另一种颜色或亮度值。

A2漫水法：将该区域内的全部象素都设置为新值的算法，即填充内定义的区域

B1边界定义区域：边界上所有象素均具有特定的颜色或亮度值，而在区域内的象素则具有不是新值的某种颜色或亮度值。

B2边界填充算法：将边界定义区域中的全部象素值都设置为新值的算法。 6 漫水法（种子填充法）

基本思想：设（x，y）为四连通区域内部的一点，old_Color为区域内部所有象素的原色。现取（x，y）为种子点，要将整个区域填充为新的颜色new_Color。

填充算法：先判别象素（x,y）的颜色：若它的值等于old_Color，说明该象素位于该区域内部，则设置该象素的颜色为new_Color，并对与该象素相邻的上、下、左、右4个相邻象素作递归填充；否则说明该象素的颜色在区域外或已被填充过，不再进行处理。 7 边界填充算法

基本思想：与漫水法的基本思想一样，只是在测试（x，y）点的象素是否处在区域之内同时又未被访问过时，包括两部分的内容：与边界值相比较，以检测此象素是否为该区域的一部分；与新值相比较，以决定该象素是否已被访问过。

前提条件：在初始状态，区域内没有一个象素已设置为新值。但是允许新值等于边界值。

在区域内测试（x，y）点的象素是否在区域之内同时又未被访问过，一般采用堆栈的方法。对边界定义的区域进行填充，基本流程如下 ：

A种子象素入栈，当栈非空时，执行如下三步操作： B栈顶象素出栈；

C将出栈象素置成多边形色；

D按上、下、左、右的顺序检查与出栈象素相邻的四个象素，若其中某个象素不在边界上且未置成多边形色，则把该象素入栈。

算法特点：

A算法程序简单，表达清楚 B需要反复递归，其执行效率并不高

C未考虑象素间的相关性，而是孤立地对一个个象素进行测试。 8 扫描线区域填充算法

基本思想：利用了象素之间的连贯性，将扫描线上位于区域内部的相邻象素作为一个区域来考虑，只选一个象素作为代表进栈，从而极大地减少了对栈空间的需求，并且显著地提高了执行效率。

算法过程：首先填充当前扫描线上位于区域内部的一个区段，它的颜色为old_Color，现在将fill_Color作为区域填充的新颜色；然后确定与这一区段相邻的上、下两条扫描线上位于区域内部的区段，分别将它们右端象素作为种子点保存起来。反复进行这一过程，直到保存的区段都填充完毕为止。

基本步骤：

A种子象素压入堆栈；

B从包含种子象素的堆栈中推出区段的种子象素；

C沿着扫描线对种子象素的左右象素进行填充，直至遇到边界象素为止，标记区段的左、右端点坐标为xl和xr；

D在区间[xl，xr]中检查与当前扫描线y上、下相邻的两条扫描线上的象素。若存在非边界、未填充的象素，则把每一区间的最右象素作为种子点压入堆栈，返回第②步。

E堆栈为空时结束。

第四章 1输出图元属性

在图元输出之前，可为其指定不同的属性，属性定义了图元在输出设备上的外部特征。如线宽、线型、色彩等。 （1）线宽控制

顺着扫描所产生的线条轨迹，移动一把具有一定宽度的 “刷子”，刷子的形状可以是一条线段或一个正方形。也可以采用区域填充的办法间接产生有宽度的线。 （2）线型控制

使用具有不同线型的线条来表示不同的含义，线型属性主要包括实线、虚线、点划线。 2线宽控制

（1）线刷子法：在扫描转换图元时，同时显示n个像素。这样就将原来绘制单个像素的语句改写成以该像素为中心绘制水平或垂直排列的多个像素。（斜率绝对值小于1，垂直方向上像素复制；斜率绝对值大于1，水平方向上像素复制）

优点：算法简单、执行效率高，适合于比较小的线宽。 缺点：

A线段的两端只有水平或垂直两种情况；

B曲线要根据当前绘制像素的斜率来决定是在水平方向还是垂直方向复制像素 C在折线连接处由水平复制转为垂直复制时，会产生缺口

D当线宽为偶数个像素时，线条要么粗一个像素，要么细一个像素。

（2）方形刷子法：将原来绘制单个像素的语句改写成以该像素为中心绘制画笔位图的语句。也就是将设定宽度为k的画笔的中心沿线段移动，即可产生具有线宽k的线条。

（3）区域填充法：根据线条的宽度，计算出线条的外轮廓，然后调用填充图元的生成函数将其填充，产生具有一定线宽的线条。 3线型控制

显示虚线时：把画线算法修改为沿一直线输出带有间隙的短实线； 点划线：是每画一短实线加入一点；

其他线型：可通过短划线的长短不同及间隙不同来重新组合得到。 *4 字符

分类：ASCII码字符、汉字字符 表示方法: （1）位图表示

对输出字符要求较高时使用。

缺点：需占用大量存储空间，可以使用固定大小的字体来产生大小和字形等方面的各种变化，但效果往往不能令人满意。

（2）轮廓线表示：采用直线或二、三次Bezier曲线的集合来描述一个字符的轮廓线。

特点：可对字符的轮廓线作变换产生一种字体的各种变化，只需存储一套轮廓线表示，可节省大量的存储空间，但扫描转换需要更长的处理时间。

字符属性：在输出字符之前，往往需要指定一系列字符属性。包括字体、字形、字符大小、字符间距、字符颜色、字符串对齐方式等 5 图形裁剪

在放大显示一幅图形的一部分区域时，必须确定图形中哪些部分落在显示区之内，哪些落在显示区之外，以便显示落在显示区内的那部分图形。这个选择过程称为裁剪。

实质：决定图形中哪些点、线段、文字、以及多边形在窗口之内。 裁剪的基础：图元关于窗口内外关系的判别、图元与窗口的求交。

A点裁剪：点(x, y)在窗口内的充分必要条件是，X属于XMIN,XMAX，Y同理

B直线裁剪：待裁剪线段和窗口的关系若为线段完全可见、显然不可见，可直接处理；若线段至少有一端点在窗口之外，但非显然不可见，需求交。 6直线裁剪算法

（1）Cohen-Sutherland法

对于每条线段P1P2，若P1P2完全在窗口内则显示该线段P1P2，取之；若P1P2明显在窗口外则丢弃该线段P1P2，弃之；若线段既不满足“取”的条件也不满足“弃”的条件，则把线段分成两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。

算法步骤： A建立区域码：

区域码：表示直线端点相对位置的4位二进制代码。区域码按照点与窗口边界的相对位置编码，即区域码的4位分别代表端点位于窗口的上、下、左、右——在窗口上边线之上，第4位为1，否则第4位为0；在窗口下边线之下，第3位为1，否则第3位为0；在窗口右边线之右，第2位为1，否则第2位为0；在窗口左边线之左，第2位为1，否则第1位为0；

B依区域码裁剪：

若code1=0且code2=0，P1P2明显在窗口内，则取

若code1&code2≠0，P1P2明显在窗口外，则弃;

在交点处把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。 注：如何判定应该与窗口的那条边求交？答：编码中对应位为1的边。 （2）中点分割算法

从P0点出发找出离P0最近的可见点，和从P1点出发找出离P1最近的可见点。这两个可见点的连线就是原线段的可见部分

算法步骤：

与Cohen-Sutherland算法一样首先对线段端点进行编码，并把线段与窗口的关系分为三种情况，对前两种情况进行一样的处理；对于第三种情况，用中点分割的方法求出线段与窗口的交点。

具体流程：找距离P0最近可见点—— A先求出P0P1的中点Pm,

B若P0Pm不是显然不可见的，并且P0P1在窗口中有可见部分，则距P0最近的可见点一定落在P0Pm上，所以用P0Pm代替P0P1；

C否则取PmP1代替P0P1。

D再对新的P0P1求中点Pm。重复上述过程，直到PmP1长度小于给定的控制常数为止，此时Pm收敛于交点。

7多边形裁剪：Sutherland-Hodgman算法

基本思想：每次用窗口的一条边裁剪多边形。 流水线过程(左上右下)：前边的结果是后边的输入。

算法实现：窗口的一条边以及延长线构成的裁剪线把平面分成两个部分，多边形的各条边的两端点S、P与裁剪线的位置关系有四种。仅用一条裁剪边对多边形进行裁剪，得到一个顶点序列，作为下一条裁剪边处理过程的输入。

缺点：在所裁剪的多边形是一个凹多边形时，最后裁剪生成的区域可能存在两个或多个不相连接的多边形。

*8 字符裁剪

标准字符一般把字符作为一个整体裁剪；线段组成的字符，可用直线裁剪方法。 字符裁剪方法可分为：

A以串为单位的裁剪：把整个字符串作为整体来处理。或全部显示，或全不显示。

B字符裁剪：每1个字符被一个称为字符框的矩形所包围，然后以这个框和窗口进行比较，若这个框在完全窗口内则显示该字符。

C矢量裁剪：把每个字符都看作是一些短直线(笔划)的组合，每一笔划都进行裁剪。 9反走样

原因：由于在对信号进行数字化处理时，物体上的某坐标点的位置是以光栅上的整数象素位置近似表示的。

分类：

A阶梯状的边界：即光滑的线段变成了离散的阶梯形状。

B图形细节失真：当且仅当象素中心被这些矩形覆盖时象素才被显示。

C狭小图形遗失：由于狭小的多边形分布在两条扫描线之间，它们不覆盖任何一个象素中心，因此，没有被显示出来。

反走样方法：

A提高分辨率：显示器的分辨率提高(代价大)。或使用软件来提高分辨率，即用高分辨率计算，用低分辨率显示(代价小).

B反走样线段方法：将位于相邻台阶之间的象素置为过渡颜色或灰度，使得颜色或灰度自然过渡，变化柔和，这样线段看起来就显得平直了，从而可消除台阶效应。

C反走样多边形边界算法：根据象素与多边形相交部分的面积来设置象素的亮度，这样能够明显减少多边形边界上的台阶现象。

第五章 1图形变换：

定义：对图形的几何信息经过几何变换后产生新的图形。

对于线框图的变换，通常以点变换作为基础，把图形的一系列顶点作几何变换，连接新的顶点系列即可产生新的图形.

对于用参数方程描述的图形，可以通过参数方程作几何变换，实现对图形的变换. 2平移变换

平移是一物体从一个位置到另一个位置所作的直线移动。 P’=P+T

3比例变换

用来改变一物体大小的变换，也称为缩放变换。 P’=S*P

4旋转变换

物体上的各点绕一固定点沿圆周路径作转动称为旋转变换。 P’=R *P

5齐次坐标技术的引入原因

平移变换的处理方法与其他两种变换的形式不一样，希望能够用一种一致的或同类的方法来处理这3

种变换，使得这3种基本变换能很容易地结合在一起，形成各种复杂的组合变换。 6齐次坐标：

基本思想：把一个n维空间的几何问题，转换到n＋1维空间中去解决。

形式：用一个有n＋1个分量的向量去表示一个有n个分量的向量的方法。如二维平面上的点(x，y)的齐次坐标表示为( hx，hy ，h)，h是任一不为0的比例系数。

规格化齐次坐标：齐次坐标表示不是唯一的，通常将h＝1时的齐次坐标称为规格化的齐次坐标。 7齐次坐标表示法在计算机图形处理中的优越性

（1）将平移、旋转、缩放3种变换用统一的方式（矩阵乘积）表达。提供了用矩阵运算将二维、三维或更高维空间中的一个点集从一个坐标系变换到另一个坐标系的有效方法。

（2）可以表示无穷远点。 8几何变换的齐次坐标表示

由于齐次坐标表示的点是用3个分量的行向量来表示的，这样变换矩阵也必须是3×3的矩阵，以便于矩阵相乘，当然变换后得到的点也是有3个分量的齐次坐标。

8.1平移变换

8.2比例变换

8.4反射变换

用来产生物体的镜像。

8.3旋转变换

?x*??ab0??x??ax?by?????????y*?de0y?dx?ey???????? ?1??001??1??1?????????当a=-1, e=1时，与y轴对称的反射变换。 当a=1, e=-1时，与x轴对称的反射变换。 当a=e=-1时，与原点对称的反射变换。 当b=d=1 时，与y=x对称的反射变换。 当b=d=-1时，与y=-x对称的反射变换。

8.5错切变换

使物体产生变形，即物体产生扭转。错切的角度为?，令shx＝tan ?。错切变换引起图形角度关系的改变，甚至导致图形发生变形。

?x*??1b0??x??x?by?????????y*?d10y?dx?y???????? ?1??001??1??1?????????1) 当d=0时，图形的y坐标不变；

当b>0：图形沿+x方向作错切位移。 当b<0：图形沿-x方向作错切位移。

2)当b=0时， 图形的x坐标不变；

当d>0：图形沿+y方向作错切位移。 当d<0：图形沿-y方向作错切位移。

3) 当b?0且d?0时，图形沿x, y两个方向作错切位移。 9二维几何变换的一般形式(仿射变换)

X’=AX+BY+C Y’=DX+EY+F

?x*??ab????y*???de?1??00???10二维变换矩阵

c??x????f??y?

?1????1?c??f? i??T2D?a???d?g?beh?ab???：对图形进行缩放、旋转、堆成、错切 de???c???：平移 ?f?（G H）： 投影

（I）：图形整体伸缩（I>1缩小，I<1放大） 11组合变换

任意一个变换序列均可表示为一个组合变换矩阵。由若干基本变换矩阵相乘求得组合变换矩阵的方法称为矩阵的级联。

（1） 组合平移变换：进行连续两次平移，实际上是把平移距离相加。

（2） 组合比例变换：连续进行两次比例变换，实际上是把相应的比例因子相乘。

（3） 组合旋转变换: 连续旋转实际是把旋转角相加。 R(θ2)*R(θ1)= R(θ1+θ2) 12多个基本变换的组合变换

（1） 相对于任一固定点的比例变换

由基本平移变换矩阵及比例变换矩阵，可得到相对于任一固定点A（xA,yA）的比例运算的组合矩阵。此时实际上是进行由三个基本变换形成的一个变换序列。 1）把图形及固定点一起平移，使固定点移到坐标原点上； 2）把图形相对于原点进行比例变换

3）把图形及固定点一起平移，使固定点又回到原来位置。

（2） 围绕任一基准点的旋转变换

1）把物体平移，使基准点与坐标原点重合。 2）把物体绕原点旋转。

3）把物体平移，使基准点回到原来位置

（3） 关于任意轴的对称变换

1）平移使l过坐标原点，记变换为T1，图形A被变换到A1 2）旋转?角，使l和ox轴重合，记变换为R1，图形A1被变换到A2 3）求图形A关于x轴的对称图形A3，记变换为RFx 4）旋转-?角，记变换为R2，图形A3被变换到A4

5）平移使l回到其原先的位置，记变换为T2，图形A4被变换到A5，A5即为A关于l的对称图形。

*13 三维变换

三维图形的平移、比例及旋转变换是对二维变换的扩展，即三维情况下应附加考虑z坐标的变换。对于三维空间点需要用4个数来表示，而相应的变换矩阵是4×4阶矩阵。 左手坐标系、右手坐标系 3*3比例旋转、3*1平移

*14 窗口和视图

（1） 用户区 ：程序员用来定义草图的整个自然空间

（2） 窗口区：用户指定的任一区域。窗口区小于或等于用户域. （3） 屏幕域：设备输出图形的最大区域，如显示器分辨率。

（4） 视图区：任何小于或等于屏幕域的区域。视图区用设备坐标定义在屏幕域中。窗口区显示在视图

区，需做窗口区到视图区的坐标转换。

第六章

1 曲线的表示形式

（1）显式表示，Y=F(X)，特点：不能表示封闭或多值曲线

（2）隐式表示，F(X,Y)=0，特点：与坐标轴相关；会出现斜率为无穷大的情况；不便于计算和编程。 （3）参数表示：X=X(T)，Y=Y(T),T属于(0,1) 矢量形式为：

p(t)?[x(t) y(t)]

2参数表示优点

A有更大的自由度来控制曲线、曲面的形状。

B对非参数方程表示的曲线、曲面进行变换，必须对曲线、曲面上的每一个型值点进行几何变换，而对参数曲线、曲面可对其参数方程直接进行几何变换，节省计算量。

C便于处理斜率为无穷大的问题，不会因此中断计算。

D参数方程中，代数、几何相关和无关的变量是完全分离的，且对变量个数不限，便于将低维空间扩展到高维空间。

E参数变量定义了几何分量的界限。

F易于用矢量和矩阵表示几何分量，简化了计算。 3插值

给定函数f(x)在区间[a,b]中互异的n个点的值f(xi) i=1,2,?,n，基于这个列表数据，寻找一个函数g(x)去逼近f(x)。若要求g(x)在xi处与f(x)相等，就称这样的函数逼近问题为插值。称g(x)为f(x)的插值函数。xi为插值节点。

（1） 线性插值

设给定函数f(x)在两个不同点x1和x2的值，y1=f(x1)，y2=f(x2)，要求用一个线性函数： Y=AX+B近似代替y=f(x)。（Y的表达式：点斜式/两点式） （2） 抛物线插值

又称二次插值。设已知f(x)在三个互异点x1、x2、x3的函数值为y1、y2、y3，要求构造一个函数：Y=AX2+BX+C，使其在节点xi处与f(x)在xi处的值相等。 4插值

当型值点太多时，构造插值函数使其通过所有的型值点相当困难。选择一个次数较低的函数，在某种意义上最佳逼近这些型值点。

假设已知一组型值点(xi,yi)（i=1,2,?,n)，要求构造一个m(m

其中关键是确定出F(x)系数aj，使偏差平方和达到极小。这里有m+1个方程，可解出m+1个未知数

a0,a1,?,am，代入定义即可求得多项式函数F(x)逼近已知的n个型值点。

5光顺、拟合

光顺是指曲线的拐点不能太多，对平面曲线而言，相对光顺的条件是：具有二阶几何连续(G2)、不存在多余拐点和奇异点、曲率变化较小。

拟合指的是曲线、曲面的设计过程中，用插值或逼近方法是生成的曲线、曲面达到某些设计要求。 6参数曲线的代数形式和几何形式 （1）代数形式

x(t)?a3xt3?a2xt2?a1xt?a0xy(t)?a3yt3?a2yt2?a1yt?a0y t?[0,1]; z(t)?a3zt3?a2zt2?a1zt?a0z（2）几何形式

对曲线两端点，P0=A0,P(1)=A0+A1+A2+A3,P(0)’=A0, P(1)’=A1+A2+A3

解得A0~A3，代入有P(t)=F1P0+F2P1+F3P0’+F4P1’，P0~P1’为几何系数，F1~F4为调和函数。

F1?2t3?3t2?1,F2??2t3?3t2,F3?t3?2t2?t,F4?t3?t2

7 Bezier曲线

Bezier曲线由一组折线（Bezier特征多边形）定义，曲线的起点和终点与该多边形的起点和终点重合，

且多边形的第一条边和最后一条边表示了曲线在起点和终点处的切矢量方向。曲线的形状趋于特征多边形的形状。.

调和函数的性质：正性、权性、对称性、递归性 曲线的性质：

（1）对称性——保持顶点Pi的位置不变，将其次序颠倒过来，则新的Bezier曲线形状不变，只是走向相反。

（2）凸包性——曲线上各点均落在Bezier特征多边形构成的凸包内。 （3）几何不变性——曲线的几何特征不随一定的坐标变换而变化性质。 缺点：

（1）特征多边形顶点个数决定了Bezier曲线的阶次，并且当n较大时，特征多边形对曲线的控制将会减弱。

（2）Bezier曲线不能作局部修改，即改变某一个控制点的位置对整个曲线都有影响。 *8 B样条曲线

由空间的n+1个控制点生成的k阶B样条曲线是由L段B样条曲线逼近而成，每个曲线段的形状仅由点列中的k个顺序排列的点所控制。

由不同节点矢量构成的均匀B样条函数所描绘的形状相同，可以看成是同一个B样条函数的简单平移。性质：局部性、连续性、几何不变性（曲线的形状和位置与坐标系的选择无关）、变差缩小性（平面内任一直线与曲线的交点不多于和外接多边形的交点）、造型灵活性

梁友栋-Barsky裁剪算法

Cyrus和Beck用参数化方法提出了比Cohen-Sutherland更有效的算法。后来梁友栋和Barsky独立地提出了更快的参数化线段裁剪算法，也称为Liany-Barsky（LB）算法。

一、梁友栋-Barsky裁剪算法思想：

我们知道，一条两端点为P1（x1，y1）、P2（x2，y2）的线段可以用参数方程形式表示：

x= x1+ u·（x2-x1）= x1+ u·Δx 0≤u

y= y1+ u·（y2-y1）= y1+ u·Δy ≤ 1

（1）

式中，Δx=x2-x1，Δy=y2-y1，参数u在0～1之间取值，P（x，y）代表了该线段上的一个点，其值由参数u确定，由公式可知，当u=0时，该点为P1（x1，y1），当u=1时，该点为P2（x2，y2）。如果点P（x，y）位于由坐标（xmin，ymin）和（xmax，ymax）所确定的窗口内，那么下式成立：

xmin≤x1+ u·Δx≤xmax ymin≤y1+ u·Δy≤ymax （2）

这四个不等式可以表示为： u·pk ≤qk ， k=1，2，3，4 （3）

其中，p、q定义为：

p1=-Δx， q1=x1-xmin p2= Δx， q2=xmax-x1 p3=-Δy， q3=y1-ymin p4= Δy， q4=ymax-y1

从（4）式可以知道：任何平行于窗口某边界的直线，其pk=0，k值对应于相应的边界（k=1，2，3，4对应于左、右、下、上边界）。如果还满足qk<0，则线段完全在边界外，应舍弃该线段。如果pk=0并且qk

4） （

≥0，则线段平行于窗口某边界并在窗口内，见图中所示。公式（4）式还告诉我们：

1、当pk<0时，线段从裁剪边界延长线的外部延伸到内部； 2、当pk>0时，线段从裁剪边界延长线的内部延伸到外部；

例如，当Δx≥0时，对于左边界p1<0（p1=-Δx），线段从左边界的外部到内部； 对于右边界p2>0（p2=Δx），线段从右边界的内部到外部。 当Δy<0时，对于下边界p3>0（p3=-Δy），线段从下边界的内部到外部； 当pK

对于每条直线，可以计算出参数u1和u2，该值定义了位于窗口内的线段部分：

1、u1的值由线段从外到内遇到的矩形边界所决定（pk<0），对这些边界计算rk=qk/pk，u1取0和各个r值之中的最大值。

2、u2的值由线段从内到外遇到的矩形边界所决定（pk>0），对这些边界计算rk=qk/pk，u2取0和各个r值之中的最小值。

3、如果u1>u2，则线段完全落在裁剪窗口之外，应当被舍弃；否则，被裁剪线段的端点可以由u1和u2计算出来。

二、梁友栋-Barsky裁剪算法实现：

1、初始化线段交点的参数：u1=0，u2=1； 2、计算出各个裁剪边界的p、q值；

3、根据p、q来判断：是舍弃线段还是改变交点的参数。

（1） 当p<0时，参数r用于更新u1； （u1=max{u1，?，rk}） （2） 当p>0时，参数r用于更新u2。 （u2=min{u2，?，rk}） （3）如果更新了u1或u2后，使u1>u2，则舍弃该线段。

（4）当p=0且q<0时，因为线段平行于边界并且位于边界之外，则舍弃该线段。见下图所示。

u = qk/pk （5）

伸的窗口边界k的交点，即：

对于上边界p4<0（p4=Δy），线段从上边界的外部到内部。 ≠0时，可以计算出参数u的值，它对应于无限延伸的直线与延

4、p、q的四个值经判断后，如果该线段未被舍弃，则裁剪线段的端点坐标由参数u1和u2的值决定。

三、算法代码

bool_rtPruneLB(RtVector& vector, RtRect rect) {

RtVector dest; boolflag =false; floatu1 = 0, u2 =1; intp[4], q[4];

floatr;

p[0] = vector.sp.x - vector.ep.x; p[1] = vector.ep.x - vector.sp.x; p[2] = vector.sp.y - vector.ep.y; p[3] = -vector.sp.y + vector.ep.y;

q[0] = vector.sp.x - rect.x;

q[1] = rect.x + rect.w - vector.sp.x; q[2] = vector.sp.y - rect.y;

q[3] = rect.y + rect.h - vector.sp.y; for(inti = 0; i < 4; i++) {

r = (float)q[i] / (float)p[i]; if(p[i] < 0) {

u1 = max(u1,r); if(u1 > u2) {

flag =true; } }

if(p[i] > 0) {

u2 = min(u2, r); if(u1 > u2) {

flag =true; } }

if(p[i] == 0 && p[i] < 0) {

flag =true; } }

if( flag ) {

return; }

dest.sp.x = vector.sp.x - u1 *(vector.sp.x - vector.ep.x); dest.sp.y = vector.sp.y - u1 *(vector.sp.y - vector.ep.y); dest.ep.x = vector.sp.x - u2 *(vector.sp.x - vector.ep.x); dest.ep.y = vector.sp.y - u2 *(vector.sp.y - vector.ep.y); vector =dest; }

本文来源：https://www.bwwdw.com/article/uti.html