先日直方体と線分の交差判定について考える機会があったので、備忘録としてその方法を記しておきます.
- 軸に垂直な直方体 対 直線
- 軸に垂直な直方体 対 線分
- 直方体 対 線分
について述べ、最後にpythonによるコードサンプルを掲載しています.
すべての辺が軸に垂直な直方体(AABB)と直線(ray)
ベースとなる考え方(Slab Method)
Slab Method(https://en.wikipedia.org/wiki/Slab_method)
という有名な手法があります.これは、「AABBを、3つの無限に広がる厚い板(Slab)の共通部分として捉える」という考え方に基づきます.
- x-slab:平面$x=x_{min}$と$x=x_{max}$で挟まれた領域
- y-slab:平面$y=y_{min}$と$y=y_{max}$で挟まれた領域
- z-slab:平面$z=z_{min}$と$z=z_{max}$で挟まれた領域
直線がAABBと交差するということは、
「その直線がこれら3つのスラブを貫通する共通の区間を持つこと」
を意味します.Slab Methodは、この共通区間の有無を調べることで交差判定を行います.
手順
直線をパラメータ$t$を用いて次のように表現します.
- 始点:$\boldsymbol{o}=(o_{x}, o_{y}, o_{z})$
- 方向ベクトル:$\boldsymbol{d}=(d_x,d_y,d_z)$
- 直線上の点: $\boldsymbol{p}(t)=\boldsymbol{o} + t\boldsymbol{d}$
Step 1
直線が各スラブをいつ通過し始め($t_{near}$)、いつ通過し終えるか($t_{far}$)を計算します.($t_{near} < t_{far}$)
x-slabの場合
$t=t_{x1}, t_{x2}$でそれぞれ$x=x_{min},x_{max}$に到達するとします.このとき
\begin{align*}
t_{x1} = \dfrac{x_{min} - o_x}{d_x}\\
t_{x2} = \dfrac{x_{max} - o_x}{d_x}
\end{align*}
です.よって$t_{xnear}, t_{xfar}$はそれぞれ$\min(t_{x1}, t_{x2}), \max(t_{x1}, t_{x2})$となります.
同様にしてy-slab, z-slabについても区間$[t_{ynear}, t_{yfar}], [t_{znear}, t_{zfar}]$が求まります.
※直線とスラブの底面が並行で、交点を持たない場合
この場合($d_i = 0$)、直線はスラブに完全に含まれる($i_{min} \leqq o_i\leqq i_{out}$)or完全に含まれない($o_i<i_{min}$または$i_{max}<o_i$)のどちらかです($i=x,y,z$).
前者の場合は$(-\infty, \infty)$で交差しているとみなせます.後者の場合は,この時点で直線と直方体が衝突することは絶対にないので判定をここで終了できます.
Step 2
先の３つの区間に共通部分が存在するか確認します.
\begin{align*}
t_{in} &= \max(t_{xnear}, t_{ynear}, t_{znear})\\
t_{out} &= \min(t_{xfar}, t_{yfar}, t_{zfar})
\end{align*}
として, $t_{in} \leqq t_{out}$ならば交差、そうでなければ交差しないと判定できます.
すべての辺が軸に垂直な直方体(AABB)と線分
線分の両端点をO,Dとします.先の場合で
\boldsymbol{d}=\overrightarrow{OD}
として、最後の交差判定を
t_{in} \leqq t_{out} かつ t_{in} \leqq 1 かつ t_{max} \geqq 0
とすればよいです.
一般的な直方体と線分
変換行列によって直方体の各辺に並行な3軸を持つ座標系に変換すればAABB対直線[線分]の交差判定に帰着できます.
コードサンプル(Python)
def is_crossing_between_line_segment_and_cuboid(
segment: tuple[tuple[float, float, float], tuple[float, float, float]]
cuboid: tuple[tuple[float, float, float], tuple[float, float, float], tuple[float, float, float], tuple[float, float, float]]
) -> bool:
"""線分と直方体が交差しているかを判定する.
Args:
segment (tuple[tuple[float, float, float], tuple[float, float, float]]):
線分の(開始点, 終了点)
cuboid (tuple[tuple[float, float, float], tuple[float, float, float], tuple[float, float, float], tuple[float, float, float]]):
直方体ABCD-EFGHの(頂点A, ベクトルAB, ベクトルAC, ベクトルAE)
"""
cuboid_origin, v1, v2, v3 = cuboid
cuboid_origin_np = np.array(cuboid_origin, dtype=float)
seg_start_np, seg_end_np = np.array(segment, dtype=float)
seg_vec_np = seg_end_np - seg_start_np
# 直方体のローカル座標系を定義
axes = np.array([v1, v2, v3], dtype=float)
slabs_max = np.linalg.norm(axes, axis=1)
if np.any(slabs_max < 1e-9):
return False
rotation_matrix = axes / slabs_max[:, np.newaxis]
# ローカル座標系における線分の始点,方向ベクトルの定義
starts = rotation_matrix @ (seg_start_np - cuboid_origin)
dirs = rotation_matrix @ seg_vec_np
slabs_min = np.array([0., 0., 0.])
# スラブに平行な場合のチェック
mask_zero = np.abs(dirs) < 1e-9
if np.any(mask_zero & ((starts < slabs_min) | (starts > slabs_max))):
return False
# 線分と平行でないスラブに対して、区間の更新
t1 = np.full(3, -np.inf)
t2 = np.full(3, np.inf)
mask_nonzero = ~mask_zero
t1[mask_nonzero] = (slabs_min[mask_nonzero] - starts[mask_nonzero]) / dirs[mask_nonzero]
t2[mask_nonzero] = (slabs_max[mask_nonzero] - starts[mask_nonzero]) / dirs[mask_nonzero]
t_min = np.max(np.minimum(t1, t2))
t_max = np.min(np.maximum(t1, t2))
return t_min <= t_max and t_min <= 1 and t_max >= 0