第一章 绪论

本章复习重点

• 图形学和图像学的区别。
• 走样的原因和反走样的概念。
• 选择题（直线算法）。
• 光栅显示系统。

计算机图形学概述

图形学研究内容

1. 建模：创建用计算机表示的三维物体模型，主要是形状表述与定义。
2. 渲染：通过各种矩阵变换从模型产生物体的二维图像，主要考虑光照、透视变换。
3. 动画：描述物体运动变化。

光栅扫描系统

随机扫描与光栅扫描

随机扫描技术的本质是按照显示命令的任意顺序，将电子束从一个端点偏转到另一个端点。

光栅图形具有对显示区域填充颜色或图案的能力，存储的图像更加易于操作。

光栅显示器上的图形由光栅（raster）形成。

光栅是一组互相平行的水平扫描线。每行扫描线是由大小一致的显示单元组成的显示序列，每一显示单元称为一个像素，可显示给定的颜色和灰度。

光栅显示器将显示图元（primitive）如线、文字、填充颜色或图案区域等，以像素的形式存储到一个刷新缓冲器中。

光栅扫描系统

构成：

1. 帧缓冲区（Frame Buffer）。
2. 视频控制器（Video Controller）。
3. 显示处理器（Display Processor / GPU）。

视频控制器如何实现基本刷新：

1. 有两个寄存器用来存放屏幕像素的坐标。
2. 存储在帧缓冲区中该像素对应位置的值被取出，并用来设置 CRT 电子束的强度值。

显示处理器的主要任务是将应用程序给出的图形定义数字化为一组像素强度值，并存放在帧缓冲区中。这个数字化过程称为扫描转换（Scan Conversion）。

直线段的扫描转换算法

当我们对直线进行光栅化时，需要在显示器有限个像素中，确定最佳逼近该直线的一组像素，并且按扫描线顺序，对这些像素进行写操作，这个过程称为用显示器绘制直线或直线的扫描转换。

三种算法：

1. 基本增量算法（DDA）数值微分算法。
2. 中点画线算法。
3. Bresenham 算法（使用最广泛）。

DDA 算法

在一个坐标轴上以单位间隔对线段取样，则另一个坐标轴以常数 m 或 1/m 变化，从而获得线段上各像素点。

算法迭代公式：

$$\text{若 } |m| \le 1: \begin{cases} x_{k+1} = x_k + 1, \quad y_{k+1} = y_k + m, & (x_a < x_b) \\ x_{k+1} = x_k - 1, \quad y_{k+1} = y_k - m, & (x_a > x_b) \end{cases} \\ \text{若 } |m| \ge 1: \begin{cases} y_{k+1} = y_k + 1, \quad x_{k+1} = x_k + \dfrac{1}{m}, & (y_a < y_b) \\ y_{k+1} = y_k - 1, \quad x_{k+1} = x_k - \dfrac{1}{m}, & (y_a > y_b) \end{cases}$$

Bresenham 算法

只用整数计算寻找最接近实际直线的整数坐标。即从 Yk 和 Yk + 1 中取出最贴近 y 坐标的点作为拟合点，但只通过整数计算。

推导过程如下：

$$\\ \textbf{假定：} \quad 0 < m < 1 \\ 已知点 (x_k, y_k)，求下一点 (x_{k+1}, y_{k+1})。(x_{k+1}, y_{k+1}) 的两种可能为：(x_{k+1}, y_k) \quad \text{或} \quad (x_{k+1}, y_k + 1)。其中：x_{k+1} = x_k + 1 \\ \textbf{推导：} \\ 设两点与理想直线的距离分别为 d_1、d_2： \\ \begin{aligned} d_1 &= y - y_k = m x_{k+1} + b - y_k, \\ d_2 &= y_{k+1} - y = y_{k+1} - (m x_{k+1} + b). \end{aligned} \\ 因此：d_1 - d_2 = 2m x_{k+1} - 2y_k + 2b - 1 \\ 令：m = \frac{\Delta y}{\Delta x} \\ 代入上式，引入决策参数 P_k 表示相对距离： \\ P_k = \Delta x (d_1 - d_2) = 2\Delta y x_k - 2\Delta x y_k + C \\ 其中：C = 2\Delta y + \Delta x (2b - 1) \\ \textbf{推论：} \\ \begin{cases} P_k < 0, & \text{则选择 } y_{k+1} = y_k \\ P_k \ge 0, & \text{则选择 } y_{k+1} = y_k + 1 \end{cases} \\ P_k 的递推公式： \\ 由 \\ \begin{aligned} P_{k+1} &= 2\Delta y x_{k+1} - 2\Delta x y_{k+1} + C, \\ P_k &= 2\Delta y x_k - 2\Delta x y_k + C, \end{aligned} \\ 两式相减得： \\ P_{k+1} - P_k = 2\Delta y (x_{k+1} - x_k) - 2\Delta x (y_{k+1} - y_k) \\ = 2\Delta y - 2\Delta x (y_{k+1} - y_k) \\ \therefore \; {P_{k+1}} \text{ 的递推公式：} \\ P_{k+1} = \begin{cases} P_k + 2\Delta y, & (P_k < 0) \\[6pt] P_k + 2\Delta y - 2\Delta x, & (P_k \ge 0) \end{cases} \\ 初始值为：\\ P_0 = 2\Delta y - \Delta x$$

中点画线算法

用判别式判断点与直线的关系。

算法思路：

$$F(x, y) = (m x + b) - y \\[6pt] F(x_{k+1},\, y_k + 0.5) = 0, \quad \text{对应点 } (x_{k+1},\, y_{k+1}) \text{ 可能为 } (x_{k+1},\, y_k + 1) \text{ 或 } (x_{k+1},\, y_k) \\[6pt] \begin{cases} F(x_{k+1},\, y_k + 0.5) < 0, & \text{中点在直线上方，选择 } (x_{k+1},\, y_k) \\[6pt] F(x_{k+1},\, y_k + 0.5) > 0, & \text{中点在直线下方，选择 } (x_{k+1},\, y_k + 1) \end{cases}$$

走样与反走样

对于光栅系统来说，只能用光栅网格上的像素近似地描绘平滑的直线、多边形和圆、椭圆等曲线图元。如果引起了图中看到的锯齿状或阶梯状的边界线问题，在图形学中称为“走样”。

用于减少或消除这种现象的技术称为“反走样”。

第二章 颜色模型

本章复习重点

• 什么是设备无关的颜色模型。
• 什么是设备相关的颜色模型。
• RGB 和 CMY 颜色模型的比较。
• 哪些颜色模型是设备相关的？哪些颜色模型是设备无关的？
• 颜色模型之前的转换。

颜色模型

颜色模型就是用一组数值来描述颜色的数学模型。

设备无关的颜色模型：这类颜色模型是基于人眼对色彩感知的度量建立的数学模型，这些颜色模型主要用于计算和测量。

设备相关的颜色模型：以最常见的 RGB 模型为例，一组确定的 RGB 数值，在一个 LED 屏上显示，最终会作用到三色 LED 的电压上。这样一组值在不同设备上解释时，得到的颜色可能并不相同。

颜色模型是某个三维空间中的一个可见光子集。任何一个色彩域都只是可见光的子集，任何一个颜色模型都无法包含所有的可见光。

三原色：红、绿、蓝。

RGB 颜色模型

三维直角坐标颜色系统中的一个单位正方体。

RGB 颜色模型构成的颜色空间是 CIE 原色空间的一个真子集。RGB 三原色是加性原色。

RGB 颜色模型通常用于彩色阴极射线管和彩色光栅图形显示器。

CMY 颜色模型

CMY 颜色模型是以红、绿、蓝三色的补色青（Cyan）、品红（Magenta）、黄（Yellow）为原色构成的颜色模型。

CMY 颜色模型常用于从白光中滤去某种颜色，故称为减色原色空间。

CMY 颜色模型对应的直角坐标系的子空间与 RGB 颜色模型对应的子空间几乎完全相同。

RGB 和 CMY 颜色模型的对比

HSV 颜色模型

HSV 颜色模型是面向用户的。在 HSV 颜色模型中，每一种颜色和它的补色相差 180 度。

HSV 颜色模型的优点：

• 符合人眼对颜色的感觉。
• 当采用 RGB（或者 CMY）颜色模型时，改变某一颜色的属性，比如改变色调就必须同时改变 R、G、B（或者 C、M、Y）三个坐标；而采用 HSV 颜色模型时只需改变 H 坐标。即它的三个坐标是独立的。
• HSV 颜色模型构成的是一个均匀的颜色空间，采用线性的标尺，彩色之间感觉上的距离与 HSV 颜色模型坐标上点的欧几里德距离成正比。

CIE（国际照明委员会）颜色模型

CIE 颜色模型包括一系列颜色模型，这些颜色模型是由国际照明委员会提出的，是基于人的眼睛对 RGB 的反应，被用于精确表示对色彩的接收。

CIE 是设备无关性：

• 被用来定义所谓的独立于设备的颜色。
• 它能够在任何类型的设备上产生真实的颜色，例如：扫描仪、监视器和打印机。
• 很适合计算机描述颜色的范围。

CIE XYZ

XYZ 三刺激值的概念是以色视觉的三元理论为根据的，它说明人眼具有接受三原色(红、绿、蓝)的接受器，而所有的颜色均被视作该三原色的混合色。

CIE 制定了一种配色函数，能和 RGB 通过矩阵运算进行转化。

**颜色的概念可以分为两部分：亮度（光的振幅，即明暗程度）、色度（光的波长组合，即具体某种颜色）。**我们将光的亮度 Y 变量分离出来，之后用比例来表示三色刺激值：

可以发现，r、g、b 三者和为 1，只要知道其中两个就能求出另外一个。然后再和光的亮度 Y 结合起来，就能绘制 Yxy 颜色空间。

CIE L*a*b*

L*a*b* 颜色空间是在 1976 年制定的，它是 CIE XYZ 颜色模型的改进型，以便克服 Yxy 颜色空间存在的在 x、y 色度图上相等的距离并不相当于所觉察到的相等色差的问题。同样是一种描述人类视觉感知的、设备无关的颜色模型。

L*a*b* 的概念图：

• L：明亮度。
• a：从绿色到红色。
• b：从蓝色到黄色。

与 XYZ 比较，CIE L*a*b* 颜色更适合人眼的感觉。

利用 CIE L*a*b*，颜色的亮度（L）、灰阶和饱和度（a、b）可以单独修正，这样，图像的整个颜色都可以在不改变图像或其亮度的情况下，发生改变。

YUV

“Y” 表示明亮度（Luminance），“U” 和 “V” 分别表示色度（Chrominance）和浓度（Chroma)。

**采用 YUV 颜色空间的重要性是它的亮度信号 Y 和色度信号 U、V 是分离的。**这样能解决彩色电视机和黑白电视机的兼容问题，使黑白电视机也能接收到彩色信号。如果只有 Y 信号分量而没有 U、V 分量，那么这样表示的图就是黑白灰度图。

各种颜色模型之间的转换

各种颜色模型之间的转换一般是以 RGB 和 CIE XYZ 作为桥梁进行的。

RGB 和 CMY

RGB 的取值通常是 0 ~ 255 的整数。

1
2
3

C = 255 – R
M = 255 – G
Y = 255 – B

RGB 和 HSV

1. 查表法

最可靠方法：

把 RGB 坐标转换为 1931 CIE XYZ 系统中的 (x， y， Y) 坐标。根据 (x， y， Y) 查找对应表，得到相应的 (H， S， V) 坐标。逆向操作则可以从 HSV 坐标转换到 RGB 坐标。

xyY 坐标与 HSV 坐标的对照表已由色度学实验得到。这种方法需要依赖对照表，比较笨重。

2. 数学公式

从 RGB 到 HSV：

设 m=max(r, g, b)，n=min(r, g, b)。

从 HSV 到 RGB：

RGB 和 CIE XYZ

CIE XYZ 和 CIE L*a*b*

L 的范围是 0 ~ 100，a, b 的范围是 -300 ~ 300。从 -a 到 +a 表示绿到红过渡，-b 到 +b 表示蓝到黄过渡。

RGB 和 CIE YUV

第三章 物体表示

本章复习重点

• 什么是建模坐标系，和世界坐标系的区别。
• OBJ 数据结构。
• 什么是 BREP，其结构中包含哪些信息。
• 半边数据结构。
• 多边形的优缺点。
• Bézier 曲线优缺点。
• NURBS 曲线和 B 样条曲线的改进是什么。
• 参数曲线的优缺点。
• 细分曲面的作用。
• 细分曲面的原理。
• Catmull-Clark subdivision。
• 有哪些常见的细分规则。
• 细分曲面的翼边存储。
• 物体的 CSG 表示。
• 什么是分形几何。
• 分型维数计算。
• L- 系统，能够用 L- 系统绘制物体。

多边形

坐标表示

一些概念：

1. 世界坐标系(WC)：场景参照坐标系，一个场景只有一个世界坐标系。
2. 观察坐标系(VC)：根据场景观察时的视点和观察方向所建立的坐标系。
3. 投影坐标(PC)：观察坐标系下场景的二维投影坐标。
4. 设备坐标系(DC)或屏幕坐标系：该场景的世界坐标系描述转换为一个或多个输出设备参照系来显示。该坐标系依赖于具体的显示输出设备。
5. 规范化坐标系(NC)：指独立于具体物理设备的一种坐标系，它的显示范围在 x 和 y 上都是 0 到 1，主要用于在计算机内部处理图形，对一个具体物理设备，NC 与 DC 仅仅是相差一个比例因子，NC可被看成是一个抽象的图形设备。

在一个世界坐标系中，由许多物体组成。不同物理的几何描述和空间坐标系密切相关，在不同坐标系中有着不同的表示方式。选择某个空间坐标系能使得该物体的几何表示最简单，这就是建模坐标系。

例如，一个单位正方体在世界和建模坐标系中的不同表示如下。明显建模坐标系更简洁。

建模坐标系除了形式简洁，还方便几何操作。在同一几何场景中，一个物体可能会多次出现，它们可以通过复制加变换的方式得到：标准体素＋变换＝新的物体。

例如，以下是在建模和世界坐标系中旋转一个圆柱面。

多边形表示

物体的多边形表示是通过大量的平面片，三角形、四边形以及 n 边形。本质是线性表示形式。

数据来源

一个物体经过三维测量和扫描以后，原始数据一般是三维空间中的点集。通过适当的重建算法得到其多边形的表示。

常用物体外形用数学表示方法包括参数曲面、细分曲面、隐式曲面等。

表示方法：OBJ 格式

重点！！！

1. 顶点坐标表（x, y, z）：每个顶点处可能有多个平面片，一般情况下顶点数小于面片数。
2. 纹理坐标表（u, v）：控制纹理映射时纹理在表面上的位置。
3. 法向表 (nx, ny, nz) ：控制物体绘制时的着色光滑程度。如果顶点法向为取作该面片的法向，绘制出来的多边形物体棱角分明如果顶点法向是周围面片法向的某种平均，则绘制结果是光滑的。
4. 面表：由指向顶点、纹理坐标以及法向的指针组成。

数据结构

BRep 表示

边界表示，也称为 BRep 表示，它是几何造型中最成熟、无二义的表示法。实体的边界通常是由面的并集来表示，而每个面又由它所在的曲面的定义加上其边界来表示，面的边界是边的并集，而边又是由点来表示的。

在边界表示法中，边界表示按照体－面－环－边－点的层次，详细记录构成形体的所有几何元素的几何信息及其相互连接的拓朴关系。

1. 顶点：0 维度几何元素。
2. 边：一维几何元素。对正则形体，边是两邻面的交集，对非正则形体，边有可能是多个邻面的交集。边的形状可以是直线，也可以是曲线。
3. 环：二维几何元素。有序、有向边（直线段或曲线段）组成的面的封闭边界。外环边通常按逆时针方向排序，内环边通常按顺时针方向排序。
4. 面：二维几何元素。可以无内环，但必须有且只有一个外环。面有方向性，一般用其外法线方向作为该面的正向。面的形状可以是平面，也可以是曲面。
5. 体：三维几何元素。由封闭表面围成的空间，其边界是有限面的并集。

半边数据结构

半边结构（Half-Edge Structure）：可定向的二维流形及其子集。

每条边被记为两条半边，记录每条半边：

• 起始顶点的指针。
• 邻接面的指针(如果为边界，指针为 NULL)。
• 下一条半边(逆时针方向)。
• 相邻的半边。
• 前一条半边(可选)。

面：边界上的一条半边。

顶点：

• 坐标值。
• 指向以此顶点为起始端点的半边。

对于一个半边数据结构的简单形式，一个面仅仅需要储存一条围绕它的半边的指针。在半边数据结构中的点储存着 x，y，z 的位置和以其为起始点的半边的指针。

一个半边结构的实例：

半边结构的优势和不足：

• 优势：查询时间 O(1)， 操作时间 (通常) O(1)。
• 缺点：只能表示可定向流形，信息冗余。

优势与不足

优势：

• 表示简单。
• 可以表示具有任意拓扑的物体。
• 可以表示具有丰富细节的物体。
• 大部分图形硬件支持多边形物体的加速绘制。

不足：

• 逼近表示，难以满足交互时放大要求。
• 难以用传统方法修改(编辑)物体外形。
• 缺乏解析表达式，几何属性计算困难。
• 在表示复杂拓扑和具有丰富细节的物体时，数据量庞大，建模、编辑、绘制、存储的负担重。

参数曲面

数学原理

直线段的参数表示：

直线段参数表示的直观几何意义：

• 参数空间中每一个参数(点)都对应于直线段上一个点。
• 参数空间的两个端点对应于直线段的两个端点。

一般三维参数曲线形式：

• 参数空间中每一个 t 对应于曲线上一个点 R(t)。
• 图形学中，参数空间通常是有限区间，此时参数曲线称为参数曲线段。
• 图形学中，参数函数通常为分段多项式或有理多项式曲线。

参数表示的平面：

参数表示的曲面：

参数表示的优势：

• 参数表示是显式的。

  • 对每一个参数值，可以直接计算曲面上的对应点。

  • 参数表示的物体可以方便地转化为多边形逼近表示。

• 曲面上的几何量计算简便(微分几何)：法向、曲率、测地线、曲率线等。

• 特殊形式的参数表示的外形控制十分直观。Bézier、B- 样条、NURBS(Non-Uniform Rational B-Spline, 非均匀有理 B- 样条)曲线/曲面。

参数曲线

Bézier 曲线

曲线长这样：

曲线定义：

例如二次曲线，由三个控制点生成：

$$B_{0,2}(t) = (1-t)^2\\ B_{1,2}(t) = 2t(1-t)\\ B_{2,2}(t) = t^2$$

曲线性质：

• Bézier 多项式次数 ＝ 控制点个数 - 1
• 端点插值：R(0)=R0，R(1)=Rn。Bézier 曲线总是通过第一和最后一个控制点。
• 端点切向：R’(0)=n(R1−R0)，R’(1)=n(Rn−Rn-1)。

• 剖分性质：

曲线的不足：

整体性质：当移动曲线的一个控制顶点时，整条曲线的形状都会发生改变。

表示复杂形状时，需要将多条 Bézier 曲线光滑拼接起来，即 Bézier 样条曲线。

• 位置连续：C0(或 G0)。
• n 次导数(或几何)连续：Cn(或 Gn)。

B- 样条曲线

曲线长这样：

曲线定义：

B- 样条曲线是分段连续的多项式曲线，其定义与节点向量密切相关。

设 U 是 n + 1 个非递减数的集合，u0 <= u1 <= u2 <= … <= un。ui 称为节点，集合 U 称为节点向量，半开区间 [ui, ui+1) 是第 i 个节点区间。

K = 2 的均匀 B 样条基函数：

K = 3 的均匀 B 样条基函数：

曲线性质：

• B- 样条曲线具有凸包性和几何不变性。
• 当曲线的两个端节点的重复度 R=k-1 时，
  • B- 样条曲线具有类似于 Bézier 曲线的性质：端点插值性质、端点导数与控制的起始边与终止边相切。
  • 当 n=k-1 时，节向量有 2k 个,分别有 k 个节点在首尾固定，B- 样条曲线就是一条 Bézier 曲线。例如，三次（四阶）B- 样条，则节点向量 {0，0，0，0，1，1，1，1}。
• 局部性：当移动一个控制顶点时，只会影响曲线的一部分，而不是整条曲线。

优点：

• B- 样条曲线多项式独立于控制点数目。
• B- 样条允许局部控制曲线或曲面。

缺点：

• B- 样条比 Bezier 样条更复杂。

NURBS 曲线

B- 样条不能精确表示二次曲面与平面的交线的情形，如圆锥曲线(平面与圆锥的交线)。

NUBRS：非均匀有理 B- 样条的简称。

曲线定义：

曲线例子：

参数曲面

Bézier 曲面

曲面定义：

曲面性质：

• Bézier 曲面的控制顶点所形成的控制网格大致反应了曲面的形状，所以可通过编辑控制顶点的方式来实现对曲面形状的改变。
• 在角点处曲面与控制多边形相切。
• Bézier 曲面具有剖分算法：用加密的控制多边形来逼近显示 Bézier 曲面。

曲面不足：

• 全局性：当移动一个控制顶点的位置时，整个曲面的形状会发生改变，这对于外形设计是很不方便的。
• 生成复杂外形需要多个 Bézier 曲面的光滑拼接，十分复杂。

B- 样条曲面

曲面定义：

曲面性质：

• 局部性质。
• 控制顶点数目。
• Bézier 曲面的次数确定后，控制顶点数目就定了。
• B- 样条曲面的次数确定后，控制顶点数目可任意。
• 其它性质：参考曲线情形。

曲面不足：不能精确表示常用的二次曲面，如球面、圆柱面、圆锥面等。

NURBS 曲面

NURBS 曲面：

• 增加了权因子作为形状控制手段。
• 包含 B- 样条曲面和 Bézier 曲面。
• 可以精确表示机械零件中常用的二次曲面。

细分曲面（Subdivision Surfaces）

简介

如何使得一条曲线变光滑？

**每次细分都是在每条边上插入一个新的顶点，可以看到随着细分次数的增加，折线逐渐变成一条光滑的曲线。**曲面细分需要有几何规则和拓扑规则，几何规则用于计算新顶点的位置，拓扑规则用于确定新顶点的连接关系。

应用细分曲面做三维模型的原型设计非常的方便。通常只需要两个步骤，先创建出模型的大致轮廓，然后设置需要切割的点线面。比如这个桌子模型，先创建出它的轮廓模型，看起来非常简单，然后设置哪些点线面需要切割。

关键问题：

• 怎样计算曲面？使得物体平滑。
• 怎样存储曲面？能够有效的实现曲面细分。

Loop 细分

Loop 细分是一种三角形网格的细分法则。

如何细分？增加新的顶点（分裂阶段)，通过分边和连接顶点，将每个三角形分为 4 个三角形。

平均阶段，移动新三角形和老三角形顶点，让细分结果更光滑。

边界边、内部边、边界点、内部点。

两个新增顶点位置计算的规则：

旧顶点位置更新的规则：

Loop 细分方案对任意拓扑结构的多边形进行细分。细分粒度实现多个分辨率自由变换。

Catmull-Clark 细分

Catmull-Clark 细分是一种四边形网格的细分法则，每个面计算生成一个新的顶点，每条边计算生成一个新的顶点，同时每个原始顶点更新位置。

生成过程：

举例：

下图为 Catmull-Clark 细分格式的细分掩膜，对于新增加的顶点位置以及原始顶点位置更新规则如下：

**细分曲面的核心就一个点：细分规则。不同的细分规则，生成的细分曲面外形是有区别的。**常见的细分规则有 Catmull-Clark 细分，Doo-Sabin 细分，Loop 细分等。

Butterfly 细分

Doo-Sabin 细分

Dainel Doo 和 Malcolm Sabin 在 1978 提出的一种可以对任意拓扑的网格进行细分的一种算法，是递归定义的。

• 原来的顶点变面（度为几，就是几边形）。
• 边也变面。
• 原来的面也变为新面。

每次递归，计算面的中心点和边的中心点，对于每一个点 P，计算一个新的点 P’，是原顶点，相邻的边的中心点和面的中心点的平均值。

每次递归，对于每一个面，连接面内的新点生成新的面，对于每一个点，连接点周围的新点生成新的面，对于每一条边，连接边相邻的新点生成新的面。

四种细分算法效果

Loop 只能用于三角形网格。

Catmull-Clark 可以运用于任意拓扑的网格。

Doo-Sabin 的计算效率不如 Catmull-Clark。

在 3D 计算机图形学中，Doo-Sabin 细分曲面是一种基于双二次均匀B样条推广的细分曲面，而 Catmull-Clark 基于广义双立方均匀 B 样条。

多边形的面片

面表示：

• 独立面。
• 顶点和面表。
• 邻近边表。
• 翼边表示法。

面表

每个面表有顶点组成，冗余顶点，没有拓扑信息。

顶点表 & 面表

每个面的顶点坐标。

参考：共享顶点、仍然没有拓扑信息。

邻接边表

存储所有的点, 边, 面邻接关系。

邻接：有效保存拓扑信息、带来额外存储。

翼边表示法

• 将邻接关系存储在边信息中。
• 所有邻接信息 O(1) 查询。
• 较小的存储开销。
• 任意形状的多边形。

对每条边，储存其两个顶点，左右两个面，左边面与之连接的两条边，右边面与之连接的两条边。

对每个点，储存其对应的一个边索引。

对每个面，储存其中的一个边索引。

例子：

优点：

• 表现面的简单方法。
• 容易实现。
• 任意拓扑结构。
• 实现光滑曲面。
• 多分辨率。

难点：

• 难于直观感受。
• 难于参数化计算。
• 难于交互。

隐式曲面

几何物体的表示：

• 参数曲面，如 Bezier 曲面、B 样条曲面、NURBS 曲面等。参数曲面在造型和动画设计中取得了非常大的成功，很多造型和动画系统都是基于 NURBS 曲面的。
• 多边形网格(Polygon Mesh)。
• 细分曲面(Subdivision Surface)。
• 隐式曲面(Implicit surface, level set)。

隐式曲面很适合表示可变形和可变拓扑的物体，因而对动画非常有用(如 morphing)。

三维空间中的隐式曲面：

与参数曲面相比，隐式曲面的优点：

• 隐式曲面可以表示具有复杂拓扑的形状。
  • NURBS 曲面只能表示拓扑等价于矩形的四边曲面。
  • NURBS 曲面表示非退化封闭光滑曲面时，需要光滑拼接。
• 隐式曲面比 NURBS 曲面更适合于进行布尔运算、光线跟踪、点集判断等。

与参数曲面相比，隐式曲面的不足：

• 隐式曲面表示不直观，难以进行外形的交互修改。NURBS 曲面的外形控制手段非常直观。
• 隐式曲面通常没有边界，而 NURBS 曲面具有显式的边界。
• 隐式曲面难以直接进行显示，而 NURBS 曲面则可以借助于剖分算法，对逼近多边形表示进行绘制。

隐式化：从参数曲面到隐式曲面。

• 消除 NURBS 曲面的两个参数 (u, v) 得到其隐式表示。

参数化：从隐式曲面到参数曲面。

• 并非所有的隐式曲面都可以参数化。
• 对于非退化的二次代数曲面和具有一个奇异点的三次代数曲面，可以进行有理多项式参数化。

图形学中常用的隐式曲面造型技术：

• 基于骨架的隐式曲面造型。

  • 基于点、线和面骨架的 Metaball 方法。

  • 基于骨架的卷积曲面。

• 树木造型：

  • 利用其平滑的特性建模树木分叉的平滑过渡。

  • BLOBTree。

  • 通过布尔操作、融合操作、变形操作，拼接成一个复杂树状结构的隐式曲面。

• 代数曲面片造型技术，包括二次代数曲面、A-Patch 方法等。

隐式曲面的显示：

• 多边形化：用平面多边形逼近隐式曲面，Marching Cube 方法。
• 光线跟踪：生成高质量的图像。
• 粒子系统：在隐式曲面上均匀布撒粒子。

物体的 CSG 树表示

CSG：Constructive Solid Geometry

• 表示实体：即有边界，也包含内部。
• 表示边界：多边形、参数曲面、隐式曲面、细分曲面。

CSG 树表示：面向浇铸、加工或拉伸等 CAD/CAM 过程。

CSG 树：通过一系列几何操作将简单的基本体素组合起来。

• 基本体素：立方体、球、圆柱、圆锥等。
• 几何操作：
  • 布尔运算：并、交、差、补等。
  • 几何变换：平移、旋转、放缩、剪切等。

CSG 树：含有丰富的造型信息。

• 物体生成过程。
• 物体表示。

CSG 树的缺点：

• 绘制耗时。
• 限制了物体外形的修改。

改进：混合表示。将边界表示和布尔运算结合起来，形成一种边界表示和 CSG 实体表示之间的混合表示。

一个例子：

自然景物表示方法

L- 系统

三种常用方法：

• 分形几何。
• 基于语法规则的 L- 系统。
• 粒子系统。

L- 系统：

• 语法规则：根据语法规则对所给字符进行迭代生成新字符串，每次迭代结果称为一代。
• 字符解释：将字符串中的字符解释为适当的几何体素，就可以得到一个基于语法规则生成的物体。

L- 系统成功地用于植物建模。

一个例子：

在 L- 系统中引入更多控制：

• 不同“代”之中的字符的不同解释。(n+1) 代的树枝要比 n- 代的树枝细一些、短一些。
• 终止节点处赋予树叶和花朵。

粒子系统

粒子系统：

• 由一组随时间变化的粒子组成。
• 粒子的变化由某种随机统计规律控制。
• 粒子有生命：产生、发展（运动）、消亡。
• 按照确定或随机运动规律进行运动。

模拟火、雾、烟、焰火等外形随时间的变化而变动的模糊物体。

粒子系统是一个动态变化的系统，生成其中每一瞬间画面的步骤：

• 产生新的粒子并加入系统中。
• 赋予每一个新粒子一定的属性。
• 删除那些已经超过其生命周期的粒子。
• 根据粒子运动属性对粒子进行移动和变换。
• 绘制并显示出所有有生命粒子组成的画面。

粒子系统被用来描述自然界大量的随机的运动方式。最直观的例子就是雨雪、飘落的树叶、还有节日的烟花。

粒子系统的例子很多，几乎每部游戏都有粒子系统的应用，粒子系统是游戏中相当出彩的地方。就如同帧动画特效的秩序运动一样，粒子系统事实上体现了游戏世界的乱序，而这种乱序是真实世界必不可少的。

粒子系统并不适于描述少量非随机的运动方式，在有些情况下，使用粒子系统并不比使用帧动画更好，那么在这种情况下，不妨使用帧动画来提高一些效率。

粒子系统对游戏效率的压力是比较高的。这主要是因为大部分粒子系统都要求动态 VB 的缘故。

粒子系统，从其功能而言包括如下部分：

• 发射某一类粒子的发射器，Emitter。
• 被发射的粒子，Particle。
• 以上两者是最核心的部分，还有为了方便扩展而设置的影响器，Affector。

Emitter 用于发射 Particle。事实上，Emitter 就是一组配置的集合，Particle “出生”时的状态被 Emitter 的配置所决定。

Emitter 过于臃肿对于扩展是很不利的，因此有些人想出了 Affector 的方法，以使得扩展性得到满足。扰动子 Affector 是一类附加修缮配置的统称，主要包括粒子生成和运行的因素。

分形

分形分类：

• 自相似分形：组成部分是整个物体的收缩形式。
• 自仿射分形：组成部分为不同坐标方向上的不同缩放因子形成。
• 不变分形集：由非线性变换形成。
  • 自平方分形。
  • 自逆分形：由自逆过程形成。

普通几何学研究的对象，一般都具有整数的维数。比如，零维的点、一维的线、二维的面、三维的立体、乃至四维的时空。但是现实生活中象弯弯曲曲的海岸线这些对象就不能用传统欧几里德几何学的整数维描述或者说测量了。**要描述这一大类复杂无规的几何对象，就引入了分形理论，把维数视为分数维数。**这是几何学的新突破，引起了数学家和自然科学者的极大关注。

分形的本意是不规则的、破碎的、分数的。是指以非整数维形式填充空间的形态特征。分形几何通俗一点就是研究无限复杂但具有一定意义下的自相似图形和结构的几何学，基本思想是客观事物具有自相似的层次结构，局部与整体在形态、功能、信息、时间、空间等方面具有统计意义上的相似性，称为自相似性。

如何计算分型维数？

如果某图形是由把原图缩小为 1/a 的相似的 b 个图形所组成，有：

$$a^D=b, D=logb/loga$$

则指数 D 称为相似性维数，D 可以是整数，也可以是分数。

分形体没有特征尺度，不能用一般测度即长度、面积、体积这类几何对象的特征量来表示，只能用分形维数(Fractal dimension，也即“分维”)来度量，因而分维已成为描述无标度现象的特征参数。

分形树：以自然界中的丫字形树杈为生成元，将生成元在每一个层次上不断重复，会得到分形树。

分形树实现算法：递归算法、LS 文法、迭代函数系统算法。

“递归”，这两个字用得十分好。递，即依次递变；归，即向一个方向归拢。“分形”，故名思议是指把一个形状细分为同样的形状。

分形几何的主要特征：

• 自相似性质：分形物体的任何一个部分都和物体整体具有某种程度的相似。
• 无限小细节性质：当无限地放大分形物体时，物体总是表现有细节，而不是像欧氏空间的物体一样最终会表现出光滑性。
• 维数非整数。

分形的自我相似，自我复制和自我嵌套用递归算法来实现是合适的，事实上经典分形图的绘制大多数可采用递归算法。一个很经典的例子就是 Koch 雪花曲线。

计算 Koch 的分形维度。Koch 曲线是把一条直线缩小为 1/3 的相似的 4 个图形组成，根据定义是 log4/log3。

分形艺术的特点：

• 自相似性。
• 极小性。
• 嵌套性。
• 缠绕性。

第四章 图形渲染通道

本章复习重点

• 掌握图形渲染通道由那几个部分组成。
• 每一个功能点的作用。

渲染

渲染：通过几何物体生成真实可见图像的过程。

用点线面描述物体：

• 融合了数学表达。
• 物体集合的代表。

渲染物体：

• 渲染通道 render pass (Vulkan)。
• 渲染管线 rendering pipeline (OpenGL)。
  • 立即渲染模式（Immediate mode，也就是固定渲染管线）。
  • 核心模式(Core-profile, V 3.2)。

3D 渲染管线的三个阶段：

• 应用阶段：模型、数据读取、交互。
• 几何阶段。
• 光栅化阶段。

照相机模型

最通用的模式是小孔成像模型。所有捕捉到的光线都沿着指向焦点的路径到达，没有镜头变形（所有物体都处于焦点位置）。传感器响应与射线成比例。

照相机参数

内参：在小孔成像模型中有一个光点P，其将光以直线的方式穿过纸板的小孔(光心），射到显示纸板（物理成像平面）上，其坐标系结构如下图所示。而内参的作用即是在知道P的x、y、z后可以求出x`、y`。

外参：假象你的头部就是三维世界的中心，相机、篮球都有一个坐标，但是现在要知道的是相机中照片中的篮球的一个点的位置，因此应该将以你头部为中心的世界转换为以相机焦点为中心的世界，这样不就更直观了么。所以第一步就是求外参矩阵，然后把 xw,yw,zw 转换为以相机为中心的世界中的坐标 xc,yc,zc。

第二步，就是小孔成像问题，将转换为相机为中心世界的 xw,yw,zw，利用相机内参转换为图片中的点的位置，在将图片中的点转换为是哪个像素（像素坐标）。

渲染通道

经典的 3D 渲染通道：

模型变换

将所有场景中的点 3D “世界”变换到世界坐标系。大小缩放、平移、旋转物体，建模坐标系 -> 世界坐标系。

光线模拟

光照参数：光源发散、表面反射、大气衰减、相机感应。

直接光照模型、全局光照模型。

视窗转换

旋转转换世界坐标系为相机坐标系。世界坐标系 -> 视窗坐标系。

裁剪

去掉视窗外的几何物体部分。

投影变换

应用透视原理。视窗坐标系 -> 场景/图像坐标系。

光栅化

转换图像坐标系为像素和颜色。

第五章 变换

本章复习重点

• 齐次坐标系及其作用。
• 二维平移，旋转、缩放矩阵。
• 理解模型变换、取景变换、投影变换、设备变换、视窗变换的作用。
• 一点透视、两点透视、三点透视。

几何（模型）变换

基本变换

2D 平移

图形对象沿直线运动产生的变换。

$$x' = x + t_x \\ y' = y + t_y \\ \\ P = \begin{bmatrix} x \\ y \end{bmatrix} P' = \begin{bmatrix} x' \\ y' \end{bmatrix} T = \begin{bmatrix} t_x \\ t_y \end{bmatrix} \\ \begin{bmatrix} x' \\ y' \end{bmatrix} = \begin{bmatrix} x \\ y \end{bmatrix} + \begin{bmatrix} t_x \\ t_y \end{bmatrix} \\ P' = P + T$$

2D 旋转

图形对象沿圆弧路径运动产生的变换。

基准点(pivot)，坐标原点或任意点。旋转角 θ。方向,约定：逆时针为正。

$$P = \begin{bmatrix} x \\ y \end{bmatrix} P' = \begin{bmatrix} x' \\ y' \end{bmatrix} R = \begin{bmatrix} \cos\theta & -\sin\theta \\ \sin\theta & \cos\theta \end{bmatrix} \\ \begin{bmatrix} x' \\ y' \end{bmatrix} = \begin{bmatrix} \cos\theta & -\sin\theta \\ \sin\theta & \cos\theta \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} \\ P' = R \cdot P$$

2D 缩放

改变图形对象大小的变换。

$$P = \begin{bmatrix} x \\ y \end{bmatrix} P' = \begin{bmatrix} x' \\ y' \end{bmatrix} S = \begin{bmatrix} S_x & 0 \\ 0 & S_y \end{bmatrix} \\ \begin{bmatrix} x' \\ y' \end{bmatrix} = \begin{bmatrix} S_x & 0 \\ 0 & S_y \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} \\ P' = S \cdot P$$

2D 缩放讨论：

1. 如果 |Sx| 或 |Sy| 大于 1，则表示图形在 X 轴方向或 Y 轴方向放大；
2. 如果 |Sx| 或 |Sy| 小于 1，则表示图形在 X 轴方向或 Y 轴方向缩小；
3. 如果 |Sx| = |Sy|，则表示均匀缩放；
4. 如果 |Sx| < |Sy| 或 |Sx| > |Sy|，则表示差值缩放；
5. 如果 |Sx| 或 |Sy| 等于 1，则表示图形在 X 轴方向或 Y 轴方向不变；
6. 如果 Sx 或 Sy 小于零，则表示图形在 X 轴方向或 Y 轴方向作镜面变换。

2D 矩阵表示

对于平移、旋转和缩放变换，每个基本的变换都可表示为通用矩阵形式：

$$P' = M1 \cdot P + M2 \\ P’、P 表示变换前后两个点的坐标的列向量。\\ M1 是一个包含乘法系数的 2×2 矩阵。\\ M2 是一个包含平移项的两元素列矩阵。$$

齐次坐标表示：基本思想是把一个 n 维空间的几何问题转换到 n+1 维空间中去。

例如：二维空间中点的坐标(x, y)的齐次坐标表示为(h*x，h*y，h)(h≠0的任意实数)。只要给定一个点的齐次坐标表示(xh，yh，h)，就能得到唯一的笛卡儿坐标(x, y)。其中 x=xh/h，y=yh/h。

一个笛卡儿坐标表示的点，用齐次坐标表示时，是无穷的（h 取值不同），但一个齐次坐标表示的点，用笛卡儿坐标表示时，是唯一的。

齐次坐标表示不是唯一的，通常当 h=1 时，称为规格化齐次坐标。用齐次坐标技术，可改写平移变换、缩放变换和旋转变换为统一的乘积形式。

规格化齐次坐标下的变换矩阵如下：

1. 平移变换

$$P' = T(t_x, t_y) \cdot P\\ \begin{bmatrix} x' \\ y' \\ 1 \end{bmatrix} = \begin{bmatrix} 1 & 0 & t_x \\ 0 & 1 & t_y \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} x \\ y \\ 1 \end{bmatrix}$$

2. 旋转变换（坐标原点为旋转中心）

$$P' = R(\theta) \cdot P\\ \begin{bmatrix} x' \\ y' \\ 1 \end{bmatrix} = \begin{bmatrix} \cos\theta & -\sin\theta & 0 \\ \sin\theta & \cos\theta & 0 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} x \\ y \\ 1 \end{bmatrix}$$

3. 缩放变换

$$P' = S(S_x, S_y) \cdot P\\ \begin{bmatrix} x' \\ y' \\ 1 \end{bmatrix} = \begin{bmatrix} S_x & 0 & 0 \\ 0 & S_y & 0 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} x \\ y \\ 1 \end{bmatrix}$$

复合变换

利用矩阵表示，就可通过计算单个变换的矩阵乘积，将任意顺序变换的矩阵建立为复合变换矩阵。

连续平移

两个连续的平移向量(tx1, ty1)和(tx2, ty2)被用于点 P，那么最后的点坐标可计算为

$$P' = T(tx2, ty2) · { T(tx1, ty1) · P } = { T(tx2, ty2) · T(tx1, ty1) } · P$$

计算时，可先计算两个平移变换矩阵的乘积。

$$T(tx2, ty2) · T(tx1, ty1) = T(tx2 + tx1, ty2+ ty1)$$

连续平移是可加的。

连续旋转

应用于点 P 的两个连续旋转，得到的点P’的坐标可计算为

$$P' = R(θ2) · { R(θ1) · P } = {R(θ2) · R(θ1)} · P \\ R(θ2) · R(θ1)= R(θ1+θ2)$$

则P’的坐标可计算为

$$P' = R(θ1+θ2) · P$$

连续旋转是可加的。

连续缩放

两个连续缩放操作的变换矩阵连接，产生的复合变换矩阵：

$$S(sx2, sy2) · S(sx1, sy1) = S(sx1· sx2, sy1· sy1)$$

连续缩放操作是相乘的，非叠加的。

通用基准点变换

1. 平移使基准点移动到坐标原点。
2. 针对原点做指定变换。
3. 反向平移使基准点回到原始位置。

通用方向变换

1. 旋转对象使任意方向与坐标轴方向重合。
2. 针对坐标轴方向做指定变换。
3. 反向旋转使任意方向回到原方向。

连接特性

$$A*B*C = (A*B)*C = A*(B*C) \\ A*B <> B*A$$

复合二维变换

平移、旋转和放缩矩阵通常记为 T、R 和 S。

二维变换具有结合性：(AB)C=A(BC)。

二维变换不具有交换性，一个例子是如下：

两个特殊的二维变换：

1. 刚体变换

可以分解为：平移和旋转的组合。

物体的形状没有变化，位置和方位有变化。

2. 仿射变换

可以分解为：平移、旋转和放缩的组合。

保持点的共线性、长度的比例＝>平行线。

3D 几何变换

3D 平移

$$平移向量：t_x, t_y, t_z \\ T = \begin{bmatrix} 1 & 0 & 0 & t_x \\ 0 & 1 & 0 & t_y \\ 0 & 0 & 1 & t_z \\ 0 & 0 & 0 & 1 \end{bmatrix}$$

3D 缩放

$$缩放因子：S_x, S_y, S_z \\ T = \begin{bmatrix} S_x & 0 & 0 & 0 \\ 0 & S_y & 0 & 0 \\ 0 & 0 & S_z & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}$$

针对给定点缩放（思路依旧是平移，然后按照原点缩放的方式，然后平移回去）：

$$参数: s_x, s_y, s_z, (x_f, y_f, z_f) \\ 变换矩阵 M = T(x_f, y_f, z_f)S(s_x, s_y, s_z)T(-x_f,-y_f, -z_f)$$

3D 旋转

1. 绕 Z 轴旋转

绕 Z 轴旋转，Z 坐标不变，矩阵上只有 x, y 有因子。

$$P' = R_z(\theta) \cdot P\\ R_z(\theta) = \begin{bmatrix} \cos\theta & -\sin\theta & 0 & 0\\ \sin\theta & \cos\theta & 0 & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1 \end{bmatrix}$$

2. 绕 X 轴旋转

同理。

$$P' = R_x(\theta) \cdot P\\ R_x(\theta) = \begin{bmatrix} 1 & 0 & 0 & 0\\ 0 & \cos\theta & -\sin\theta & 0\\ 0 & \sin\theta & \cos\theta & 0\\ 0 & 0 & 0 & 1 \end{bmatrix}$$

3. 绕 Y 轴旋转

同理。

$$P' = R_y(\theta) \cdot P\\ R_y(\theta) = \begin{bmatrix} \cos\theta & 0 & \sin\theta & 0\\ 0 & 1 & 0 & 0\\ -\sin\theta & 0 & \cos\theta & 0\\ 0 & 0 & 0 & 1 \end{bmatrix}$$

3D 复合变换

一般 3D 物体旋转：

• 旋转轴平行于坐标轴。
• 旋转轴不平行于坐标轴。

1. 旋转轴平行于坐标轴之一。

• 平移使旋转轴与平行坐标轴重合。
• 完成指定旋转。
• 反向平移使回到原位置。

2. 旋转轴不平行于任何坐标轴。

• 平移使旋转轴过原点。
• 旋转使旋转轴与坐标轴之一重合。
• 完成指定旋转。
• 反向旋转。
• 反向平移。

下面我们需要细细分析一下这个过程。

$$旋转轴由两个坐标点确定\\ P1(x1, y1, z1) -> P2(x2, y2, z2)\\ \\ 旋转轴矢量\\ V = P2－P1 = (Vx, Vy, Vz)\\ \\ 沿旋转轴的单位向量\\ u=V/|V| =(a, b, c)\\ a=(x2-x1)/|V|、b=(y2-y1)/|V|\\ c=(z2-z1)/|V|\\ |V| = sqrt(Vx2 + Vy2 + Vz2)$$

第一步

平移旋转轴矢量使其过原点。

$$T_1 = \begin{bmatrix} 1 & 0 & 0 & -x_1 \\ 0 & 1 & 0 & -y_1 \\ 0 & 0 & 1 & -z_1 \\ 0 & 0 & 0 & 1 \end{bmatrix}$$

第二步

旋转物体使旋转轴与 z 轴重合。

这一步又分为两小步：

• 将向量 U 绕 x 轴旋转到 xz 平面上: Rx(α)。
• 将向量 U 绕 y 轴旋转到 z 轴上: Ry(β)。

第一小步，Rx(α)。

计算 α 的关键点是利用旋转角等于在 Y-Z 平面里的投影来计算。

注意在我们假想的正方向情境下，绕 y 轴旋转是顺时针，是负方向，所以 sin(β)=-a。

第三步

完成指定旋转 Rz(θ)。

$$R_z(\theta) = \begin{bmatrix} \cos\theta & -\sin\theta & 0 & 0\\ \sin\theta & \cos\theta & 0 & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1 \end{bmatrix}$$

第四步

反向旋转使旋转轴回到原始方向。

$$R_y(-β)= R_y^{-1}(β) \\ R_x(-α)= R_x^{-1}(α)$$

第五步

反向平移使旋转轴回到原始位置。

$$T_2 = \begin{bmatrix} 1 & 0 & 0 & x_1 \\ 0 & 1 & 0 & y_1 \\ 0 & 0 & 1 &z_1 \\ 0 & 0 & 0 & 1 \end{bmatrix} = T_1^{-1}$$

整个过程的流程图如下：

观察（取景）变换

观察平面和观察坐标系的确定。

• 观察平面：也叫投影平面。
• 观察坐标系：用来指定观察者的观察位置及投影平面的参照系。

观察坐标系的建立：

• 观察参考点 Pref，观察坐标原点 P0。
• 观察平面法向量 N。观察 Zv 轴的正方向和观察平面方向。Zview = N = P0 - Pref
• 建立 Yview 轴的正方向，将 V 在观察平面上投影，即可得到 Yview 轴。
• 指定观察向上向量，只要与 N 不平行，如：Vup = (0,1,0)。
• 利用右手原则得到 Xview, Yview。X_view = V_up×Z_view，Y_view = Z_view×X_view。

视点坐标系：

• 视点坐标系定义于世界坐标系中。
• 类似拍照片：
  • 照相机镜头的朝向：视线方向。
  • 照相机的位置。
  • UP 方向。

视点坐标系的交互建立：

• 坐标原点 C = (Cx, Cy, Cz)：相机的位置。

• 单位向量 N = (Nx, Ny, Nz)：镜头的朝向。

• 与 N 不平行的向量 UP：

• 得到两个向量 U = (Ux, Uy, Uz) 和 V = (Vx, Vy, Vz)，然后单位化。
• 四个矢量 C、U、V、N 组成了视点坐标系。
• 由世界坐标系到视点坐标系的取景变换，其中 (x, y, z, 1) 为世界坐标系中的点，(u, v, n, 1) 为视点坐标系中的点。

投影变换

投影分类

• 平行投影：物体坐标位置沿平行线变换到观察平面上。
• 透视投影：物体坐标位置沿收敛于某点的直线变换到观察平面。

二者的对比：

• 平行投影保持对象相关比例，立体感不强，常用于建筑和工程制图。
• 透视投影符合人类的视觉特点，不保持对象的相关比例，但立体感较好。

投影的分类图：

平行投影

正投影的投影向量垂直于观察平面，斜投影不垂直。

正投影：

• 正三面投影：三视图（正视图、俯视图、侧视图），投影平面法向量与三个坐标轴之一平行。
• 轴测正投影：显示物体多个侧面的正投影。
• 等轴测投影：投影平面与每个坐标轴的交点距原点距离相等。

斜投影：

• 斜等测投影：α 等于 45°，生成的视图。所有垂直于投影平面的线条投影后长度不变。
• 斜二测投影：投影角满足 tanα=2(63.4°) 生成的视图。垂直于投影平面的线条投影后得到一半长度。

透视投影

透视投影是一种中心投影法。

透视投影类型：

• 灭点：3D 物体的一组平行线投影后收敛于一点，此点称为灭点。
• 主灭点：3D 物体平行于坐标轴的平行线收敛产生的灭点 -> 主灭点。
• 一点、二点、三点透视。

投影中心与投影平面之间的距离为有限的，例如室内白炽灯的投影，视觉系统等。特点是产生近大远小的视觉效果，由它产生的图形深度感强，看起来更加真实。

透视投影点坐标计算：

1. 假定投影参考点在 z 轴 的（xprp, yprp, zprp)，投影平面在 zvp，直线参数方程为：

$$x_r = x - (x - x_{prp})u\\ y_r = y - (y - y_{prp})u\\ z_r = z - (z - z_{prp})u\\ u 的取值范围为 [0,1], (x_r, y_r, z_r) 代表投影线上任意点。$$

2. 投影点的 Z 坐标是 Zvp，计算 u：

$$u = (z_{vp} - z) / (z_{prp} - z)$$

3. 计算投影点的 X、Y 坐标，带入 u 即可。

透视投影变换矩阵

透视投影变换矩阵，当其中的元素（p , q , r)取非全 ０ 时，能产生透视效果。

1. 一点透视

现在来对 Ｙ 的取值情况进行讨论：

• 当 y = 0（在 X0Z 坐标平面内）：[x’ y’ z’ 1] = [x 0 z 1]。
• 当 y 趋于无穷：[x’ y’ z’ 1] = [0 1/q 0 1]。

当 Ｙ 值无限变大时，所有点经过变换后均集中于 Ｙ 轴上的 1/q 处，于是所有平行于 Ｙ 轴的直线将延伸相交于此点。该点(0，1/q，0)称为灭点。形成一个灭点的透视称为一点透视。为了取得较好的效果，取 q<0。（让灭点位于Ｙ轴的负半轴上）

2. 两点透视

如果在 p , q , r 中有两个非 ０ 元素，这时将会产生两个灭点，得到的透视图称为两点透视，或称成角透视。

3. 三点透视

以此类推，当 p、q、r 三个元素全为非 0 时，变换的结果将形成三点透视。产生的三个灭点将分别位于 Ｘ 轴上的 1/p 处、Ｙ 轴上的 1/q 处和 Ｚ 轴上的 1/r 处。此时，投影平面与三坐标轴均不平行。这时的三组平行线均产生灭点。

最后，可以简单的推断：

• 与一个坐标轴垂直的平面作为投影平面的话，该平面上的投影一定是一点投影。
• 与两个坐标轴相交且与第三个坐标轴不相交的平面作为投影平面的话，该平面上的投影一定是两点投影。
• 与三个坐标轴都相交且不含有任何坐标轴的平面作为投影平面的话，该平面上的投影一定是三点投影。

透视图的生成

1. 一点透视图

在生成一点透视图时，为了避免特殊位置透视，使产生的透视图立体感较好，通常要在进行透视变换前先将立体平移到一个合适的位置（例如离开坐标系中心)，然后再进行透视变换。

2. 两点透视图

先使立体绕 Ｚ 轴旋转一个角度 θ，以使得立体上原平行于坐标平面 XOZ 和 YOZ 的表面与投影面 XOZ 产生一定的倾斜角（成角透视），向 XOZ 投影面作透视投影。

变换矩阵：

在以上生成的变换矩阵中，有两个透视参数为非 ０（qsinθ, qcosθ)，故生成的透视图为两点透视。在两点透视图中，只有原来与 Ｚ 轴平行的立体上的棱线仍旧保持与 Ｚ 轴平行，其余的棱线（例如原来与 Ｘ 轴及 Ｙ 轴平行的棱线）将倾斜（成角）。

3. 三点透视图

类似的。先使立体绕 Ｚ 轴旋转一个角度 θ，再绕 Ｘ 轴旋转一个角度 Φ（类似于轴测变换），这样使得立体上原平行于三个坐标平面的表面均与投影面 XOZ 产生一定的倾斜角；向 XOZ 投影面作透视投影。

设备变换

在投影平面上，有一个矩形区域称为视窗。

• “视域四棱锥” 图中的矩形。
• 物体投影后：二维齐次坐标表示。

设备变换：投影后二维齐次坐标除以最后一个坐标分量 w，便得到了规格化设备坐标。

视窗变换

屏幕坐标系：通常以像素为单位。

视窗变换

• 二维变换：将定义在视窗中的规格化设备坐标转换到以像素为单位的屏幕坐标。
• 扫描转换：将连续的几何物体转换为离散的光栅表示。

三维变换流程图（牢记）

这几个变换不同的作用总结：

1. 模型变换（Model Transformation）
   • 作用：将物体从模型坐标系（物体自身的局部坐标）变换到世界坐标系。意义：确定物体在整个三维场景中的位置、朝向和大小。
   • 常见操作：平移、旋转、缩放。
   • 举例：把一个立方体从原点移动到 (3, 0, 2)，并绕 y 轴旋转 45°。
2. 取景变换（View Transformation）
   • 作用：将场景从世界坐标系变换到观察（摄像机）坐标系。
   • 意义：相当于“确定摄像机的视角”，即从哪个位置、方向去看这个世界。
   • 实质：通过移动与旋转整个世界，让摄像机位于原点并面向 -Z 方向。
   • 参数：通常由摄像机位置、目标点、上方向确定。
3. 投影变换（Projection Transformation）
   • 作用：把三维场景投影到二维平面（视平面）。
   • 分类：
     • 透视投影：近大远小，符合人眼视觉。
     • 平行投影：无透视变化，保持比例，用于工程绘图。
   • 结果：将三维点转为“规范立方体空间”（裁剪空间），为后续设备映射做准备。
4. 设备变换（Device Transformation）
   • 作用：将投影后的坐标标准化为设备坐标（NDC，Normalized Device Coordinates）。
   • 意义：将投影结果进行透视除法（除以齐次坐标 w）得到规格化设备坐标，便于硬件统一处理。
5. 视窗变换（Viewport Transformation）
   • 作用：将设备坐标映射到屏幕坐标（像素坐标）。
   • 意义：确定最终图像显示在屏幕上的具体位置与大小。
   • 最终输出：屏幕上可见的二维图像。

第六章 裁剪

本章复习重点

• 二维剪裁和三维剪裁在渲染 pipeline 中的位置。

• Cohen-Sutherland 裁剪算法。
• 中点分割算法。
• 梁友栋剪裁方法。

关于裁剪

裁剪

• 二维线裁剪。
• 二维多边形裁剪。
• 文本裁剪。
• 三维裁剪。

裁剪是确定场景或画面中位于给定区域(2D 或 3D 裁剪窗口)之内的部分。

裁剪还可用于图形反走样、隐藏线、隐藏面、阴影、纹理等算法中。

裁剪推广应用：

• 多面体对多面体的裁剪，实体造型系统中执行布尔运算。
• 在窗口系统中复制、移动或删除画面中某一部分(Cut-Copy-Paste)。

二维线裁剪

图形裁剪的策略：

• 先变换后裁剪：将图形经过扫描转换后变成像素的集合，然后对图形中的每一个像素进行裁剪。
• 先裁剪后变换：将原始图形进行裁剪，保留窗口内的可见部分，舍弃窗口外的不可见部分。然后对窗口内保留的这部分图形进行扫描转换。
• 先裁剪后变换！可以省去许多不必要的扫描转换的工作。

点的裁剪

对于一点 P(x,y)，要判断其是否可见：

$$x_{min} \le x \le x_{max}\ and\ y_{min} \le y \le y_{max}$$

满足上述不等式组的点则在窗口范围内，则保留；反之，该点落在窗口外，应裁剪。

直线的裁剪

对于矩形窗口，任何直线至多只有一段处于该窗口之内，即在此窗口范围内永远不会产生一条直线的两条或更多的可见部分线段。

基本思想是判断直线与窗口的位置关系，确定该直线是完全可见、部分可见或完全不可见，输出处于窗口内线段的端点，并显示此线段。

Cohen-Sutherland 裁剪算法

对矩形窗口的不同区域进行编码：

编码规则：

算法运行过程：

1. 若某线段两个端点的四位二进制编码全为 0000，线段位于窗口内，显示之。
2. 若对两端点的四位二进制编码进行逻辑与运算（&）结果不为 0，线段位于窗口外，直接舍弃。
3. 若线段既不能直接保留，也不能直接舍弃，它可能与窗口相交。这个时候对线段进行再分割，并找到与窗口边线的一个交点，根据交点位置，赋予 4 位二进制编码。对分割后的线段，舍弃一定在窗口外部分，另一部分做进一步检查。

求交的过程：

1. 将两个端点的编码 CtCbCrCl 进行逻辑或操作。
2. 根据其结果中 1 的位置来确定可能相交的窗口边。
3. 求交按照固定的顺序来进行（左右下上或上下右左）。
4. 一条线段与窗口最多求交 4 次。

特点：简单，易实现。依次裁剪在窗口外部分，直到直线完全处于窗口内。快速判断线段的完全可见和显然不可见，巧妙的编码方法。

中点分割算法

与 Cohen-Sutherland 裁剪算法类似，但是求交的过程不同。

中点将线段分割为两个部分，必然有一个部分存在最近可见点（交点）。保留存在最近可见点部分，舍弃另一部分。

求出中点以后，如何判断应该舍弃线段的哪个部分呢？

1. 若如果 P1 与 P 同侧，移动 P1 点；（即可能的交点只能出现在 PP2 段，此时的新线段是 PP2，相当于 P1 移动打了 P）。

1

if ( (C1 & C) != 0 ) P1 = P;

2. 若 P1 与 P 不同侧，移动 P2 点。（即可能的交点只能出现在 P1P 段）。

1

if ( (C2 & C) != 0 ) P2 = P;

3. 然后，将中点分割进行到底！最终收敛到最近可见点！

特点：

• 求交点的次数（n）与线段长度（L)有关，其关系为：L=2^n 。线段长度为 256，则求交点的次数为 8。
• **求出的交点是边界上的有效交点（最近可见点），而非边界及其延长线上的交点。**这点与 Cohen-Sutherland 算法不同。
• 使用加法和除法，硬件容易实现。

梁友栋-Barsky 裁剪算法

TODO。

二维多边形裁剪

多边形的各条边是顺次连接。

直线裁剪：

• 把一条线段的两个端点孤立考虑，会产生孤立线段。
• 裁剪之后各条边不一定能保持原来的连接顺序。

多边形可以描述为一组顶点按一定顺序连接而成的有向点列。一般可将多边形的顶点按逆时针方向顺序形成有向线段，进而连接成一个环来描述多边形的组成。数据结构上，可用链表结构来描述。

Sutherland-Hodgman 算法

每次用窗口的一条边界对多边形进行裁剪。把落在窗口外部的图形去掉，落在窗口内部的图形保留。并把它作为下一次待裁剪的多边形。连续用窗口的四条边界对原始多边形进行裁剪后，最后得到的就是裁剪后的结果多边形。

对凸多边形应用本算法可以得到正确的结果，但是对凹多边形的裁剪将显示出一条多余的直线。这种情况在裁剪后的多边形有两个或者多个分离部分的时候出现。因为只有一个输出顶点表，所以表中最后一个顶点总是连着第一个顶点。

解决这个问题有多种方法，一是把凹多边形分割成若干个凸多边形，然后分别处理各个凸多边形。二是修改本算法，沿着任何一个裁剪窗口边检查顶点表，正确的连接顶点对。三就是 Weiler-Athenton 算法。

Weiler-Athenton 算法

我们按照一个方向，将多边形和裁剪窗口的交点分成两类。一类是入点，即裁剪多边形由该点进入裁剪窗口（顺时针），如图中 a、c、e。另一类是出点，如图 b、d、f。

算法从被裁剪多边形的一个入点开始，碰到入点，沿着被裁剪多边形按顺时针方向搜集顶点序列；而当遇到出点时，则沿着裁剪窗口按顺时针方向搜集顶点序列。

按上述规则，如此交替地沿着两个多边形的边线行进，直到回到起始点。这时，收集到的全部顶点序列就是裁剪所得的一个多边形。

由于可能存在分裂的多边形，因此算法要考虑：将搜集过的入点的入点记号删去，以免重复跟踪。将所有的入点搜集完毕后算法结束。

执行过程如下：

特点：

1. 裁剪窗口可以是矩形、任意凸多边形、任意凹多边形。
2. 可实现被裁剪多边形相对裁剪窗口的内裁或外裁，即保留窗口内的图形或保留窗口外的图形，因此在三维消隐中可以用来处理物体表面间的相互遮挡关系。
3. 裁剪思想新颖，方法简洁，裁剪一次完成，与裁剪窗口的边数无关。

字符裁剪

串精度裁剪，字符精度裁剪，以及笔画象素精度：将笔划分解成直线段对窗口作裁剪，构成字符最小元素裁剪。

三维裁剪

裁剪对象：线裁剪、面裁剪。

裁剪窗口：规范的立方体、视域四棱锥。

关于三维变换与裁剪

什么时候裁剪？

1. 投影之前裁剪：三维裁剪。

优点：只对可见的物体进行投影，提高消隐效率。缺点：三维裁剪相对复杂。

2. 投影之后裁剪：二维裁剪。

优点：二维裁剪相对容易。缺点：需要对所有的物体进行投影变换。

第七章 光栅化

光栅化在三维变换流程图中的位置如下：

本章复习重点

• 区域填充算法及其递归函数实现。
• 扫描线算法中如何判断一个点是在面内还是面外。
• 分类的边表 ET 构建方法。
• 活化边链表 AEL 构建方法。
• 参考第 7 章案例。

光栅图形的基本概念

光栅图形：

• 本质：点阵表示。
• 特点：面着色，画面明暗自然、色彩丰富。
• 与线框图相比：更加生动、直观、真实感强。

图形学中多边形的两种表示方式：

1. 顶点表示：用多边形的有序顶点序列表示多边形。

优点：直观、几何意义明显、存储量小。缺点：难以判断哪些像素位于多边形内部、不能直接用多边形着色。

2. 点阵表示：用位于多边形内部的像素集合来表示多边形。

优点：便于用帧着色器（Frame Buffer）表示图形。面着色所需的图形表示。缺点：丢失几何信息、存储量大。

多边形的扫描转换：把顶点表示转换为点阵表示。从多边形的给定边界出发，求出其内部的各个像素。并给帧缓冲器中各个对应元素设置相应灰度或颜色。

区域填充

区域的表示：

1. 内部表示：把给定区域内部的像素枚举出来。
2. 外部表示：把区域边界上的像素枚举出来。

区域填充的类型：

1. 四连通区域：区域内任意两个像素，从一个像素出发，可以通过上、下、左、右四种运动，到达另一个像素。
2. 八连通区域：区域内任意两个像素，从一个像素出发，可以通过水平、垂直、正对角线、反对角线八种运动，到达另一个像素。

区域种子填充算法

假设内部表示区域为 G，其中的像素原有颜色为 G0，需要填充的颜色为 G1。算法需要提供一个种子点(x, y)，它的颜色为 G0。以四连通区域为例。

注意整个填充是一个递归的过程。考试写填充顺序的时候需要注意。

1. 内部表示区域种子填充算法

1
2
3
4
5
6
7
8
9
10
11

Flood_Fill_4(x, y, G0, G1)
{
    if (GetPixel(x, y) == G0) // GetPixel(x,y) 返回(x,y)的颜色
    {
        SetPixel(x, y, G1); // 将(x,y)的添上颜色G1
        Flood_Fill_4(x - 1, y, G0, G1);
        Flood_Fill_4(x, y + 1, G0, G1);
        Flood_Fill_4(x + 1, y, G0, G1);
        Flood_Fill_4(x, y - 1, G0, G1);
    }
}

2. 边界表示区域种子填充算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14

Fill_Boundary_4_Connnected(x, y, BoundaryColor, InteriorColor)
// (x,y) 种子像素的坐标；
// BoundaryColor 边界像素颜色； InteriorColor 需要填充的内部像素颜色
{
    if (GetPixel(x, y) != BoundaryColor && GetPixel(x, y) != InteriorColor)
    // GetPixel(x,y): 返回像素(x,y)颜色
    {
        SetPixel(x, y, InteriorColor); // 将像素(x, y)置成填充颜色
        Fill_Boundary_4Connnected(x, y + 1, BoundaryColor, InteriorColor);
        Fill_Boundary_4Connnected(x, y - 1, BoundaryColor, InteriorColor);
        Fill_Boundary_4Connnected(x - 1, y, BoundaryColor, InteriorColor);
        Fill_Boundary_4Connnected(x + 1, y, BoundaryColor, InteriorColor);
    }
}

多边形的扫描转换

逐点判断算法

逐个像素判别其是否位于多边形内部。

判断一个点是否位于多边形内部：射线法。从当前像素发射一条不经过顶点的射线，计算射线与多边形的交点个数。内部：奇数个交点，外部：偶数个交点。

问题在于速度慢，并且没有考虑像素之间的联系。最终结论是不可取。

连贯性

扫描线算法充分利用了相邻像素之间的连贯性，避免了对像素的逐点判断和求交运算，提高了算法效率。

各种连贯性：区域连贯性、扫描线连贯性、边的连贯性。

区域连贯性

区域的连贯性是指多边形定义的区域内部相邻的像素具有相同的性质。例如具有相同的颜色。

两条扫描线之间的长方形区域被所处理的多边形分割成若干梯形(三角形可以看作退化梯形)。梯形的底边为扫描线，梯形的腰为多边形的边或窗口边缘。

梯形分为两类：多边形内部（图中红色）和多边形外部（图中绿色）。两类梯形在多边形内部相间排列(相邻的两个梯形必然有一个位于多边形内部，有一个在多边形外部)。

如果上述梯形属于多边形内(外)，那么该梯形内所有点的均属于多边形内(外)。这样就把逐点判断转换成了区域判断。

扫描线连贯性

交点序列：扫描线与多边形的交点个数为偶数(1, 2, 3, 4, 5, 6)（一进一出）。

红色区间(1, 2)、(3, 4)、(5, 6)位于多边形内部。其余绿色区间位于多边形外部。两类区间相间排列。

如果上述交点区间属于多边形内(外)，那么该区间内所有点均属于多边形内(外)。这样就把逐点判断转换成了区间判断。

边的连贯性

相邻两条扫描线的 y 相差 1。相邻扫描线与多边形的同一条边的交点的关系如下：

当知道扫描线与一条边的一个交点之后，通过上述公式可以通过增量算法迅速求出其他交点。

$$\frac{y_1 - y_{11}}{x_1 - x_{11}} = k \\ x_1 = x_{11} + \frac{1}{k}$$

边的连贯性是连接区域连贯性和扫描线连贯性的纽带。

扫描线连贯性＋边连贯性＝区域连贯性

奇异点

奇异点是扫描线与多边形交交于多边形的顶点。

奇异点计为几个交点？

• 扫描线 1：一个交点。
• 扫描线 2：两个交点。

极值点：相邻三个顶点的 y 坐标满足如下条件，即相邻三个顶点位于扫描线的同一侧。

$$(y{i-1} - y_i)(y_{i+1} - y_i) \ge 0$$

非极值点则反过来，相邻三个顶点位于扫描线的两侧。

关于奇异点的处理，在极值点处，按两个交点计算，在非极值点处，按一个交点计算。

实际计算前，奇异点(非极值点)的预处理。将扫描线上方线段截断一个单位，这样扫描线就只与多边形有一个交点。

多边形扫描转换算法

核心思想(从下到上扫描)：

1. 计算扫描线 y = ymin 与多边形的交点，通常这些交点由多边形的顶点组成。
2. 根据多边形边的连贯性，按从下到上的顺序求得各条扫描线的交点序列。
3. 根据区域和扫描线的连贯性判断位于多边形内部的区段。
4. 对位于多边形内的直线段进行着色。

算法实现的数据结构：

1. 分类的边表 ET (Sorted Edge Table)：记录多边形信息。
2. 活化边链表 AEL (Active Edge List)：记录当前扫描线信息。

边的数据结构：

1. ymax：边的上端点的 y 坐标。
2. x：边的下端点 x 坐标，在活化边链表中，表示扫描线与边的交点的 x 坐标。
3. dx：边的斜率的倒数。
4. next：指向下一条边的指针。

分类的边表 ET：按边的下端点的纵坐标y对非水平边进行分类的指针数组。

1. 下端点的纵坐标 y 值等于 i 的边，归入第 i 类；
2. 同一类中，各边按 x 值(x 值相等时，按 dx 的值)递增的顺序排成行；
3. 水平边不加入分类边表中。

注意 P0 和 P4 是非极值点，所以按一个交点计算，在扫描转换的时候需要截掉底部一个像素的宽度，所以起始的坐标需要 y + 1。

活化边链表 AEL：由与当前扫描线相交的边组成。

1. 记录了多边形的边沿扫描线的交点序列。
2. 根据边的连贯性不断刷新交点序列。
3. 基本单元是边(与扫描线相交的边)。
4. 与分类边表不同：分类边表记录初始状态。活化边表随扫描线的移动而动态更新。

注意 Xcur 填入的是扫描线和当前直线的交点的 x 坐标。

算法执行过程（我们只需要掌握写 ET 和 AEL 即可）

优点：充分利用多边形的区域、扫描线和边的连贯性，避免了反复求交的大量运算。

不足：算法的数据结构和程序结构复杂。对各种表的维持和排序开销太大，适合软件实现而不适合硬件实现。

多边形的扫描转换与区域填充的比较

基本思想不同：

1. 多边形扫描转换将多边形顶点表示转换为点阵表示，扫描过程利用了多边形的各种连贯性。
2. 区域填充只改变区域的颜色，不改变区域的表示方法。填充过程利用了区域的连贯性。

对边界的要求不同：

1. 多边形扫描转换只要求每一条扫描线与多边形有偶数个交点。
2. 区域填充中，四连通区域必须是封闭的八连通边界。八连通区域必须是封闭的四连通边界。

出发点不同：

1. 区域填充：知道需要区域内一个种子点(复杂计算)。
2. 多边形扫描转换：没有要求。

第八章 隐藏面消除

消隐在三位变换流程图中的位置如下：

本章复习重点

• 图像空间算法，及其特点。
• 对象空间算法。
• Z-buffer 算法，及其优缺点。
• 如何检测后向面。
• 画家算法原理，及其特性。
• 二叉空间剖分树构建过程。
• 二叉空间剖分树遍历过程。
• Area Subdivision 算法原理。
• 有哪些常用的消隐算法。

消隐

为什么要消除不可见部分？

1. 怎加图形真实感。
2. 减少歧义。

排序：根据对象到视点的距离对场景中的对象进行排序。连贯性：区域中的像素通常表现出相似性。两者决定了消隐的效率。

按输出形式分类：隐藏线、隐藏面。

按消隐空间分类：图形空间消隐，景物/对象空间消隐。

按照不同空间分类的两种算法

注意：这里是一种类型的算法，不是某个具体算法。

图像空间消隐算法

遍历图像中的每个像素，连接像素和视点找到最近的对象，计算像素的颜色。

受分辨率限制。

时间复杂度 O(nN)：

• 每个像素都需对物体排序(能否采用连贯性)。
• n: polygons 数。
• N: 像素个数。

示例算法：z-buffer, scan line algorithm。

对象空间消隐算法

对于世界坐标空间中的每个对象，确定其不被遮挡的部分，然后使用扫描转换算法查找像素。计算像素的颜色。

适合于精密的 CAD 工程领域。

复杂度 O(n^2)：

• n: 对象数

Back surface culling(后向面剔除)。

示例算法：画家算法。

算法思想：从视点向每个像素点发射射线，并找到第一个相交平面。

后向面剔除：

V：摄像机的视线。n：面法线。

$$N \cdot V<0：不可见\\ N \cdot V>=0：可见$$

如何计算 N？面上的两个边叉乘即可。

局限性：仅适用于凸多面体。不能处理遮挡。可以被用于预处理过程。

Z-Buffer 算法（图形空间）

Frame-buffer: 存储像素颜色值(帧缓存)。

Z-buffer：存储像素的 z-coordinates。

• 投影面：z=0; 观察方向：(0,0,-1)。
• 投影类型：平行投影。
• 深度值：z-component。

在像素层级进行存储。思想是扫描多边形时，只画离视点更近的点。

算法步骤如下：

如何计算 Z-Buffer 的 Z 值？利用直线的方程计算。

优缺点：

• 复杂度：O(nN)。
• 不需要物体排序。
• 能够处理任意几何形状。
• 可以使用硬件加速。
• Z-buffer 很吃占显存。
  • 如果深度范围从 0 到 106, 一个像素点需要 24 bits。
  • 如果分辨率 is 1280×1024， z-buffer 空间需要 4 MB。
• 受限分辨率，存在走样。
• 不好处理透明物体。

能否对该算法进行加速呢？利用扫描线的连贯性。

对于每个扫描线, 构建深度分类 span。

画家算法（对象空间，背面剔除）

原理：离视点远的不会遮挡离视点近的。在景物空间确定物体的可见性顺序(离视点远近)，由远及近地绘制出正确的图像结果。

条件：场景中物体在 z 方向上没有相互重叠。

关键是如何进行可见性顺序的排序，也就是对象深度排序？

画家算法按减小最大深度的顺序对曲面进行排序。扫描转换曲面，从深度最大的曲面开始，根据重叠进行绘制。

若物体之间的 Z 值不重合，例如下面假设 Z 越大离视点越近，由于 QZmin > PZmax，那么 Q 肯定离视点更近，P 的优先级更低。

当物体间的 z 值范围重叠时：判断多边形 P 是否遮挡场景中多边形 Q，需作如下 5 个判别步骤：

1. 多边形 P 和 Q 的 x 坐标范围是否不重叠。

2. 多边形 P 和 Q 的 y 坐标范围是否不重叠。

3. 从视点看去，多边形 P 是否完全位于 Q 的背面。

4. 从视点看去，多边形 Q 是否完全位于 P 的同一侧。

5. 多边形 P 和 Q 在 xy 平面上的投影是否不重叠。

如果上述五种情况中只要有一种成立，就表明多边形 P 和 Q 是互不遮挡的，即多边形 P 的绘制优先级低于 Q。

如果上述判断都不成立，说明多边形 P 有可能遮挡 Q，此时把多边形 P 和 Q 进行互换重新进行判断，而重新判断只要对上述条件 3 和 4 进行即可。

如果 P 和 Q 交换顺序后，仍不能判断其优先级顺序，可以按如下方法处理：将其中一个多边形沿另一个物体剖分。

• 避免循环判断：P 做标记。
• 多边形剖分：将 P 沿 Q 剖分。

相互遮挡时，将其中一个多边形沿另一个多边形进行剖分。

深度排序算法有时可能将具有正确深度顺序的多边形进行剖分。

三维物体的深度排序算法适合于固定视点的消隐。

• 通过多边形的剖分，总是可以实现多边形物体在三维空间中的深度排序。
• 深度排序算法可以有效地实现透明效果。

在视点变化的场合中(如飞行模拟)，深度排序算法难以满足实时性的要求。算法复杂度 O(nlogn)。

二叉树空间剖分树算法（表面优先级）

如果场景中的多边形可以被一个平面分割成两部分，与视点同侧的物体不会被异侧物体遮挡。

对位于分割平面两侧的多边形继续进行递归分割，直至每一个分割平面两侧或一侧只有一个多边形。

分割过程可以用一个二叉树的数据结构来表示。

在 BSP 树算法中，分割平面取作场景中的多边形。

适用于视点变化场景不变的绘制。

一个切分的简单例子：如图空间 ABC 由 A、B、C 三个独立的房间组成，首先，分割平面 1 将空间分成了平面正向的 A 房间和平面负向的 BC 空间，BC 空间被 2 紧接着分割为平面 2 正向的 C 房间和负向的 B 房间。注意这里平面的方向一般由墙壁面向的方向而定。

如果有一个人处于 C 房间内，那么如何判断所有房间的遮挡顺序呢？从树根开始，由于人处于平面 1 的“后”面，所以，BC 空间应该先于 A 房间（后：先负后正），然后，由于人处于分割平面 2 的“前”面，所以，C 房间应该先于 B 房间（前：先正后负）。这样，整个房间离人由近到远的顺序就可以确定了：C－B－A。

对于由多边形面组成的物体，可以选择与多边形面重合的分割平面，利用平面方程来区分“内”、“外”多边形顶点。随着将每个多边形面作为分割平面，可生成一棵树，与分割平面相交的每个多边形将被分割为两部分。一旦 BSP 树创建完毕，即可选择树上的面并由后往前显示，即前面物体覆盖后面的物体。

另一个切分例子：

二叉剖分树的遍历：可以从后往前, 也可以从前往后(被绘制的象素不再绘制)。

例如，BSP 树的从后往前遍历：

• 视点位于分割平面的正侧，遍历顺序：负侧分支 → 根结点多边形 → 正侧分支。
• 视点位于分割平面的负侧，遍历顺序：正侧分支 → 根结点多边形 → 负侧分支。

算法优点：

• 可以处理带透明度的遮挡。
• 快：不用每个像素点都计算 Z 并检测。

第九章 真实感图形绘制

本章复习重点

• 基础的光照模型。
  • Lambert 漫反射模型构成。
  • Phong 镜面反射模型构成。
  • Whitted 整体光照明模型构成。
• 基础的明暗处理模型。
  • Flat Shading。
  • Gouraud Shading。
  • Phong Shading。
• 光线跟踪算法步骤。
• 光线树生成过程。
• 终止条件。
• 光线跟踪的 4 类光线。
• 包含阴影的 phone 模型。
• 光线跟踪加速技术：包围盒技术，空间分割技术。
• 纹理分类。
• 纹理的两种映射方法。
• 常用纹理反走样方法：前置滤波方法，超采样方法，Mipmap 方法。
• Mipmap 映射方法原理。
• 常用的三维纹理：凹凸映射，法向映射，位移映射，及其原理。
• 辐射度系统方程。
• 辐射度算法流程。
• Gathering 方法与 Shooting 方法的区别。
• 本影与半影的区别。
• Depth Fail 计算方法。
• Depth Pass 计算方法。

引言

目的是让计算机生成如同照片般真实的图像。步骤如下：

1. 建立几何模型，确定景物表面的光照属性。
2. 进行取景变换，将物体投影到二维平面上。
3. 采用消隐算法剔除当前视点处不可见的场景表面。
4. 根据光照明模型，计算在可见场景表面的光亮度。

光照明模型

影响物体表面光照明效果的因素：

• 光源。
• 观察点位置。
• 物体表面局部几何形状。
• 表面朝向。
• 材料属性。

光照明模型考虑物体表面上每一个点所代表的微小面元受到来自光源或周围环境光线的照射而产生的反射或透射光亮度。

最常用的光照明模型：

• 泛光模型。
• Lambert 漫反射模型。
• Phong 镜面反射模型。
• Whitted 整体光照明模型。

泛光模型

最简单的光照明模型。试图刻画周围环境反射光对物体表面照明贡献。照明效果如下：

假定环境反射光沿任何方向对任何物体表面入射的光亮度都相等。

Lambert 模型（考虑漫反射）

直接光源对物体表面的照射有方向性。物体表面的反射光分为：漫反射光、镜面反射光。

纯漫射表面只产生漫反射，例如地面、树木等。

漫反射光是物体表面对入射光线朝各个方向的均匀反射。大小只与入射光的光亮度和入射方向有关，与漫反射光的反射方向无关。

漫反射光亮度和光源入射角（入射光线和表面法向量的夹角）的余弦成正比。

计算 cosα。

Lambert 光照模型：考虑上漫反射及泛光反射分量。

模型效果对比：

光传播计算模型

**光的强度与距离 d 的平方成反比。**当 d 为极限值时，光的强度改变得太快，导致不同的物体的明暗差别太大。通常使用 d 的线性或是二次函数的倒数来实现光强度的衰减。

Phong 模型（考虑镜面反射）

镜面反射光：一种朝向一定方向的反射光，它遵从光的反射定律。

**在靠近反射光方向上仍然可以观察到反射光，形成了反射光方向周围的一个高光区。**这与物体表面粗糙度有关系。

Phong 采用余弦函数的幂次来模拟镜面反射光。

镜面反射方向的计算。

Blinn-Phong 模型（对 Phong 的改进）

Phong 模型中计算反射光线的向量是一件相对比较耗时的任务，因此 Blinn-Phong 对这一点进行了改进。

定义虚拟镜面法向 H。

Phong 模型综合了综合了漫反射、镜面反射及泛光反射分量。

Whitted 模型（考虑光线在物体之间的相互反射和投射）

局部光照明模型的局限：

• 仅考虑从光源直接发出的光线对物体表面光亮度的贡献。
• 没有考虑光线在物体之间的相互反射和透射。

Whitted 模型是整体光照明模型。可模拟现实世界中景物表面之间的镜面反射和透射现象。

从某一观察方向 V 所观察到的物体表面某点 P 的光亮度的贡献来自于三个方面：

• 由光源直接照射引起的反射光亮度 Ic。
• 镜面反射光。
• 规则透射光。

Whitted 整体光照明模型：

进一步完善

光照明模型分类：

1. 基于经验的简单光照明模型。
   • Phong 模型。
2. 基于物理的光照明模型。
   • Blinn 模型。
   • Cook-Torrence 模型。
3. 双向反射率函数（BRDF）模型。

多边形物体的明暗处理

在计算机图形学中，场景中的许多物体都采用多边形表示。

三类常用的明暗处理（Shading）方式：

• Flat Shading
• Gouraud Shading
• Phong Shading

Flat Shading

方法：

• 依据局部光照明模型按每一个多边形的法向计算出一个颜色值 C。
• 将 C 赋给该多边形在屏幕上的投影所覆盖的全体像素。

优缺点：

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

Gouraud Shading

方法：

• 为多边形物体的每一个顶点赋一个法向量。
• 利用局部光照明模型计算每一顶点处的光亮度。
• 多边形内部各点处的光亮度值通过对多边形顶点处的光亮度的双线性插值得到。

Gouraud 明暗处理法举例：

Gouraud Shading 又称光亮度插值明暗处理。

优缺点：

• 简单快速，所生成的图形在真实感上较 Flat Shading 有了较大的提高。
• 马赫带效应依然存在。
• 不能正确模拟高光。

Phong Shading

方法：

• 为多边形物体的每一个顶点赋一个法向量。
• 多边形内部各点处的法向量则通过对多边形顶点处法向量的双线性插值得到。
• 利用 Phong 模型计算每一点的光亮度。

总结

Gouraud 和 Phong 的明暗处理方法在处理静态画面时可以得到很好的效果。

处理动画显示时：当画面逐帧更新时，明暗变化太快。

因为是对投影后的图形而不是对原始空间中的三维物体本身的图形进行明暗处理。

因此用这两种方法得到的处理结果都不具备对物体旋转的不变性。

光线跟踪算法

光线跟踪算法是迄今为止最为成功的生成真实感图形算法之一。

• 算法简单。
• 生成的图形真实感强。
• 计算量大。
• 其前身是光线投射（Ray Casting）算法。

光线传播方式很复杂，如果按照光照路线去计算效果，计算过程会非常复杂。因此，我们采用由视线出发求出视线与其他物体或光源的关系。

算法原理

对屏幕上每一像素，执行下述 3 步操作：

1. 从视点出发通过该像素中心向场景发出一条光线，并求出该条光线与场景中物体的全部交点。
2. 将各交点沿光线方向排序，获得离视点最近交点。
3. 依据局部光照明模型计算该交点处的光亮度，并将所得光亮度值赋给该像素。

当所有屏幕像素都处理完毕时，即得到一幅真实感图形。

下面具体说明一下：

1. 从视点出发通过该像素中心向场景发出一条光线，并求出该条光线与场景中物体的全部交点。

2. 将各交点沿光线方向排序，获得离视点最近交点。

回顾 Whitted 模型：

对于屏幕上的每个像素，执行一下 4 个步骤：

1. 从视点出发通过该像素中心向场景发出一条光线 R，并求出 R 与场景中物体的全部交点；获得离视点最近交点 P；并依据局部光照明模型计算 P 处颜色值 Ic (光线投射)。
2. 在 P 处沿着 R 镜面反射方向和透射方向各衍生一条光线。若点 P 所在表面非镜面或不透明体，则无需衍生出相应光线。
3. 分别对衍生出的光线递归地执行前面步骤，计算来自镜面反射和透射方向上周围环境对点 P 光亮度的贡献 Is 和 It。
4. 依据 Whitted 光照明模型即可计算出点 P 处的光亮度，并将计算出的光亮度赋给该像素。

光线树

树的结点代表物体表面与跟踪线的交点。结点连线代表跟踪线。每个结点的左儿子代表反射产生的跟踪线（r），右儿子代表透射产生的跟踪线（t)。空箭头表示跟踪线射出场景。P0 处的光强是 P0、P1、P2、P3 点光强的合成。计算方法是以后序算法遍历这颗光线跟踪树。在每一结点处，递归调用光照模型，算出跟踪射线方向的光强，并按两表面交点之间的距离进行衰减后，传递给父结点。如此上递，最后得出 P0 点处的光强，亦即得到屏幕象素处的亮度。

一个例子如下：

对于树上任一结点 Pi 所受到的光照，除了光照模型中的漫射光源 Ipd、直射光源 Ips、透射光源 Ipb 之外，还有左儿子结点传来的光强 Ir（反射跟踪线传来的光强），和右儿子结点传来的光强 It（透视跟踪线传来的光强）。设前三种光源（Ipd、Ips、Ipb）使得 Pi 沿着跟踪线射回的光强为 IC。Is 沿着跟踪线在 Pi 点射的回光强主要由 Pi 点的镜面反射系数所控制，强度为 Ks × Is。因为跟踪线 V 正在 Ir 之反射线上。It 在 Pi 处射出的光强为 Kt × It。

综合起来，Pi 处沿视线方向 V 射去的光强 I 为：

$$I = I_C + K_s * I_S + K_t * I_t$$

递归终止条件

1. 光线与环境中任何物体均不相交，或交于纯漫射面。
2. 被跟踪光线返回的光亮度值对像素颜色的贡献很小。
3. 已递归到给定深度。

伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

main() // 主函数
{
    for (需要计算颜色的每一像素pixel)
    {
        确定通过视点V和像素pixel的光线R;
        depth = 0;   // 递归深度
        ratio = 1.0; // 当前光线的衰减系数，1.0表示无衰减
        // color是经计算后返回的颜色值
        RayTrace(R, ratio, depth, color);
        置当前像素pixel的颜色为color;
    }
} // 主函数main( )结束

RayTrace(R, ratio, depth, color) // 说明：光线跟踪子函数
{
    if (ratio < THRESHOLD)
    { // 终止条件2
        置color为黑色； return;
    }
    if (depth > MAXDEPTH)
    { // 终止条件3
        置color为黑色； return;
    }

    光线R与场景中的所有物体求交。若存在交点，找出离R起始点最近的交点P；

    if (交点不存在)
    { // 终止条件1
        置color为黑色； return;
    }
    用局部光照明模型计算交点P处的颜色值，并将其存入local_color；

    if (交点P所在的表面为光滑镜面)
    {
        计算反射光线Rs;
        // 递归调用！
        RayTrace(Rs, ks * ratio, depth + 1, reflected_color);
    }
    if (交点P所在的表面为透明表面)
    {
        计算透射光线Rt;
        // 递归调用！
        RayTrace(Rt, kt * ratio, depth + 1, transmitted_color);
    }

    依照Whitted模型合成最终的颜色值，即：
        color = local_color + ks * reflected_color +
                kt * transmitted_color；

    return;
} // 光线跟踪子函数 RayTrace() 结束

关键问题

1. 光线怎么和物体求交点？
2. 镜面反射如何计算？
3. 折射如何计算？
4. 如何处理阴影？

光线的表示

一般用直线的参数方程进行表示：

$$R(t) = P+tD\\ \\ P: 起始点。\\ D: 方向，单位矢量。\\ 一般在世界坐标系中进行计算。\\ t = 0表示为光线起点，即点 P。\\ t > 0表示在光线的正方向。\\ t < 0表示在光线的负方向，此时交点为无效交点。$$

光线与物体的求交

光线方程：R(t) = P + tD。

物体表示：

• 函数表示： f(X) = 0。
• 参数表示： X = g(u, v)。

计算交点：将光线方程待入曲面方程，求根。

• 隐函数表示：f(P + tD) = 0。一个方程一个未知数，单变量求根。
• 参数表示 P + tD - g(u, v) = 0。三个方程三个未知数（t, u, v），多变量求根。
• 多数时候需要采用数值求解。会遇到计算量大、误差累积、甚至不收敛等问题。

光线与球相交

光线与三角形相交

思路：光线与三角形所在平面求交点。若存在，判断交点是否在三角形的内部。

第一步：

第二步：

镜面反射方向计算

P 为入射光线 L 和物体的交点；N 为点 P 处的物体表面法向；Rr 为镜面反射光线的方向。θi 为 L 与 N 的夹角；θr 为 Rr 与 N 的夹角。

由光线反射定律知道，θi＝θr。假设 L，N 均为单位矢量，Rr = L - 2(L·N)N。

透视方向计算

P 为入射光线 L 和物体的交点；N 为点 P 处的物体表面法向 Rt 为透射光线的方向。

折射定律：位于折射率为 η1 的介质 1 中、与表面法向 N 的夹角为 θ1 的入射光线 L，在进入折射率为 η2 的介质 2 后，将产生折射，其折射方向 Rt 与 N 的夹角为 θ2，且有 η1sinθ1 ＝ η2sinθ。

阴影计算

从 P 出发向光源 L 发射一条阴影测试光线 R，若 R 在到达 L 的途中与场景中的物体不相交，则点 P 受光源 L 直接照射。反之，点 P 被位于它与光源 L 之间某一物体所遮挡，若遮挡物为不透明体，则点 P 位于光源阴影之中。

包含阴影计算的 Phong 模型：

产生颜色

前面的光照模型仅用于白光，只能产生灰度。

彩色模型计算：选择合适模型（如 RGB、HSV 等），为颜色的三个分量分别建立光照方程。

RGB 模型：

• 光源的颜色 [IpR, IpG, IpB]，环境光的颜色 [IaR, IaG, IaB]。
• 表面反射系数
  • 环境反射：[KaR, KaG, KaB]
  • 漫反射：[KdR, KdG, KdB]
  • 镜面反射：[KsR, KsG, KsB]

彩色光照方程（模型）：

光线跟踪中的四类光线

1. Eye rays：从视点发出。
2. Shadow rays：从物体表面上的点向光源发出。
3. Reflected rays：从物体表面上的点沿镜面反射方向发出。
4. Refracted rays：从物体表面上的点沿透射方向发出。

优缺点

它不仅考虑到光源的光照，而且考虑到场景中各物体之间彼此反射的影响，因此显示效果十分逼真。

有消隐功能：采用光线跟踪方法，在显示的同时，自然完成消隐功能。

有影子效果：光线跟踪能完成影子的显示，

该算法具有并行性质：每条光线的处理过程相同，结果彼此独立，因此可以大并行处理的硬件上快速实现光线跟踪算法。

光线跟踪算法的缺点是计算量非常大，因此，显示速度极慢。

反走样

引起走样的原因：光线跟踪算法本质上是对画面的点采样。

反走样处理方法：

• 超采样。
• 自适应超采样。

光线跟踪加速技术

常用加速技术：

• 包围盒技术。
• 空间分割技术。

包围盒技术

原理：

• 将场景中的所有表面按其空间位置关系分层次组织成树状结构。

  • 根结点：整个场景。

  • 中间结点：空间位置较为接近的一组表面。

  • 叶结点：单个景物表面。

• 每一结点中的表面或表面片集合都用一形状简单的包围盒包裹起来。

• 当光线与包围盒有交时，才进行光线与其中所含的景物面片求交运算。光线与包围盒不相交，必定不与其中所含的景物面片相交。

常用包围盒：包围盒、包围球、包围圆柱、平行 2n 面体。

空间分割技术

原理：

• 将景物空间分割成一个个小的空间单元。
• 被跟踪的光线仅与它所穿过空间单元中所含物体表面进行求交测试。
• 利用相邻空间单元的空间连贯性，使光线快速跨越空单元，迅速到达非空单元，求得光线与景物的第一个交点。

典型方法：

• 均匀网格。
• Kd 树。
• BSP 树。
• 四叉树（二维）/八叉树（三维)。

纹理映射

传统光照明模型仅考虑表面法向的变化，且假设表面反射率为一常数，因而只能生成颜色单一的的光滑景物表面。通过纹理映射技术可以解决这个问题。

纹理（texture）通常指物体的表面细节。纹理贴图是一个用图像、函数或其它数据源来改变表面在每一处的外观的过程。

例如，我们不必用精确的几何去表现一块砖墙，而只需把一幅砖墙的图像贴到一个多边形上。除非观察者非常靠近墙，否则我们并不会觉得缺少几何细节。既节省了大量的造型工作量，也节省了内存空间，加快了绘制速度。

纹理生成过程实质上是将所定义的纹理映射为反映某种三维景物表面的属性，并参与后续的光照明计算。

表面属性：与光照明模型及表面几何有关的各种参数，如表面法向、漫/镜面反射率等。

景物表面的纹理属性主要有以下几种：

1. 表面颜色，色彩分布。即表面的反射率；例如漫反射和镜面反射分量，即表面的镜面反射率；
2. 透明度；
3. 表面法向，即挠动表面法向来产生表面的凹凸纹理；
4. 环境的漫反射和镜面反射效果；
5. 光源强度和色彩。

纹理分类

根据纹理定义域的不同，纹理可分为：

• 二维纹理。
• 三维纹理。

基于纹理的表现形式，纹理又可分为：

• 颜色纹理。
• 几何纹理。
• 过程纹理。

两类最常用的纹理：颜色纹理、三维/几何纹理。

确定表面上颜色纹理的两个步骤：

1. 预先建立表面的纹理模型。
2. 纹理映射：建立表面上的每一点和一已知图像上的点的对应关系，取图像上相应点的颜色值作为表面上各点的颜色值。

实际纹理非常复杂，难以解析描述。采用图象来描述表面纹理细节。

纹理映射

采用景物表面的参数化表示来确立表面的纹理映射坐标，即可实现纹理图像在景物表面的映射。

• 景物表面参数化表示为 f(u，v)。
• 纹理图像表示为 T(s，t)。
• 建立景物表面参数空间 (u，v) 和纹理图像参数空间 (s，t) 之间的一一对应关系。

两种映射方法：纹理扫描和像素次序扫描。

纹理扫描

将纹理模式映射至物体表面，然后再进行投影变换映射至投影平面，称为纹理扫描。

纹理扫描通常用线性函数进行纹理映射变换，实现纹理空间到物体空间的映射。

不利因素：选中的纹理表面常常与像素边界不匹配，需要进行像素分割计算。因此像素次序扫描方法成为最常用的纹理映射方法。

像素次序扫描

将投影平面的像素区域映射至物体表面，再映射至纹理空间，称为像素次序扫描。

之所以叫投影映射，是因为主要有两种方法可以将三维的空间坐标点转化为二维的纹理坐标点：Projector 和 UV Mapping。

对于一些简单的几何体，通常用投影的方式，例如这种将矩形地图纹理均匀贴到球表面的投影。Projector 只适用于简单情况，对于更复杂的几何体贴图，往往需要用到 UV Mapping：用于将 3 维模型中的每个顶点与 2 维纹理坐标一一对应。UV map 则需要建模师精心制作。例如下图所示的 Uvmapping。像素次序扫描将一个像素映射到物体表面一个区域，再投影到纹理数据的一个区域获得具体的颜色数据。具体的运算就是前面已经讲过的投影变换，坐标系变换。

思考

纹理采样方式

若投影得到的象素数目比原始纹理大，则需要把纹理图像放大(magnification)。

若投影得到的象素数目比原始纹理小，则需要把纹理图像缩小(minification)。**当纹理图像缩小时，多个纹素可能覆盖一个象素单元。**为了得到每个象素正确的颜色，应该综合考虑影响该象素的那些纹素。

有三种办法：

• 最近邻域法：选择在象素中心可见的纹素。但会引起严重的走样现象，见上图。当这类表面相对视点移动时，走样现象更加明显，称为时间走样（temporal aliasing）。
• 双线性插值：效果仅比最近邻域法稍好，也会引起较严重的走样现象。
• Mipmap 方式：对纹理进行预处理，建立多个纹素覆盖单个象素的快速逼近计算的数据结构。这样，一个采样点可以检索出一个或多个纹素的效果。

纹理重复方式

• wrap or tile：纹理图像在表面重复。例子：地上的大理石贴图。
• mirror：纹理图像在表面重复，但每隔一幅进行翻转(flipped)。这样在纹理的边界处，纹理可以保持连续。
• clamp：把 [0,1) 范围之外的进行截断。截断到 [0,1) 内的半个纹素。
• border：参数范围在 [0,1) 之外的用单独定义的边界颜色或把纹理的边作为边界。用于在表面上印花样，地形绘制中相邻纹理的缝合。截断到 [0,1) 外的半个纹素。

纹理与背景的叠加融合

• Replace：把原来表面的颜色替换为纹理的颜色。
• Decal(印花)：与替换类似，但是若纹理中包含 Alpha 值，则用它与表面的颜色进行混合。
• Modulate(调节)：把表面的颜色与纹理颜色相乘。

纹理反走样

常用纹理反走样方法：

• 前置滤波方法。
• 超采样方法。
• Mipmap 方法。

前置滤波方法

• 确定屏幕像素 P 上可见的景物表面区域 A。
• 将区域 A 直接映射到纹理空间区域 T。
• 取区域 T 内的所有纹理像素颜色值的平均作为景物表面区域 A 的平均纹理颜色。
• 代入光照明模型，计算出像素 P 应显示的光亮度值。

超采样方法

• 将屏幕像素 P 的四个角点分别映射到纹理空间，得到四个纹理像素值。
• 将上述四个纹理颜色值取平均作为像素 P 所对应的可见表面区域的纹理颜色。

Mipmap 方法

目前应用最广的纹理反走样算法之一。

1. 预处理：生成一个由不同分辨率图像构成的纹理图像序列。

从原始纹理图像出发，生成一个其分辨率为原始图像 1/4 的新的纹理图像版本。新版本中的每一个像素值取为原始图像中相对应的四个像素颜色值的平均。类似地基于所得到的新纹理图像版本生成一个更低分辨率的、尺寸更小的纹理图像版本。这一过程一直持续到最后生成的纹理图像仅包含一个像素为止。

2. 映射阶段：屏幕上的每一像素内的可见表面区域被映射到原始纹理图像上的一块区域。估计该区域所覆盖的原始纹理图像中像素的个数并以此作为选取适当分辨度的纹理图像版本的一种测度。

从预先构造的纹理图像序列中找出其压缩率最接近当前纹理像素与屏幕像素比率的两个纹理图像。在相邻分辨率的两纹理图像上计算当前屏幕像素映射点的纹理颜色值。根据两纹理图像对原始图像的压缩率在所得到的两个纹理颜色值间取加权平均，作为当前屏幕像素可见表面区域的颜色值。

三维纹理映射技术

二维纹理映射技术的缺陷：

1. 在一般情况下，由纹理平面至景物表面的映射是一种非线性映射，在曲面上曲率变化较大的区域可能发生纹理的非均匀变形，导致不真实的视觉效果。
2. 对具有非平凡拓扑（由多个曲面拼接而成）的景物表面进行二维纹理映射时，很难保证相邻曲面片间纹理的连续性。

解决方案：三维纹理映射技术、优化纹理映射技术。

三维纹理映射技术：纹理直接定义于三维空间中。映射变成是一个简单的嵌入映射。通过过程纹理合成生成三维纹理。

常见的三维纹理：

1. 凹凸映射（bump mapping）：在不改变物体宏观几何的前提下，模拟物体表面粗糙的、褶皱的、凹凸不平的光照效果。

凹凸纹理的基本思想是：用纹理去修改物体的法向而不是颜色。物体表面的几何法向保持不变，我们仅仅改变光照明模型计算中的法向。

方法如下：

2. 法向映射（normal mapping）：利用法向纹理保证高质量的表面细节复现。

借助低精度模型和一个法向纹理，获得高精度模型的绘制效果。先计算高精度模型的法向，保存在法向纹理中，再将法向纹理映射到低精度模型上进行光照计算。

3. 位移映射（displacement mapping）：利用纹理改变物体表面上点的几何位置，获得很强的深度感和细节。

依据与表面上点所对应的纹理值，沿表面法向偏移该点的几何位置。能产生很强的深度感（自遮挡、自阴影、轮廓），但相比凹凸映射、法向映射，计算代价大。

纹理优化处理技术

纹理缓存（Texture Caching）

复杂的应用需要相当多的纹理, 不一定把所有的纹理都一次性送到显存。

有多种纹理高速缓存技术，在速度和内存中的纹理数目之间取得平衡。例如：当贴了纹理的多边形离视点较远时，可只载入需要的子纹理。

使用纹理内存的一般原则：

• 尽量使用较小的纹理。
• 尽量使相同的纹理多边形成组。
• 采用 Tiling 或者 Mosaicing 技术：把一些小纹理拼成一块大纹理，这样可以避免纹理的切换，加快存取的速度。

纹理压缩

一个直接针对纹理内存和带宽的解决方法是固定速率的纹理压缩（fixed-rate texture compression)。

通过硬件即时对压缩的纹理进行解压，所需的纹理内存可减少，从而增加了有效 Cache 的大小，同时减少了带宽需要。

环境映照

这一技术的雏形是为近似模拟光线跟踪的效果而又不必去跟踪反射光线而设计的。原因是光线跟踪计算量太大了。在低硬件条件下，光线跟踪要实时计算比较难以实现。这种技术中将视点移动到物体的中心处，然后将环境图贴图到物体上。纹理图像通过正投影观察一个纯反射球面的外形来得到，故得到的纹理称为球面图(sphere map)。将几何体参数化到一个球上, 然后进行映射。

当前象素内可见景物区域的平均纹理属性：

纹理图像通过正投影观察一个纯反射球面的外形来得到，故得到的纹理称为球面图(sphere map)。

立方体环境映照通过把摄像机置于立方体的中心，然后把环境投影到立方体的面上。立方体上的图像作为环境图。

辐射度方法

辐射度技术概述

直接照明效果。

艺术家在此场景中精心放置了三类光源以模拟真实的光照效果：

聚光灯：能产生阴影，置于窗外。

泛光：缺少泛光，房间内所有可见但未被光源直接照射的表面会是全黑的。

点光源：不产生阴影，可减弱泛光产生的“平板”效果。

辐射度效果。

采用辐射度算法绘制，光效未经艺术家特别处理。场景中仅包含一个面光源，即放置于窗外的天空。与直接照明效果相比，主要区别在于：

• 房间有发光效果。
• 地板上软影清晰可见，房间周围可观察到细微的光效。
• 地毯上的红色辉映到灰墙上，产生淡淡的温暖的感觉。

辐射度技术原理：

• 光是一种辐射能，在一个封闭环境中，场景中的光能经过表面之间的反射和透射，最终达到平衡状态。
• 场景中各表面的光亮度实际上是场景中光能分布的反映。
• 前提：针对理想漫射环境。

什么是辐射度：**单位时间内从物体单位表面积向外辐射的光能。**包含两部分：

• 物体作为光源自身向外发出的能量。
• 物体表面接受来自周围场景表面传递给它的能量后，再次反射出去的部分。

辐射度方法

基本前提：

1. 光源和普通物体之间没有区别。
2. 场景中的一个表面被它周围的所有可见的表面所照亮。

简单地说，辐射度算法就是：把场景细分到很细很细的面片(如 1 个像素那么大的三角形)，分别计算它们接受和发出的光能，然后逐次递归，直到每个面片的光能数据不再变化（或者到一定的阀值）为止。因此，计算量很大（要计算很多次），而且难以并行（因为递归）。

优点：

• 非常真实的漫反射表面光照。
• 概念简单，容易实现。
• 能够容易地使用 3D 硬件加速计算。

缺点：

• 慢。
• 不能很好地处理点光源。
• 也不能处理有光泽的表面。
• 总是过于复杂而且很少在书本中解释。

辐射度系统方程

根据辐射度的思想，将场景中的每个物体的表面分解为互不重叠的小面片（patch），Ai（i = 1, 2, 3…）。

• 前提：假设每一小面片的辐射度和漫反射率均为常数。
• 小面片大小可以不一致，一般分解为方形，也有分解为三角形等其他形状的。

辐射度计算中的几个定义：

方程的推导过程如下：

矩阵形式：

辐射度系统方程实例

矩阵形式：

辐射度算法流程图

表面分割

均匀网格化。

自适应网格化。

形状因子计算

方程求解

理论上说，辐射度系统方程可采用任何一种线性方程组的求解算法来求解。

直接求逆：高斯消去法(Gauss elimination)。

迭代法：

• Gauss-Seidel 迭代—Gathering。
• Southwell 迭代—Shooting。

Gathering：对于每一面片，收集场景中其它面片对它辐射的光能，更新该面片的辐射度。

Shooting：选取辐射源面片（具有最大待辐射光能），将其辐射光能发送到其他面片，更新各面片的辐射度。选取新的辐射源面片。

逐步求精辐射度算法：

• 通过迭代过程求解辐射度方程。
• 每次迭代相当于一次光能传递过程。
• 每次迭代后，采用场景中各面片的当前辐射度值绘制整个场景。
• 经过多次迭代后，各面片的辐射度值逐渐逼近方程组的解。
• 可用于对场景进行交互预览。

辐射度和光追对比

辐射度方法能很好的解决光能传播。

• 处理漫反射。
• 无法处理镜面反射。
• 图像是视点独立的。

光线跟踪反应的是光线复杂的反射行为。

• 对于镜面表面表现很好。
• 漫反射光线反射到各个方向光线跟踪无法抓住所有方向光线。
• 必须使用环境映照来替换缺失的扩散。

阴影

阴影可以反映物体之间的相对位置，增强场景的立体感和层次感。

阴影是由于物体截断了光线而产生的，如果光源位于物体的一侧，阴影总是位于物体的另一侧，也就是与光源相反的一侧。

本影和半影

场景中的一个点 P，如果它不被光源的任何一部分所照射到，就称为在本影区里。本影就是不被任何光源所照到的区域。

半影是指只有部分光线到达的区域。

在单点光源的照射下，阴影分为自身阴影与投射阴影。一部分是由于物体自身的遮挡而使光线照射不到它的某些表面产生自身阴影；另一部分是由于不透明的物体遮挡光线使得位于物体另一侧的区域受不到光照而形成投射阴影。

阴影计算方法

一般有三种：

• Planar Shadow
• Shadow Mapping
• Shadow Volume

Planar Shadow 类似投影，计算最简单，缺点只能绘制抛射在平面上的阴影。

Shadow mapping 利用站在光源处所沿光源法线看去所生成的深度图来检测场景中的体象素是否处于阴影中，缺点是光源与物体位置相对固定、且在极端情况下计算精度差，不太适合精确到象素的动态光阴场合。

Shadow Volume 是目前最适合精确表现动态光阴场景的技术，适用性最广。

Planar Shadow

Planar Shadow 的思想很简单，根据光源和投影面位置推导一个投影矩阵，通过这个矩阵能把模型上所有顶点投射到投影面（比如地面）上，也就是将渲染物体压扁到一个平面上。

地面如果不平整，影子就会穿插到地表以下。

Shadow Mapping

绘制自身阴影与投射阴影图形的算法如下：

1. 根据视点原来的观察位置，对物体实施隐面算法，使用正常的光照模型计算光强来绘制可见表面。
2. 将视点移到光源的位置。从光源处向物体所有背光面投射光线，建立光线的参数方程，计算该光线与投影面（地面）的交点，使用深灰色填充交点所构成的阴影多边形，形成投射阴影。若选用简单光照模型，对于背光面，由于得不到光源的直接照射，只有环境光对其光强有贡献。

Shadow Volume

Shadow Volume 的一般步骤为：

1. 生成阴影体积（Mesh）。
2. 阴影渲染。

只有处于 shadow volume 里面的物体才会受阴影的影响。

优点：

• 全方位方法。
• 视窗空间的阴影确定。
  • 阴影精确到像素。
  • 超采样是可行的。

缺点：

• 仅适合理想光源。

  • 适用于点光源和直接光源。

  • 不适用区域光源和 soft shadows。

• 要求多边形是连接封闭的。

  • 模型必须是闭合的 (2-manifold)。

  • 不适用非平面多变形。

• 需要轮廓计算。

  • 大量 CPU 计算。

  • 动态场景计算量大。

阴影体积算法背后的想法是将光线减弱时创建的对象轮廓扩展到一个 Volume 中，然后使用一些简单的模版操作将该 Volume 映射到模板缓冲区中。关键的想法是，当一个对象在 Volume 内（因此在阴影中）时，Volume 前面的多边形会对对象的多边形进行深度测试，并且该 Volume 后部的多边形将相同的测试，或者说不参与测试。

• ZPass
• ZFail

Depth Pass 算法

ZPass：

1. 先关闭光源，将整个 scence 渲染一遍，此时一片漆黑，但获得了深度值 depth map（注意是以真实视点作为视点得到的）。
2. 关闭深度写，然后渲染所有的 shadow volume，渲染阴影体的正面（既面对视点的这一面），如果 depth test 的结果是 pass, 那么和这个象素对应的 stencil 值加 1。如果 depth test 的结果是 fail, stencil 值不变。
3. 然后渲染阴影体的背面，深度测试通过则模板值减 1。
4. 最后模板值不为 0 的面就在阴影体中，开启深度写。
5. 用模板手法重新渲染一次加光的 scence 即可，让阴影部分为黑色。

算法过程：

1. 初始化 depth buffer。Depth values 指出了最近的可见面片（消隐）。
2. 使用 stencil 进出计数方法。
   • 用面消隐算法画 shadow volume 两次。
     • 1st pass: 渲染前面并当深度测试通过时计数增。
     • 2nd pass: 渲染背面并当深度测试通过时减一。
   • 不更新深度和颜色。
3. 后续, 像素的 stencil 非零，像素在阴影中，否则如果是零则不在阴影中。

例子：

现在假设我们要计算这个蓝色的物体的 stencil 值，我们从视线引射线到达物体的最近面。这条视线要穿过部分 shadow volume。在本例中是穿过了所有的 shadow volume。那么首次检测每个 shadow volume 的前面，三条红色虚线。根据深度值，可以看到所有的 shadow volume 的前面，相对视点靠前的面都在物体之前，都位于物体之前，物体没有遮挡任何一个 shadow volume 的前面。因此对每一个 shadow volume 的前面进行通过测试，都通过。因此每个从左向右，第一个 shadow volume 前面测试通过，stencil 值加 1，此时 stencil 值为1，检测第二个 shadow volume 前面测试通过，stencil 值加 1，此时 stencil 值为 2，检测第二个 shadow volume 前面测试通过，stencil 值加 1，此时 stencil 值为 3。然后进行后面的检测，三条绿色虚线。同样物体在三个 shadow volume 后面的后面。因此三次后面检测也通过。检测第 1 个 shadow volume 后面测试通过，stencil 值减 1，此时 stencil 值为 2。检测第 2 个 shadow volume 后面测试通过，stencil 值减 1，此时 stencil 值为 1。检测第 3 个 shadow volume 后面测试通过，stencil 值减 1，此时 stencil 值为 0 。由于 stencil 值为 0，因此物体不在阴影范围中。

图中有三个可能遮挡阴影的物体。三条红色虚线是前面的光线，三条绿色虚线是后面的光线。

ZPass 的过程是，从视点开始往物体扫，遇到红色虚线加 1，绿色虚线减 1，直到到达物体。

Z-PASS 算法在视点位于阴影锥内或者跟近裁剪面相交时，会得到错误的 stencil values，如下图所示：

Depth Fail 算法

ZFail：

1. 先关闭光源，将整个 scence 渲染一遍，获得深度值。
2. 关闭深度写，渲染阴影体的背面，深度测试失败则模板值加 1。
3. 渲染阴影体的正面，深度测试失败则模板值减 1。
4. 最后模板值不为 0 的面便处于阴影体中，开启深度写。
5. 用模板手法重新渲染一次加光的 scence 即可，阴影部分不渲染色度。

算法过程如下：

1. 渲染场景初始化 depth buffer。
   • 深度值指示最近的可见面片。
2. 使用 stencil 进出计数方法。
   • 用面消隐画 shadow volume 两次。
     • 1st pass: 渲染背面并当深度检测失败时加 1。
     • 2nd pass: 渲染前面并当深度检测失败时减 1。
   • 不更新深度和颜色。
3. 然后, 像素的 stencil 值非零则像素在阴影中, 如果为零则不在阴影中。

ZFail 和 ZPass 几乎相反。过程是，从物体开始往视点反方向扫，遇到绿色虚线（物体后面）加 1，红色虚线（物体前面）减 1，直到到达无穷远。

第十章 实时绘制加速技术

本章复习重点

• 什么是 LOD 技术。
• 三角形带方法点传输序列。
• 三角形扇方法点传输序列。

实时绘制技术

利用计算机快速生成三维场景的真实感图形。与图形硬件发展和人们对人机交互的需求密不可分。图像绘制速度采用帧频（单位为帧/秒）来衡量。关键是如何充分发挥图形硬件和图形算法各自长处，在绘制速度和图形质量之间取得平衡。

图形绘制流水线：

图形硬件、硬件驱动程序、图形 API 及应用程序间的关系：

LOD 技术

细节层次模型是以不同精度刻画物体几何细节的一组模型。

基本思想：根据物体在画面上的视觉重要性选取适当细节层次绘制该物体。

LOD 是图形交互化处理的重要工具。

• 关注保真度/性能折衷。
• 不是唯一的方式! 可以配合以下技术：
  • Parallel rendering
  • Occlusion culling
  • Image-based rendering

问题是原始几何数据集可能过于复杂，无法以交互速率进行渲染。

解决方法是简化小对象物体或远处对象的多边形几何体，称为 Level of Detail 或 LOD。

离散 LOD

传统 LOD:

• 在预处理中分别为每个对象创建 LOD。
• 在运行时，根据对象的距离（或类似标准）选取每个对象的 LOD。

由于 LOD 是以固定分辨率离线创建的，因此我们称之为离散 LOD(discrete LOD)。

优点：

1. 最简单的编程模型；解耦简化和渲染。
   • LOD 创建不需要受到实时渲染约束。
   • 运行时渲染只需要选取 LOD。
2. 非常适合现代图形硬件。
   • 易于将每个 LOD 预编译为三角形条带、显示列表、顶点阵列等。
   • 这些渲染速度比当今硬件上的无组织三角形快得多(3-5 x)。

缺点：有时离散的 LOD 不适合进行剧烈的简化。例如：地形交叉、体积等曲面、超细节范围扫描（GIS 地图）、多个模型等问题。对于剧烈的简化，大的对象必须进过切分处理，小的对象必须进过连接后处理。离散 LOD 处理非常困难或不可行。

连续 LOD

与传统的离散方法不同：

• 离散 LOD：在预处理中创建各个详细级别。
• 连续 LOD：在运行时创建各个详细级别。

优点：

1. 更好的粒度、更好的保真度。
   • LOD 是精确计算的，而不是从几个预先创建的选项中选择的。
   • 因此，对象使用的多边形不超过所需数量，这将为其他对象释放多边形。
   • 最终结果：更好的资源利用率，导致更好的整体保真度/多边形。
2. 更好的粒度、平滑过渡。
   • 在传统 LOD 之间切换会引入视觉“冲击”效果。
   • 连续 LOD 可以逐步增量调整细节，减少视觉冲击。
3. 支持渐进传输。
4. 引出了 view-dependent LOD技术。
   • 使用当前视图参数为当前视图选择最佳表达。
   • 单个对象可能跨越多个细节级别。
   • 以比远处更高的分辨率显示对象的附近部分。
   • 显示用户看的地方比他们的周边视觉更详细。

分层 LOD（Hierarchical LOD）

View-dependent LOD 解决了大物体渲染的问题。Hierarchical LOD 可以解决小物体渲染的问题。

Hierarchical LOD 和 view-dependent LOD 很好的吻合。将整个场景视为单个对象，以与视图相关的方式进行简化。

总结

1. 离散 LOD：为每个对象生成少量 LOD。

2. 连续 LOD (CLOD)：为每个对象在线生成数据结构，从中可以提取细节光谱。

3. View-dependent LOD：

   • 生成数据结构，从中可以动态生成专门用于当前视图参数的 LOD。
   • 一个对象可以跨越多个详细级别。

4. Hierarchical LOD：用各个部件的 LOD 聚合成为对象。

网格压缩传输技术

场景绘制的速度受到场景中三角形数目的制约，在绘制一个三角形时，必须将其全部三个顶点的信息传送到图形硬件。为避免同一顶点信息的重复传送，大多数图形 API 均采用三角形带和三角形扇等复合三角形结构进行传输，以充分利用图形硬件的有限带宽。

三角形带：

三角形扇：

采用类似于三角形带或三角形扇这样的复合结构，将把处理与传输 m 个三角形的代价从 3m 个顶点降到 m＋2 个顶点。

遮挡剔除技术

在对场景作取景变换之前剔除场景中对于当前视点不可见的某些物体的整体或局部，从而加速场景的绘制。

为实现遮挡剔除，需要对物体进行可见性检查。

• 物体的可见性检查一般在场景数据组织阶段由计算机 CPU 计算完成，不涉及到图形硬件。
• 针对当前视点，预计算其可能可见的所有面片的集合。

IBR 技术

以待绘制的场景的一系列二维图像作为输入，通过将其画面像素重新整合来生成在新的视点和新的视线方向上的场景画面。前身是环境映射技术。

优点：

• 无需进行复杂的场景几何造型即可实现对场景的浏览、漫游。
• 绘制计算量与场景的几何复杂度无关，而仅与所需绘制的画面分辨率有关。

缺点：

• 仅适用于静态场景，用户无法与场景中的景物进行实时交互。
• 绘制质量在很大程度上取决于原始图像的采样数目和相应的插值方法。

第十二章 OpenGL 编程基础

10 中基本图元模型

程序的基本结构

一段实例代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

#include <windows.h>
#include <gl/gl.h>
#include <gl/glu.h>
#include <gl/glaux.h>
#include <stdio.h>


void myinit(void);
void CALLBACK myReshape(int w, int h);
void CALLBACK display(void);


void myinit(void)
{                                     // 初始化
    glClearColor(0.0, 0.0, 0.0, 0.0); // 将窗口清为黑色
}
void CALLBACK display(void)
{
    glClear(GL_COLOR_BUFFER_BIT);
    // 将颜色缓存清为glClearColor命令所设置的颜色，即背景色
    glColor4f(0.2, 0.8, 1.0, 1.0); // 选颜色(R,G,B)
    glRotatef(30, 1.0, 1.0, 0.0);  // 做旋转变换
    auxWireCube(1.0);              // 绘制六面体的虚线图
    glFlush();                     // 强制绘图，不驻留缓存
     
}

void CALLBACK myReshape(int w, int h)
// 用于窗口大小改变时的处理，与绘图无关
{
    glViewport(0, 0, w, h);
}


void main(void)
{
    auxInitDisplayMode(AUX_SINGLE | AUX_RGBA); // 窗口显示单缓存和彩色模式
    auxInitPosition(0, 0, 200, 200);           // 屏幕左上点及大小
    auxInitWindow("openglsample.c");           // 初始化窗口，标题
    myinit();
    auxReshapeFunc(myReshape);
    auxMainLoop(display);
}

绘制效果如图：

代码中需要注意以下几点：

1. 头文件使用

若应用程序使用 OpenGL 核心函数，应包括头文件 <gl/gl.h>。

使用 GLU 库函数，应包括头文件 <gl/glu.h>。

使用 AUX 库函数，应包括头文件 <gl/glaux.h>。

使用 WGL 和 Win32 应包括头文件 <windows.h>。

2. 程序的基本结构

（1）定义窗口

Windows 下的 OpenGL 实现提供了一个辅助函数库 aux，用于解决开窗口和处理输入事件等问题

窗口管理函数：

1
2
3
4
5
6
7
8

void auxInitDisplayMode(Glbitfield mask); // 函数定义窗口的特性，如颜色和缓存区的性质。

// 窗口显示单缓存和 RGB(彩色)模式。
// auxInitDisplayMode(AUX_SINGLE | AUX_RGBA);

void auxInitPosition(Glint x, Glint y, Glint width, Glint height); // 定义窗口在屏幕上的位置和大小。

void auxInitWindow(Glbyte *titleString) // 打开窗口。窗口的标题为字符串 titleString。窗口把 ESC 键与退出函数联系起来，可以用来关闭窗口，退出程序。

处理输入事件:

当改变窗口尺寸、移动窗口、重新显示窗口时，由 auxReshapeFunc(myReshape) 调用函数 myReshape 重新定义窗口属性。通常 myReshape 函数调用 glViewPort 函数，对当前图形进行裁剪，重新定义投影矩阵等。

OpenGL 辅助函数库中还包括处理键盘和鼠标输入事件的函数。

（2）初始化操作

由于 OpenGL 的绘图方式是由一系列的状态确定的，因而在绘制图形前需要做一些准备工作，包括清缓存区、定义光照模型、纹理映射等基本操作的初始化状态、设置三维视景体、定义视口。

例如：

1
2
3

glClearColor(0.0, 0.0, 0.0, 0.0); // 将窗口清为黑色。

glClear(GL_COLOR_BUFFER_BIT); // 将颜色缓存清为 glClearColor 命令所设置的颜色，即背景色。

（3）设置观察坐标系下的取景模式和取景框位置及大小，主要利用了三个函数：

1
2
3
4
5
6
7
8
9

// 设置屏幕上视口大小。(x, y)指定视口左下角在窗口坐标系中的位置，width 和 height 分别确定矩形视口宽和高，均以像素为单位。注意：视口的大小和尺寸是在窗口坐标系中进行度量的，默认状态下其坐标原点位于窗口的左下角，其尺寸与窗口的大小相同。
void glViewport(GLint x, Glint y, Glsizei width, Glsizei height);

// 设置投影方式为正交投影（平行投影），其取景体积是一个各面均为矩形的六面体，在默认状态为平行正交投影。
void glOrtho(left, right, bottom, top, near, far);

// 设置投影方式为透视投影，其取景体积是一个截头锥体。
// 它通过指定 x-z 平面内的视角大小及宽高比来确定沿视线方向的棱锥，并通过指定远、近剪切面与视点间的距离来截断棱锥，得到观察体。
void gluPerspective(fovy, aspect, zNear, zFar);

（4）使用 OpenGL 的库函数构造几何物体对象的数学描述，包括点线面的位置和拓扑关系、几何变换、光照处理等，这是 OpenGL 程序的主要部分。

（5）程序的微机运行环境配置

程序中除了包含必需的头文件如 <windows.h> <gl/gl.h> <gl/glaux.h> <gl/glu.h> 外。在创建执行文件时，在 VC 环境设置中要链接 opengl32.lib, glu32.lib 和 glaux.lib 三个函数库。运行已创建的执行文件时，在 windows\system 目录下要有 opengl32.dll，glu32.dll 两个动态连接库。

基本绘制单元

要绘制某个几何对象，必须指明究竟是哪种类型的几何对象（例如点、线和多边形）。

OpenGL 绘制部分的代码结构类似于代码分段的形式：

1
2
3
4
5
6
7
8
9
10
11

glBegin(mode);

	...

    glVertex3f(x,y,z);
    glVertex3f(x,y,z);
    glVertex3f(x,y,z);

	...

glEnd();

点的绘制

OpenGL 中点定义为一个方块，在默认状态下，点是屏幕上的一个像素。在 OpenGL 中，一个点是当作一个 n（2,3,4）维向量来处理的。

例如在屏幕上绘制三个点：

1
2
3
4
5

glBegin(GL_POINTS)
    glVertex3f(1.0, 0.0, 0.0);
    glVertex3f(1.0, 1.0, 0.0);
    glVertex3f(0.0, 1.0, 1.0);
glEnd();

线的绘制

与数学意义上两端无限延伸的直线不同，OpenGL的线是数学定义中的线段，用成对的端点来描述。

1
2
3
4
5

// 一条由坐标原点到点（1.0,1.0）的线段。
glBegin(GL_LINES)
    glVertex2f(0.0, 0.0);
    glVertex2f(1.0, 1.0);
glEnd()；

多边形的绘制

多边形指封闭线段围成的区域。但 OpenGL 中可以描述的多边形有两点限制：多边形的边除了多边形的顶点外不允许相交，即确保多边形为简单多边形；多边形为凸多边形，即任给多边形的两个内部点，其连线完全在多边形内。

1
2
3
4
5
6
7

// 其中，* 表示 glVertex 函数的上述任一种组合形式，由多边形顶点 v0,v1,…,vn 的表示形式而定。注意：多边形顶点应按一定顺序排列（如逆时针）。
glBegin(GL_POLYGON);
    glVertex*(v0);
    glVertex*(v1);
    ...
    glVertex*(vn);
glEnd();

矩形的绘制

用的比较频繁，OpenGL 专门设置了绘制矩形的函数。

1
2
3

// 矩阵的左上、右下角点坐标分别为（x1,y1）和(x2,y2)，或者用数组指针 v1、v2 表示。用上述函数描述的矩形位于 z=0 平面内，并且各边分别平行于 x、y 轴。但注意：经过坐标变换之后，这些特性可能改变。 
void glRect{dfis}(TYPE x1, TYPE y1, TYPE x2, TYPE y2);
void glRect{dfis} v(TYPE *v1, TYPE *v2);

例 10.2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

void CALLBACK display(void)
{
    glClear(GL_COLOR_BUFFER_BIT);    // 将颜色缓存清为glClearColor命令所设置的颜色，即背景色
    glColor4f(1.0, 1.0, 1.0, 1.0); // 选颜色(R,G,B)
    glPointSize(6.0);                // 设置点的大小

glBegin(GL_POINTS);              // 在屏幕上绘制三个点
    glVertex3f(0.1, 0.2, 0.0);
    glVertex3f(0.2, 0.7, 0.0);
    glVertex3f(0.5, 0.8, 0.0);
glEnd();

glBegin(GL_LINES); // 在屏幕上绘制一条线段
    glVertex2f(0.0, 0.4);
    glVertex2f(-0.3, 0.8);
glEnd();

glBegin(GL_POLYGON); // 在屏幕上绘制一个四边形
    glVertex2f(-0.6, 0.0);
    glVertex2f(-0.4, 0.0);
    glVertex2f(-0.4, 0.3);
    glVertex2f(-0.6, 0.4);
glEnd();

    glColor3f(1.0, 0.0, 0.0);    // 设置当前颜色为红色
    glColor3f(0.0, 0.0, 1.0);    // 设置当前颜色为蓝色
    glRectf(0.5, 0.5, 0.7, 0.7); // 绘制一个矩形
    glColor3f(0.0, 1.0, 0.0);    // 设置当前颜色为绿色
    glRectf(0.8, 0.8, 0.9, 0.9); // 绘制一个矩形
    glRectf(0.2, 0.2, 0.4, 0.4); // 绘制一个矩形
   	glFlush();                  // 强制绘图，不驻留缓存
}

最终绘制效果如下：

坐标变换

在二维平面上创建三维物体的过程：在三维空间中创建所绘制物体的模型，由计算机经过适当的变换，将三维坐标系中的点转换为屏幕上的相应位置，以得到理想的视觉效果。

OpenGL 就是实现将物体的各个顶点通过各种变换矩阵的作用映射到屏幕的过程。

（1）通用的矩阵操作命令

1
2
3
4
5
6

// 参数取值：GL_MODELVIEW、GL_PROJECTION或GL_TEXTURE
// 默认的选定矩阵为 GL_MODELVIEW 变换矩阵。
void glMatrixMode(Glenum mode);

// OpenGL 中的变换命令都是对当前矩阵进行操作，因此在选定可修改矩阵后，应首先用上述命令设置当前操作矩阵为单位矩阵。
void glLoadIdentity(void);