Determine if a line will interest with a rectangular prism

Question

Alright lets say I have 2 points in 3 dimensional space how could I determine if a line interesting those 2 points will pass through a rectangular prism when all I have is that prisms min and max value for all 3 coordinates? Is there an easy way I can check for an intersection here?

I found this which is similar to my question however it does not seem to be answered either. The last comment left on the post has an example that is similar to what I would be doing since they defined the box with its min and max values. How to check if an infinite line intersects a rectangular prism in 3d space?

My end goal is to be able to throw it into software to be able to detect intersections however I am not sure how I am suppose to actually create a useable formula from the info given on that post.

Answer 1

Write the line as $(a_1, a_2, a_3) + t (b_1, b_2, b_3)$ and the rectangular prism as $[c_1, d_1] \times [c_2, d_2] \times [c_3, d_3]$. For a point of the line to intersect the prism, there must be a value of $t$ such that $$ \begin{cases}c_1 \le a_1 + t b_1 \le d_1 \\ c_2 \le a_2 + tb_2 \le d_2 \\ c_3 \le a_3 + tb_3 \le d_3 \end{cases} $$

Each inequality $c_i \le a_i + tb_i \le d_i$ (for $i=1, 2, 3$) is solved in the same way, but the result depends on the sign of $b_i$:

• If $b_i > 0$, then we get $\frac{c_i - a_i}{b_i} \le t \le \frac{d_i - a_i}{b_i}$.
• If $b_i < 0$, then we instead get $\frac{d_i - a_i}{b_i} \le t \le \frac{c_i - a_i}{b_i}$, because dividing by $b_i$ reverses the inequalities.
• If $b_i = 0$, then either $c_i \le a_i \le d_i$ (and the inequality is true for all $t$), or not (and the inequality is false for all $t$).

We'll get several lower and upper bounds on $t$. If the largest lower bound is less than or equal to the smallest upper bound, then we can combine them to get an interval of $t$-values that work. (This can be used to find all the points where the line intersects the prism.)

If the largest lower bound is bigger than the smallest upper bound, or if one of the inequalities we started with was false for all $t$, then there is no intersection.

---

For example, suppose we want to intersect the line through $(1,2,3)$ and $(3,2,1)$ with the prism $[-1,1] \times [0,5] \times [4,6]$.

We rewrite the line as $(1,2,3) + t(2,0,-2)$, and get the three inequalities $$ \begin{cases}-1 \le 1 + 2t \le 1 \\ 0 \le 2 + 0t \le 5 \\ 4 \le 3 - 2t \le 6 \end{cases} $$ The first inequality $-1 \le 1+2t \le 1$ simplifies to $-2 \le 2t \le 0$ and then to $-1 \le t \le 0$. That's our first interval for $t$: the interval $[-1,0]$.

The second inequality $0 \le 2 + 0t \le 5$ does not depend at all on $t$. Luckily for us, it's true. (If it were false, we'd already know there's no intersection.)

The third inequality $4 \le 3-2t \le 6$ simplifies to $1 \le -2t \le 3$ and then to $-\frac32 \le t \le -\frac12$. That's our second interval for $t$: the interval $[-\frac32, -\frac12]$.

The intersection of these intervals is $[-1,0] \cap [-\frac32, -\frac12]$ is $[-1, -\frac12]$, so for any $t$ in this range, the line is inside the prism. (In particular, the line does intersect the prism.) For example, when $t = -\frac34$, the point $(1,2,3) - \frac34 (3,2,1) = (-\frac54, \frac12, \frac94)$ is inside the prism.