计算机图形学期末复习提纲#

By 陈浩杰 注：计算机学院学长整理

---

题型#

题型	分值
单选 15 题（其中 5 题关于程序设计）	15×2 = 30 分
填空 10 题	10×2 = 20 分
判断 5 题	5×2 = 10 分
大题 4 题	4×10 = 40 分

---

一、大题#

1. 中点画线算法#

第三章中点画线算法的推导过程。判别式怎么得到，判别式的初值是怎么得到的。

2. 中点画圆算法#

中点画圆算法的推导过程。

3. 多边形填充算法#

多边形填充算法中基于改进的边表填充算法的计算过程。活动边等，要会写边表和对应某一条扫描线的 AET 表。

4. 图形几何变换#

第四章图形几何变换中二维图形相对某一条任意直线的对称变换，三维相对于任意点的缩放变换。写变换矩阵或端点坐标，用齐次坐标形式。

5. 裁剪算法#

用 LB 算法对直线段的裁剪过程（参数化直线裁剪算法对直线段进行裁剪）；多边形的 SH 逐边裁剪算法。

6. Phong 明暗度模型#

第八章明暗度处理模型中 Phong 明暗度模型的计算过程，即双线性法向插值步骤，三步，每一步的计算公式。

---

二、知识点#

1. 图形学的三个基本任务#

表示、绘制、交互。

2. 图形学和其相关学科的关系#

相互渗透，相互交叉。

3. 图形学的应用领域#

• 计算机辅助设计与制造 CAD/CAM
• 科学计算可视化
• 虚拟现实
• 动画

4. 计算机图形学之父#

伊凡·苏泽兰（Ivan E. Sutherland），美国人。

5. 输入设备#

鼠标、键盘、光笔、跟踪球、空间球、操纵杆、触摸屏、数字化仪、数据手套、Kinect、扫描仪、声频输入系统、视频输入系统。

6. 输出设备#

显示器、绘图仪、打印机、录像带。

7. 图形流水线三个阶段#

应用程序阶段 → 几何处理阶段 → 像素处理（光栅）阶段。

8. 彩色图形的显示原理#

CRT：是一种真空器件，利用电磁场产生高速的、经过聚焦的电子束，偏转到屏幕的不同位置轰击屏幕表面的荧光材料而产生可见图形。

液晶：是一种介于液体和固体之间的特殊物质，具有液体的流态性质和固体的光学性质，受到电压影响时物理性质改变导致形变，光的折射角度变化从而产生色彩。

9. 三种图像显示方式#

随机扫描显示：电子束的定位和偏转具有随机性，扫描轨迹随显示内容而变化，只在需要的地方扫描。不能显示逼真场景，与电视标准不一致，驱动系统较复杂。本质是按显示命令的任意顺序将电子束从一个端点偏转到另一个端点。

直视存储管式显示：一条线一旦画在屏幕上，在一小时之内都将是可见的。无需刷新；很复杂的图形都可以在极高的分辨率下无闪烁地显示；成本较低；不能显示彩色；不能局部修改；擦除和重画过程可能持续较长时间。

光栅扫描显示：控制电子束按某种光栅形状进行顺序扫描，字符、图像靠 Z 轴信号控制辉亮来形成。是画点设备，可看作点阵单元发生器，可控制每个点阵单元的亮度。具有对显示区域填充颜色或图案的能力，存储的图像更加易于操作。

10. 帧缓存大小计算#

帧缓存大小 = 分辨率 × 位面数（颜色数）。

11. 种子填充算法#

种子填充算法的基本思想和适用范围，简单的种子填充算法和扫描线种子填充算法的基本原理。

• 简单的种子填充：适合已经存在边界的区域，借助像素连通性遍历。
• 扫描线种子填充算法：批量处理，适用于较大面积填充。

12. 多边形包含性测试#

射线法：从点 P 向任意方向发出一条射线，若与多边形交点个数为奇数则 P 在多边形内，偶数则在外。

当射线正好通过多边形某顶点时，分两种情况：

• 与顶点连接的两条边全部位于射线一侧（极值点）：计两个交点
• 两条边分别位于射线两侧（非极值点/奇异点）：只计一个交点

弧长法：假定多边形由有向边组成。以被测点为圆心作单位圆，将全部有向边向单位圆作径向投影，计算单位圆上各边投影辐角的代数和。

• 代数和为 0：被测点在多边形之外
• 代数和为 $2\pi$：被测点在多边形之内

13. 字符#

• 点阵字符：每个字符由一个点阵位图来表示（用像素点拼出来的字符）。
• 矢量字符：采用直线和曲线段来描述字符形状，字符库中记录的是笔划信息。

14. 走样与反走样#

• 走样：用离散量表示连续量引起的失真现象。
• 反走样：用于减少或消除走样的技术。

15. 走样表示的三种形式#

1. 倾斜的直线和区域的边界处呈现阶梯状、锯齿状的效果。
2. 图形细节失真：应均匀间隔的纹理图案，由于离散像素的四舍五入，造成不均匀的间隔显示。
3. 一些非常细的线或很小的点由于低于分辨率而不能被显示出来。

16. 常用的反走样技术#

超采样方法、线段反走样技术、多边形反走样算法。

17. 基本的几何变换#

基本的几何变换都是相对于坐标原点和坐标轴进行的。

18. 齐次坐标#

概念：用 $n+1$ 维向量表示 $n$ 维向量。

优点：

1. 将各种变换用阶数统一的矩阵来表示，提供了用矩阵运算把二维、三维甚至高维空间上的一个点从一个坐标系变换到另一坐标系的有效方法。
2. 便于表示无穷远点。例如：普通坐标 = 齐次坐标 ÷ $h$。
3. 变换具有统一表示形式，便于变换合成，便于硬件实现。

19. 齐次坐标下二维几何变换矩阵#

会应用以下变换：

• 平移
• 旋转
• 缩放
• 整体比例变换
• X 轴对称
• Y 轴对称
• 原点对称
• $y=x$ 轴对称
• $y=-x$ 轴对称

20. 三维变换#

三维暂时跳过，等看大题再说。

21. 图形几何变换模式#

固定坐标系模式：图形改变，坐标系不变。矩阵合并时，先调用的矩阵放在右边，后调用的放在左边。在绘图的情况下多用固定坐标系模式，因为用户比较容易估计变换后的结果。

活动坐标系模式：图形不变，坐标系改变。矩阵合并时，先调用的放在左边，后调用的放在右边。整体变换的基础上再作一些较独立的局部变换时，常用活动坐标系模式。

22. 视口变换#

见 PPT。

23. Cohen-Sutherland（C-S）编码裁剪算法#

对每条直线段 $p_1(x_1,y_1)$、$p_2(x_2,y_2)$ 分三种情况处理：

1. 直线段完全可见，“简取”之。
2. 直线段显然不可见，“简弃”之。
3. 直线段既不满足”取”的条件，也不满足”弃”的条件，则把直线分割为两段，其中一段完全在窗口外，弃之；直线段更新为另一段。
4. 重复上述处理，直到满足 1 或 2。

24. 投影#

平行投影：

• 正平行投影：

  • 正投影（三视图）：主视图、俯视图、左（侧）视图。
  • 正轴测投影：
    • 正等测：观察平面与三个坐标轴之间的夹角都相等。
    • 正二测：观察平面与两个坐标轴之间夹角相等。
    • 正三测：观察平面与三个坐标轴之间夹角都不相等。

• 斜平行投影：将三维形体向一个单一的投影面作平行投影，但投影方向不垂直于投影面。

  • 斜等测：投影方向与投影面成 45°（$\arctan 1$）。与投影面垂直的直线段投影长度不变。
  • 斜二测：投影方向与投影面成 $\arctan 2$。与投影面垂直的直线段投影长度为原来的一半。

透视投影：所有投影线都从空间一点射出，离视点近的物体投影大，离视点远的投影小。透视投影的深度感更强，更加具有真实感，但透视投影不能够准确反映物体的大小和形状。透视投影的大小与物体到投影中心的距离有关。不平行于投影面的平行线的投影会汇聚到一个点（灭点），坐标轴方向的平行线在投影面上形成的灭点称作主灭点。

• 一点透视：有一个主灭点，投影面与一个坐标轴正交，与另外两个坐标轴平行。
• 二点透视：有两个主灭点，投影面与两个坐标轴相交，与另一个坐标轴平行。
• 三点透视：有三个主灭点，投影面与三个坐标轴都相交。

25. 三维几何物体的拓扑关系#

点→点、点→边、点→面、边→点、边→边、边→面、面→点、面→边、面→面。A→B 意思是从 A 能找到相邻的 B。

26. 有效实体具有的性质#

1. 刚性：一个实体必须有不变的形状。
2. 具有封闭的边界：根据其边界可将空间分为外部和内部两部分。
3. 内部连通。
4. 占据有限的空间。
5. 经过集合运算后，仍然是有效的实体。

27. 三维实体的表示方法#

边界表示：描述实体的边界来表示实体，记录点、边、面的拓扑关系。

优点：

1. 能够显式地表示形体边界，绘制时能快速计算法向和光照效果，算法简单。
2. 在不改变拓扑关系的前提下便于局部几何变换。
3. 可用欧拉公式来判断实体的有效正则性。
4. 便于多个形体做并、交、差等几何运算。

扫描表示法：将空间中的一个点、一条边或一个面沿某一路径扫描，用得到的扫描轨迹表示三维物体。

构造实体几何表示（CSG）：由简单实体（又称体素）间的集合运算（并、交或差）操作生成新的实体。

优点：

1. 输入方便，可直观地构造复杂形体。
2. 数据结构简单，数据量小，用一棵二叉树即可表示。
3. 形体的有效性可由实体集合运算得以自动保证。

缺点：

1. 集合运算的中间结果难以用简单的代数方程表示，求交困难。
2. CSG 法中集合运算会破坏原有的点、边、面的显式拓扑关系。
3. CSG 法的体素只是有限的几种形状，对体素不能做局部变形操作，使 CSG 的表示能力受到限制。

空间细分表示：包括体素表示法、八叉树表示法等。

优点：

1. 物体之间的集合运算（并、交、差）在八叉树表示中具有十分简单的形式。
2. 只需要同时遍历参加集合运算的两物体相应的八叉树，就可以获得拼合体的八叉树，而无需进行复杂的求交运算。
3. 很容易计算实体的整体性质，如质量、体积等。
4. 容易实现隐藏线和隐藏面的消除。
5. 易于检查实体间的碰撞、距离关系。

缺点：

1. 所需要的存储容量较大，存在大量冗余编码。
2. 不能精确地表示一个实体。
3. 几何变换也比较困难。

28. 消隐#

消除隐藏线或者隐藏面的过程叫做消隐。

29. 消隐算法按空间分类#

对象空间消隐算法：三维空间中，比较两两物体的面的遮挡关系。空间有 $k$ 个物体，算法复杂度为 $O(k^2)$。

图像空间消隐算法：投影到二维平面上，确定每个像素点的颜色，哪个物体离观察者最近就用该物体的颜色。空间有 $k$ 个物体，屏幕分辨率为 $m \times n$，算法复杂度为 $O(k \times m \times n)$。

30. 消隐的基本原则#

1. 排序：各景物表面按照距离视点远近排序的结果，用于确定消隐对象之间的遮挡关系。
2. 连贯性：所考察的物体或视区内的图像局部保持不变的一种性质，用于提高排序效率。
3. 不能处理相互贯穿或循环遮挡的物体，此时应做特殊处理。

31. 深度缓冲器算法（Z-Buffer 算法）#

图像空间消隐算法。将投影平面每个像素所对应的所有面片的深度进行比较，然后取离视线最近面片的属性值作为该像素的属性值。

优点：

1. 算法复杂度 $O(n \times N)$：对于给定的图像空间，$N$ 是固定的，算法复杂度只会随着场景的复杂度线性增加。
2. 无须排序：场景中的物体按任意顺序写入帧缓冲器和 Z 缓冲器，无须对物体进行排序，节省排序时间。
3. 适合于任何几何物体：能够计算与直线交点。
4. 适合于并行实现（硬件加速），目前的 3D 加速卡一般都可支持 16 位的 Z-Buffer，高级卡已可支持到 32 位。

缺点：

1. Z 缓冲器需要占用大量的存储单元。深度范围可能为 $10^6$，一个像素需要 24bit 存储深度信息。分辨率为 $1280 \times 1024$ 时，深度缓冲器需要 4MB 存储空间。
2. 深度的采样与量化带来走样现象。
3. 难以处理透明物体。

32. 画家算法#

算法约定距视点近的优先级高，距视点远的优先级低。生成图像时，优先级低的多边形先画，优先级高的后画，后画的多边形将先画的遮挡住。属于物体空间消隐算法，将物体空间和图像空间结合起来。

算法的特点：

1. 同时在物体空间和图像空间中进行处理：在物体空间中排序以确定优先级，显示结果不断写入图像空间的帧缓冲区中。
2. 利用几何关系来判断可见性，按物体（多边形）的深度排序，比较容易实现。
3. 要求场景中多边形为凸多边形。
4. 比较适于解决图形的动态显示问题，只要事先把不同视点的景物的优先队列算出，再实时采用画家算法来显示，就能实现快速消隐与显示。

33. 颜色模型#

RGB 模型通常用于彩色阴极射线等彩色光栅图形显示设备中。CMY 通常用于印刷行业。

34. 光照模型#

漫反射：粗糙的物体表面往往将反射光向各个方向散射，这种光线散射的现象称为漫反射。

镜面反射：表面非常光滑的物体表面会产生强光反射，称为镜面反射。

Phong 光照模型：从视点观察到物体上任一点 P 处的光强度 $I$ 应为环境光反射光强度 $I_e$、漫反射光强度 $I_d$ 以及镜面反射光的光强度 $I_s$ 的总和。两种形式计算都要会。

$I = I_e + I_d + I_s$

35. 明暗度处理模型#

恒定光强的多边形绘制：适用于平面体真实感图形的处理，只用一种颜色绘制整个多边形。

• 优点：处理简单，计算量小。
• 缺点：景物表面上相邻的多边形之间颜色差异较大，存在马赫带效应。

Gouraud 明暗处理（亮度插值明暗处理）：通过对多边形顶点颜色进行线性插值来绘制其内部各点，使得图形变得光滑。

• 优点：算法简单，计算量小，解决了两多边形之间明暗度不连续以及多边形片内光强单一的问题，应用于简单的漫反射光照模型时效果最好。
• 缺点：明暗插值法只能保证在多边形边界两侧光强的连续性，不能保证变化的连续性，马赫带效应依然存在；将相邻多边形的法矢量平均值作为顶点处法矢量，法矢量是平行的，不能正确模拟高光。

Phong 明暗处理（法矢量插值明暗处理）：对多边形顶点的法矢量进行插值以产生中间各点的法矢量。

• 优点：能较好地模拟高光；相邻多边形之间的光亮度过渡更自然。
• 缺点：既要通过三角形网格各顶点的法矢量来插值计算多边形内各点的法矢量，还要调用光照模型计算其光强，计算时间是 Gouraud 明暗处理的 6~8 倍。

36. 光线跟踪算法#

思想：基于几何光学的原理，通过模拟光的传播路径来确定反射、折射和阴影，采用逆向跟踪技术完成整个场景的绘制。

跟踪的结束条件：

1. 光线未碰到任何物体。
2. 光线碰到了背景。
3. 光线经过许多次反射和折射后，光线对视点的光强小于某个设定值。
4. 光线反射或折射次数即跟踪深度大于一定值。

使用 Whitted 整体光照模型计算。

特点：

1. 简单有效。
2. 可实现场景中交相辉映的景物、阴影、透明等高度真实感图形的显示。
3. 用到大量的求交运算，复杂度高。

37. 纹理映射技术#

颜色纹理映射：使绘制出来的物体表面具有花纹图案效果。

几何纹理映射：一种无需修改表面几何模型，即能模拟表面凹凸不平效果的有效方法。

---

三、OpenGL 变换实例代码#

#include "stdafx.h"
#include <GL\glut.h>

// 初始化窗口
void Initial(void) {
    glClearColor(1.0f, 1.0f, 1.0f, 1.0f);
}

// 绘制三角形
void DrawTriangle() {
    glBegin(GL_TRIANGLES);
        glVertex2f(0.0f, 0.0f);
        glVertex2f(40.0f, 0.0f);
        glVertex2f(20.0f, 40.0f);
    glEnd();
}

void Display(void) {
    glClear(GL_COLOR_BUFFER_BIT);
    glMatrixMode(GL_MODELVIEW);
    glLoadIdentity();

    // 绘制黑色坐标轴
    glBegin(GL_LINES);
        glColor3f(0, 0, 0); glVertex2f(-400, 0);
        glColor3f(0, 0, 0); glVertex2f(400, 0);
        glColor3f(0, 0, 0); glVertex2f(0, 400);
        glColor3f(0, 0, 0); glVertex2f(0, -400);
    glEnd();

    // 画出初始的红色三角形
    glColor3f(1, 0, 0);
    DrawTriangle();

    // 画出逆时针旋转200度角的绿色三角形
    glPushMatrix();
        glRotatef(200, 0, 0, 10);
        glColor3f(0, 1.0, 0);
        DrawTriangle();
    glPopMatrix();

    // 画出沿X轴负向平移40的黄色三角形
    glPushMatrix();
        glTranslatef(-80, 0, 0);
        glColor3f(1, 1.0, 0);
        DrawTriangle();
    glPopMatrix();

    // 画出沿X轴对称、沿X轴正向平移10、Y轴负向平移10、
    // 缩放因子为1.5,2.0,1.0的蓝色三角形
    glPushMatrix();
        glTranslatef(10, -10, 0);
        glRotatef(180, 10, 0, 0);
        glScalef(1.5, 2.0, 1.0);
        glColor3f(0, 0, 1);
        DrawTriangle();
    glPopMatrix();

    glFlush();
}

int main(int argc, char *argv[]) {
    glutInit(&argc, argv);
    glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);
    glutInitWindowPosition(100, 100);
    glutInitWindowSize(400, 400);
    glutCreateWindow("变换实例");
    glutReshapeFunc(ChangeSize);
    glutDisplayFunc(Display);
    Initial();
    glutMainLoop();
    return 0;
}