GAMES101 重要公式推导与算法补充

Rodrigues 旋转公式

概要

实现某三维物体的坐标绕过原点的向量轴n(默认过原点),旋转 α 角度(右手定则的四指方向)的旋转矩阵为 R(n,α),其表达形式为:
Rodrigues旋转公式

该旋转矩阵左乘三维物体上的某个点(列向量、列矩阵)即可得到旋转变换后的点。

推导过程

说明:字母上带有表示向量,不带箭头表示该向量对应的列矩阵;字母上的^表示该向量的单位向量。

Step1

S向量分解为旋转轴n方向和垂直于旋转轴方向的两个向量,其中I表示旋转轴的单位列矩阵

Step2

求出与旋转轴n和向量S所在平面垂直的向量C

Step3

S在垂直于旋转轴的分量向C旋转 α 度

Step4

上一步得到的向量与S在旋转轴的分量相加,得到旋转后的向量,由于两个向量的叉乘可以写成一个矩阵乘以列向量的形式(证明略)

整理与提取,即可得到旋转矩阵 R(A 为单位矩阵):


正交投影矩阵求法

透视投影矩阵求法

概要

透视投影是利用相似三角形原理将远处平面坐标映射到相机可见的窗口处:

但该过程可以等价为:可以看作先将远处的平面压缩为等同于相机可见的窗口大小的平面,得到一个长方体,然后再进行正交投影(先平移,后放缩)得到以原点为中心的边长为 2 的立方体(规范立方体)
远处平面压缩
正交投影变换

推导






求取方法

  • 总公式

    Mpersp =Mortho Mpersp  ortho M_{\text {persp }}=M_{\text {ortho }} M_{\text {persp } \rightarrow \text { ortho }}

  • 透视变换到正交(压缩远平面的矩阵)

    Mpersp  ortho =(n0000n0000n+fnf0010)M_{\text {persp } \rightarrow \text { ortho }}=\begin{pmatrix} n & 0 & 0 & 0\\ 0 & n & 0 & 0\\ 0 & 0 & n+f & -n f \\ 0 & 0 & 1 & 0 \end{pmatrix}

  • 正交变换矩阵

    Mortho =(2rl00002tb00002nf00001)(100r+l2010t+b2001n+f20001)M_{\text {ortho }}=\begin{pmatrix} \frac{2}{r-l} & 0 & 0 & 0 \\ 0 & \frac{2}{t-b} & 0 & 0 \\ 0 & 0 & \frac{2}{n-f} & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix}\begin{pmatrix} 1 & 0 & 0 & -\frac{r+l}{2} \\ 0 & 1 & 0 & -\frac{t+b}{2} \\ 0 & 0 & 1 & -\frac{n+f}{2} \\ 0 & 0 & 0 & 1 \end{pmatrix}

  • 整理得到 (r>0,l=r,t>0,b=t)(r>0,l=-r,t>0,b=-t)

    Mpersp =(n/r0000n/t0000n+fnf2nfnf0010)M_{\text {persp }}=\begin{pmatrix} n/r & 0 & 0 & 0 \\ 0 & n/t & 0 & 0 \\ 0 & 0 & \frac{n+f}{n-f} & \frac{-2nf}{n-f} \\ 0 & 0 & 1 & 0 \end{pmatrix}

透视投影变换坐标变化证明

结论


将远处的平面压缩的过程(即经过Mpersp  ortho M_{\text {persp } \rightarrow \text { ortho }} 变换)规定:近处的平面的大小和位置永远不变;远处平面的大小会被压缩,但远近(z 值)不变;远处平面的中心点在压缩后也不变。那么对于近处和远处平面中间的点,其坐标的变化是——向远处平面靠近的,下面给出证明。

证明过程

Step1 透视投影变换矩阵形式

该矩阵的推导过程见课程 PPT,下面直接给出其形式:

Mpersp  ortho =(n0000n0000n+fnf0010)M_{\text {persp } \rightarrow \text { ortho }}=\begin{pmatrix} n & 0 & 0 & 0\\ 0 & n & 0 & 0\\ 0 & 0 & n+f & -n f \\ 0 & 0 & 1 & 0 \end{pmatrix}

Step2

初始点经过变换后得到新坐标,其中 z 方向的新坐标为f(z0)/z0f(z0)/z0

M(x0y0z01)=(nx0ny0f(z0)z0)/z0(nx0/z0ny0/z0f(z0)/z01)M \cdot\left(\begin{array}{c} x_{0} \\ y_{0} \\ z_{0} \\ 1 \end{array}\right)=\left(\begin{array}{c} n x_{0} \\ n y_{0} \\ f\left(z_{0}\right) \\ z_{0} \end{array}\right) \stackrel{/z_{0}}{\longrightarrow}\left(\begin{array}{c} n x_{0} / z_{0} \\ n y_{0} / z_{0} \\ f\left(z_{0}\right) / z_{0} \\ 1 \end{array}\right)

Step3

判断新坐标与初始坐标的 zz 方向上的大小,记为函数g(z0)g(z0)

g(z0)=f(z0)z0z0=n+fnfz0z0=?0\begin{aligned} g\left(z_{0}\right) &=\frac{f(z_{0})}{z_{0}}-z_{0} \\ &=n+f-\frac{n f}{z_{0}}-z_{0} \\ & \stackrel{?}= 0 \end{aligned}

g=nfz02z02,z0[f,n]g^{\prime}=\frac{n f-z_{0}^{2}}{z_{0}^{2}}, z_{0} \in[f, n]

g<0g(f)<0,g(n)>0,g(x)[f,n]g(f)=g(n)=0g(z0)<0\begin{aligned} & g^{\prime \prime}<0且g^{\prime}(f)<0, g^{\prime}(n)>0, 易知,g(x)在[f,n]区间内先减后增\\ & \Rightarrow g(f)=g(n)=0 \\ & \Rightarrow g(z_0)<0 \end{aligned}

最终得到 g(z0)<0g(z_0)<0 恒成立,即新坐标小于初始坐标,由于视角方向是 z-z 方向,可以得到中间点是向远处平面靠近的。

当然用绘图软件把f(z0)/z0f(z0)/z0绘制出来,y轴代表经过透视投影矩阵变换之后的深度,x轴表示变换之前的深度。在远近平面之间的点,其y值都会更加接近远平面。

推广:为什么需要进行近平面裁剪?

从上面的图中可以看出,当摄像机空间坐标下的深度值z:

  • 从近平面变化到0的过程中(近平面为负值,变化过程中始终为负值),经过透视投影之后其深度值从近平面变化到正无穷,即深度由负值变为了正值,这就导致这段距离的某个点经过透视投影跑到了摄像机的后面(摄像机处于原点),不需要保留。
  • 从0变化到正无穷的过程中,经过透视投影之后其深度值永远为负值,这就导致本来在摄像机后面的某个点经过透视投影跑到了摄像机的前面且在远平面之后,不应该被绘制,因此不应该保留。

注意

该透视投影矩阵作用到坐标系的某个点后,该点始终是处于右手坐标系的(+Z指向屏幕外,且公式中的n和f均在-Z轴上,即0>n>f0>n>f

该透视矩阵的特点:

  • 传入的n和f为负值
  • 在进行深度判断时,z(z<0)越大,离相机越近
  • 初始化深度缓冲时应该设置为最小的负值

对于OpenGL中透视投影矩阵的构造,最终得到的透视投影矩阵是改变了左右手坐标系的,即世界、观察空间坐标是右手坐标系,经过OpenGL的透视投影矩阵变换之后变为了左手坐标系(且公式中的n和f均在-Z轴上,但本身是正值,即0<n<f0<n<f):
  $$
  M_{\text {persp-opengl }}=\begin{pmatrix}
  n/r & 0 & 0 & 0 \
  0 & n/t & 0 & 0 \
  0 & 0 & \frac{-(n+f)}{f-n} & \frac{-2nf}{f-n} \
  0 & 0 & -1 & 0
  \end{pmatrix}
  $$
OpenGL投影矩阵(Projection Matrix)构造方法

相应的需要修改的地方有:

  • 传入的n和f要变为正值
  • 在进行深度判断时,z(z>0)越大,离相机越远
  • 初始化深度缓冲时应该设置为最大的正值

重心坐标插值——透视投影矫正

问题来源

  • 世界坐标下的三角形 ABC\triangle{ABC} 投影到屏幕空间对应的三角形为ABC\triangle{A'B'C'}

  • 在光栅化的时候需要知道屏幕空间三角形内某点 PP' 的深度值 ,我们目的实际是——获得 PP' 对应在世界坐标下的 PP 的深度值 。

  • 通过重心坐标插值来获得 PP 的深度值 ,即(世界坐标下):

    ZP=αZA+βZB+γZC Z_P = \alpha Z_A + \beta Z_B + \gamma Z_C

  • 世界坐标下的 αβγ\alpha 、\beta 、\gamma 不方便获取,于是直接拿到的是屏幕坐标下的 ABC\triangle{A'B'C'} 坐标,因此可以直接求出 αβγ\alpha '、\beta ' 、\gamma ' 进行插值,即(屏幕坐标下):

    ZP=αZA+βZB+γZC Z_P = \alpha ' Z_A + \beta ' Z_B + \gamma ' Z_C

  • 但是透视实际上是一种近大远小的视觉现象,离视点远的部分会被缩放得更加厉害,所以需要对这个结果进行所谓的插值校正。

  • 更本质的原因在于透视投影矩阵本身(参考:齐次空间的裁剪

    • 经过透视投影矩阵的变换之后,观察空间的所有点的x、y、z值与变换前相比都是线性的(只与远近平面、近平面的纵横比线性相关),但是经过透视除法之后,w值是变换前的-z值,因此x、y、z值与变换前相比是非线性的了。
    • 上述的结论还告诉我们,对于透视投影变换后的顶点属性,那么将不能运用线性插值(当然可以使用这里将要推导的透视矫正插值),否则很多在原来坐标系中的存储信息将会变形;

矫正公式推导

根据重心坐标插值:

ZP=αZA+βZB+γZC=[ZAZBZC][αβγ]Z_{P}=\alpha Z_{A}+\beta Z_{B}+\gamma Z_{C}=\left[\begin{array}{lll} Z_{A} & Z_{B} & Z_{C} \end{array}\right]\left[\begin{array}{l} \alpha \\ \beta \\ \gamma \end{array}\right]

ZP=αZA+βZB+γZC=[ZAZBZC][αβγ]Z_{P'}=\alpha ' Z_{A'}+\beta ' Z_{B'}+\gamma ' Z_{C'}=\left[\begin{array}{lll} Z_{A'} & Z_{B'} & Z_{C'} \end{array}\right]\left[\begin{array}{l} \alpha ' \\ \beta ' \\ \gamma ' \end{array}\right]

由重心插值公式的性质推导:

1=α+β+γ 1 = \alpha ' + \beta ' + \gamma '

ZPZP=ZAZAα+ZBZBβ+ZCZCγ\begin{array}{l} \frac{Z_{P}}{Z_{P}}=\frac{Z_{A}}{Z_{A}} \alpha^{\prime}+\frac{Z_{B}}{Z_{B}} \beta^{\prime}+\frac{Z_{C}}{Z_{C}} \gamma^{\prime} \end{array}

ZPZP=[ZAZBZC][1ZAα1ZBβ1ZCγ]\frac{Z_{P}}{Z_{P}}=\left[\begin{array}{lll} Z_{A} & Z_{B} & Z_{C} \end{array}\right]\left[\begin{array}{c} \frac{1}{Z_{A}} \alpha^{\prime} \\ \frac{1}{Z_{B}} \beta^{\prime} \\ \frac{1}{Z_{C}} \gamma^{\prime} \end{array}\right]

ZP=[ZAZBZC][1ZAα1ZBβ1ZCγ]ZP{Z_{P}}=\left[\begin{array}{lll} Z_{A} & Z_{B} & Z_{C} \end{array}\right]\left[\begin{array}{c} \frac{1}{Z_{A}} \alpha^{\prime} \\ \frac{1}{Z_{B}} \beta^{\prime} \\ \frac{1}{Z_{C}} \gamma^{\prime} \end{array}\right]Z_{P}

ZP=[ZAZBZC][ZPZAαZPZBβZPZCγ]Z_{P}=\left[\begin{array}{lll} Z_{A} & Z_{B} & Z_{C} \end{array}\right]\left[\begin{array}{c} \frac{Z_{P}}{Z_{A}} \alpha^{\prime} \\ \frac{Z_{P}}{Z_{B}} \beta^{\prime} \\ \frac{Z_{P}}{Z_{C}} \gamma^{\prime} \end{array}\right]

得到如下结论(重要结论):

ZPZAα=αZPZBβ=βZPZCγ=γ\frac{Z_{P}}{Z_{A}} \alpha^{\prime}=\alpha , \frac{Z_{P}}{Z_{B}} \beta^{\prime}=\beta , \frac{Z_{P}}{Z_{C}} \gamma^{\prime}=\gamma

其含义是某一点 PP' 在屏幕空间下的重心坐标 (α,β,γ)(\alpha ' , \beta ' , \gamma ') 对应于世界坐标点 PP 的重心坐标变成了 (ZPZAα,ZPZBβ,ZPZCγ)(\frac{Z_{P}}{Z_{A}} \alpha^{\prime} , \frac{Z_{P}}{Z_{B}} \beta^{\prime} , \frac{Z_{P}}{Z_{C}} \gamma^{\prime})

由于重心坐标相加为 1:

ZPZAα+ZPZBβ+ZPZCγ=1\frac{Z_{P}}{Z_{A}} \alpha^{\prime}+\frac{Z_{P}}{Z_{B}} \beta^{\prime}+\frac{Z_{P}}{Z_{C}} \gamma^{\prime}=1

得到正确的深度值:

ZP=1αZA+βZB+γZCZ_{P}=\frac{1}{\frac{\alpha^{\prime}}{Z_{A}}+\frac{\beta^{\prime}}{Z_{B}}+\frac{\gamma^{\prime}}{Z_{C}}}

接下来的步骤就是求屏幕空间的点 PP' 的重心坐标 αβγ\alpha ' 、 \beta ' 、 \gamma ' 代入上述公式得到其实际对应的深度值。

通用属性插值

正确得出深度的插值结果之后,再看看任意属性(法线向量,纹理坐标等)插值结果,设 IPI_P 为要插值求得的在屏幕空间中 PP' 点所对应到世界坐标 PP 点的属性。

对于 ABC\triangle ABC ,根据重心坐标插值有:

IP=αIA+βIB+γIC=[IAIBIC][αβγ]I_{P}=\alpha I_{A}+\beta I_{B}+\gamma I_{C}=\left[\begin{array}{lll} I_{A} & I_{B} & I_{C} \end{array}\right]\left[\begin{array}{l} \alpha \\ \beta \\ \gamma \end{array}\right]

根据上述重要结论有:

IP=[IAIBIC][ZPZAαZPZBβZPZCγ]I_{P}=\left[\begin{array}{lll} I_{A} & I_{B} & I_{C} \end{array}\right]\left[\begin{array}{c} \frac{Z_{P}}{Z_{A}} \alpha^{\prime} \\ \frac{Z_{P}}{Z_{B}} \beta^{\prime} \\ \frac{Z_{P}}{Z_{C}} \gamma^{\prime} \end{array}\right]

最后整理一下:

IP=(αZAIA+βZBIB+γZCIC)ZPI_{P}=\left(\frac{\alpha^{\prime}}{Z_{A}} I_{A}+\frac{\beta^{\prime}}{Z_{B}} I_{B}+\frac{\gamma^{\prime}}{Z_{C}} I_{C}\right) Z_{P}

折射光线的计算

折射(refraction) 是指光通过非均匀介质或者穿过不同介质的分界面时,由于其传播速度的变化而引起传播方向变化的现象。

折射定律(law of refraction) 又称 斯涅耳定律(Snell’s law),它描述了光从一种介质进入另一种介质时产生折射现象的规律,内容如下:

  • 折射光线位于入射光线和界面法线所决定的平面内;
  • 折射光线和入射光线分别在法线两侧;
  • 入射角 θi\theta_i 和折射角 θt\theta_t 的正弦之比是一个与入射角无关的常数,等于相对折射率,即 ηisinθi=ηtsinθt\eta_{i}\sin \theta_{i}=\eta_{t} \sin \theta_{t},其中 ηi\eta_{i}ηt\eta_{t} 分别是入射侧和折射侧介质的绝对折射率, 是相对折射率;

推导过程

假设入射光线 ωi\overrightarrow{\omega_i} 、出射光线 ωi\overrightarrow{\omega_i}、法线向量n\overrightarrow{n}均为单位向量,将出射光线ωt\omega_t分成垂直于法线向量和平行于法线向量的两个分量ωt=ωt+ωt\overrightarrow{\omega_t}={\overrightarrow{\omega_t}}_{\perp}+{\overrightarrow{\omega_t}}_{\|},入射光线也是如此ωi=ωi+ωi\overrightarrow{\omega_i}={\overrightarrow{\omega_i}}_{\perp}+{\overrightarrow{\omega_i}}_{\|}

由于:

sinθt=ηisinθi/ηtcosθt=1(ηiηtsinθi)2\begin{array}{c} \sin \theta_{t} = \eta_{i} \sin \theta_{i}/\eta_{t} \\ \\ \Rightarrow \cos \theta_{t} = \sqrt{1- \left(\frac{\eta_{i}}{\eta_{t}} \sin \theta_{i}\right)^{2}} \end{array}

其中:

ωt=cosθt(n)=(n)1(ηiηtsinθi)2=1(ηiηt)2(1(ωin)2)(n)\begin{aligned} {\overrightarrow{\omega_t }}_{\|} &= \cos \theta_{t} \cdot (-\overrightarrow{n }) \\ &=(-\overrightarrow{n }) \cdot \sqrt{1- \left(\frac{\eta_{i}}{\eta_{t}} \sin \theta_{i}\right)^{2}} \\ &= \sqrt{1- \left(\frac{\eta_{i}}{\eta_{t}} \right)^{2}(1-(\overrightarrow{\omega_i } \cdot \overrightarrow{n })^2)}(-\overrightarrow{n }) \end{aligned}

由于:

ωt/sinθt=ωi/sinθi=1ωt=ωisinθt/sinθi=ωiηi/ηt\begin{array}{c} | \overrightarrow{\omega_t }_{\perp} | / \sin \theta_{t}= | \overrightarrow{\omega_i }_{\perp} | /\sin \theta_{i} =1 \\ \\ \Rightarrow\overrightarrow{\omega_t }_{\perp} = -\overrightarrow{\omega_i }_{\perp} \cdot \sin \theta_{t} /\sin \theta_{i} = -\overrightarrow{\omega_i }_{\perp} \cdot \eta_i / \eta_t \end{array}

对于上述公式的未知量ωi\overrightarrow{\omega_i}_{\perp}有:

ωi=ωiωi=ωicosθin=ωi(ωin)n\overrightarrow{\omega_i }_{\perp} = {\overrightarrow{\omega_i }} - {\overrightarrow{\omega_i }}_{\|} = {\overrightarrow{\omega_i }} - \cos \theta_{i} \cdot \overrightarrow{n } = {\overrightarrow{\omega_i }} - (\overrightarrow{\omega_i } \cdot \overrightarrow{n }) \overrightarrow{n }

得到

ωt=ωt+ωt=ηi/ηt(ωi+(ωin)n)+1(ηiηtsinθi)2(n)\begin{aligned} \overrightarrow{\omega_t } &={\overrightarrow{\omega_t }}_{\perp}+{\overrightarrow{\omega_t }}_{\|} \\ &= \eta_i / \eta_t(-\overrightarrow{\omega_i }+(\overrightarrow{\omega_i } \cdot \overrightarrow{n }) \overrightarrow{n }) + \sqrt{1- \left(\frac{\eta_{i}}{\eta_{t}} \sin \theta_{i}\right)^{2}}(-\overrightarrow{n }) \end{aligned}

因此,在计算折射光线时,只需要得到:

ωt=ηi/ηt(ωi+(ωin)n){\overrightarrow{\omega_t }}_{\perp} = \eta_i / \eta_t(-\overrightarrow{\omega_i }+(\overrightarrow{\omega_i } \cdot \overrightarrow{n }) \overrightarrow{n })

ωt=1(ωt)2(n)=1(ηiηt)2(1(ωin)2)(n)\begin{aligned} {\overrightarrow{\omega_t }}_{\|} &=\sqrt{1- ({\overrightarrow{\omega_t }}_{\perp})^2}(-\overrightarrow{n })\\ &= \sqrt{1- \left(\frac{\eta_{i}}{\eta_{t}} \right)^{2}(1-(\overrightarrow{\omega_i } \cdot \overrightarrow{n })^2)}(-\overrightarrow{n }) \\ \end{aligned}

蒙特卡洛路径追踪算法

示意图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 着色算法
shade(p, wo)
// Contribution from the light source.
L_dir = 0.0
Uniformly sample the light at x’ (pdf_light = 1 / A)
Shoot a ray from p to x’
If the ray is not blocked in the middle
L_dir = L_i * f_r * cos θ * cos θ’ / |x’ - p|^2 / pdf_light

// Contribution from other reflectors.
L_indir = 0.0
Test Russian Roulette with probability P_RR
Uniformly sample the hemisphere toward wi (pdf_hemi = 1 / 2pi)
Trace a ray r(p, wi)
If ray r hit a non-emitting object at q
L_indir = shade(q, -wi) * f_r * cos θ / pdf_hemi / P_RR
Return L_dir + L_indir