我正在尝试确定线段（即两点之间）是否与球体相交。我对交叉点的位置不感兴趣，只关心线段是否与球面相交。有人对最有效的算法有什么建议吗？（我想知道是否有比通常的射线球相交算法更简单的算法，因为我对相交位置不感兴趣）
问问题
12827 次
4 回答
11
如果您只对知道它是否相交感兴趣，那么您的基本算法将如下所示......
假设你有你的射线线的矢量，A -> B。
你知道这个向量和球体中心之间的最短距离发生在你的射线向量和一个与它成 90 度的向量的交点处，它穿过球体的中心。
因此，您有两个向量，其方程完全定义。您可以使用线性代数计算向量的交点，从而计算线的长度（或更有效地计算线长度的平方）并测试它是否小于半径（或半径的平方） ) 你的领域。
于 2010-01-14T21:16:10.273 回答
5
我不知道标准的做法是什么，但如果你只想知道它是否相交，这就是我会做的。
一般规则...避免执行 sqrt() 或其他昂贵的操作。如果可能，处理半径的平方。
- 确定起点是否在球体的半径内。如果您知道情况并非如此，请跳过此步骤。如果你在里面，你的光线将与球体相交。
从这里开始，您的起点在球体之外。
- 现在，想象一下适合球体的小盒子。如果您在该框之外，请检查射线的 x 方向、y 方向和 z 方向，以查看它是否会与您的射线开始的框的一侧相交。这应该是一个简单的符号检查，或与零比较。如果你在外面并远离它，你将永远不会与它相交。
从这里开始，你处于更复杂的阶段。你的起点在想象的盒子和球体之间。您可以使用微积分和几何获得简化的表达式。
您想要做的事情的要点是确定您的光线和球体之间的最短距离是否小于球体的半径。
让您的射线由 (x0 + i t, y0 + j t, z0 + k t) 表示，球体的中心位于 (xS, yS, zS)。因此，我们希望找到 t，使其给出 (xS - x0 - i t, yS - y0 - j t, zS - z0 - k t) 中最短的一个。
设 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 = ... 的方程。如果结果小于或等于球体半径的平方，则有一个交点。如果它更大，则没有交集。
于 2010-01-14T20:16:30.987 回答
4
这个页面有这个问题的精确解决方案。本质上，您是将直线方程代入球体方程，然后计算所得二次方的判别式。判别式的值表示交集。
于 2010-01-14T20:46:29.550 回答
-1
如果你想要准确性，你无论如何都必须在这个位置上工作。在算法上提高速度的唯一方法是从光线球体相交切换到光线边界框相交。
或者您可以更深入地尝试改进 sqrt 和其他内部函数调用
于 2010-01-14T05:17:31.043 回答