Does a line intersect a box in a 3D space?

3.8k Views Asked by At

Known parameters:

  • Coordinates of the $8$ corners of the box: $\{(X_1;Y_1;Z_1), ..., (X_8;Y_8;Z_8)\}$
  • The box is alligned with the global coordinate system
  • Begin and end coordinates of the line: $\{(X_b;Y_b;Z_b),(X_e;Y_e;Z_e)\}$

Is there a general way to calculate this for the whole box at once or do I have to calculate if there's an intersection for every single face of the box?

If it should be calculated for every face I already found how to calculate the intersection from the line with the plane of the face. This will raise the next question:

How do I determine if an intersection point with the plane is an intersection with the face?

2

There are 2 best solutions below

6
On BEST ANSWER

You asked for a general method, so here we go:

Let $g$ be the line and let $H_1^+,H_1^-$ be the planes bounding your box in the first direction, $H_2^+,H_2^-$ and $H_3^+,H_3^-$ the planes for the 2nd and 3rd direction respectively.

Now find w.l.o.g $\lambda_1^+\leq\lambda_1^-$ (otherwise flip the roles of $H_1^+$ and $H_1^-$) such that $g\left(\lambda_1^+\right)\in H_1^+$ and $g\left(\lambda_1^-\right)\in H_1^-$ (take $\lambda_1^+=-\infty$ and $\lambda_1^-=+\infty$ for $g\parallel H_1^+$)

Analogeous get $\lambda_2^+\leq\lambda_2^-$ and $\lambda_3^+\leq\lambda_3^-$.

Now check for existence of $\lambda$ such that $\max\left(\lambda_1^+,\lambda_2^+,\lambda_3^+\right)\leq\lambda\leq\min\left(\lambda_1^-,\lambda_2^-,\lambda_3^-\right)$.

If there is no such $\lambda$ your line doesn't cut the box.

remark

  • you will find explicit formulae for $\lambda_1^+,...,\lambda_3^-$.

  • if $\lambda$ equals $\lambda_1^+$ then $g\left(\lambda\right)$ is in $H_1^+$ and so on.

  • in the case of the box being aligned with the coordinate system, calculating $\lambda_1^+$ and $\lambda_1^-$ would only need information of the first component of $g$ and is thus easy. You do not even need matrix calculus in that simple case.

  • I use $\lambda_1^+$ to indicate that $g$ is entering the region bounded by $H_1^+$ and $H_1^-$ at $\lambda_1^+$. (analogeously it is exiting at $\lambda_1^-$)

  • given a point $x$ you can check if it is inside of a convex polygon by checking if for each bounding plane $P=y+V$ ($V$ is a Plane containing $0$, y is a Vector inside the Plane $P$) with outer normal vector $n$ holds that the inner product $\left<x-y,n\right>$ is negative.

  • if you want to check if a point is in the inner of a convex polygon generally you have to check if it is in the inner (given an outer normal direction) of each bounding plane. If you find one plane such that it is on the outside you are already done and can stop.

0
On

Maybe check the slabs method that is often used in ray-tracing?

http://www.siggraph.org/education/materials/HyperGraph/raytrace/rtinter3.htm