计算几何基础

Shaun's Space

　　由于本篇主要是谈谈基础，所以一些快速运算方法一般不在本篇探讨范围之内，一些特殊的快速手法等后续专门独立开篇再谈。

解线性方程组：令 A 为 n×n 的矩阵，α 和 β 为 n 维的列向量，设 A=[α1α2α3...αn]，对于线性方程组 Ax=β，初等数学中最常规的就是消元法了，但在线性代数中，有两种解法，一种是等式两边同乘 A 的逆阵，得到 x=A−1β；另一种是克莱姆法则，可得 xi=|Ai|/|A|，其中 |A| 为 矩阵 A 对应的行列式， |Ai| 为将矩阵 A 中第 i 列换成 β 后对应的行列式，如 x3=|α1α2β...αn|/|A|。

向量内积：又称向量点积，向量点乘。设 a，b 为空间中两个 n 维向量 a=(x1,x2,x3,...,xn)，b=(y1,y2,y3,...,yn)，则 a·b=|a|∗|b|∗cos(α)=n∑i=1xiyi，其中|a|=√(x1)2+(x2)2+(x3)2+...+(xn)2,α 为两向量之间夹角。向量内积一般用来计算投影（令 |b|=1，则 a⋅b=|a|cos(α)，即为向量 a 在 b 上的投影），和两向量之间角度。

向量外积：又称向量叉积，向量叉乘，|a×b|=||a|∗|b|∗sin(α)|。向量外积一般只针对二维向量和三维向量，对于二维向量，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|=|AT|，该混合积的几何意义为这三个向量组成的平行六面体的体积。

直线参数方程：设 P 为直线上任意一点，若 P1 和 P2 为直线上已知两点，则 P=P1+(P2−P1)∗t,t∈[−∞,+∞]。当然直线的参数方程有很多种形式，之所以用两点式，是因为两点式除了能表示直线，同样能表示射线（t≥0），也能表示线段（0≤t≤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∈[0,1],v∈[0,1],u+v≤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)⋅n。

直线到直线的距离

　　设 P1 和 P2 为直线 1 上两点，Q1 和 Q2 为直线 2 上两点，则直线 1 与直线 2 之间的距离计算流程为：

1. 先判断两直线是否平行，即 (P2−P1)=k∗(Q2−Q1),k≠0 有解。若平行，则相当于计算点到直线的距离；若不平行，则进行下一步。
2. 再判断两直线是否共面，即 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)⋅n。

直线到平面的距离

　　设 P1 和 P2 为直线上两点，n 为平面法向量，则直线与平面之间的距离计算流程为：

1. 先判断直线与平面是否平行，即若 (P2−P1)⋅n=0 ，则直线与平面平行，则直线到平面的距离为 点 P1 到平面的距离；
2. 若直线与平面不平行，则直线与平面必相交。

　　一般的相交求交点都是联立方程组，但有些只需要做相交测试的，可以利用一些特殊方法快速求出来。有些相交直接求很麻烦或很难，可以反向求不相交的情况，而在实际编程中，一般都有很多条件语句，以便快速返回提高效率。

直线与直线相交

　　设直线 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，设 v0=Q2−Q1,v1=P1−P2,v2=P1−Q1，即 v0∗u+v1∗t=v2，现在的问题就是解这个方程了，一种是直接把向量分解成单一维度，列方程组；一种是等式两边分别同时点乘 v0 和 v1，可得 {(v0⋅v0)∗u+(v1⋅v0)∗t=v2⋅v0,(v0⋅v1)∗u+(v1⋅v1)∗t=v2⋅v1 解得： {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)) 若方程有解，则两直线相交，由于两点式方程可以很简单的转换为线段和射线，所以该方法同样可以判断两线段相交，两射线相交，射线与直线与线段相交等。针对二维直线，还有一种解法是将原方程写成矩阵形式，利用克莱姆法则进行求解，不过总的来说，最终的解都是一种形式。

直线与平面相交

　　求直线与平面相交，直接联立直线方程和平面方程即可，得 (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，令 V0=P1−Q1,V1=P1−P2,V2=Q2−Q1,V3=Q3−Q1，则 V0=V1∗t+V2∗u+V3∗v，可以分解向量求解，也可以使用克莱姆法则得： t=|V0V2V3||V1V2V3|u=|V1V0V3||V1V2V3|v=|V1V2V0||V1V2V3| 由于三阶行列式也可以用向量混合积来求值，所以 t=−V0×V3·V2V1×V2·V3u=V0×V3·V1V1×V2·V3v=V1×V2·V0V1×V2·V3 若方程有解，且满足三角形条件，则相交。

二维中凸多边形与凸多边形相交

　　曾在「快速判断三角形与长方体相交」中写过判断两凸多边形是否相交直接使用分离轴理论（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|<=hx|nx|+hy|ny|+hz|nz| ，则 直线与长方体相交。法向量 n 的求法为：设 P 为直线上一点，l 为直线方向向量，则 n=−(P·l)∗l+P。

球与 AABB 相交

判断球与 AABB 相交，首先需要将坐标原点平移至球心，设平移后的 AABB 最小顶点为 V1，最大顶点为 V2，球半径为 r。最简单粗暴的当然是若原点不在 AABB 内，则直接求原点到 8 个面的距离，取最小值，若最小值比半径大，则不相交。另一种方法是将这个问题转化为求解不等式，若存在一点 P(x,y,z)，使 P 在球内，同时 P 在 AABB 中，即： {x2+y2+z2≤r2,V1.x≤x≤V2.x,V1.y≤y≤V2.y,V1.z≤z≤V2.z 若该不等式有解，则球与 AABB 相交，否则不相交。解该不等式也简单，由于是存在而不是任意，所以只需要求 min(x2+y2+z2)≤r2⇒min(x2)+min(y2)+min(z2)≤r2，则若 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⋅N|∗N，2∗|I⋅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∈[0,1]，t 为入射向量到平面法向量上的投影，即点积。

　　该篇不出意外的话也会是一个长期支持篇，等以后有碰到其他的一些计算几何知识再持续更新吧。