Ray polytope intersection?

Question

Context: I am working with polytopes, I am looking for a general way of testing if a point exists within an n-polytope by a vector ray-cast (most of what I have been able to gather while hunting via google was in relation to ray-plane intersection while employing line/plane equations, I believe this approach is restrictive or that a more robust solution can be developed to solve this problem because e.g. I don’t see how the equation for say a non-convex 5-polytope is possible, I may be wrong, regardless I am looking for a solution where I am not being restricted in this manner).

I have a 2-polytope (from a 3-polytope) made up of vertices $a,b,c$ and vectors $\vec{v_1}, \vec{v_2}, \vec{v_3}$.
$e$ is the origin of the ray being cast, $\vec{u}$ is the ray-vector, $d$ is the point the ray-vector hits the 2-polytope

while $\vec{n}$ below is the normal to the 2-polytope (I am guessing this might be required for any general solution)

How do I get the point $d$ where the ray $\vec{u}$ hits $a,b,c$. I know that this is rather supposed to be a simple question using some vector algebra/rule but the only thing I am seeing is $\vec{v_1} \times \vec{ad}=0$, $\vec{v_2} \times \vec{bd}=0$ etc since they lie within the same plane.

I hope to adapt the logic of whatever general solution provided to the problem above to that being addressed by the context provided earlier

Answer 1

With $\vec d=\vec e+\lambda\vec u$, you want $\left(\vec e + \lambda\vec u\right)\cdot\vec n=\vec a\cdot n$, so

$$ \lambda=\frac{\left(\vec a-\vec e\right)\cdot\vec n}{\vec u\cdot\vec n}\;, $$

which gives you

$$ \vec d=\vec e+\frac{\left(\vec a-\vec e\right)\cdot\vec n}{\vec u\cdot\vec n}\,\vec u\;. $$

Answer 2

Dot products are your (dimension-independent) friend here. One approach is to write $d = e + tu$ with $t$ unknown. The point $d$ lies in the plane containing $a$ and perpendicular to $n$ if and only if $$ 0 = n \cdot (d - a) = n \cdot (e - a) + t(n \cdot u), $$ from which we obtain $t = \frac{n \cdot (a - e)}{n \cdot u}$, and therefore $$ d = e + \frac{n \cdot (a - e)}{n \cdot u}\, u. $$

Answer 3

The ray $R$ from the point $e$ in the direction of the vector $\vec{u}$ can be expressed parametrically as the set of points $(x,y,z)$ such that $$ \left\lbrace \begin{align*} x&=e_x+u_xt\\ y&=e_y+u_yt\\ z&=e_z+u_zt\\ \end{align*} \right. $$ where the parameter $t$ satisfies $t\ge 0$, but is otherwise arbitrary.

Let $P$ be the plane through the $3$ distinct points $a,b,c$.

Choose a point $(x_0,y_0,z_0)$ on the plane $P$ (for example you could take $(x_0,y_0,z_0)=a$).

Then $P$ is the set of points $(x,y,z)$ satisfying the equation $$ n_x(x-x_0)+n_y(y-y_0)+n_z(z-z_0)=0 $$ Assume $e$ is not on $P$.

To find the point $d$ where the ray $R$ passes through the plane $P$ simply plug the parametric form for $R$ into the equation for $P$ and solve for $t$. Since $e$ is not on $P$, there will be at most one solution for $t$. The point $d$ exists provided a solution for $t$ exists and has $t > 0$.

Let $T$ denote the closed triangular region with vertices $a,b,c$.

To determine whether $d$ resides in $T$, proceed as follows . . .

. Express the vector $\vec{d}-\vec{a}$ as a linear combination of the vectors $\vec{b}-\vec{a},\vec{c}-\vec{a}$. $$ d-a = g_b(\vec{b}-\vec{a}) + g_c(\vec{c}-\vec{a}) $$ Then expand and rewrite the above equation in the form $$ d = h_a\vec{a} + h_b\vec{b} + h_c\vec{c} $$ where $h_a+h_b+h_c=1$.

Then $d$ resides in $T$ if and only if $h_a,h_b,h_c\ge 0$.

Answer 4

Suppose the 2-polytope has $N$ vertices $\{P_i\}$, numbered $i = 0, 1, 2, ..., N-1$, such that the numbering is sequential, i.e.

$ (P_k - P_i) \times (P_{k+1} - P_i ) $ doesn't change its sign for all $i$ and $k$

Now define the normal to the plane of the 2-polytope as follows

$ n = (P_1 - P_0) \times (P_2 - P_0) $

To determine if a point $Q$ lies inside the 2-polytope, we have to consider all the sides and define vectors

$V_i = P_{i+1} - P_i $

And define the vectors pointing to the inside of the 2-polytope as follows

$U_i = n \times V_i \hspace{25pt}, i = 0, 1, 2,... , N-1$

Then, evaluate the dot product

$ \alpha_i = U_i \cdot (Q - P_i) $ for all $ i = 0, 1, 2, ..., N-1 $

For point $Q$ to be within the 2-polytope we must have

$ \alpha_i \ge 0 , \hspace{25pt} i = 0, 1, 2, ..., N-1 $