1 渲染管线

• 顶点处理
  • 变换，将世界坐标中的顶点投影到屏幕空间上
• 三角形处理
  • 顶点间的连接关系不变，在屏幕上连接三角形
• 光栅化
  • 将三角形离散成屏幕上的像素，称为片段(fragment)
• 片段处理
  • 片段着色、纹理映射
• 输出帧图像

2 OpenGL流程 - 类比于画油画

• 放置模型
  • 模型描述、模型变换
  • Vertex buffer object(VBO)
    • 一块传给GPU的buffer，存储模型的顶点、法线、纹理坐标
• 放置画架
  • 视图变换
    • 相机属性
  • 创建framebuffer
• 将画布放在画架上
  • 用同一个framebuffer可以输出多个不同纹理(renderTarget)
    • 一个pass里可以输出多张结果：normal、depth等
    • 用户在fragment shader中决定输出纹理的样式
• 在画布上画画
  • Vertex shader
    • 对每个顶点，顶点变换、投影、插值
  • fragment shader
    • 对每个片段，光照、阴影、深度测试
• 可以画多次
  • 之前的帧可以作为参考

最近做课程的大作业时频繁用到 C++ STL 的有序容器，在此记录一下各种结构的用法与摸索出来的小技巧。

1 std::vector 的排序和搜索

std::vector 是比较常用的 STL 容器。假设我们现在有这样一个 arr：

1

auto arr = std::vector<int>{4, -3, 1, 5, 2};

我们可以使用 std::sort() 函数对该数组进行排序，使用该函数需要引用头文件 <algorithm>。我们只需将 arr 开始和结束位置的 iterator 传递给 std::sort() 函数，即可对其进行排序。

1
2
3
4

#include <algorithm>

std::sort(arr.begin(), arr.end());
// result: -3 1 2 4 5

我们还可以通过 lambda 表达式定义不同的排序方式，只需要将用于比较的 lambda 表达式当成第三个参数传递给 std::sort() 函数即可。默认情况下，该比较函数为 operator< 函数，将 arr 从小到大进行排序。

如果我们想将 arr 按照从大到小的顺序排序，则将比较函数改为大于即可。

1
2
3

std::sort(arr.begin(), arr.end(),
          [](const int& a, const int& b) { return a > b; });
// result: 5 4 2 1 -3

又例如，我们想将 arr 按照平方的值从小到大进行排序：

1
2
3

std::sort(arr.begin(), arr.end(),
          [](const int& a, const int& b) { return a * a < b * b; });
// result: 1 2 -3 4 5

另外，很多时候我们需要在 arr 中搜索满足条件的值。C++ 提供了 std::find_if() 函数，通过 lambda 表达式给定查找规则，返回一个 iterator。若查找成功，该 iterator 指向的是第一个符合查找规则的元素；否则，该 iterator 指向的是 arr 的末尾。

例如，我们想要找到 arr 中第一个小于 0 的数：

1
2
3

auto it = std::find_if(arr.begin(), arr.end(),
                       [](const int& val) { return val < 0; });
std::cout << *it; // result: -3

2 有序结构

2.1 堆 —— std::priority_queue

为了方便说明，我们先对 int 类型进行操作。有关自定义结构体的内容详见第3节。

我们可以使用 STL 提供的 std::priority_queue 结构来表示一个堆。如果我们想要有一个最大堆 maxHeap，可以用下面的方式定义：

1 图探索

1.1 DFS

• 使用栈实现
• 时间复杂度：O(V + E)
• 使用 DFS 判断连通分量的数量
  • 每次调用 DFS 时，连通分量数 +1
• 括号定理
  • 把调用递归前的操作和递归结束后的操作看作一组括号
  • 递归过程中，不同对的括号只有包含和独立的关系，不存在相交
    • 只有 ( [ ] ) 和 ( ) [ ]，不存在 ( [ ) ]
    • 根据访问时间，记作 [pre number, post number]
• 先序遍历和后序遍历
• 边的类型
  • Tree edge：DFS 生成树的边
  • Forward edge：从一个结点指向非子结点的后代结点的边
  • Back edge：指向祖先的边
  • Cross edge：指向非祖先也非后代的已访问结点
• 有向无环图 Directed Acyclic Graph (DAG)
  • 如果有环，DFS的过程中会发现一个 back edge
  • 没有入度的结点称为 source
  • 没有出度的结点称为 sink
• 线性化、拓扑排序
• 强连通分量
  • 可以将强连通分量看作一个大的结点
  • 以这种方式，可以将任何图转化为有向无环图
• 如何寻找强连通分量
  • 引理
    • 从 sink 出发进行DFS，可以将sink对应的分量全部便利到
    • 最大的 post number 一定在 source 中
  • 先将图reverse，用 post number 找到 reverse之后的 source，即为原图的 sink
  • 从该 sink 出发可以找到对应的强连通分量
  • 把该分量记录下来并从原图中拿掉
  • 对剩下的图重复上述步骤，从而得到所有分量

• 推荐书籍： Computers and Intractability: A guide to the Theory of NP-Completeness
  • 附录整理了大部分 NP 问题以及规约方法

1 概念

• NP 优化问题 (NPO)

• 对于一个问题 P(I, sol, m, goal)

  • I：目标数据的集合
  • sol：可行解
  • m：评估函数
  • goal：最大问题 / 最小问题

• 近似比

  • $R(x, y) = \max{ \frac{m(x,y)}{opt(x)}, \frac{opt(x)}{m(x,y)} } > 1$

• F-APX

  • 该集合中的函数与函数 F 的近似比为常数
  • 例：log-APX

• PTAS (Polynomial Time Approximation Scheme)

• FPTAS

• 包含关系

  

2 集覆盖问题 Set Cover Problem

• 在子集的序列中挑出一些子集，使得这些子集可以覆盖原集，并使得权重和最小

• 思路

  • 获得当前没被覆盖的 set 中权值最小的
  • 更新剩下的 price 为 $price(e) = \frac{c(S)}{|S-C|}$

1 Weighted Interval Scheduling

• 设计子函数：前 j 个元素的最优解 OPT(j)
• 具体递推关系
  • 选第 j 个任务， $OPT(j) = w_j + OPT(j-1)$
  • 不选第 j 个任务， $OPT(j) = OPT(j - 1)$
  • 取二者的最大值
• 动态规划分为两步
  • Sub-optimal: 发现递推关系
  • Tabulation: 记录在内存中，自底向上地执行

2 分段最小二乘 (Segmented Least Square)

• 描述
  • 对数据做分段的线性拟合
  • 要求有最小的均分误差与最少的直线段数
  • 是一个多目标规划问题
    • 首先考虑两目标是否同质 → 可以转化为只优化一个目标
    • 本问题中，两目标是互斥的，需要把两个目标组合起来
  • 互斥目标的解决方式
    • 线性组合 → 方便设计，但缺乏可解释性
    • 带约束的优化 → 先限制某一个目标，在此条件下优化另一个目标
• 定义
  • 均方差为 E，线段个数为 L
  • OPT(j): 前 j 个点的最小 cost
  • e(i, j): i 到 j 之间的最小均方差
  • 递推关系：
    • 遍历前面所有的 j - 1 个点
    • 假设在第 i 个到第 j 个之间新加一条线
    • 新加一条线后，得到的 cost 为 e(i, j) + c + OPT(i - 1)
    • 因此最小的cost是所有 i 得到的值的最小值
    • 即： $OPT(j) = \min_{1 \le i \le j} { e(i, j) + c + OPT(i - 1) }$
• 时间复杂度： $O(n^3)$
  • 算最小二乘的过程需要 O(n)！

1 简介

• 流程：divide → conquer(recursive) → combine
• 关键问题
  • 如何划分为子问题
  • 如何解决递归尾部的最小原子问题
  • 如何将各子部分结合起来

1.1 例子

• 复数相乘：(a + bi)(c + di) = ac - bd + (ad + bc)i
• 优化：ad + bc = (a + c)(b + d) - ac - bd
• 这样可以将4个乘法优化到3个乘法

1.2 使用上例优化整数乘法

设有两个n位二进制整数x、y，将整数分成高位、低位两部分

• 该算法的运行时间为 $T(n) = 4T(n / 2) + O(n)$
  • 使用后面提到的主定理分析，复杂度为 $O(n^2)$
• 利用1.1的优化方案，运行时间为 $T(n) = 3T(n / 2) + O(n)$
  • 使用主定理，复杂度为 $O(n^{log_23}) \approx O(n^{1.58})$

2 主定理

$T(n) = a T(\lceil n / b \rceil) + O(n^d)$

• $O(n^d)$：merge消耗的复杂度 $T(n) = a T(\lceil n / b \rceil) + O(n^d)$
• b：每次分成b段
• a：每次在分好的b段中使用几段
  • a可以小于b，如二分搜索a = 1，b = 2
  • a可以大于b，当使用的子问题有overlap的时候

结论：

Tips：比较 a 和 $b^d$

证明：

1 活动安排问题(Interval Scheduling)

• 描述

  • 任务 j 从 $s_j$ 开始，到 $f_j$ 结束
  • 选出一个最大的不冲突的任务子集合

• 尝试

  • 最早开始时间
  • 最早结束时间 — correct
  • 最短持续时间
  • 最少冲突事件

• 算法

  

• 复杂度：O(nlogn)

  • 先要对结束时间排序，需要O(nlogn)
  • 遍历只需要O(n)

• 证明贪心算法的思路

  • Counter — 反证
  • Induction — 数学归纳法
  • Nature — 分析问题的本质原理（高级）

• 证明该问题：反证法

  • 假设该算法不能得到最优解
  • 令 $i_1, \cdots, i_k$是贪心得到的结果，而 $j_1, \cdots, j_m$是一个最优解
  • 并且假设这两个序列的前 r 项是相同的
  • 由于贪心算法每次加入的都是结束时间最早的，因此 $f{i{r + 1}} \le f{j{r+1}}$
  • 如果 $f{i{r + 1}} = f{j{r+1}}$，与“前 r 项相同”的假设冲突
  • 如果 $f{i{r + 1}} < f{j{r+1}}$，那么可以用 $i{r+1}$ 把 $j{r+1}$ 替换掉，替换后仍然是最优解
  • 综上，贪心得到的结果必是最优解

1 证明

1.1 构造证明

1.2 反向证明

• 反证法
• 逆否命题

1.3 分类讨论

1.4 数学归纳法

• 弱数学归纳法
  • 假设k成立，证明k+1成立
• 最小反例集（贪心）
  • 假设k为最小的反例，则k-1成立，证明两者矛盾
• 强数学归纳法
  • 假设从$n_0$~k都成立，证明k+1成立

1.5 Peano公理

1.6 伪代码

• 标题
• 输入、输出
• 注释
  • 注释行没有行号
  • 只标注重要步骤

2 算法分析

2.1 计算理论

2.2 时间复杂度

• O上确界、$\Omega$下确界、$\Theta$等势
• o上界、$\omega$下界
• 
• 偏序小于$\prec$，可看做小o关系
• $\sum\lfloor x \rfloor$形式一般用两边夹来分析

2.3 空间复杂度

2.4 复杂度分析

• best
• worst
• average
• amortized 均摊分析
  • 考虑的是worst case

1 for each循环

1.1 只读形式

for each循环语句是在Java和Python语言中一种循环语句。C++11标准也提供了类似的语句，称为范围for(range for)语句。为了方便叙述，在后文中这个语句统一称为for each循环语句。

假设现在我们要遍历数组a中的所有元素并输出。在C++11之前，我们一般会使用下面的for循环语句：

1
2
3
4
5
6

int a[10];
/* ..初始化数组a.. */

for (int i = 0; i < 10; i++) {
    std::cout << a[i] << ' ';
}

使用这样的for循环需要提前知道数组a的大小。在C++11标准下，我们可以使用for each循环语句，把上面的代码改写成：

1
2
3

for (int val : a) {
    std::cout << val << ' ';
}

for each语句遍历给定序列中的每个元素，并对序列中的每个值执行某种操作。语法形式是：

1
2
3

for (declaration : expression) {
    statement
}

其中declaration部分定义了一个变量，用于访问序列中的基础元素。由于我们访问的对象是数组中的元素，而数组元素的类型显然是已知的，因此在声明时可以使用auto类型符，让编译器来决定变量c的类型。这样，上面的遍历输出可以改写成：

1
2
3

for (auto val : a) {
    std::cout << val << ' ';
}

需要注意的是，遍历时我们声明了一个变量来访问数组中的每一个元素。也就是说，每次迭代时，数组中的当前元素会被拷贝给该变量。因此，这种遍历方式只能对数组元素进行只读操作，无法修改原数组中元素的值。

1.2 遍历并修改——使用引用

如果我们想使用for each语句逐一修改数组中的值，应该怎样操作呢？我们使用引用来对数组进行遍历即可。例如，下面的例子将数组a中的每一个值修改为原来的两倍：

1
2
3

for (auto &val : a) {
    val = val * 2;
}

当使用引用作为循环控制变量时，这个变量实际上被依次绑定到了序列的每个元素上，因此可以使用该引用修改其绑定的字符。

如果想使用引用进行只读操作的遍历，我们将引用声明为const属性即可，例如：

之前我们分析了红黑树的原理和操作算法，现在我们来用C++语言实现一个基本的红黑树结构。在后文的插入和删除操作中提到的各种情况，详细描述请参见上一篇文章。

具体代码可参考https://github.com/LumiOwO/DS-Playground/blob/master/include/tree/RBTree.h

1 数据结构定义

首先，为红黑树结点的颜色定义一个枚举：

1
2

/// Enumeration for node color.
enum RBColor { BLACK, RED };

之后定义红黑树结点RBTreeNode模板类。这里我额外增加了模板参数ALLOW_DUP，该参数表示是否允许结点出现相同的值。具体实现这个类时，我考虑了以下几点：

• 在这个类中，指向左右子树的指针使用的是C++11标准提供的智能指针，这样就不需要在程序结束后手动释放申请的结点内存了；
• 由于在插入和删除过程中都需要根据当前结点找到父结点的位置，因此在结点中加入指向父结点的指针；
• 为了避免shared_ptr循环引用，指向父结点的指针应该使用weak_ptr；
• 将指向RBTreeNode类的智能指针重命名为RBTree

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

template <typename T, bool ALLOW_DUP = false>
class RBTreeNode {
public:
    /// 重命名shared_ptr智能指针
    using RBTree = std::shared_ptr<RBTreeNode<T, ALLOW_DUP>>;
    
    /// 结点颜色
    RBColor _color;
    /// 结点值
    T _value;
    /// 指向父结点的指针，应使用weak_ptr
    std::weak_ptr<RBTreeNode<T, ALLOW_DUP>> _parent;
    /// 左子树
    RBTree _left;
    /// 右子树
    RBTree _right;

    /// 构造函数
    /* ...省略... */

    /// 析构函数
    virtual ~RBTreeNode() { }

    bool IsRoot() const { return !_parent.lock(); }
    bool IsLeaf() const { return !_left && !_right; }

}; ///< class RBTreeNode

// 在类的外面需要再次重命名指向结点的智能指针
// 否则只能通过RBTreeNode::RBTree访问这个指针类的名字
template <typename T, bool ALLOW_DUP = false>
using RBTree = std::shared_ptr<RBTreeNode<T, ALLOW_DUP>>;

2 Inline函数

主要有两个Inline函数：IsBlack()和IsRed()，用来判断结点的颜色。之所以不把这两个函数写成结点的成员函数，是因为空的NIL结点将被看做黑色的结点，而访问空指针的成员函数将会报错。换句话说，如果在代码中用IsRed()函数判断出一个结点为红色，则该指针必不为空指针。

1
2
3
4
5
6
7
8

template <typename T, bool ALLOW_DUP>
inline bool IsBlack(RBTree<T, ALLOW_DUP> p) {
    return !p || p->_color == BLACK;
}
template <typename T, bool ALLOW_DUP>
inline bool IsRed(RBTree<T, ALLOW_DUP> p) {
    return !IsBlack(p);
}

3 搜索

搜索过程和在二叉搜索树中查找目标值的过程相同。这里给出非递归的搜索代码：

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

template <typename T, bool ALLOW_DUP>
RBTree<T, ALLOW_DUP> Search(const RBTree<T, ALLOW_DUP> &root, T value) {
    RBTree<T, ALLOW_DUP> cur = root;
    while (cur) {
        if (value == cur->_value) {
            break;
        } else if (value < cur->_value) {
            cur = cur->_left;
        } else {
            cur = cur->_right;
        }
    }
    return cur;
}

4 旋转

旋转操作分为左旋和右旋。这里以左旋为例。