前言
由于本篇主要是谈谈基础，所以一些快速运算方法一般不在本篇探讨范围之内，一些特殊的快速手法等后续专门独立开篇再谈。
基础篇
解线性方程组：令 \(A\) 为 \(n×n\) 的矩阵，\(α\) 和 \(β\) 为 n 维的列向量，设 \(A = \begin{bmatrix} \alpha_1 & \alpha_2 & \alpha_3 & ... & \alpha_n \end{bmatrix}\)，对于线性方程组 \(Ax = β\)，初等数学中最常规的就是消元法了，但在线性代数中，有两种解法，一种是等式两边同乘 \(A\) 的逆阵，得到 \(x = A^{-1}β\)；另一种是克莱姆法则，可得 \(x_i = |A_i| / |A|\)，其中 \(|A|\) 为 矩阵 \(A\) 对应的行列式， \(|A_i|\) 为将矩阵 \(A\) 中第 \(i\) 列换成 \(β\) 后对应的行列式，如 \(x_3 = \left| \begin{array}{cccc} \alpha_1 & \alpha_2 & \beta & ... & \alpha_n \end{array} \right| / |A|\)。
向量内积：又称向量点积，向量点乘。设 a，b 为空间中两个 n 维向量 \(a=(x_1,x_2,x_3,...,x_n)\)，\(b=(y_1,y_2,y_3,...,y_n)\)，则 \(a·b=|a|*|b|*cos(α)=\sum\limits_{i=1}^{n}x_iy_i\)，其中\(|a|= \sqrt{(x_1)^2+(x_2)^2+(x_3)^2+...+(x_n)^2},\alpha\) 为两向量之间夹角。向量内积一般用来计算投影（令 \(|b|=1\)，则 \(a \cdot b=|a|cos(α)\)，即为向量 a 在 b 上的投影），和两向量之间角度。
向量外积：又称向量叉积，向量叉乘，\(|a×b|=||a|*|b|*sin(\alpha)|\)。向量外积一般只针对二维向量和三维向量，对于二维向量，\(a×b=a.x*b.y-b.x*a.y\)，可以认为是一个值（其实也是一个向量），对于三维向量 \(a×b=(a.y*b.z-b.y*a.z, a.x*b.z-b.x*a.z, a.x*b.y-b.x*a.y)\)，是一个向量，且该向量一定垂直于 a，b 两向量构成的平面，所以三维向量的外积一般可以用来计算平面的法向量。向量外积的几何意义为两向量构成平行四边形的面积，二维向量外积直接取绝对值即为面积，不取绝对值则可以用来判断两向量构成三角形的点是以顺时针排列（小于 0）的还是逆时针排列（大于 0）的，三维向量外积取所得向量的模即为面积。
向量混合积： 设 \(a\)，\(b\)，\(c\) 为空间中三个向量，则其混合积 \((a,b,c)= (a×b)·c = -(c×b)·a = -(a×c)·b\)，\((a,b,c) = (b,c,a) = (c,a,b)\)。若 \(a\)，\(b\)，\(c\) 都为 3 维的向量，矩阵 \(A = [a, b, c]\)，则 \(|A| = (a, b, c)\) ，其中 \(a,b,c\) 是列向量或行向量都可以，因为 \(|A| = |A^T|\)，该混合积的几何意义为这三个向量组成的平行六面体的体积。
直线参数方程：设 P 为直线上任意一点，若 P1 和 P2 为直线上已知两点，则 \(P=P1 + (P2-P1)*t, t\in[-∞,+∞]\)。当然直线的参数方程有很多种形式，之所以用两点式，是因为两点式除了能表示直线，同样能表示射线（\(t\ge 0\)），也能表示线段（\(0\le t\le 1\)）。
平面方程：设 P 为平面上任意一点，O 为平面上已知一点，n 为平面法向量，则平面方程为：\((P-O)·n=0\) 。
三角形内的点：设 P0，P1，P2 为三角形 3 个顶点，若 P 为三角形内一点，同时可认为 (P1-P0) 和 (P2-P0) 为一组基向量，则 P 满足 \(P=P0+u*(P1-P0)+v*(P2-P0),u \in [0,1],v \in [0,1],u+v\le 1\)。
距离篇
一般的距离计算都是向量计算，要么点乘，要么叉乘。
点到直线的距离
计算点到直线的距离通用的解法是使用向量叉乘，设 P 为直线外一点，Q1 和 Q2 为直线上两点，则可得到两向量 \(a=P-Q1, b=Q2-Q1\)，则 P 到直线的距离为 \(d=|a×b|/|b|\)，叉乘是面积，而面积又等于底乘高，\(|b|\) 为底，\(d\) 为高。当然点到直线的距离还有其他的一些方法，如 利用公式，利用点积再使用勾股定理，直接利用点积计算直线法向量上的投影等，这些方法都有一定的局限性。
点到线段的距离
设 d 为点 P 到线段的距离，表示为点 P 到线段上最近点的距离，设 P1，P2 分别为线段两端点，计算 \(a=(P-P1)·(P2-P1) / |P2-P1|\)，若 \(0≤a≤1\)，则 d 为点 P 到线段所在直线的距离，若 \(a<0\)，则 d 为点 P 到点 P1 的距离，若 \(a>1\)，则 d 为点 P 到点 P2 的距离。
三维中点到三角形的距离
先计算点 P 到三角形所在平面的投影点 \(P'\)，若 \(P'\) 在三角形内，则只需要求点 P 到三角形所在平面的距离，否则需要分别求点 P 到三角形三条边的距离（点到线段的距离），取三个距离中最小值即为点到三角形的距离。
点到平面的距离
直接利用点乘计算，平面外一点与平面内一点构成的向量到平面法向量上的投影，即为点到平面的距离。设 P 为平面外一点，O 为平面内一点，n 为平面法向量，则点 P 到平面的距离为 \(d=(P-O) \cdot n\)。
直线到直线的距离
设 P1 和 P2 为直线 1 上两点，Q1 和 Q2 为直线 2 上两点，则直线 1 与直线 2 之间的距离计算流程为：
- 先判断两直线是否平行，即 \((P2-P1) = k*(Q2-Q1), k \neq 0\) 有解。若平行，则相当于计算点到直线的距离；若不平行，则进行下一步。
- 再判断两直线是否共面，即 P1，P2，Q1，Q2 四点共面，先计算 \(n=(P2-P1)×(Q2-Q1)\)，再分别计算 \(n·(Q1-P1), n·(Q2-P1), n·(Q1-P2), n·(Q2-P2)\)，若这四个值都为 0 ，则两直线共面（之所以需要判断 4 个值，是为防出现 3 点共线情况，当然也可以先判断 3 点共线，再取不共线的一点构成向量与 n 做点积进行判断），若两直线共面，则两直线必然相交；若两直线不共面，则两直线间距离为 \(d=(Q1-P1) \cdot n\)。
直线到平面的距离
设 P1 和 P2 为直线上两点，n 为平面法向量，则直线与平面之间的距离计算流程为：
- 先判断直线与平面是否平行，即若 \((P2-P1) \cdot n = 0\) ，则直线与平面平行，则直线到平面的距离为 点 P1 到平面的距离；
- 若直线与平面不平行，则直线与平面必相交。
相交篇
一般的相交求交点都是联立方程组，但有些只需要做相交测试的，可以利用一些特殊方法快速求出来。有些相交直接求很麻烦或很难，可以反向求不相交的情况，而在实际编程中，一般都有很多条件语句，以便快速返回提高效率。
直线与直线相交
设直线 1 方程为 \(P=P1 + (P2-P1)*t\)，直线 2 方程为 \(P=Q1 + (Q2-Q1)*u\)，联立两方程得 \(P1 + (P2-P1)*t = Q1 + (Q2-Q1)*u\)，即 \(P1-Q1 = (Q2-Q1)*u - (P2-P1)*t\)，设 \(v_0=Q2-Q1,v_1=P1-P2,v_2=P1-Q1\)，即 \(v_0*u+v_1*t=v_2\)，现在的问题就是解这个方程了，一种是直接把向量分解成单一维度，列方程组；一种是等式两边分别同时点乘 \(v_0\) 和 \(v_1\)，可得 \[ \begin{cases} (v_0 \cdot v_0)*u+(v1 \cdot v_0)*t=v_2 \cdot v_0 , \\ (v_0 \cdot v_1)*u+(v1 \cdot v_1)*t=v_2 \cdot v_1 \end{cases} \] 解得： \[ \begin{cases} u=((v1·v1)(v2·v0)-(v1·v0)(v2·v1)) / ((v0·v0)(v1·v1) - (v0·v1)(v1·v0)) , \\ t = ((v0·v0)(v2·v1)-(v0·v1)(v2·v0)) / ((v0·v0)(v1·v1) - (v0·v1)(v1·v0)) \end{cases} \] 若方程有解，则两直线相交，由于两点式方程可以很简单的转换为线段和射线，所以该方法同样可以判断两线段相交，两射线相交，射线与直线与线段相交等。针对二维直线，还有一种解法是将原方程写成矩阵形式，利用克莱姆法则进行求解，不过总的来说，最终的解都是一种形式。
直线与平面相交
求直线与平面相交，直接联立直线方程和平面方程即可，得 \((P1-O+(P2-P1)*t)·n=0\) ，即 \(t=(P1-O)·n/((P1-P2)·n)\)。若 t 有解，则直线与平面相交。同样也可以用该方法判断线段或射线与平面相交。
直线与三角形相交
二维中判断直线和三角形相交相当于判断直线和线段相交，而在三维中则同样需要联立直线和三角形方程，设直线方程为 \(P=P1+(P2-P1)*t\)，三角形方程为 \(P=Q1+(Q2-Q1)*u+(Q3-Q1)*v\)， 则联立后方程为 \(P1-Q1=(P1-P2)*t+(Q2-Q1)*u+(Q3-Q1)*v\)，令 \(V_0=P1-Q1,V_1=P1-P2,V_2=Q2-Q1,V_3=Q3-Q1\)，则 \(V_0=V_1*t+V_2*u+V_3*v\)，可以分解向量求解，也可以使用克莱姆法则得： \[ t = \frac{\begin{vmatrix} V_0 & V_2 & V_3 \end{vmatrix}}{\begin{vmatrix} V_1 & V_2 & V_3 \end{vmatrix}} \qquad u = \frac{\begin{vmatrix} V_1 & V_0 & V_3 \end{vmatrix}}{\begin{vmatrix} V_1 & V_2 & V_3 \end{vmatrix}} \qquad v = \frac{\begin{vmatrix} V_1 & V_2 & V_0 \end{vmatrix}}{\begin{vmatrix} V_1 & V_2 & V_3 \end{vmatrix}} \qquad \] 由于三阶行列式也可以用向量混合积来求值，所以 \[ t = \frac{-V_0 × V_3 · V_2 }{V_1 × V_2 · V_3} \qquad u = \frac{V_0 × V_3 · V_1 }{V_1 × V_2 · V_3} \qquad v = \frac{V_1 × V_2 · V_0 }{V_1 × V_2 · V_3} \qquad \] 若方程有解，且满足三角形条件，则相交。
二维中凸多边形与凸多边形相交
曾在「快速判断三角形与长方体相交」中写过判断两凸多边形是否相交直接使用分离轴理论（separating axis theorem， AST）即可，简而言之就是，取两多边形任意一条边，计算两多边形在该边法向量上的投影是否相交，若存在一条边，使投影不相交，则两凸多边形不相交。
二维中点在多边形内
判断点在多边形内有很多种方法，利用叉乘，面积等方法虽然思想简单粗暴但一般计算量较大，且有一定的局限性，仅限凸多边形，但有一种相对快速且能应对各种简单多边形的方法——射线法，射线法的本质是判断射线与线段相交，即从已知点处引一条沿 X 轴正向的射线，若射线与多边形边的相交条数为奇数，则该点在多边形内，该法的缺陷在于若点在边上则需要单独判断。判断该射线与多边形的边是否相交也比较简单，设射线起点为 P0，多边形边的两个端点分别为 P1 和 P2，则射线与边相交需满足的条件为：1、\(min(P1.y, P2.y)<=P0.y<=max(P1.y, P2.y)\)；2、\(P0.x <= (P2.x-P1.x)*(P0.y-P1.y)/(P2.y-P1.y)+P1.x\)。
圆与三角形相交
判断圆与三角形相交，即判断圆心到三角形各边的距离是否小于圆的半径，若存在一条边，使圆心到其的距离小于半径，则圆与三角形相交，该距离计算不是点到直线的距离，而是点到线段的距离。
直线与长方体相交
判断直线与长方体相交，首先需要将坐标原点平移至长方体中心，再计算过原点且垂直于直线的法向量 n ，随后计算原点到直线的距离 d，若满足 \(|d| <= h_x|n_x| + h_y|n_y| + h_z|n_z|\) ，则 直线与长方体相交。法向量 n 的求法为：设 P 为直线上一点，l 为直线方向向量，则 \(n=-(P·l)*l+P\)。
球与 AABB 相交
判断球与 AABB 相交，首先需要将坐标原点平移至球心，设平移后的 AABB 最小顶点为 V1，最大顶点为 V2，球半径为 r。最简单粗暴的当然是若原点不在 AABB 内，则直接求原点到 8 个面的距离，取最小值，若最小值比半径大，则不相交。另一种方法是将这个问题转化为求解不等式，若存在一点 \(P(x, y, z)\)，使 P 在球内，同时 P 在 AABB 中，即： \[ \begin{cases} x^2+y^2+z^2 ≤ r^2 , \\ V1.x ≤ x ≤ V2.x , \\ V1.y ≤ y ≤ V2.y , \\ V1.z ≤ z ≤ V2.z \end{cases} \] 若该不等式有解，则球与 AABB 相交，否则不相交。解该不等式也简单，由于是存在而不是任意，所以只需要求 \(min(x^2+y^2+z^2)≤r^2 \Rightarrow min(x^2) + min(y^2)+ min(z^2)≤r^2\)，则若 xyz 分量可以取 0，则对应分量取 0，否则取 \(x = min(|V1.x|, |V2.x|), y = min(|V1.y|, |V2.y|),z = min(|V1.z|, |V2.z|)\)，若满足不等式，则相交。
该方法同样可用来求 OBB 与球相交，只需要先利用坐标系变换将 OBB 转成 AABB。
反射篇
令入射向量为 \(I\)，法向量为 \(N\)，反射向量为 \(R\)，入射向量与反射向量构成的平面与镜面交线的方向向量为 \(T\)，这四个向量都为单位向量。首先以 \(I\) 和 \(R\) 组成一个菱形，则 \(N\) 和 \(T\) 则为该菱形对角线的方向向量，若已知 \(I\) 和 \(R\)，则 \(N = (R - I).normalize()\)，\(T = (I + R).normalize()\) ，\(normalize()\) 指向量归一化；若已知 \(I\) 和 \(N\)，则 \(R = I + 2*|I \cdot N|*N\)，\(2*|I \cdot N|*N\) 为菱形 \(N\) 方向的对角线向量。
镜面反射公式为 \((r',g',b') = (r,g,b) + (1-r,1-g,1-b)*t\)，当 \(t\) 越大则越接近白色，表现为越亮；漫反射公式为 \((r',g',b') = (r,g,b)*t\)，当 \(t\) 越小，则越接近黑色，表现为越暗。 其中 \(t\in[0,1]\)，\(t\) 为入射向量到平面法向量上的投影，即点积。
后记
该篇不出意外的话也会是一个长期支持篇，等以后有碰到其他的一些计算几何知识再持续更新吧。