one sphere and many line segments intersection

Question

I am familiar with BSP, KD-tree and BVH for the general ray-primitive intersection finding problem. Are there any more efficient algorithms and data structures for finding intersections between only one sphere and many line segments? Please note that the sphere is query object.

Answer 1

One solution would be:

• Determine the line segments' bounding boxes and create a BVH or kd-tree from them.
• Determine the query sphere's bounding box.
• In your intersection algorithm, walk the sphere through the tree by checking for overlap between the sphere's BB and the current node.
  • If there is no overlap, the sphere's BB doesn't intersect any line segment in the given node, and you can skip the node's children.
  • If there is overlap, walk the node's children.
  • At the leaf nodes, you have to perform a ray-intersection test for each line segment in the node and the sphere (it's not clear from your question, but I assume multiple segments can intersect the sphere and that you're interested in all such intersections). You can optimize the actual intersection test a bit like so:

Suppose that

• The sphere has radius R and its center is at point C,
• the line segment has ends at points P0 and P1,
• D0 is the distance between C and P0, and
• D1 is the distance between C and P1.

Then:

• If D0 < R and D1 < R, the line segment is contained entirely inside the sphere and does not intersect the surface.

• If D0 < R xor D1 < R, the line segment intersects the sphere's surface.

• Otherwise, the points are outside the sphere, but the line might intersect the surface, so run a regular ray-sphere intersection test.

A further optimization would be to compare squared distances with the squared radius, to avoid taking the roots.