图形学高等代数知识集

作者: 离原春草 | 来源:发表于2020-12-13 00:30 被阅读0次

在图形学的一些技术方案的推导中，经常会有需要用到一些高等数学相关的知识与公式，这里考虑将每次查阅得到的内容整理并列举出来，以避免每次查阅搜索导致的时间浪费，因为无法做到一蹴而就，因此文章内容会不定时更新。

1. 函数展开

求取极限、复杂函数模拟等将复杂函数转换成简单函数来处理，是工作中常用的问题解决思路，而函数展开则是其中最为常用的技术手段，下面列举了常用的一些展开方案，具体方案的来龙去脉，由于篇幅有限，此处就直接省略了，有需要请另行查阅文档进行补齐。

1.1 泰勒展开

函数的泰勒展开指的是使用函数在某个点处的各阶导数为系数形成的多项式来实现对当前函数模拟的技术手段。

1.1.1 泰勒公式通用形式

如果函数 $f(x)$ 在包含 $x_0$ 的某个开区间 $(a,b)$ 上具有 $n+1$ 阶导数，那么对于任意属于 $(a,b)$ 范围内的变量 $x$ 而言，有如下的近似模拟公式：
$f(x) = \sum_{i = 0}^n \frac{f^{(n)}(x_0)}{i!} + R_n(x)$

$f^{(n)}(x_0)$ 指的是函数 $f(x)$ 的第n阶导数在 $x_0$ 处的取值， $R_n(x)$ 为泰勒展开的余项（即泰勒展开与原函数的误差）：
$R_n(x) = \frac{f^{(n+1)}(\epsilon)}{(n+1)!}(x-x_0)^{n+1}$

通常 $R_n(x) = o((x-x_0)^n)$ ，为了计算简便，通常取 $x_0 = 0$ ，前面的公式就转换成：
$f(x) = \sum_{i = 0}^n\frac{f^{(n)}(0)}{i!} + R_n(x)$

1.1.2 常用公式的泰勒展开

$e^x = (\sum_{i=0}^n \frac{x^i}{i!})+ o(x^n)$

$ln(1+x) = (\sum_{i=1}^n \frac{x^i}{i} * (-1)^{i+1})+ o(x^n)$

$\frac{1} {1-x}= (\sum_{i=0} ^n x^i) + o(x^n)$

$(1+x)^a = (\sum_{i=0}^n \frac{C_a^i \cdot x^i}{i!})+ o(x^n)$

$sin(x) = (\sum_{i=0}^n \frac{(-1)^i\cdot x^{2i+1}}{(2i+1)!})+ o(x^{2n+1})$

$cos(x) = (\sum_{i=0}^n \frac{(-1)^i\cdot x^{2i}}{(2i)!})+ o(x^{2n})$

1.2 傅里叶展开

傅里叶提出，任意函数都可以展开为一系列三角函数之和，具体公式给出如下，对来历有兴趣的，可以参考文后参考文献[1]中的推导：
$f(x) = \frac{a_0}{2} + \sum_{n=1}^{\infty}[a_n cos(n\omega x) + b_n sin(n \omega x)]$

其中

$a_n = \frac{2}{T} \int_{x_0}^{x_0+T} f(x) cos(n\omega x)dx$

$b_n = \frac{2}{T}\int_{x_0}^{x_0+T} f(x) sin(n\omega x)dx$
这个公式存在的条件是下面积分是存在的：
$\int_{x_0}^{x_0+T} f(x) dx$

更广义的傅里叶展开公式是使用指数形式给出的：
$f(x) = \sum_{-\infty}^{\infty} c_n e^{i \frac{2\pi n x}{T}}$

$c_n = \frac{1}{T}\int_{x_0}^{x_0+T} f(x) e^{-i \frac{2\pi n x}{T}}dx$

常见波形的傅里叶展开公式间参考文献[2]。

2. 三角函数常用公式

2.1 三角函数拆分与合并

2.1.1 和差角公式

$cos(a+b) = cos(a) cos(b) - sin(a) sin(b)$

$cos(a-b) = cos(a) cos(b) + sin(a) sin(b)$

$sin(a+b) = sin(a) cos(b) + sin(b) cos(a)$

$sin(a-b) = sin(a) cos(b) - sin(b) cos(a)$

$tan(a+b) = \frac{tan(a) + tan(b)} {1- tan(a) \cdot tan(b)}$

$tan(a-b) = \frac{tan(a) - tan(b)} {1+ tan(a) \cdot tan(b)}$

2.1.2 和差化积公式

$sin(a) + sin(b) = 2sin( \frac{a+b} {2}) cos(\frac{a-b} {2})$

$sin(a) - sin(b) = 2sin(\frac{a-b}{2}) cos(\frac{a+b}{2})$

$cos(a) + cos(b) = 2cos(\frac{a+b} {2}) cos(\frac{a-b} {2})$

$cos(a) - cos(b) = -2 sin(\frac{a+b}{2}) sin(\frac{a-b}{2})$

$tan(a) \pm tan(b) = \frac{sin(a \pm b)}{cos(a) \cdot cos(b)}$

$cot(a) \pm cot(b) = \pm \frac{sin(a \pm b)}{sin(a) \cdot sin(b)}$

2.1.3 积化和差公式

$sin(a) cos(b) = \frac{1}{2} (sin(a+b) + sin(a-b))$

$cos(a) cos(b) = \frac{1}{2} (cos(a+b) + cos(a-b))$

$sin(a) sin(b) =- \frac{1}{2} (cos(a+b) - cos(a-b))$

2.1.4 二倍角公式

$sin(2a) = 2sin(a) cos(a)$

$cos(2a) = 2cos^2(a) - 1 = 1- 2sin^2(a) = cos^2(a)-sin^2(a)$

$tan(2a) = \frac{2tan(a)} {1-tan^2(a)}$

2.2 三角函数与指数函数之间的转换

这些公式是根据泰勒展示推导而来的：
$sin(x)=\frac{e^{ix}-e^{-ix}}{2i}$

$cos(x)=\frac{e^{ix}+e^{-ix}}{2}$

$tan(x)=\frac{e^{ix}-e^{-ix}}{ie^{ix}+ie^{-ix}}$

3. 线性代数

3.1 矩阵相关

3.1.1 行主序 VS 列主序

图形学的各种坐标变换是通过与矩阵相乘来完成的，而矩阵乘法（向量与矩阵相乘）是不可交互的，因此在使用的时候需要稍加注意，也因为这个原因，衍生出了“左乘”与“右乘”的术语，这两个概念针对的是矩阵M与向量V在进行乘法运算时的矩阵在其中的位置关系：
左乘：矩阵放在左边，即 $M \times V$
右乘：矩阵放在右边，即 $V \times M$

而与这个相关的另一个问题则是，由于内存中的数据存放通常是线性的，因此在感官上按照矩阵存放的二维数据，最终都会转换成一维数组来存放，而这种转换过程，对于不同的API，其实现逻辑是不一样的。

如参考文献[3]中所述，存储时，将矩阵一行接一行的写入到一维数组的存储方式，称之为行主序，而将矩阵一列接一列的写入到一维数组的存储方式，称为列主序。

行主序

列主序

所谓的存储方式的区别就在于，到底哪几个矩阵的元素被塞入到一个常量寄存器中，对于Shader中使用的左乘右乘的运算结果而言，并不会导致区别，比如，如果是行主序矩阵，在Shader中使用的是右乘，就会导致在Shader中进行计算的时候，需要从四个常量寄存器中分别取出第一个元素再组合成一个向量来与输入向量进行相乘，这种情况下其计算效率显然就不如直接使用列主序的存储方式。

为了能够最大化计算效率，对于一些应该左乘的实现逻辑，行主序存储方式无需处理，而列主序则最好将矩阵转置后传入（此时相应的需要将左乘更换成右乘），反之亦然，这就是引擎代码中传入矩阵参数的时候，为什么有些矩阵需要转置，有些则不用的原因。

这里给出一些常见的使用情景中的矩阵的主序，更多内容可参考文献[4]：

DirectXMath Library中矩阵使用的是行主序（CPU），这是为什么在可编程管线中，矩阵传入GPU之前，要做一次转置的原因（D3DX Effects会自动完成这个过程）。
早期固定管线中，DirectX矩阵使用的是行主序
HLSL中矩阵使用的是列主序（GPU），在D3D11之后的HLSL中，虽然默认使用的是列主序，但是允许通过编译关键字指定为行主序。
GLSL中矩阵使用的是列主序（GPU）

4. 微积分

4.1 Importance Sampling/蒙特卡洛积分

在工程实践中，经常会遇到需要对一些无法得出函数表达式的函数曲线进行积分，这类问题无法通过解析的方式来得出答案，通常需要使用蒙特卡洛积分（Importance Sampling）来计算。

蒙特卡洛积分来源于大数定理，对于某个其概率分布函数（pdf）为p(x)的变量x而言，我们可以给出其期望计算公式：
$E[f(x)] = \int{f(x) \cdot p(x)d(x)} \approx \frac{1}{N}\sum_{i=1}^N f(x_i)$

上述公式中，最右边的近似解表示的意思是，只要采样数足够多，就可以用离散的方式来模拟积分结果，而这也是求取期望最常见的方式。不过这里有个问题，这个公式计算的是f(x)p(x)的积分，但我们在工作中常常遇到的是f(x)的积分求取，为了得到这个积分的结果，我们需要做一步转换：g(x) = f(x)*p(x)。

在上述转换的作用下，我们可以得到如下的公式：
$\int g(x) dx \approx \frac{1}{N} \sum_{i=1}^N \frac{g(x_i)}{p(x_i)}$

也就是说，我们要想得到某个函数的积分近似结果，就需要对 $\frac{g(x_i)}{p(x_i)}$ 进行累加平均，通常 $g(x_i)$ 是现成的，但是 $p(x_i)$ 的获取可能需要动下脑筋，不过通常在进行计算的时候，大致是可以判断出样本的分布方式的，无外乎那几种常见的分布，比如均匀分布，正太分布等。

参考文献

[1]. 傅里叶级数的推导
 [2]. 几种常见波形的傅里叶级数展开式
 [3]. Memory layout of multi-dimensional arrays
[4].A word on Matrices