一个球体和许多线段交集

Question

我熟悉BSP，KD-Tree和BVH，对于一般的射线主要相交查找问题。是否有更有效的算法和数据结构来查找仅一个领域和许多线段之间的交叉点？请注意，球体是查询对象。

Answer 1

一个解决方案将是：

• 确定线段的边界框，并从中创建一个BVH或KD-Tree。
• 确定查询球的边界框。
• 在您的交叉点算法中，通过检查球体的BB和当前节点之间的重叠，将球体穿过树。
  • 如果没有重叠，则Sphere的BB不会与给定节点中的任何线段相交，您可以跳过节点的孩子。
  • 如果有重叠，请走节点的孩子。
  • 在叶节点上，您必须对节点和球体中的每个线段进行射线截距测试(从您的问题中不清楚，但是我认为多个段可以与球体相交，并且您感兴趣的是在所有此类交叉口中(。您可以像这样优化实际的交叉点测试：

假设

• 球体具有半径R，其中心位于点C，
• 线段在点P0和P1，
以结束
• D0是C和P0之间的距离，
• D1是C和P1之间的距离。

然后：

• 如果D0 < R和D1 < R，该行段完全包含在球体内，并且不会与表面相交。

• 如果D0 < R XOR D1 < R，则行节与球体的表面相交。

• 否则，这些点在球体之外，但是线可能相交表面，因此进行常规的射线透明相交测试。

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