在3D中两条射线的相交性检测

时间:2023-03-09 15:16:02
在3D中两条射线的相交性检测

摘自[3D数学基础: 图形与游戏开发]

考虑在3D中两条以参数形式定义的射线:

\(\vec{r_1}(t_1)=\vec{p_1}+t_1\vec{d_1}\)
\(\vec{r_2}(t_2)=\vec{p_2}+t_2\vec{d_2}\)

我们能够解得它们的交点。暂时先不考虑\(t_1,t_2\)的取值范围。因此,我们考虑的是无限长的射线;同样,向量\(\vec{d_1},\vec{d_2}\)也不必是单位向量。如果这两条射线在一个平面中,那么和前一节的情况一样,也存在有一种可能性:

  • 两条射线交于一点;
  • 两条射线平行,没有交点;
  • 两条射线重合,有无限多交点。

在3D中,还有第四种可能性:两条射线不在一个平面中。

下面演示如何解得交点处的\(t_1,t_2\):

\(\vec{r_1}(t_1)=\vec{r_2}(t_2)\)
\(\Rightarrow \vec{p_1}+t_1\vec{d_1}=\vec{p_2}+t_2\vec{d_2}\)
\(\Rightarrow t_1\vec{d_1}=\vec{p_2}+t_2\vec{d_2}-\vec{p_1}\)
\(\Rightarrow (t_1\vec{d_1})\times\vec{d_2} =(\vec{p_2}+t_2\vec{d_2}-\vec{p_1})\times\vec{d_2}\)
\(\Rightarrow t_1(\vec{d_1}\times\vec{d_2}) =t_2(\vec{d_2}\times\vec{d_2})+(\vec{p_2}-\vec{p_1})\times\vec{d_2}\)
\(\Rightarrow t_1(\vec{d_1}\times\vec{d_2}) =t_2\vec{0}+(\vec{p_2}-\vec{p_1})\times\vec{d_2}\)
\(\Rightarrow t_1(\vec{d_1}\times\vec{d_2})\cdot(\vec{d_1}\times\vec{d_2}) =(\vec{p_2}-\vec{p_1})\times\vec{d_2}\cdot(\vec{d_1}\times\vec{d_2})\)
\(\Rightarrow t_1 =\cfrac{(\vec{p_2}-\vec{p_1})\times\vec{d_2}\cdot(\vec{d_1}\times\vec{d_2})}{(\vec{d_1}\times\vec{d_2})\cdot(\vec{d_1}\times\vec{d_2})}\)
\(\Rightarrow t_1 =\cfrac{(\vec{p_2}-\vec{p_1})\times\vec{d_2}\cdot(\vec{d_1}\times\vec{d_2})}{\Vert\vec{d_1}\times\vec{d_2}\Vert^2}\)

也可以用类似的方法求出\(t_2\):

\(t_2 =\cfrac{(\vec{p_1}-\vec{p_2})\times\vec{d_1}\cdot(\vec{d_2}\times\vec{d_1})}{\Vert\vec{d_2}\times\vec{d_1}\Vert^2}\)

\(\Rightarrow t_2 =\cfrac{(\vec{p_2}-\vec{p_1})\times\vec{d_1}\cdot(\vec{d_1}\times\vec{d_2})}{\Vert\vec{d_1}\times\vec{d_2}\Vert^2}\)

如果两条射线平行或重合,\(\vec{d_1},\vec{d_2}\)的叉乘为零,所以上面两个等式的分母都为零。如果两条射线不在一个平面内,那么\(\vec{r_1}(t_1),\vec{r_2}(t_2)\)是相距最近的点。通过检查\(\vec{r_1}(t_1),\vec{r_2}(t_2)\)间的距离即可确定两条射线相交的情况。当然,在实践中,因为浮点数的精度问题,精确的相交很少出现,这时就需要用到一个偏差值。

上面的讨论假设没有限定\(t_1,t_2\)的取值范围,如果射线的长度有限(或只沿一个方向沿伸),在计算出\(t_1,t_2\)后,还应作适当的边界检测。