algorithm - 一个球体与多条线段相交

Question

我熟悉 BSP、KD-tree 和 BVH 来解决一般的射线原始相交问题。是否有更有效的算法和数据结构来查找仅一个球体和许多线段之间的交点？请注意，球体是查询对象。

Answer 1

一种解决方案是：

• 确定线段的边界框并从中创建 BVH 或 kd-tree。
• 确定查询球体的边界框。
• 在您的交集算法中，通过检查球体的 BB 和当前节点之间的重叠来让球体穿过树。
  • 如果没有重叠，则球体的 BB 不会与给定节点中的任何线段相交，您可以跳过该节点的子节点。
  • 如果有重叠，则遍历节点的子节点。
  • 在叶节点处，您必须对节点和球体中的每个线段执行射线相交测试（从您的问题中不清楚，但我假设多个线段可以与球体相交并且您对所有这些都感兴趣路口）。您可以像这样优化实际的交叉点测试：

假设

• 球体有半径R，其中心在点C，
• 线段在点P0和处结束P1，
• D0C是和之间的距离P0，并且
• D1C是和之间的距离P1。

然后：

• 如果D0 < R和D1 < R，则线段完全包含在球体内并且不与曲面相交。

• 如果D0 < Rxor D1 < R，则线段与球体表面相交。

• 否则，这些点在球体之外，但线可能与表面相交，因此请运行常规的射线-球体相交测试。

进一步的优化是将平方距离与平方半径进行比较，以避免取根。