测试线段是否与球体相交

Question

我试图确定线段（即两点之间）是否与球体相交。我对相交的位置不感兴趣，只对线段是否与球体表面相交感兴趣。有人对最有效的算法有什么建议吗？ （我想知道是否有比通常的射线球相交算法更简单的算法，因为我对相交位置不感兴趣）

Answer 1

如果您只对知道它是否相交感兴趣，那么您的基本算法将如下所示......

考虑您有射线线的向量，A -> > B.

您知道该矢量与球体中心之间的最短距离出现在射线矢量与穿过球体中心的与其成 90 度的矢量的交点处。

因此，你有两个向量，其方程完全定义。您可以使用线性代数计算出向量的交点，从而计算出直线的长度（或更有效地计算直线长度的平方），并测试它是否小于半径（或半径的平方） ）你的领域。

Answer 2

我不知道这样做的标准方法是什么，但如果您只想知道它是否相交，这就是我会做的。

一般规则...避免执行 sqrt() 或其他昂贵的操作。如果可能的话，处理半径的平方。

1. 确定起点是否在球体半径内。如果您知道情况并非如此，请跳过此步骤。如果您在内部，您的光线将与球体相交。

从这里开始，你的起点就在球体之外。

2. 现在，想象一下适合球体的小盒子。如果您位于该盒子之外，请检查光线的 x 方向、y 方向和 z 方向，看看它是否会与光线开始的盒子一侧相交。这应该是一个简单的符号检查，或与零比较。如果你在它之外并远离它，你将永远不会与它相交。

从现在开始，你就进入了更加复杂的阶段。您的起点位于假想的盒子和球体之间。您可以使用微积分和几何得到简化的表达式。

您要做的要点是确定射线和球体之间的最短距离是否小于球体的半径。

让射线由 (x0 + it, y0 + jt, z0 + kt) 表示，球体中心位于 (xS, yS, zS)。因此，我们希望找到 t，使其给出 (xS - x0 - it，yS - y0 - jt，zS - z0 - kt) 中最短的一个。

设 x = xS - x0、y = yX - y0、z = zS - z0、D = 向量幅度平方

D = x^2 -2*xit + (i*t) ^2 + y^2 - 2*yjt + (j*t)^2 + z^2 - 2*zkt + (k*t) ^2

D = (i^2 + j^2 + k^2)t^2 - (xi + yj + zk)*2*t + (x^2 + y^2 + z^2)

dD/dt = 0 = 2*t*(i^2 + j^2 + k^2) - 2*(xi + yj + z*k)

t = (xi + yj + z*k) / (i^2 + j^2 + k^2)

将 t 代入方程，得到 D = ....如果结果小于或等于球体半径的平方，则有一个交集。如果更大，则不存在交集。

Answer 3

此页面针对此问题提供了精确的解决方案。本质上，您是将直线方程代入球体方程，然后计算所得二次方程的判别式。判别式的值表示交集。

Answer 4

13年后你还在寻找答案吗？这是一个完整且简单的解决方案

假设如下：

• 线段由端点定义为 3D 向量 v1 和 v2
• 球体以 vc 为中心> 以半径 r

定义三角形 ABC 的三个边长为：

• A = v1-vc
• B = v2-vc
• C = v1-v2

如果|A| < r 或 |B| < r，然后我们完成了；线段与球体相交

完成上述检查后，如果 A 和 B 之间的角度为锐角，则完成；线段不与球体相交。

如果这两个条件都不满足，则线段可能会或可能不会与球体相交。为了找到答案，我们只需要找到H，它是以C为底的三角形ABC的高度。首先我们需要φ，即A和C之间的角度：

φ = arccos( dot(A,C) / (|A||C|) )

然后求解H：

sin(φ) = H/|A|
    ===> H = |A|sin(φ) = |A| sqrt(1 - (dot(A,C) / (|A||C|))^2)

我们就完成了。结果是

• 如果 H < r，则线段与球体相交，
• > r，则线段与球体相切
• 如果 H = r，则如果 H 。 r，则线段不与球体相交

这是用 Python 编写的：

import numpy as np

def unit_projection(v1, v2):
    '''takes the dot product between v1, v2 after normalization'''
    u1 = v1 / np.linalg.norm(v1)
    u2 = v2 / np.linalg.norm(v2)
    return np.dot(u1, u2)

def angle_between(v1, v2):
    '''computes the angle between vectors v1 and v2'''
    return np.arccos(np.clip(unit_projection(v1, v2), -1, 1))

def check_intersects_sphere(xa, ya, za, xb, yb, zb, xc, yc, zc, radius):
    '''checks if a line segment intersects a sphere'''
    v1 = np.array([xa, ya, za])
    v2 = np.array([xb, yb, zb])
    vc = np.array([xc, yc, zc])
    A = v1 - vc
    B = v2 - vc
    C = v1 - v2

    if(np.linalg.norm(A) < radius or np.linalg.norm(B) < radius): 
        return True
    
    if(angle_between(A, B) < np.pi/2):
        return False

    H = np.linalg.norm(A) * np.sqrt(1 - unit_projection(A, C)**2)
    if(H < radius):
        return True
    if(H >= radius):
        return False

请注意，我已经编写了此代码，以便当任一端点位于球体表面时返回 False，或者当线段与球体相切时，因为它更符合我的目的。

这可能本质上就是用户 Cruachan 的建议。那里的评论表明其他答案“过于复杂”。可能有一种更优雅的方法来实现这一点，即使用更紧凑的线性代数运算和恒等式，但我怀疑所需的实际计算量可以归结为这样的东西。如果有人发现可以节省一些精力的地方，请告诉我们。

---

这是代码的测试。下图显示了从 (-1, 1, 1) 位置出发的几条试验线段，单位球体位于 (1,1,1) 处。蓝色线段已相交，红色线段未相交。

这是另一幅图，它验证了在球体表面附近停止的线段不相交，即使它们所属的无限射线相交：

此处是生成图像的代码：

import matplotlib.pyplot as plt
radius = 1
xc, yc, zc = 1, 1, 1
xa, ya, za = xc-2, yc, zc
nx, ny, nz = 4, 4, 4
xx = np.linspace(xc-2, xc+2, nx)
yy = np.linspace(yc-2, yc+2, ny)
zz = np.linspace(zc-2, zc+2, nz)
n = nx * ny * nz
XX, YY, ZZ = np.meshgrid(xx, yy, zz)
xb, yb, zb = np.ravel(XX), np.ravel(YY), np.ravel(ZZ)

fig = plt.figure()
ax = fig.add_subplot(111, projection='3d')
for i in range(n):
    if(xb[i] == xa): continue
    intersects = check_intersects_sphere(xa, ya, za, xb[i], yb[i], zb[i], xc, yc, zc, radius)
    color = ['r', 'b'][int(intersects)]
    s = [0.3, 0.7][int(intersects)]
    ax.plot([xa, xb[i]], [ya, yb[i]], [za, zb[i]], '-o', color=color, ms=s, lw=s, alpha=s/0.7)

u = np.linspace(0, 2 * np.pi, 100)
v = np.linspace(0, np.pi, 100)
x = np.outer(np.cos(u), np.sin(v)) + xc
y = np.outer(np.sin(u), np.sin(v)) + yc
z = np.outer(np.ones(np.size(u)), np.cos(v)) + zc
ax.plot_surface(x, y, z,  rstride=4, cstride=4, color='k', linewidth=0, alpha=0.25, zorder=0)
ax.set_xlabel('x')
ax.set_ylabel('y')
ax.set_zlabel('z')
plt.tight_layout()
plt.show()

Answer 5

如果您只需要知道是否相交，而不需要知道相交点，有一种方法可以轻松做到这一点：

fn intersects(seg: &LineSegment, sphere: &Sphere) -> bool {
    let seg_sq_mag = (seg.b.pos - seg.a.pos).sq_mag();
    
    let sq_dist_to_a = (sphere.center - seg.a.pos).sq_mag();
    let sq_dist_to_b = (sphere.center - seg.b.pos).sq_mag();

    let a_within_sphere = sq_dist_to_a <= sphere.sq_radius;
    let b_within_sphere = sq_dist_to_b <= sphere.sq_radius;
    
    let seg_within_sphere =

        // The segment is within the sphere if either endpoint is within the sphere.
        a_within_sphere ||
        b_within_sphere ||

        // If neither endpoint is within the sphere, the segment is within the sphere iff:
        // 1. The line spanned by the segment passes through the sphere.
        // 2. Two non-overlapping right triangles are formed by each of the segment's endpoints, the center of the sphere,
        //    and the closest point on the line to the sphere. We can confirm this by creating inequalities
        //    using the Pythagorean theorem. 
        {
            let sq_dist_to_line = cross(sphere.center - seg.a.pos, sphere.center - seg.b.pos).sq_mag() / seg_sq_mag;
            let line_passes_through_sphere = sq_dist_to_line <= sphere.sq_radius;
            
            line_passes_through_sphere
            && (sq_dist_to_a - sq_dist_to_line <= seg_sq_mag)
            && (sq_dist_to_b - sq_dist_to_line <= seg_sq_mag)
        };
    
    return seg_within_sphere;
}

请注意，如果段完全包含在球体中。我发现这很有用，但如果你不这样做，只要确保在两个端点都在球体中时返回 false 即可。

v.sq_mag() 计算 v 的平方幅值。

在这种情况下，使用平方值会更有效，因为它避免了调用 sqrt。

cross(a, b) 计算 a 和 b 之间的叉积。

有一个部门，但如果您愿意，您可以重构以轻松删除它。

我在Wolfram上找到了点线距离公式。如果您想了解它，那里有信息： https://mathworld.wolfram.com /Point-LineDistance3-Dimensional.html

最后一部分关于两个不重叠的直角三角形可以直观地理解：

Answer 6

如果你想要准确性，无论如何你都必须在这个位置上工作。从算法上提高速度的唯一方法是从射线球体相交切换到射线边界框相交。

或者您可以更深入地尝试改进 sqrt 和其他内部函数调用

http://wiki.cgsociety .org/index.php/Ray_Sphere_Intersection