寻求3D空间中直线与轴对齐立方体的相交检测算法

直接用Slab算法就能解决，这是针对轴对齐体相交检测的高效方案，比硬套2D算法更靠谱，步骤和实现如下：

核心思路 #

轴对齐立方体可以看作三个正交的“区间板（Slab）”——x轴方向[Xc, Xc+1]、y轴方向[Yc, Yc+1]、z轴方向[Zc, Zc+1]。直线与立方体相交的充要条件是：直线穿过这三个Slab的参数区间存在重叠。

具体步骤 #

1. 参数化直线：用参数t表示直线上的任意点，公式为：
   P(t) = A + t*(B - A)，其中t∈(-∞, +∞)（若检测线段则t∈[0,1]）。

2. 计算每个Slab的t区间：
   对x、y、z三个轴分别处理：

   • 以x轴为例，解不等式 Xc ≤ Xa + t*(Xb - Xa) ≤ Xc+1，得到对应的t区间[t_x_min, t_x_max]。
   • 若直线平行于当前轴（比如Xb - Xa = 0），则直接检查A点的对应坐标是否在立方体该轴的范围内，不在则直接判定不相交；在的话，该Slab的t区间为(-∞, +∞)。
   • y、z轴同理，得到[t_y_min, t_y_max]和[t_z_min, t_z_max]。

3. 求区间交集：
   计算三个区间的共同重叠部分：
   t_low = max(t_x_min, t_y_min, t_z_min)
t_high = min(t_x_max, t_y_max, t_z_max)

4. 判定相交：
   若t_low ≤ t_high，则直线与立方体相交；否则不相交。若需要交点，将t_low和t_high代入参数方程即可得到两个交点（t_low=t_high时为相切）。

伪代码实现 #

def line_intersects_cube(A, B, C):
    # 计算直线方向向量
    dir_x = B.x - A.x
    dir_y = B.y - A.y
    dir_z = B.z - A.z

    # 初始化t的有效范围
    t_min = float('-inf')
    t_max = float('inf')

    # 处理X轴Slab
    if dir_x != 0:
        t1 = (C.x - A.x) / dir_x
        t2 = (C.x + 1 - A.x) / dir_x
        curr_min = min(t1, t2)
        curr_max = max(t1, t2)
        t_min = max(t_min, curr_min)
        t_max = min(t_max, curr_max)
        if t_min > t_max:
            return False
    else:
        # 直线平行X轴，检查A的x坐标是否在立方体内
        if A.x < C.x or A.x > C.x + 1:
            return False

    # 处理Y轴Slab
    if dir_y != 0:
        t1 = (C.y - A.y) / dir_y
        t2 = (C.y + 1 - A.y) / dir_y
        curr_min = min(t1, t2)
        curr_max = max(t1, t2)
        t_min = max(t_min, curr_min)
        t_max = min(t_max, curr_max)
        if t_min > t_max:
            return False
    else:
        if A.y < C.y or A.y > C.y + 1:
            return False

    # 处理Z轴Slab
    if dir_z != 0:
        t1 = (C.z - A.z) / dir_z
        t2 = (C.z + 1 - A.z) / dir_z
        curr_min = min(t1, t2)
        curr_max = max(t1, t2)
        t_min = max(t_min, curr_min)
        t_max = min(t_max, curr_max)
        if t_min > t_max:
            return False
    else:
        if A.z < C.z or A.z > C.z + 1:
            return False

    # 区间有效，存在相交
    return True

补充说明 #

• 若要检测线段AB而非无限直线，只需在最后返回前额外判断：t_low <= 1 and t_high >= 0，因为线段对应的t范围是[0,1]。
• 该算法计算量小，适合实时场景，避免了复杂的几何计算。

内容的提问来源于stack exchange，提问作者RoseGoldIsntGay