0

Consider N disjoint line segments and a ray.

Let's say the line segments are stored as a list of $N$ 4-tuples, each tuple storing the coordinates of the endpoints of the line segment $(x_0, y_0, x_1, y_1)$.

Let's say the ray is stored as a 4-tuple, with its elements as coordinates of its starting point and another point on the ray $(x_0, y_0, x_1, y_1)$. Here we are referring to a ray with its origin at $(x_0, y_0)$ and pointing towards $(x_1, y_1)$.

Question: What is the fastest way to find the first line segment intersected as this ray progresses forward from the origin?

Many of the online tutorials I have seen just find the intersection with all the line segments and pick the one which has the intersection closest to the origin. Is this the best way of doing this?

I am working on a ray-tracing application in which I need this to be extended to $3D$ (with rays in $3D$ and triangles in place of line segments). So a better (with time complexity better than $O(n)$ ) way of finding the first line segment which intersects the ray will be very helpful. If you know any algorithms or have any ideas please let me know with a clear explanation.

Venu Nathan
  • 1

1 Answers1

1

If no preprocessing is allowed, faster than $O(n)$ is just impossible because you need to look at all segments at least once.

If preprocessing is allowed, and assuming that your segments are relatively short, you can try wrapping every segment in its axis-aligned bounding box and establish a hierarchy of bounding boxes (for instance a binary tree where on every level you try to split along a coordinate in a well-balanced way, leading to a kind of kD-tree).

Then for every ray, you will traverse the tree depth-first and keep a trace of the closest hit. When you process a new node of the tree, check for overlap of the bounding box of this node and the bounding box of the remaining portion of the ray. This will prune away a number of segments. In good conditions, you could expect a reduction to $O(\log n)$, with a small asymptotic constant.

This generalizes to 3D.