1
$\begingroup$

i'm looking for a fast method to get the intersecting points between a ray and a parallelgram defined by the 4 vertices!

till now i've thought to test the intersection point between ray and the 4 edge, but mayebe there are computationally faster OR mathematically more elegant way to do it.

mayebe check ray-triangles intersection with the 4 triangles that forms the parallelogram?

some advice?

EDIT: as copper.hat point me out the intersection points could be 0, 1 or 2. or the entire edge if the ray is coincident with an edge

  • 0
    yeah, thanks for point me out, the question is modified2012-05-08

2 Answers 2

2

Assume that the ray starts at the origin $o$ and has direction $u\ne0$, and let $a_0$, $a_1$, $a_2$, $a_3$ be the four vertices. The line through $o$ in direction $u$ intersects the line $a_0\vee a_1$ in a point satisfying $t u= a_0+s (a_1-a_0)$ with real $s$ and $t$. It follows that $0=u\wedge a_0 +s u\wedge (a_1-a_0)\ ,\qquad t u\wedge(a_1-a_0)=a_0\wedge(a_1-a_0)\ ,$ which gives $ s=-{u\wedge a_0\over u\wedge(a_1-a_0)}\ ,\qquad t={a_0\wedge a_1\over u\wedge(a_1-a_0)}\ .$ The ray intersects the parallelogram side $[a_0,a_1]$ iff $t\geq0$ and $0\leq s\leq1$. Leaving the special case that the ray passes through one of the endpoints apart, the latter condition is easily seen to be equivalent with ${\rm sgn}(u\wedge a_0)=-{\rm sgn}(u\wedge a_1)$ (as is geometrically evident).

These preparations suggest the following procedure: Compute the eight quantities $p_k:= a_{k-1}\wedge a_k\ ,\quad q_k:=u\wedge a_k\qquad(1\leq k\leq 4(=0))\ .$ Assume for simplicity that all $q_k\ne0$. If there is a sign change between $q_{k-1}$ and $q_k$ check whether $t_k:={p_k\over q_k-q_{k-1}}\geq0\ .$ In this case the ray hits the side $[a_{k-1},a_k]$ of theparallelogram at the point $t_k u$.

1

Classify the four vertices with respect to the line containing the ray by computing the sign of the (degree-one) expression defining the line. If all four vertices have the same sign, then the line does not cross the parallelogram. Othewise, find the two edges where the signs differ and find the intersection points. Make sure you check the intersection points are in the ray. You'll also have to take care of the special cases of the line passing through one vertex or an edge.

  • 0
    @nkint, I've edited my answer slightly.2012-05-08