0
$\begingroup$

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$ enter image description here here the ray $\vec{r}$ intersects $abcd$ internally at $d$ enter image description here here the ray $\vec{r}$ intersects $abcdefgh$ externally at $d$ enter image description here here the ray $\vec{r}$ intersects $abcdefgh$ internally at $d$ enter image description here here the ray $\vec{r}$ intersects $abcdefgh$ externally at $dh$ enter image description here here the ray $\vec{r}$ intersects $abcdefgh$ internally at $dh$ enter image description here

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

$\endgroup$
13
  • $\begingroup$ In all shown cases polytope consists of parallel opposite faces. Is this a part of problem statement? $\endgroup$ Apr 29, 2022 at 10:58
  • $\begingroup$ How exactly are the polytope and the ray specified? For example, can we assume that we already have a matrix $A$ and vectors $\vec b, \vec p, \vec r$ such that the polytope is specified by $Ax \leq b$ and the ray eminates from $p$ in the direction $r$? $\endgroup$ Apr 29, 2022 at 11:52
  • $\begingroup$ As I understand it, the question is whether or not, at the intersection point (if any), the vector is pointing towards the inside of the polyhedron. As said by Ben Grossmann, if your polytope is defined by $AX \le B$ with $X=(x,y,z)^T$ and $A$ is a $n \times 3$ matrix ($n$ being the number of facets), it is easy, once you are at the boundary, to take an $Y:=X+\varepsilon U$ and test if $AY < B$. .. $\endgroup$
    – Jean Marie
    Apr 29, 2022 at 12:08
  • $\begingroup$ @LiNKeR, I think any polytope has center of gravity (O). this is where the sum of all vectors (resulting vector) is zero. We can assume this point the origin of coordinate system. Now you have a point (A) with certain coordinate. If the vector passing through this point is perpendicular to vector OA, then it definitely passes the polytope externally. If the point is on a common boundary you must have it's coordinate and follow the same rule. $\endgroup$
    – sirous
    Apr 29, 2022 at 14:02
  • $\begingroup$ I apologize firstly for responding late, secondly for disturbing everyone on here thirdly just incase the question wasn’t asked properly. @BenGrossmann I am not quite sure so let me explain in simple terms (without the maths) given the vertices of some arbitrary polytope I am trying to determine that a ray vector $\vec{r}$’s infinite line through some arbitrary point $\vec{p}$ cuts through the polytope (divides its vertices in two halves/hemispheres/…) or that it doesn’t cut through the vertices (all vertices are just on a side/area of the infinite line) $\endgroup$
    – linker
    Apr 29, 2022 at 20:22

1 Answer 1

1
$\begingroup$

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.

enter image description here

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .