计算机图形学基础-线性代数

基础

向量Vector

基本定义

(欧几里得)向量是一个具有大小和方向的实体。
$$
\vec p=\left[
\begin{matrix}
p_x\\
p_y\\
p_z
\end{matrix}
\right]
\in R^3
$$
对于零向量,有:
$$
\vec o=
\left[
\begin{matrix}
0\\
0\\
0
\end{matrix}
\right]
$$
向量可以堆叠起来表示高维向量,通常用于描述对象的状态。假设有向量$x_0,x_1,x_2,…,x_{10}$,则这几个向量堆叠起来可以表示为:
$$
\vec p=
\left[
\begin{matrix}
x0\\
…\\
x_i\\
…\\
x_n
\end{matrix}
\right]
\in R^{33}
\\
for\ ever\ x_i\in R^3
$$
这是一个堆叠向量,而不是方向向量。

另外,向量也可以用于表示一个点、速度、力或直线/射线/线段。
$$
p(t)=\vec p+t \vec v\\
t\ stands\ for\ time
$$
$p(t)$表示从点$p$开始沿向量$v$移动$t$个时刻后的一个点,或是表示该点和$p$点之间的线段。

同时,若有$p,q$两个点,则可以用如下公式表示两点之间任意的一个点(即线性插值):
$$
p(t)=(1-t)\vec p+t\vec q
$$
我们用这一符号表示向量的长度(两点之间的距离):
$$
||\vec p-\vec q||
$$
其中,我们定义单位向量为:
$$
||\vec p||=1
$$
基于此,我们可以通过这一公式将任意向量转换为指向该方向的单位向量:
$$
\overline p=\frac{\vec p}{||p||},||\overline p||=1
$$
这一过程被称为向量的标准化。其中,$\overline p$表示向量$p$的标准化形式。

在剩余内容中,为方便表示,当等式中仅存在向量时,将直接以字母本身来表示向量,去除字母上的箭头。

向量的范数

对于任意向量,其向量范数(norm)代表了它在某种意义下的长度。举个例子,向量的欧几里得长度即为向量的二阶范数(欧几里得范数):
$$
||p||_2=(p_x^2+p_y^2+p_z^2)^{\frac{1}{2}}
$$
通常情况下我们会省略二阶范数的下标2。

向量的$n$阶范数可以表示为:
$$
||p||_n=(|p_x|^p+|p_y|^p+|p_z|^p)^{\frac{1}{p}}
$$

点乘

对于两个向量的点乘(内积),我们可以将其记作:
$$
p\cdot q=p_xq_x+p_yq_y+p_zq_z=p^Tq=||p||\ ||q||\ cos\theta
$$
其中,$\theta$是两向量的夹角。同时,向量的点乘也可以表示为$<p,q>$

向量的点乘遵循交换律和结合律,即:
$$
p\cdot q=q\cdot p\
p\cdot (q+r)=p\cdot q + p\cdot r
$$
一个向量点乘它自己可以得到其二阶范数的平方,即:
$$
p\cdot p=||p||_2^2
$$
向量$\vec a$在向量$\vec b$上的投影长度$s$也可以表示为点乘:
$$
s=\vec a \cdot \vec b
$$
我们可以使用一个平面的法向量与点$p$的点乘来判断该点与平面的位置关系。假设法向量与平面的交点为$n$,则有:
$$
(p-c)^Tn=
\begin{cases}
\gt0,Above\ the\ plane\\
=0,On\ the\ plane\\
\lt0,Blow\ the\ plane
\end{cases}
$$

叉乘

叉乘的结果是一个与原向量分别正交(垂直)的向量:
$$
\vec r=\vec p\times \vec q
$$
这个向量$\vec r$满足:
$$
r\cdot q=0,r\cdot p=0
$$
同时,叉乘向量的值可以表示为:
$$
||r||=||p||\ ||q||sin\theta
$$
向量的叉乘不满足交换律,但满足结合律:
$$
p\times q=-q\times p\
p\times (q+r)=p\times q+p\times r
$$
对于任意三角形$x_0x_1x_2$,我们可以使用叉乘求其法线及面积:
$$
n=(x_{10}\times x_{20})/||x_{10}\times x_{20}||\\
S=||x_{10}\times x_{20}||/2
$$
叉乘也用于判断二维平面中一个点是否在三角形内。假设目前要判断点$p$和三角形$x_0x_1x_2$的关系,则有:
$$
(x_i-p)\times(x_j-p)\cdot n
$$
若对于按顺序的任意$i,j$,计算该等式的符号均一致,则该点在三角形内部,否则在三角形外部。

通过任意一点$p$与三角形三边的叉积,将三角形面积分为三份,可以得到三角形的重心坐标系。设平面三角形面积为$A$,则有:
$$
A_1 = \frac{1}{2}(x_0-p)\times(x_1-p)\cdot n
$$
$$
A_2 = \frac{1}{2}(x_1-p)\times(x_2-p)\cdot n
$$

$$
b_0=A_0/A
$$

$$
b_1=A_1/A
$$

$$
b_2=A_2/A
$$

$$
b_0+b_1+b_2=1
$$

$b_1,b_2,b_3$即为重心坐标系的系数。

叉乘也用于计算四面体。设有四面体$C$,其上有四个相邻顶点$x_0x_1x_2x_3$,则四面体的面积可以表示为:
$$
V=\frac{1}{3}hS=\frac{1}{6}x_{30}\cdot x_{10}\times x_{20}
$$
通过四面体体积公式,也可以得到体积化的重心坐标系。同时,当点$p$与三角面构成的四面体体积为0时,点$p$在三角形面上。

矩阵Matrix

基本定义

一个实数矩阵指一系列以行排列的元素。
$$
A=
\left[
\begin{matrix}
a_{00}\ a_{10}\ a_{20}\\
a_{01}\ a_{11}\ a_{21}\\
a_{02}\ a_{12}\ a_{22}\\
\end{matrix}
\right]
$$
定义如下矩阵,分别为转置矩阵(Transpose)、对角矩阵(Diagonal)和单位矩阵(Identity)。
$$
A^T=
\left[
\begin{matrix}
a_{00}\ a_{01}\ a_{02}\\
a_{10}\ a_{11}\ a_{21}\\
a_{20}\ a_{21}\ a_{22}\\
\end{matrix}
\right]
\
D=
\left[
\begin{matrix}
a_{0}\ \ 0\ \ 0\\
0\ \ a_{1}\ \ 0\\
0\ \ 0\ \ a_{2}\\
\end{matrix}
\right]
\
I=
\left[
\begin{matrix}
1\ \ 0\ \ 0\\
0\ \ 1\ \ 0\\
0\ \ 0\ \ 1\\
\end{matrix}
\right]
$$

对于对称矩阵,有
$$
A^T=A
$$
矩阵不满足交换律,但满足结合律:
$$
AB\neq BA\\
(AB)x=A(Bx)
$$
对于转置矩阵,有:
$$
(AB)^T=B^TA^T\\
(A^TA)^T=A^TA
$$
对于一个矩阵$A$,我们称A^{-1}$,是$A$的逆矩阵,满足:
$$
AA^{-1}=A^{-1}A=I\\
(AB)^{-1}=B^{-1}A^{-1}
$$
不是所有的矩阵都有逆矩阵。

正交矩阵

我们可以用多个向量组合,来形成矩阵。
$$
A=[a_0\ a_1\ a_2]
$$
若这些向量分别垂直,且这些向量都是单位向量,则称$A$为正交矩阵。有:
$$
a_i^Ta_j=\begin{cases}
1,if\ i=j\\
0, if\ i\neq j
\end{cases}
\\
A^T=A^{-1}
$$

对于正交矩阵,其本身与其转置相乘,有:
$$
A^TA=I\\
A^T=A^{-1}
$$
正交矩阵可以用于表示旋转。对于物体原本的坐标轴$x,y,z$,使用正交矩阵$A$与其相乘,可得:
$$
\begin{cases}
Ax=u\\
Ay=v\\
Az=w
\end{cases}
$$
物体旋转后的新坐标轴为$u,v,w$。同理,我们用对角矩阵来表示物体的缩放。

奇异值分解与特征值分解

假设有任意矩阵$A$,其可以被分解为$A=UDV^T$,其中$U,V$是正交矩阵,$D$是对角矩阵。其中,$D$的元素值即为矩阵$A$的奇异值。易知,任意矩阵的线性变换都能通过旋转-缩放-旋转来表示。(因为物体只能向坐标轴方向缩放,因此要先将物体旋转至缩放方向)

假设有对称矩阵$A$,其可以被分解为$A=UDU^{-1}$,其中$D$是对角矩阵,$U$是正交矩阵。其中,$D$的元素值被称为$A$的特征值。

正定矩阵

我们将一个矩阵称之为正定矩阵(s.p.d),当且仅当
$$
v^TAv>0,v\neq0.
$$
我们将一个矩阵称为半正定矩阵,当且仅当
$$
v^TAv\ge0
$$
推论:对称矩阵如果特征值均为正数,那么这个对称矩阵一定是正定矩阵。

推论2:每一行对角线上的值大于其他值之和的矩阵对角占优,对角占优的矩阵一定正定。

线性系统和线性问题

线性问题

任何线性问题,都可以被写作这一形式:
$$
Ax=b
$$
其中$A$是一个矩阵,$b$是一个矢量。

最容易想到的方法是在等式两边同时乘以矩阵的逆矩阵,以此来解决问题。然后,在实际应用时,矩阵的逆十分难以计算,对稀疏矩阵求逆矩阵也并不方便。因此通常来说,我们会使用其他方法来解出这一线性问题,这一过程就是求解线性系统

直接方法

直接方法通过对矩阵进行分解来求出答案,常见的变种有:Cholesky,LDLT等等,这些方法通常在内存占用上有所不同。朴素的$LU$会方法将矩阵分解为上三角矩阵与下三角矩阵:
$$
A=LU
$$
在进行分解后就可以很方便地解线性系统。例如,我们将$A$分解为$LU$后,先解决:
$$
Ly=b
$$
此时,由于$L$是下三角矩阵,因此我们可以很容易地得到:
$$
y_0=b_0/l_{00}\\
y_1=(b_1-l_{10}y_0)/l_{11}\\

$$
随后,我们再以同样的方式解出:
$$
Ux=y
$$
合并两个式子,此时得到的$x$即为原线性系统的解。在这一方法中,如果$A$是一个稀疏矩阵,则$L,U$的稀疏性将会较差。此时,$L,U$的稀疏性和原矩阵$A$的数值排列方式有关,因此我们会先常常用一定方法修改原矩阵的排列顺序,然后再求解线性系统。

迭代法

迭代法通常是这样的一种形式:
$$
X^{[k+1]=}x^{[l]}+\alpha M^{-1}(b-Ax^{[k]})
$$
随迭代次数增加,$x$将逐渐收敛至正确的数值解。通常,$M$有多种选取的方法,例如Jacobi方法和Gauss-Seidel方法。同时,在这一过程中,我们会使用切比雪夫加速、梯度共轭等额外方法进行加速。

迭代法 的好处是十分容易实现,而且其数值解的求解速度较快,其过程也可以并行。然而,迭代法的收敛性较难确定,且精确解的求解十分缓慢。

微积分

一阶导数

如果$f(x)$是一个实数域的函数,其一阶导数可以写作:
$$
df=\frac{\partial f}{\partial x}dx+\frac{\partial f}{\partial y}dy+\frac{\partial f}{\partial z}dz=
\left[ \frac{\partial f}{\partial x} \frac{\partial f}{\partial y}\frac{\partial f}{\partial z}\right]
\left[
\begin{matrix}
dx\\dy\\dz
\end{matrix}
\right]
$$
即,对矢量求导相当于对其各个标量分别求导。有时,我们会使用转置后的一阶导数,即梯度(gradient):
$$
\nabla f(x)=
\left[
\begin{matrix}
\frac{\partial f}{\partial x}\\
\frac{\partial f}{\partial y}\\
\frac{\partial f}{\partial z}
\end{matrix}
\right]
$$
梯度的含义即为函数上升的最快方向。

对于矩阵求导,例如:
$$
f(x)=
\left[
\begin{matrix}
f(x)\\g(x)\\h(x)
\end{matrix}
\right]
\in R^3
$$
则有Jacobian矩阵:
$$
J(x)=\frac{\partial \vec f}{\partial \vec x}=
\left[
\begin{matrix}
\frac{\partial f}{\partial x}\frac{\partial f}{\partial y}\frac{\partial f}{\partial z}\\
\frac{\partial g}{\partial x}\frac{\partial g}{\partial y}\frac{\partial g}{\partial z}\\
\frac{\partial h}{\partial x}\frac{\partial h}{\partial y}\frac{\partial h}{\partial z}
\end{matrix}
\right]
$$
其中,我们将矩阵对角线之和称作求导的散度(Divergence):
$$
\nabla \cdot \vec f=\frac{\partial f}{\partial x} + \frac{\partial g}{\partial y} + \frac{\partial h}{\partial z}
$$
同时,我们将得到一个矩阵的旋度(Curl):
$$
\nabla \cdot \vec f=
\left[
\begin{matrix}
\frac{\partial h}{\partial y}-\frac{\partial g}{\partial z}\
\frac{\partial f}{\partial z}-\frac{\partial h}{\partial x}\
\frac{\partial g}{\partial x}-\frac{\partial f}{\partial y}\
\end{matrix}
\right]
$$

二阶导数

对$f(x)$进行二阶求导,可以得到如下Hessian矩阵:
$$
H=J(\nabla f(x)=
\left[
\begin{matrix}
\frac{\partial^2 f}{\partial x^2}\frac{\partial^2 f}{\partial x\partial y}\frac{\partial^2 f}{\partial x\partial z}\
\frac{\partial^2 f}{\partial x\partial y}\frac{\partial^2 f}{\partial y^2}\frac{\partial^2 f}{\partial y\partial z}\
\frac{\partial^2 f}{\partial x\partial z}\frac{\partial^2 f}{\partial y\partial z}\frac{\partial^2 f}{\partial z^2}
\end{matrix}
\right]
$$
Hessian矩阵的对角被称为Laplacian:
$$
\nabla \cdot \nabla f(x)=\nabla^2f(x)=\Delta f(x)=\frac{\partial^2f}{\partial x^2}+\frac{\partial^2f}{\partial y^2}+\frac{\partial^2f}{\partial z^2}
$$
我们学过常数形式的泰勒展开,对于$f(x)$,有:
$$
f(x)=f(x_0)+\frac{\partial f(x_0)}{\partial x}(x-x_0)+\frac{1}{2}\frac{\partial f^2(x_0)}{\partial x^2}(x-x_0)^2+…
$$
对于$f(\vec x) \in R$,则有:
$$
f(\vec x)=f(\vec x_0)+\nabla f(x_0)\cdot (x-x_0)+\frac{1}{2}(x-x_0)^TH(x-x_0)
$$
其中,可以发现可能存在的正定矩阵:
$$
(x-x_0)^TH(x-x_0)>0
$$
同时,向量大小的梯度为:
$$
\frac{\partial ||x||}{\partial x}=\frac{\partial (x^Tx)^{1/2}}{\partial x}=\frac{1}{2}(x^Tx)^{-1/2}\frac{\partial (x^Tx)}{\partial x}=\frac{x^T}{||x||}
$$


计算机图形学基础-线性代数
https://tridiamond.tech/post/CGMath.html
作者
想变成一只白泽
发布于
2023年3月16日
许可协议