I have a three-dimensional body $V$ and two points $R_p,R_m\in\mathbb{R}^3$. How do I find if the segment of the line between the points goes through $V$?
My initial thought was to, somehow, intersect the line with all the points inside $V$. How do I know which points are included? I started with a rectangular body of size $[L_x,L_t,L_z]$ located at $[0,0,0]$. if there is a point $(x_0,y_0,z_0)$ on the line which corresponds to $0<x_0<L_x,0<y_0<L_y,0<z_0<L_z$ then I know the line goes through the box. How do I do it for an arbitrary body?
I thought of solving 3 equations for $(x,y,z)$, where equations will come from the line and the space but I could not figure out what would be these equations. I also tried a simpler 2d case to no avail.
Is there a methodic way of solving such problems?
Best Answer
You parametrise the line using e.g. $t$, $$\vec{p} = (1-t)\vec{p}_0 + t \vec{p}_1 = \vec{p}_0 + t (\vec{p}_1 - \vec{p}_0)\tag{1}\label{1}$$ where $\vec{p}_0$ and $\vec{p}_1$ are two points on the line. Note that $\vec{p} = \vec{p}_0$ when $t = 0$, and $\vec{p} = \vec{p}_1$ when $t=1$.
Within the line segment, $0 \le t \le 1$. (Also note that this is simply just linear interpolation between the two points.) If you are concerned with the intersection between the line segment and some volume, only consider $t$ such that $0 \le t \le 1$.
Then, you need to define the surface of the volume somehow. For convex polyhedra, you can do this with halfspaces (planes); for concave polyhedra, with triangular/polygonal faces; and so on. Using an implicit function $f(x, y, z) = 0$ for the surface is particularly useful.
Finally, you find the $t$ where the point $\vec{p}$ intersects the surface. If there are no intersections, the line is completely outside the surface.
If there are no intersections $0 \le t \le 1$, the line segment is either completely inside or completely outside the surface. If there are an odd number of intersections $t \lt 0$, and/or and odd number of intersections $t \gt 0$, and the surface is a closed surface (with no plane-like zero-volume regions), then the line segment is completely inside the surface; otherwise it is completely outside the surface.
For arbitrary surfaces, you will need the surface normal at the smallest $t \gt 1$, or the largest $t \lt 0$, and determine if the surface normal points towards or away from $t = 1$ or $t = 0$, respectively (using vector dot product, for example). If the surface normals are defined to point away from the volume, and the normal is towards the line segment, then the line segment is outside; if the surface normals are defined to point into the volume, and the normal is away from the line segment, then the line segment is also outside; otherwise, the line segment is inside the volume.
Consider the intersection of the line and a sphere with radius $r$ centered at origin. The implicit equation for this sphere is $$\vec{p} \cdot \vec{p} - r^2 = 0 \quad \iff \quad x^2 + y^2 + z^2 - r^2 = 0$$ Substituting $\eqref{1}$ into above yields $$\bigr(\vec{p}_0 + t (\vec{p}_1 - \vec{p}_0)\bigr) \cdot \bigr(\vec{p}_0 + t (\vec{p}_1 - \vec{p}_0\bigr) - r^2 = 0$$ or, in Cartesian coordinate form, using $\vec{p}_0 = (x_0, y_0, z_0)$, $\vec{p}_1 = (x_1 , y_1 , z_1)$, and $\vec{p} = ( x, y, z )$, $$( (1 - t) x_0 + t x_1 )^2 + ( (1 - t) y_0 + t y_1 )^2 + ( (1 - t) z_0 + t z_1 )^2 - r^2 = 0$$ If we expand this, and group the coefficients for different powers of $t$, we get $$\begin{aligned} \bigr( (x_1 - x_0)^2 + (y_1 - y_0)^2 + (z_1 - z_0)^2 \bigr) ~ t^2 & + \\ 2 \bigr( x_1 (x_1 - x_0) + y_1 (y_1 - y_0) + z_1 (z_1 - z_0) \bigr) ~ t & + \\ x_0^2 + y_0^2 + z_0^2 - r^2 ~ & = 0 \\ \end{aligned}$$ which is a simple quadratic equation in $t$, and has an algebraic solution. It yields zero, one, or two real $t$, depending on whether the line is completely outside the sphere, grazes the sphere tangentially at a single point, or intersects the sphere in two points.
Consider an axis-aligned cube with edge length $2$ centered at origin. It has eight vertices at $(\pm 1, \pm 1, \pm 1)$, and six faces.
Because the faces are planar -- two faces at $x = \pm 1$, two at $y = \pm 1$, and two at $z = \pm 1$ -- we need to know how to find the intersection of $\eqref{1}$ and a plane.
In general, the equation of a plane is $\vec{p}\cdot\vec{n} = d$, where $\vec{n}$ is the normal of the plane (a vector perpendicular to the plane, in other words), and $d$ is the signed distance from origin in units of $\lvert\vec{n}\rvert$. Using $\vec{n} = ( x_n , y_n , z_n )$, substituting $\vec{p}$ from $\eqref{1}$ into this, we get $$\bigr(\vec{p}_0 + t (\vec{p}_1 - \vec{p}_0)\bigr) \cdot \vec{n} - d = 0$$ or, equivalently in Cartesian coordinate form, $$\bigr( x_n (x_1 - x_0) + y_n (y_1 - y_0) + z_n (z_1 - z_0) \bigr) t + x_0 x_n + y_0 y_n + z_0 z_n - d = 0$$ which has a single solution, $$t = \frac{d - x_0 x_n - y_0 y_n - z_0 z_n}{ x_n (x_1 - x_0) + y_n (y_1 - y_0) + z_n (z_1 - z_0) }$$ If the divisor is zero, the line is parallel to the plane. In that case, if and only if $$x_n x_0 + y_n y_0 + z_n z_0 - d = x_n x_1 + y_n y_1 + z_n z_1 -d = 0$$ the line is on the plane; otherwise the line does not intersect the plane at all.
For axis-aligned planes, the solution simplifies to $$t = \begin{cases} \left(\displaystyle \frac{\frac{d}{r} - x_0}{x_1 - x_0}\right), & \vec{n} = (r, 0, 0) \\ \left(\displaystyle \frac{\frac{d}{r} - y_0}{y_1 - y_0}\right), & \vec{n} = (0, r, 0) \\ \left(\displaystyle \frac{\frac{d}{r} - z_0}{z_1 - z_0}\right), & \vec{n} = (0, 0, r) \\ \end{cases} \quad \text{and} \quad 0 \ne r \in \mathbb{R}$$ For the aforementioned cube, we'll need to find the $t$ for each face, and if found, verify that $\vec{p}$ at that value of $t$ is within the face polygon, i.e. use a 2D point-in-polygon test, to see if the line intersects that face (polygon).
For axis-aligned rectangles this is simple, since you just compare the point coordinates to the face rectangle.
For convex polygonal faces, with normal $\vec{n} = (x_n, y_n, z_n)$, vertices $\vec{v}_i = (x_i, y_i, z_i)$ and a point $\vec{p} = (x, y, z)$ on the same plane as the polygon, there is a straightforward test: compute $$s_i = \bigr( \vec{p} - \vec{v}_i \bigr) \times \bigr( \vec{v}_{i+1} - \vec{v}_i \bigr) \cdot \vec{n}$$ i.e. $$\begin{aligned} s_i &= x_n \bigr( (y - y_{i}) (z_{i+1} - z_{i}) - (z - z_{i})(y_{i+1} - y_{i}) \bigr) \\ ~ &+ y_n \bigr( (z - z_{i}) (x_{i+1} - x_{i}) - (x - x_{i})(z_{i+1} - z_{i}) \bigr) \\ ~ &+ z_n \bigr( (x - x_{i}) (y_{i+1} - y_{i}) - (y - y_{i})(x_{i+1} - x_{i}) \bigr) \\ \end{aligned}$$ If all $s_i \le 0$, or if all $s_i \ge 0$, the point is inside the convex polygon. Otherwise, it is outside.