计算几何基础算法直线与平面求交
计算几何基础算法——直线与平面求交
前言
还是继续写基础算法，为后续复杂算法做铺垫。
这篇文章中要介绍的直线与平面求交，是用的非常广泛的基础算法之一。像三维射线法、几何信息采样等很多算法都会用到该算法，它也可以用到曲线与曲面求交迭代过程中。
本文介绍的算法，不会像中学数学中那样列方程组来求解，而是通过 几何意义更明确 的向量运算来求解。 几何意义明确的好处就是算法里涉及到确定精度的地方，精度也有明确的几何意义，方便多算法间的精度统一 。
做几何算法一定要熟练掌握向量的各种运算和应用，直线与平面求交就是一个典型的应用场景。关于向量运算不熟悉的朋友可以查看下面这篇文章。
算法推导
设直线由一个点和一个单位向量定义；平面由一个点和一个法线定义，如下图所示：
设交点为P，因为P在直线上，所以P可以写成如下形式：
P
P c + D c t P=P_c+D_ct
P
=
P
c
D
c
t
P点也在平面上。平面上的点，要不等于原点，要不该点和原点的连线和法线垂直。
垂直意味着点积为0，写成公式如下：
( P − P s ) ⋅ N s
0 (P-P_s) \cdot N_s=0
(
P
−
P
s
)
⋅
N
s
=
0
两个公式化简：
( P c + D c t − P s ) ⋅ N s
0 ( P c − P s ) ⋅ N s + ( D c ⋅ N s ) t
0 ( D c ⋅ N s ) t
( P s − P c ) ⋅ N s \begin{aligned} &(P_c+D_ct-P_s)\cdot N_s=0 \[2px] &(P_c-P_s)\cdot N_s+(D_c \cdot N_s) t=0 \[2px] &(D_c \cdot N_s) t=(P_s-P_c)\cdot N_s \end{aligned}
(
P
c
D
c
t
−
P
s
)
⋅
N
s
=
0
(
P
c
−
P
s
)
⋅
N
s
(
D
c
⋅
N
s
)
t
=
0
(
D
c
⋅
N
s
)
t
=
(
P
s
−
P
c
)
⋅
N
s
若：
D c ⋅ D s ≠ 0 D_c \cdot D_s \ne 0
D
c
⋅
D
s
=
0
这里由于浮点数误差的存在，我们一般用下面的判断条件代替上式：
∣ D c ⋅ D s ∣
ε |D_c \cdot D_s| > \varepsilon
∣
D
c
⋅
D
s
∣
ε
这时候可计算出：
t
( P s − P c ) ⋅ N s D c ⋅ N s P
P c + D c t \begin{aligned} &t=\frac{(P_s-P_c) \cdot N_s}{D_c \cdot N_s} \[2px] &P=P_c+D_ct \end{aligned}
t
=
D
c
⋅
N
s
(
P
s
−
P
c
)
⋅
N
s
P
=
P
c
D
c
t
若：
∣ D c ⋅ D s ∣ ≤ ε |D_c \cdot D_s| \le \varepsilon
∣
D
c
⋅
D
s
∣
≤
ε
这时候直线和平面平行或重合。
从几何意义上也好理解，平面的法线和直线的方向点积为0，表示两个向量垂直。
说明：建议该算法将重合和平行当成一种情况来处理。原因是这个算法属于基础算法，通常是某个更大算法的一部分。在更大算法中，直线和平面往往都是有界的，这种情况下重合其实很玄学。即使直线和平面夹角比较小，如果长度很长，也不一定就真的重合；同理，即使夹角大些，但直线很短，两个端点到平面的距离如果都在精度范围内，可能也需要按重合处理。所以重合判断往往会更大算法通盘考虑，在这个算法中判重合往往是无效运算。
还有一个关于精度ε的说明：因为ε比较的是两个单位向量的点积，一般有效数字不建于高于6位，即不要小于1e-6。原因是double的有效数字是14到15位，第14位很不稳定，单位向量要开方，所以对于单位向量相关有效数字高于6是不稳定的。这个建议来自于我们曾经的教训。