测试一条线段是否与一个球相交

Question

我正在尝试确定一条线段（即两个点之间的线段）是否与球相交。我不关心交点的位置，只是想知道线段是否与球面相交。是否有人对此有什么建议，最有效的算法是什么？（我想知道是否有比通常的光线-球相交算法更简单的算法，因为我不关心交点位置）

- astrofrog

---

你是真的需要一条线段还是无限直线？所有答案都是关于无限直线的。 - letmaik

Answer 1

如果您仅对相交与否感兴趣，则基本算法如下所示...

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

您知道该向量与球心之间的最短距离出现在您的射线向量和一个垂直于此向量并穿过球心的向量的交点处。

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

- Cruachan

---

这是此帖子上唯一正确的答案。其他答案都太详细了。 - FeepingCreature

谢谢你的回复。我一直在看这个页面上其他更高排名的答案，摇头不已。特别是那些以“我不知道标准做法”开头的答案，而我的回答则是标准做法 :-) - Cruachan

这个答案会给你带来你可能正在寻找的“恍然大悟”的时刻。 - allen1

不，这不是正确答案，这只适用于一条直线。问题明确要求两点之间的线段。 - credondo

Answer 2

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

一般规则是...避免进行sqrt()或其他昂贵的操作。在可能的情况下，处理半径的平方。

1.确定起点是否在球体半径内。如果您知道这永远不可能发生，则跳过此步骤。如果您在内部，则射线将与球体相交。

从这里开始，您的起点在球体外面。

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

从这里开始，您处于更复杂的阶段。您的起点位于虚拟盒子和球体之间。您可以使用微积分和几何学得到简化的表达式。

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

让你的射线表示为（x0 + i t，y0 + j t，z0 + k t ），并让你的球体的中心在（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 * x i t +（i * t）^2 + y^2 -2 * y j t +（j * t）^2 + z^2 -2 * z k t +（k * t）^2

D =（i ^ 2 + j ^ 2 + k ^ 2） t ^ 2 -（x i + y j + z k）* 2 * t +（x ^ 2 + y ^ 2 + z ^ 2）

dD / dt = 0 = 2 * t *（i ^ 2 + j ^ 2 + k ^ 2）-2 *（x i + y j + z * k）

t =（x i + y j + z * k）/（i ^ 2 + j ^ 2 + k ^ 2）

将t插入回D = ...的方程中。如果结果小于或等于球体半径的平方，则有交点。如果大于，则没有交点。

- Sparky

Answer 3

这个网页提供了一个准确的解决方案。基本上，您将直线方程代入球面方程中，然后计算所得二次方程的判别式。 判别式的值表示相交。

- plinth

---

谢谢，我在其他地方找到了这个公式，但没有太多或任何解释它的作用，很高兴有一点解释。 - David

已更新为实时链接。 - plinth

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，则线段与球相交
• 如果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()

- pretzlstyle

Answer 5

如果你想要准确性，你基本上必须处理那个位置。算法上提高速度的唯一方法是从射线-球体相交改为射线-边界框相交。

或者你可以深入研究并试图提升sqrt和其他内部函数调用。

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

- CVertex