I need to find the intersection of a segment with 3D rectangle.
I have four corners of a 3D rectangle and start, end point of a segment. I want to find the intersection point on 3D rectangle.
see the below image:
- $p_1,p_2,p_3,p_4$ are four corner of the rectangle.
- $a,b$ are start and end point of a segment.
- I need to find the intersection (red point in the image)
segment e-f and c-d are not intersecting with the rectangle.
in my case all segments are 90 degree upwards (parallel to Z axis).
all points are 3D points $(x,y,z)$
I already searched lot in google, all solutions for plane and line($\infty$) not for a finite 3D rectangle and segment.
Can anyone help me to solve this?
Best Answer
I would start from N.Bach’s suggestion: find the intersection of the segment with the plane that contains the rectangle and then test to see if this point lies within the rectangle. Here’s one way to do this.
Assuming that the rectangle isn’t parallel to the $z$-axis, compute the affine transformation $M$ that maps the unit square onto the rectangle and leaves the $z$-axis unchanged. Given a pair of segment endpoints $\mathbf q_1$ and $\mathbf q_2$, compute $\mathbf q_1' = M^{-1}\mathbf q_1$ and $\mathbf q_2' = M^{-1}\mathbf q_2$. If the $x'$- and $y'$- coordinates of the results (which should be the same for both points) are in the range $[0,1]$ and the $z'$-coordinates have different signs, then the segment intersects the rectangle. The intersection point is then $M(x',y',0)$. Since you already know what the $x$- and $y$-coordinates of the intersection point should be, you can save some work by using proportional triangles to compute $$z_{\text{int}} = {|z_2'|z_1+|z_1'|z_2 \over |z_1'|+|z_2'|} \tag1$$ for this point.
Constructing $M$ as a homogeneous transformation matrix is quite straightforward if you recall that its columns are the images of the basis vectors. We want the unit $x'$ vector to map to one side of the rectangle and the unit $y'$ vector to map to an adjacent side. Taking $\mathbf p_1$ as the origin, we therefore have $$M = \begin{bmatrix}\mathbf p_2-\mathbf p_1 & \mathbf p_4-\mathbf p_1 & \mathbf e_3 & \mathbf p_1 \\ 0&0&0&1\end{bmatrix}.$$ The first two columns can be swapped, if you like; it makes no difference to the result. The matrix inversion is a bit expensive, but it’s a one-time cost that’s amortized over all of the line segments that you’re processing.
Alternatively, you can start by finding the intersection point. The dot product $d = \mathbf n\cdot\mathbf p$ of a point $\mathbf p$ and a fixed normal to the plane $\mathbf n$ is proportional to the signed distance of the point from the plane, so you can use the two dot products $d_1$ and $d_2$ of the segment endpoints instead of $z'_1$ and $z'_2$, respectively, in the plane-crossing test and formula (1). You still need to test that this point is within the rectangle, but you can do that by computing the scalar projections of $\mathbf q_{\text{int}}-\mathbf p_1$ onto $\mathbf p_2-\mathbf p_1$ and $\mathbf p_4-\mathbf p_1$ and doing a simple range check.* This amounts to computing $M^{-1}\mathbf q_{\text{int}}$ by hand, but you can save a little computation by dropping the $z$-coordinates and making this test with the projections of the relevant points onto the $x$-$y$ plane, which is a 2-D computation.
* $\mathbf u\cdot\mathbf v$ is equal to $\|\mathbf u\|$ times the (signed) length of the orthogonal projection of $\mathbf v$ onto $\mathbf u$. This projection thus lies on the line segment defined by $\mathbf u$ iff $0\le\mathbf u\cdot\mathbf v\le\mathbf u\cdot\mathbf u$.