one sphere and many line segments intersection

0
votes

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.

1
algorithmintersectionraytracingspace-partitioning
Octrees? R-trees? Anyway asking for links, tutorials and other resources is off-topic here. Please read the How to Ask page. – meowgoesthedog
I think KD-Tree is your best bet since you'll only have to search the subsets that intersect your sphere in question (assuming you store the full line segments in your tree). – SirGuy
It doesn't make much sense to ask this question for a single sphere. Any.method would compute tye intersection for all lines. Putting the lines to a data structure like KD tree would pay off only if you need to perform many queries with the same set of lines. – n. 1.8e9-where's-my-share m.
@n.m. I agree this is a bit unusual. Query is the given sphere which is unknown until it is asked but the set of line segments exists in advance. – CCode
@meowgoesthedog thanks. I think the question did not ask for any links or tutorials. – CCode

1 Answers

0
votes

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.