计算几何基础

前言

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

基础篇

解线性方程组:\(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 之间的距离计算流程为:

  1. 先判断两直线是否平行,即 \((P2-P1) = k*(Q2-Q1), k \neq 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) \cdot n\)

直线到平面的距离

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

  1. 先判断直线与平面是否平行,即若 \((P2-P1) \cdot 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\),设 \(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\) 为入射向量到平面法向量上的投影,即点积。

后记

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