3
$\begingroup$

In 3D I have been given a ray and a rectangle:

$$Ray=\mathbf{r_o}+t*\mathbf{r_d}$$ $$Rect=\mathbf{p_o}+p*\mathbf{p_x}+q*\mathbf{p_y}$$

where

  • $\mathbf{r_o}$ is the ray origin
  • $\mathbf{r_d}$ is the ray unit direction vector
  • $t>0$
  • $\mathbf{p_o}$ is the rectangle center
  • $-rectWidth/2 < p < rectWidth/2$
  • $-rectHeight/2 < q < rectHeight/2$
  • $\mathbf{p_x}$ is the rectangle unit x-vector
  • $\mathbf{p_y}$ is the rectangle unit y-vector
  • $\mathbf{p_x}$ and $\mathbf{p_y}$ are orthogonal, i.e. $\mathbf{p_x} \cdot \mathbf{p_y} = 0$

I'm trying to find

$$Ray'=\mathbf{r_o} + t*\mathbf{r_d'}$$

that intersects the rectangle and minimizes the angle between $\mathbf{r_d}$ and $\mathbf{r_d'}$ (in other words maximizes $\mathbf{r_d} \cdot \mathbf{r_d'}$). If $\mathbf{r_d}$ intersects the rectangle then naturally $\mathbf{r_d'}=\mathbf{r_d}$ and otherwise $\mathbf{r_d'}$ points towards the rectangle edge.

I have tried couple of solutions which unfortunately do not give correct results:

1) Calculate $p$ and $q$ at the intersection between the ray and the plane of the rectangle, and clamp $p$ and $q$ to the rectangle domain. Then calculate $\mathbf{v}=\mathbf{p_o}+p*\mathbf{p_x} + q*\mathbf{p_y} - \mathbf{r_o}$ and $\mathbf{r'_d}=\mathbf{v}/||\mathbf{v}||$. This works "mostly right", but breaks down when the ray points away from the rectangle (i.e. there's no intersection). Even if the ray points towards the rectangle, clamping $p$ and $q$ between $-rectWidth/2 < p < rectWidth/2$, and $-rectHeight/2 < q < rectHeight/2$ doesn't give correct result in all cases.

2) Project the ray to the rectangle plane and calculate intersection of the infinite line going along the projected ray and the rectangle. If the line intersects the rectangle, test which of the two intersection point gives the smallest angle. If the line doesn't intersect the rectangle, test which of the 4 corners of the rectangle gives the smallest angle. This seems to be quite wrong result and worse than option 1)

I don't need the exact solution for my application, so if there are some approximations that doesn't have too large errors I'm happy to try those out. If it helps, the rectangle parameters can also be simplified with affine transformation of the ray so that $\mathbf{p_o}=[0, 0, 0]$, $\mathbf{p_x}=[1, 0, 0]$, $\mathbf{p_y}=[0, 1, 0]$, $rectWidth=1$ and $rectHeight=1$.

$\endgroup$
  • $\begingroup$ By projecting dot product of projection and and normal to plane is zero, a fact that can be used to find minimum inclination. $\endgroup$ – Narasimham Sep 16 '15 at 21:10
  • 1
    $\begingroup$ I corrected some of your $p$ to be $q$, you might want to make sure your software doesn't make the same mistake. $\endgroup$ – DanielV Sep 16 '15 at 21:56
  • $\begingroup$ Ah yes, thank you for the fixes and reformatting, it's much better (: The application does the "right" thing, my bad with the errors in the post here. $\endgroup$ – JarkkoL Sep 17 '15 at 0:43
  • 1
    $\begingroup$ What you need to do is a perspective projection from $R_o$ along the direction $R_d$. Then the ray projects to the origin of the projection plane, the rectangle projects to a quadrilateral, and you want the point on this quadrilateral closest to the origin. (I'm pretty sure this works when the rectangle is "in front of" the ray, i.e. all points $P$ on the rectangle have $(P-R_o)\cdot R_d\ge0$, but if not then things get complicated.) $\endgroup$ – Rahul Sep 17 '15 at 1:27
  • $\begingroup$ @Rahul Interesting, the perspective projection technique works perfectly for points on the positive side of the XY-plane defined by the ray. Maybe there's a full solution that can be built upon this. $\endgroup$ – JarkkoL Sep 20 '15 at 13:32
2
$\begingroup$

Here is a robust 4 step solution that gives correct result for any $Ray$ and $Rect$ according to my tests.

Step 1:

Construct 4 vectors from the origin of the ray $\mathbf{r_o}$ to each corner of the rectangle $Rect$, in counter-clockwise order as seen from $\mathbf{r_o}$. Let's call these vectors $\mathbf{v_1}$...$\mathbf{v_4}$:

$$\mathbf{v_1}=\mathbf{p_o}-\mathbf{r_o}+0.5*rectWidth*\mathbf{p_x}+0.5*rectHeight*\mathbf{p_y}$$ $$\mathbf{v_2}=\mathbf{p_o}-\mathbf{r_o}+0.5*rectWidth*\mathbf{p_x}-0.5*rectHeight*\mathbf{p_y}$$ $$\mathbf{v_3}=\mathbf{p_o}-\mathbf{r_o}-0.5*rectWidth*\mathbf{p_x}-0.5*rectHeight*\mathbf{p_y}$$ $$\mathbf{v_4}=\mathbf{p_o}-\mathbf{r_o}-0.5*rectWidth*\mathbf{p_x}+0.5*rectHeight*\mathbf{p_y}$$

To ensure that these points are in counter-clockwise order as seen from $\mathbf{r_o}$, check if $$(\mathbf{p_x}\times\mathbf{p_y})\cdot(\mathbf{p_o}-\mathbf{r_o})<0$$ If the above condition doesn't hold swap vectors $\mathbf{v_1}$ and $\mathbf{v_3}$ to swap the winding order of the points to satisfy the winding requirement.

Step 2:

Construct 4 normal vectors $\mathbf{n_1}$...$\mathbf{n_4}$ for planes that lay on each edge of $Rect$ and $\mathbf{r_o}$ using the above vectors as follows: $$\mathbf{n_1}=\frac{\mathbf{v_1} \times \mathbf{v_2}}{||\mathbf{v_1} \times \mathbf{v_2}||}$$ $$\mathbf{n_2}=\frac{\mathbf{v_2} \times \mathbf{v_3}}{||\mathbf{v_2} \times \mathbf{v_3}||}$$ $$\mathbf{n_3}=\frac{\mathbf{v_3} \times \mathbf{v_4}}{||\mathbf{v_3} \times \mathbf{v_4}||}$$ $$\mathbf{n_4}=\frac{\mathbf{v_4} \times \mathbf{v_1}}{||\mathbf{v_4} \times \mathbf{v_1}||}$$

Step 3:

Out of these 4 normals pick a normal $\mathbf{n_{min}}$ and $\mathbf{v_a}$ and $\mathbf{v_b}$ that were used for cross product for the normal, that results smallest value for $\mathbf{n_i} \cdot \mathbf{r_d}$ (i.e. the most perpendicular plane to $\mathbf{r_d}$). For example if $\mathbf{n_{min}}=\mathbf{n_2}$, then $\mathbf{v_a}=\mathbf{v_2}$ and $\mathbf{v_b}=\mathbf{v_3}$.

If $\mathbf{n_{min}} \cdot \mathbf{r_d}>=0$, then $\mathbf{r'_d}=\mathbf{r_d}$ since $Ray$ intersects $Rect$. If not, continue to the last step

Step 4:

Project the ray direction $\mathbf{r_d}$ to the plane defined by $\mathbf{n_{min}}$: $$\mathbf{r_{pd}}=\mathbf{r_d}-(\mathbf{n_{min}} \cdot \mathbf{r_d})*\mathbf{n_{min}}$$ And clamp $\mathbf{r_{pd}}$ to the edge defined by $\mathbf{v_a}$ and $\mathbf{v_b}$ as follows to get the final result $\mathbf{r'_d}$: $$ \mathbf{r'_d}= \begin{cases} \mathbf{\hat{v_a}} & \text{if }(\mathbf{r_{pd}} \times \mathbf{v_a}) \cdot \mathbf{r_d}<0\\ \mathbf{\hat{v_b}} & \text{if }(\mathbf{v_b} \times \mathbf{r_{pd}}) \cdot \mathbf{r_d}<0\\ \mathbf{\hat{r_{pd}}} & \text{otherwise}\\ \end{cases} $$ Because I need to calculate steps 1 and 2 for solid angle calculation anyway, the additional cost of this algorithm is only steps 3 and 4 in my case.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.