游戏数学

点与矢量

简书不识别公式，有道云支持，后续修改

• 点（2维或3维）
• 坐标系

  • 类型

    根据实际情况选择合适坐标系

    • 笛卡尔坐标系 （x, y, z）
    • 圆柱坐标系 （h, r, $\theta$）
    • 球坐标系 （r, $\phi$, $\theta$）

  • 方向

    反转任意轴即可相互转换，一般使用左手坐标系

    • 左手坐标系 （使用左手判定）
    • 右手坐标系 （使用右手判定）
• 矢量
  • 基矢量
  • 矢量运算
    • 矢量和标量乘法
      • 单标量
      • 分量乘法（阿达马积 Hadamard product）
    • 加法和减法
      • 矢量之间
      • 点和方向之间
    • 模
    • 归一化和单位矢量
    • 法矢量
    • 点积和投影
      • 点积判定
        • 共线
        • 共线但反方向
        • 垂直
        • 相同方向
        • 相反方向
    • 叉积
      • 模
      • 方向 （随着坐标系的选择而改变）
      • 反交换律
      • 绕笛卡儿积的正旋方向

  \vec{i}\times\vec{j} = -(\vec{j}\times\vec{i}) = \vec{k}
  
  \vec{j}\times\vec{k} = -(\vec{k}\times\vec{j}) = \vec{i}
  
  \vec{k}\times\vec{i} = -(\vec{i}\times\vec{k}) = \vec{j}
  

  • 点和矢量的线性插值

  \vec{L}=LERP(\vec{A},\vec{B},\beta)
  
  =(1-\beta)\vec{A}+\beta\vec{B}
  
  =[(1-\beta)A_x+\beta B_x,
  (1-\beta)A_y+\beta B_y,
  (1-\beta)A_z+\beta B_z]
  

• 矩阵

  • 乘法

  • 列矢量和行矢量（影响其与矩阵乘法的形式）

  • 单位矩阵

  • 逆矩阵

    • 高斯消去法
    • LU分解法

  • 转置矩阵

  • 齐次坐标

    • 点或矢量从三维延伸到四维
    • 表示点的平移
    • 点的w的分量为1，方向矢量的w分量为0
    • 四维齐次坐标转换为三维非齐次坐标，将各分量除以w

  • 基础变换矩阵

    • 特点
      • 主行矢量
      • U代表旋转及或旋转
      • t 代表平移矢量

    \begin{bmatrix} U_{3\times3} & 0_{3\times1} \\ t_{1\times3} & 1\end{bmatrix}
    

    • 平移
    • 旋转
      • 纯旋转矩阵的逆矩阵，即其转置矩阵

    rotate_x(\vec{r},\phi)=[r_x,r_y,r_z,1]\begin{bmatrix}
    1&0&0&0\\
    0&\cos\phi&\sin\phi&0\\
    0&-\sin\phi&\cos\phi&0\\
    0&0&0&1\end{bmatrix}
    
    rotate_y(\vec{r},\theta)=[r_x,r_y,r_z,1]\begin{bmatrix}
    \cos\theta&0&-\sin\theta&0\\
    0&1&0&0\\
    \sin\theta&0&\cos\theta&0\\
    0&0&0&1\end{bmatrix}
    
    rotate_z(\vec{r},\gamma)=[r_x,r_y,r_z,1]\begin{bmatrix}
    \cos\gamma&\sin\gamma&0&0\\
    -\sin\gamma&\cos\gamma&0&0\\
    0&0&1&0\\
    0&0&0&1\end{bmatrix}
    

    • 缩放
      • 统一缩放
      • 非统一缩放

    \vec{r}S=[r_x,r_y,r_z,1]\begin{bmatrix}
    s_x&0&0&0\\
    0&s_y&0&0\\
    0&0&s_z&0\\
    0&0&0&1\end{bmatrix}
    

    • 4x3矩阵
      • 4x4仿射矩阵必然有一列基矢量，可省去以节省内存

  • 坐标空间

    • 模型空间
      • 前,上,左右（F,U,L/F）
      • 欧拉角
        • 俯仰角$\phi$ 绕L/F pitch
        • 偏航角$\theta$ 绕U yaw
        • 滚动角$\psi$ 绕F roll
    • 世界空间
      • 固定坐标空间
      • 联系其他单个物体
    • 观察空间
      • 固定于摄像机的坐标系
      • 原点在摄像机的焦点
      • OpenGL的摄像机坐标系为右手坐标系

  • 基的变更

    • 坐标系是相对的
    • 其他坐标空间直接或间接地相对于世界空间
    • 坐标变换
      • $\vec{w}_c$是子空间轴相对于父空间的位置
      • $\vec{i}_c$, $\vec{j}_c$, $\vec{k}_c$ 都是子空间的轴在父空间的坐标表示

    P_p=P_cM_{c->p}
    
    M_{c->p}=\begin{bmatrix}
    \vec{i}_c&0\\
    \vec{j}_c&0\\
    \vec{k}_c&0\\
    \vec{w}_c&0\end{bmatrix}
    

    • 缩放子轴
    • 从矩阵中获取单位基矢量
    • 变换坐标系vs变换矢量
      • 某矩阵把矢量从子空间变换至父空间，则该矩阵同时也把坐标轴从父空间变换至子空间
    • 约定
      • 变换施于矢量而非坐标轴
      • 把矢量写成行而非列
      • 但也需要具体问题具体分析

  • 变换法矢量

    • 注意确保维持其长度和垂直性
    • $M_{A->B}$表示将点或矢量（非法矢）从空间A变换到B，若$M_{A->B}$只含统一缩放而无切变，则其可变换法矢量，否则不可。若$M_{A->B}$含非统一缩放或切变（非正交），则可用$(M^{-1}_{A->B})^T$逆转置矩阵变换法矢量。

  • 内存中存储矩阵

    • 行存储
    • 列存储
• 四元数
  • 矩阵变换的缺点
    • 矩阵使用9个浮点值表示旋转，有冗余，因为旋转只有三个自由度
    • 矩阵乘法旋转矢量，乘法加法运算次数多
    • 矩阵难以插值
  • 把单位四元数视为三维旋转
    • $\vec{a}$为单位旋转轴，右手法则旋转
    • $\theta$为旋转角度

    q=[\vec{q}_v\quad q_s]=[\vec{a}\sin{\frac{\theta}{2}}\quad\cos{\frac{\theta}{2}}]
    
    q_x^2+q_y^2+q_z^2+q_w^2=1
    

  • 四元数运算
    • 乘法 （格拉斯曼积 Grassmann product）

    pq=\left[(p_s\vec{q}_v+q_s\vec{p}_v+\vec{p}_v\times\vec{q}_v)\quad(p_sq_s-\vec{p}_v\cdot\vec{q}_v)\right]
    
    \text{p,q为旋转，先旋转q，再旋转p}
    

    • 共轭及逆四元数

    \text{逆四元数满足}\quad
    qq^{-1}=1\quad\text{则}\quad
    q^{-1}=\frac{q^*}{{\begin{vmatrix}q\end{vmatrix}}^2}
    
    \text{共轭}\quad
    q^{*}=[-\vec{q}_v\quad q_s]
    
    \text{逆}\quad
    q^{-1}=q^*\quad\text{当}{\begin{vmatrix}q\end{vmatrix}}=1
    

    • 积的共轭及逆四元数

    (pq)^*=q^*p^*
    
    (pq)^{-1}=q^{-1}p^{-1}
    

  • 以四元数旋转矢量
    • 将矢量写作四元数形式

    v=[\vec{v}\quad0]
    

    • 旋转

    v^{\prime}=rotate(q,\vec{v})=qvq^{-1}=qvq^*
    
    \text{或}\quad
    \vec{v}^{\prime}=rotate(q,\vec{v})=\vec{v}+2\vec{q}_v\times(\vec{q}_v\times\vec{v}+q_s\vec{v})
    

    • 四元数的串接
      • 矩阵的串接

      \vec{v}^{\prime}=\vec{v}R_1R_2R_3=\vec{v}R_{net}
      

      • 四元数的串接

      v^{\prime}=q_3q_2q_1vq_1^{-1}q_2^{-1}q_3^{-1}=q_{net}vq_{net}^{-1}
      

  • 等价的四元数和矩阵

  \text{设}
  q=[x\quad y\quad z\quad w]\text{, 则}
  
  R=\begin{bmatrix}
  1-2y^2-2z^2&2xy+2zw&2xy-2yw\\
  2xy-2zw&1-2x^2-2z^2&2yz+2xw\\
  2xz+zyw&2yz-2xw&1-2x^2-2y^2
  \end{bmatrix}    
  

  • 旋转性的线性插值

    • 线性插值

    q_{lerp}=LERP(q_A,q_B,\beta)
    
    =\frac{(1-\beta)q_A+\beta q_B}{\begin{vmatrix}(1-\beta)q_A+\beta q_B\end{vmatrix}}
    
    =normalize\left({\begin{bmatrix}
    (1-\beta)q_{A_x}+\beta q_{B_x}\\
    (1-\beta)q_{A_y}+\beta q_{B_y}\\
    (1-\beta)q_{A_z}+\beta q_{B_z}\\
    (1-\beta)q_{A_w}+\beta q_{B_w}
    \end{bmatrix}}^T \right)
    

    缺点：四元数其实是四维超球上的点。LERP实际上是沿超球的弦上进行插值，而不是在超球面上插值。这样导致----当$\beta$以恒定速度改变时，旋转动画并非以恒定角速度进行，两端慢，中间快。

    • 球面线性插值

    q_{slerp}=SLERP(p,q,\beta)
    
    =\frac{\sin{((1-\beta)\theta)}}{\sin\theta}p+\frac{\sin{(\beta \theta)}}{\sin\theta}q
    
    \cos\theta=p\cdot q
    

• 比较各种旋转表达方式
  • 欧拉角

    • 简单直观

    • 围绕单轴的旋转容易插值，但注意任意方向轴的插值

    • 万向节锁

      当旋转$90^{\degree}$时，三主轴中的一个会与另一个主轴完全对齐。

    • 旋转顺序对结果产生影响

  • $3\times3$矩阵
    • 独一无二的表达任意旋转
    • 方便但不直观
    • 不容易插值，存储空间大
  • 轴角
    • 直观，存储少 $[\vec{a}\quad \theta]$
    • 不方便插值
    • 必须转换为矩阵或四元数使用
  • 四元数
    • 可串接旋转
    • 可直接作用于点和矢量
    • 插值方便
    • 存储少，利用旋转时$q$等效为$-q$且为单位四元数可以少存储一个元素
  • $SQT$变换
    • 四元数结合平移矢量和缩放因子

    SQT=[\vec{s}\quad q\quad \vec{t}]
    

    • 容易插值，平移矢量和缩放因子采用$LREP$，四元数采用$SLREP$。
  • 对偶四元数
    • 可完整表时涉及旋转、平移、缩放的变换

    \hat a=a_0+\varepsilon a_{\varepsilon}
    

  • 旋转和自由度
    • 指物体有多少个互相独立的可变状态（位置和定向）。
    • 自由度$DOF$

      N_{DOF}=N_{\text{参数}}-N_{\text{约束}}
      

      类别	参数个数	约束个数	约束
      欧拉角	3	0	无
      轴角	4	1	轴矢量为单位长度
      四元数	4	1	四元数为单位长度
      矩阵	9	6	每个行和列矢量为单位长度

• 其他数学对象
  • 直线、光线及线段
    • 参数式方程
  • 球体
    • 存储为$[C_x\quad C_y\quad C_z\quad r]$
  • 平面
    • 一般式及点法式

      Ax+By+Cz+D=0
      
      \vec{n}\cdot\vec{P}=-d
      

    • 存储为$\vec{L}=[\vec{n}\quad d]$
    • 使用逆转置矩阵可以把$\vec{L}$从一空间转换为另一空间
  • 轴对齐包围盒（AABB）
    • 三维长方体，6个面都与某坐标系的正交轴对齐
    • $[x_{min}\quad x_{max}\quad y_{min}\quad y_{max}\quad z_{min}\quad z_{max}]$
    • 检测一点P是否在AABB盒内

    x_{min} \leq P_x \leq x_{max} ,
    
    y_{min} \leq P_y \leq y_{max} ,
    
    z_{min} \leq P_z \leq z_{max}
    

    • 用作碰撞检测的早期淘汰测试
      • AABB盒相交
  • 定向包围盒（OBB）
    • 三维长方体，其定向与其包围的物体按照某逻辑方式对齐，通常与物体的局部空间轴对齐
    • 可将点变换到与OBB对齐的坐标空间，在使用AABB相交测试
  • 平截头体
    • 观察空间中
    • 用点积测出某点是在每个平面的前面还是后面，可以判断点是否在平截头体内。
    • 或，把要测试的世界空间点，通过透视变换到齐次裁剪空间。则世界空间的平截头体在此空间变为AABB
  • 凸多面体区域
    • 由任意数量的平面集合定义，平面的法线全部向内或向外。
    • 适合作为任何形状的出发区域
• 硬件加速的SIMD运算
  • SSE寄存器
    • 在32位浮点包裹模式中，每个SSE寄存器含4个32位float
    • Visual Studio 编译器提供内建数据类型__m128
    • __m128变量需要16字节对齐
• 产生随机数
  • 线性同余产生器LGG
  • 梅森旋转算法MT（SFMT实现）
  • 所有伪随机数产生器之母及Xorshift

OpenGL

• View Matrix

• Perspective Projection Matrix

P=\begin{bmatrix}
\frac{1}{aspect\,\tan{\frac{\theta}{2}}}&0&0&0\\0&\frac{1}{\tan{\frac{\theta}{2}}}&0&0\\
0&0&-\frac{f+n}{f-n}&-\frac{2fn}{f-n}\\
0&0&-1&0
\end{bmatrix}

\text{[r,l]   [t,b]}

P=\begin{bmatrix}
\frac{2n}{r-l}&0&\frac{r+l}{r-l}&0\\
0&\frac{2n}{t-b}&\frac{t+b}{t-b}&0\\
0&0&-\frac{f+n}{f-n}&-\frac{2fn}{f-n}\\
0&0&-1&0
\end{bmatrix}

\text{if r=-l, t=-b}

P=\begin{bmatrix}
\frac{n}{r}&0&\frac{r+l}{r-l}&0\\
0&\frac{2n}{t-b}&\frac{t+b}{t-b}&0\\
0&0&-\frac{f+n}{f-n}&-\frac{2fn}{f-n}\\
0&0&-1&0
\end{bmatrix}

• Orthographic Projection Matrix

O=\begin{bmatrix}
\frac{2}{r-l}&0&0&-\frac{r+l}{r-l}\\
0&\frac{2}{t-b}&0&-\frac{t+b}{t-b}\\
0&0&-\frac{2}{f-n}&-\frac{f+n}{f-n}\\
0&0&0&1
\end{bmatrix}

\text{if r=-l, t=-b}

O=\begin{bmatrix}
\frac{1}{r}&0&0&0\\
0&\frac{1}{t}&0&0\\
0&0&-\frac{2}{f-n}&-\frac{f+n}{f-n}\\
0&0&0&1
\end{bmatrix}

DirectX