计算机图形学考试要点（卷一）
第一章 计算机图形学概论
计算机图形学与相关学科的定义
计算机图形学是研究怎样用数字计算产生、处理和显示图形的一门新兴学科
图形处理：将客观世界中原来存在的屋里映像处理成新的数字化图形
图像处理关心的问题：滤去噪声、压缩图像数据、对比度增强、图像复原、三维图像重建
模式识别：研究怎样分析和识别输入的图像，，找出其中蕴含的内在联系和抽象模型
计算机图形学的应用领域
图像用户界面 CAD/CAM 可视化
地理信息系统 多媒体 娱乐
计算机艺术
Ps:造型技术、真实图形生成技术人机交互技术
第二章 图形系统
图形输入设备的逻辑分类（6类）
定位：输入一个点坐标 笔画：输入一系列点坐标
数值：输入一个数据
选择：给应用程序返回一个整数值，实现某种选择 拾取：拾取一个显示着的图元 字符串：输入一串字符
帧缓存的用途
光栅扫描显示器是一种画点设备，当前显示的图形信息是存
放在帧缓存中。
屏幕上的像素点和帧缓存中的存储单元之间具有一一对应的关系，所以帧缓存的单元数至少等于当前分辨率下的屏幕象素总和
第三章 二维图形生成技术
自由曲线（相关概念，绘制方法）
规则曲线——可用曲线方程式表示的曲线。
不规则曲线——不能确切给出描述整个曲线的方程，而是由从实际测量中得到的一系列离散数据点采用曲线拟合的方法来逼近的。这类曲线也称之为自由曲线 插值和逼近：这是曲线设计中的两种不同
二次B样条曲线的连续性分析：分析为何连接点处一阶导数连续
二次B样条曲线
二次B样条曲线的矩阵表示形式如下：
1 －2 1 P0 Q(t)＝[t2 t 1] －2 2 0 P1 1 1 0 P2 分解后的参数式为： x (t)＝ axt2 ＋bxt＋ cx y (t)＝ ayt2 ＋byt＋ cy
式中系数分别为：
ax＝(x0－2x1＋x2)／2 bx＝x1－x0 cx＝(x0＋x1)／2 ay＝(y0－2y1＋y2)／2 by＝y1－y0 由三个控制顶点(P0、P1、P2)确定 的一条二次B样条曲线是一条抛物线， 如果再增加一个控制顶点P3，就可由 P1、P2、P3三个控制顶点生成第二条 二次B样条曲线。 由于第一条二次B样
条曲线的终点就是第二条二次B样条 曲线的起点，而且它们有一条公共的 切线P1P2，所以二条二次B样条曲线在 切点衔接处达到C1连续。
种子填充法
4连通区域递归填充算法
Void fill （int x,int y,int bcolor,int ncolor） {
Int color;
Color=getpixel(x,y);
If((color!=bcolor)&&(color!=ncolor))
{
Putpixel(x,y,ncolor); Fill(x,y+1,ncolor); Fill(x,y-1,ncolor); Fill(x-1,y,ncolor); Fill(x+1,y,ncolor); } }
堆栈实现4连通区域的填充法
初始化：将算法设置的堆栈置为空
设置种子象素（x,y）及填充颜色（ncolor）
cy＝(y0＋y1)／2
Putpixel(x,y,ncolor); Pushstack(x,y); While(栈为非空)
{
访问栈顶元素；
If(在填充区域内，栈顶元素存在未被填充的邻接象素)
{
取其中一个邻接象素（x,y）; Putpixel(x,y,ncolor) Pushstack(x,y);
} Else
Popstack(栈顶元素) }
第四章 图形的几何变换和裁剪
常用坐标系（4种，何种情况下用）
世界坐标系：为了描述被处理的对象，要在对象所在的空间中定义一个坐标系 观察坐标系：产生三维物体的视图，必须贵点观察点和观察方向
设备坐标系：与设备相关连的坐标系 规格化设备坐标系：为了是图形处理过程做到与设备无关，通常采用一种虚拟设备的方法来处理
二维几何变换（基本变换矩阵，性质）
采用齐次坐标可将二维图形变换表示成如下形式：
a b 0 [ x* y *1 ]=[ x y 1 ] c d 0 l m 1
P* = P ? M
二维变换矩阵中：
a b 是对图形进行缩放、旋转、对称、错切 c d
[ l m] 是对图形进行平移变换
x' = ax y' = dy
其中a，d分别为x，y方向上的比例因子(a，d>0)。讨论： ⑴ 若a = d = 1, 为恒等变换，即变换后点的坐标不变。
⑵若a = d≠1，则为等比变换，变换结果是图形等比例放大（a = d >1）或等比例缩小（a = d <1）
点对X轴对称应有：X'=X，Y' = –Y，(a=1,d=-1) 点对Y轴对称应有：X' = –X，Y' = Y ,(a=-1,d=1)
点对坐标原点对称变换应有：X' = –X，Y' = –Y(a=d=-1)
点对45°线的对称变换即让X、Y互换坐标，X' = Y，Y' = X， 对–45°线的对称变换，应有X' = –Y，Y' = –X.
(1)令b = 0，沿X向错切的变换矩阵为： 1 0 0 C 1 0
0 0 1 (2)令c=0，沿Y向错切的变换矩阵为： 1 d 0 0 1 0
0 0 1
假定图形的旋转是指绕坐标原点旋转θ角，且逆时针为正，顺时针为负，变换矩阵为
cos??sin?
sin?cos?0001
0平移变换矩阵为：1 0 0 x’=x+l,y’=y+m
0 1 0
L m 1
平面图形绕任意点P（Xp,Yp)旋转α角，需要通过以下几个步骤来实现：
① 将旋转中心平移到原点
② 将图形绕坐标系原点旋转α角 ③ 将旋转中心平移回到原点的位置
对任意直线的对称变换（直线方程为 Ax + By + C = 0）
直线在X轴和Y轴上的截距分别为–C/A和–C/B，直线与X轴的夹角为α，α =arctg(–A/B)
cos2α sin2α 0 T =T1×T2×T3×T4×T5= sin2α －cos2α 0 (cos2α-1)C/A sin2α*C/A 1
三维级联变换（基本变换矩阵，级联变换方法）
二维线段裁剪的编码裁剪算法之分区编码（目的方法）
分区编码方法：
以x=xL、x=xR、y=yT、y=yB将图形 区域划分成九个部分。采用四位编码表 示端点所处的位置：
第一位为“1”时，表示点在y=yT的上方； 1001 1000 1010 第三位为“1”时，表示点在x=xR的右方； 0001 0000 0010 第四位为“1”时，表示点在x=xL的左方。 0101 0100 0110
算法思想：
1．确定线段二端点P1和P2的代码值C1和C2（经一系列的判 断—— p1（x1，y1），p2（x2，y2）和xR、xL、yT、yB的比较，分别给代码中的各位赋值）。
2．对线段的端点进行检测
若线段全部在窗口外(c1 and c2≠ 0)——退出 若线段全部在窗口内(c1= 0 且c2 = 0)——画线
否则(c1≠0 or c2≠0 且 c1 and c2 = 0)要对线段进行分割，关键是求与窗口四边的交点( 利用直线的两点式方程 )。交点求出后，要对其重新编码，并继续判断
多边形的weiler_Atherton（双边裁剪）算法
W-A算法可以用一个有内孔的凹多边形去裁剪另一个也有内孔的凹多边形。 被裁剪的多边形——主多边形 裁剪区域——裁剪多边形
思路：主多边形和裁剪多边形均用它们的顶点表来定义。
各多边形的外部边界取顺时针方向，而其内部边界或孔取逆时针方向。
主多边形和裁剪多边形的边界若相交，交点必定成对地出现，其中一个交点为主多边形边进入裁剪多边形内部时的交点（称进点），另一个交点则为离开时的交点（称出点）。 这两类交点分别用进点表和出点表来存放。
算法：
分别建立主多边形和裁剪多边形的顶点表
求出主多边形与裁剪多边形的交点（进点和出点）并分别建立进点表和出点表 将交点加入各顶点表中 if 进点表为空 then finish 1 取一进点作为始点
2 跟踪主多边形顶点表，直至发现下一交点，复制这一段主多边形顶点到内表中 根据交点处指针，转到裁剪多边形顶点表中的相应位置跟踪裁剪多边形顶点表，直至发现下一交点，复制这一段裁剪多边形顶点到内表中。 if 该交点不是起始点 then 2
if 进点表中还有未遍历到的交点 then 1 3 finish
第六章
边界表示法
边界表示法是通过描述物体的边界来表示一个实体。
实体的边界面可以是平面多边形或曲面，通常情况下，曲 面最终都是被近似地离散成多边形来处理的。
设简单平面多面体的顶点数、 棱边数和面数分别用V 、 E 、 F来 表示，则:
V － E + F = 2
对于非简单多面体则应满足广义欧拉公式： V － E + F － H = 2( C － G ) 其中 V 、E 、F 的含义与前相同； H 表示多面体表面上孔的个数； C 表示独立的不相连接的多面体的个数； G 表示贯穿多面体的孔的个数
第七章 三维形体输出流水线 投影的分类与分类依据
透视投影（相关定义，概念，生成方法）
设投影中心在坐标原点，投影面与 Z 轴垂直，在 z = d 的 位置。点 P( x, y, z )在投影面上的投影为 P' ( xp, yp, d )。\\ Xp=X/z*d, Yp=Y/z*d 可知：
① 透视坐标与 z 值成反比，即 z 值越大，其透视坐标值 越小。符合近大远小的视觉效果。
② d 的取值不同，可对形成的透视投影图起放大和缩小的 作用。
观察空间的定义方法
观察空间
目的：为方便于观察某一部分景物或物体上的某一个部分，并通过投影的方式把它们表示出来。
相似：照相时的选景，并在底片上成像。
1. 观察坐标系 2. 观察空间 3. 观察空间的参数
第八章 消隐技术 重叠测试
重叠测试：
测试两个空间多边形的投影是否重叠，若重叠，则可能存 在遮挡关系；若不重叠，则不存在遮挡关系。 测试方法：用包围框方法来测试。 扫描线消隐算法的数据结构
桶 ─ 源于 Knuth 的 bucket sort。
用于存放按照一定的规则（顺序）排列的若干组数据或处
理对象。
通常情况下，桶是采用向量形式和链表形式结合起来构造成的一种特定的数据结构。
提高扫描线消隐算法的效率需要解决的问题与解决办法
为提高算法的效率，需解决几个问题： ① 如何建立扫描线与多边形投影之间的关系；
② 如何建立扫描线与多边形边投影之间的关系； ③ 如何突出边对信息；
④ 如何方便地计算边对中各像素点处的相关坐标 第九章
多边形明亮处理的Gouraud方法和Phong方法
① 计算多边形各顶点的法矢量
取该顶点各相邻多边形法矢量的平均值。 ② 计算多边形各顶点的辉度值
利用前述的phong模型公式，分别计算出I1、 I2 、I3、 I4 。 ③ 采用线性插值方法，计算出Ia 和 Ib
Ia= [I1(Ys-Y2)+I2(Y1-Y2)] / (Y1-Y2) ` Ib=[I1(Ys-Y4)+I4(Y1-Ys)] / (Y1-Y4) ④ 采用线性插值方法，计算出Is
Is=[Ia(Xb-Xs)+Ib(Xs-Xa)] / Xb-Xa
当扫描线 ys 由 j 变成 j+1时， Ia 和 Ib 的增量分别为△ Ia和 △ Ib ，则：
Ia，j+1=Ia，j + △ Ia Ib，j+1=Ia，j + △ Ib 其中
△Ia=I1-I2 / Y1-Y2
△Ib=I1-I4 / Y1-Y4
当 xs 由 i 增为 i+1 时
Is，i+1= Is，i + △ IS
其中：
△Is= Ib-Ia / Xb-Xa①
Phong方法(双线性法向量插值法) phong方法的思想是对离散的法向量采样并作双线性插值，构造一个连续的法向量函数。
计算多边形各顶点的法矢量；
② 采用线性插值方 计算出当前扫描线与多边形交点处的法矢量 Na 和 Nb ； ③ 采用线性插值方法，计算出Ns ；
④ 由Ns计算出象素点S处的辉度值 Is ； ⑤ 线性插值的计算可采用前述的增量法