Ray through Polytope boundary(vertex/surface)?

Question

This is a follow up problem to the question I asked sometime earlier also a similar problem to this, please what's the best way to quickly determine if a ray originating from a point intersects a n-polytope externally given it passes through a common boundary(vertex/surface) of the polytope. Here are some visual examples of the problem:

here the ray $\vec{r}$ intersects $abcd$ externally at $d$ here the ray $\vec{r}$ intersects $abcd$ internally at $d$ here the ray $\vec{r}$ intersects $abcdefgh$ externally at $d$ here the ray $\vec{r}$ intersects $abcdefgh$ internally at $d$ here the ray $\vec{r}$ intersects $abcdefgh$ externally at $dh$ here the ray $\vec{r}$ intersects $abcdefgh$ internally at $dh$

With some vector algebra how can one discern this for any given ray/n-polytope scenario?

UPDATE: The n-polytope is convex, all its vertices are known, also the intersection of the ray on the n-polytope is known and it could be a vertex/edge/surface/hyperface

Answer 1

First let's describe what to do when the intersection is at a vertex $v$ of the polytope. (See the image below for the 2D version, but everything I say will apply just as well in 3D.) We assume convexity so that the centroid gives us a inward vector at any vertex.

1. There are some number of faces of the polytope meeting the vertex $v$, each of which spans a plane (blue and orange dashed lines).

2. For each face, we can choose an inward vector orthogonal to the face, because we have the known inward vector from $v$ to the centroid to compare with (black dashed vector). Namely, if $v_i, v_j$ span the plane of the face then we can take $\pm (v_i\times v_j)$ where the sign is equal to that of $(v_i\times v_j)\cdot c$ where $c$ is the vector to the centroid from $v$.

3. Supposing we have a ray starting outside the polytope and passing through the face at $v$, we can measure whether a ray given by vector $r$ is inward or outward with respect to that face by taking the dot product with the normal vector obtained in the previous step and checking the sign. In other words $$(r \cdot (v_i\times v_j))(c\cdot(v_i\times v_j)) > 0$$

4. For a ray to pass inside the polytope, it must be inwards with respect to all faces, so (3.) should be repeated for every face (but you can exit early as soon as you find an outward direction with some face).

Note that if the ray comes from inside the polytope, then instead all the signs will be outward for each face. (It will be easy to account for this.) Also, if the dot product in (3.) is ever 0 then the ray intersects along the boundary at that face, and it is not interior.

Hopefully the image makes it intuitive that the test rays starting outside the polytope begin entering the interior of the polytope precisely when they have a positive dot product with the normal vectors to each face.

As for the case when intersection is an edge $(v_1,v_2)$, then you may apply the same algorithm as above but only to the pair of faces touching the edge. To find those faces simply go to $v_1$ and pick out the faces containing $v_2$.

Finally, when the intersection is a face, you only need to check the ray is not parallel to the face itself. One way is to find an inward normal vector to the plane as above and check that the dot product does not vanish.