0
$\begingroup$

Is it possible to find a 4x4 homogeneous transformation matrix that transforms line segment A into line segment B?

Each of the two segments is described by two homogeneous points, start P1 and end P2.

The first segment A is always (-0.5, 0, 0, 1) / (0.5, 0, 0, 1). The x, y and z values of B are arbitrary but the w component is always 1.

My first idea was to compose the matrix out of translation, scaling and rotation, but computing the rotation part with trigonometry is too expensive to implement. maybe there is a more direct solution?

$\endgroup$
  • $\begingroup$ It’s certainly possible, but the transformation is not unique. The remaining degrees of freedom depend on what you mean by a “homogeneous transformation.” A perspective transformation will have more unknowns than an affine transformation. $\endgroup$ – amd Mar 30 '17 at 1:18
  • $\begingroup$ Affine, no perspective distortion is desired. $\endgroup$ – thalm Mar 30 '17 at 2:35
  • $\begingroup$ You need a third pair of points to specify the mapping completely. $\endgroup$ – amd Mar 30 '17 at 6:10
  • $\begingroup$ i was hoping that the fact that the first segment is always the same and lies on the x-axis would help somehow... $\endgroup$ – thalm Mar 30 '17 at 11:17
  • $\begingroup$ Oops. I didn’t notice that you’re working in $\mathbb{RP}^3$, not $\mathbb{RP}^2$. You’ll need two more pairs of points in order to specify the mapping completely. Knowing that one of the segments is always on the $x$-axis helps a little in that it simplifies choosing the other two source points so that the four aren’t coplanar. $\endgroup$ – amd Mar 30 '17 at 17:04
1
$\begingroup$

It’s fairly easy to construct an affine map that will send one line segment to the other, but two pairs of points aren’t enough to specify this map uniquely. Since you’re working in $\mathbb{RP}^3$, you’ll need another two pairs to nail down the mapping completely.

I’ll assume the common computer graphics convention of points being represented by row vectors and right-multiplication by a matrix to apply a transformation.

The construction relies on the fact that the columns of a transformation matrix are the images of the basis. So, start by forming the matrix $Q$ that has the homogeneous coordinates of the destination points $Q_k$ as rows. These are the images of the corresponding input points $P_k$, so perform a change of basis to the standard basis by left-multiplying by the inverse of the matrix with the $P_k$ as its rows. I.e., the transformation matrix is $$P^{-1}Q=\begin{bmatrix}P_1\\P_2\\P_3\\P_4\end{bmatrix}^{-1}\begin{bmatrix}Q_1\\Q_2\\Q_3\\Q_4\end{bmatrix}.$$ This requires the $P_k$ to be linearly independent as elements of $\mathbb R^4$, of course, so that they form a basis, which means that the four points can’t be coplanar in $\mathbb{RP}^3$. If you like, you can avoid the matrix inversion and multiplication by computing this product via row-reduction. Form the matrix $\left[\,P\mid Q\,\right]$ and row-reduce to produce $\left[\,I\mid P^{-1}Q\,\right]$.

You have $P_1(-1/2,0,0,1)$, $P_2(1/2,0,0,1)$ and their images $Q_1$ and $Q_2$, the endpoints of the destination line segment. Choose $P_3$ and $P_4$ so that $P$ is nonsingular. With fixed choices for the four source points you can then precompute $P^{-1}$. A convenient choice is $P_3(0,1,0,1)$ and $P_4(0,0,1,1)$, with which $$P^{-1}=\begin{bmatrix}-1&1&0&0\\-\frac12&-\frac12&1&0\\-\frac12&-\frac12&0&1\\\frac12&\frac12&0&0\end{bmatrix}.$$

The choice of $Q_3$ and $Q_4$ determines how the transformation behaves for points that aren’t on the source line. If you don’t care about that, some simple computational choices are to collapse the rest of the space by setting them both equal to zero, or by setting them equal to $P_3$ and $P_4$, respectively. The latter choice is well-behaved most of the time, but results in a singular transformation if either of these points lies on the destination line.

By the way, depending on what it is you’re doing, mapping one line segment to another directly could be a much easier way to go. The source line segment can be parameterized as $(1-t)P_1+tP_2=(t-\frac12,0,0,1)$. The corresponding point on the destination segment is then simply $(1-t)Q_1+tQ_2$. If you examine the transformation constructed above, you’ll see that this is exactly what it’s doing for points along the source line: $(t-\frac12,0,0,1)P^{-1}=(1-t,t,0,0)$, and multiplying $Q$ by this vector yields $(1-t)Q_1+tQ_2$. (In fact, this is true regardless of what you choose for $P_3$ and $P_4$—the first and last rows of $P^{-1}$ turn out to be independent of this choice.)

$\endgroup$
  • $\begingroup$ Excellent explanation! Q3 and Q4 are indeed the missing information. In the code a matrix is required. Collapsing the space seems to be ok so far. Thanks for pointing out the singularities, that's the most important part to know. Current solution is to assume the source segment is e1 (unit vector on x-axis). Set the first row as Q2-Q1 and multiply with a translation (0.5, 0, 0). Multiplying the translation with the values set into the first matrix would be even more efficient. (DirectX uses the more common row x col notation, vectors are 1x4 matrices and vec*mat multiplication order) $\endgroup$ – thalm Mar 31 '17 at 11:57
1
$\begingroup$

If you're working in 4-D space, assume 4 element column vectors, that $x_0,x_1$ are the end points of line $A$ and $y_0,y_1$ are the end points of line $B$. Let the transformation be

$$ y-y_0=kQ(x-x_0) $$ where Q is an orthonormal matrix that rotates $x_1-x_0$ to align with $y_1-y_0$ and $k$ is a scaling factor $$ k={|y_1-y_0| \over |x_1-x_0|}. $$ An efficient way to generate the rotation matrix $Q$ (which involves no trig functions) is given here. Alternatively, the transformation can be written as $y= Mx+b$ where $M=kQ$ and $b=y_0-Mx_0$.

If instead you're wanting an affine mapping of 3-D space, assume 3 element column vectors (omitting the $w$ elements) and generate $M$ and $b$ with these vectors. Then with affine augmentation the mapping is $$ \left[ \begin{array}{c} y\\ 1 \end{array} \right] = \left[ \begin{array}{c|c} M&b\\ {0 \,\, 0 \,\, 0}&1 \end{array} \right] \left[ \begin{array}{c} x\\ 1 \end{array} \right]. $$

In either case, the advantages include no matrix inversions and no manual choice of auxiliary points with the attendant risk of singularities. Also because the rotation method referenced does not rotate vectors outside of the subspace of $x_1-x_0$ and $y_1-y_0$, it might be argued that the mapping is minimized, i.e. objects are minimally distorted. Further, the method works in higher dimension spaces.

$\endgroup$
  • $\begingroup$ Yes, a 3-d transformation is required in my case. Translation and scaling is indeed trivial. Only the rotation is the tricky part. The above method would also work for N3 i asseme. Haven't figured out what the normal of the hyperplane in the linked answer is, just the cross product v x u? I'll try to implement it... $\endgroup$ – thalm Apr 5 '17 at 23:59
  • $\begingroup$ This might help if you are familiar with MATLAB. I should probably add this link to my answer. $\endgroup$ – T L Davis Apr 6 '17 at 0:14

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.