Transformation matrix between two line segments

Question

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?

Answer 1

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.)

Answer 2

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.