While working through a paper concerning computer generated holograms I have come across a affine transform of a triangle. Since I am not that familiar with affine transforms I do not exactly understand how they obtained the final form of the transform.
Suppose we have a triangle with three non-collinear vertices at $(s_1,t_1)$, $(s_2,t_2)$ and $(s_3,t_3)$. Furthermore I want to transform these vertices to a basic triangle with the vertices $(0,0)$,$(0,1)$ and $(1,1)$ by using a affine transform of the form
$$\begin{bmatrix}s\\t\end{bmatrix}~=~\begin{bmatrix}a_{11}&a_{12}\\a_{21}&a_{22}\end{bmatrix}\begin{bmatrix}x\\y\end{bmatrix}+\begin{bmatrix}a_{31}\\a_{32}\end{bmatrix}$$
Form hereon I am struggling with determining the coefficients $a_{ij}$. Setting up the pairwise correspondence $(0,0)\to(s_1,t_1)$,$(1,0)\to(s_2,t_2)$ and $(1,1)\to(s_3,t_3)$ and solving the system of six equations yields to
$$\begin{bmatrix}s\\t\end{bmatrix}~=~\begin{bmatrix}s_2-s_1&s_3-s_2-s_1\\t_2-t_1&t_3-t_2-t_1\end{bmatrix}\begin{bmatrix}x\\y\end{bmatrix}+\begin{bmatrix}s_1\\t_1\end{bmatrix}$$
This formula looks ridiculously simple compared to the final form given within the paper
$$\begin{bmatrix}s\\t\end{bmatrix}~=~\frac1{J}\begin{bmatrix}(t_3-t_2)&(s_2-s_3)\\(t_1-t_2)&(s_2-s_1)\end{bmatrix}\begin{bmatrix}x\\y\end{bmatrix}+\frac1{J}\begin{bmatrix}-((t_3-t_2)s_1+(s_2-s_3)t_1)\\-((t_1-t_2)s_1+(s_2-s_1)t_1)\end{bmatrix}$$
with $J$ the defined as $a_{11}a_{22}-a_{12}a_{21}$.
To be honest, I have no idea to arrive at this transform or how to reshape my solution to look alike the "right" one. Further I do not exactly know how I can compute something at all with this equation since $J$ is defined in terms of the original coefficients $a_{ij}$ and so for example $a_{11}$ would be given by
$$a_{11}=\frac{t_3-t_2}{a_{11}a_{22}-a_{12}a_{21}}$$
which is kind of recursive. Hence I have got for equations of this type and four variables it would be possible to determine each coefficient individually but I do not think that this is the right way to approach to this.
Could someone explain to me where I did made a mistake that leads to the wrong solution or how to transform my own attempt to look alike the one given in the article. I would appreciate if someone could show me how to set up the final formula starting by the general defintion of an affine transform and the given pairwise correspondences.
Thanks in advance!
Best Answer
Your guess as to what went wrong is correct: you’ve computed the transformation that maps the basic triangle onto the arbitrary one—the inverse of the map that’s needed.† Try plugging in any of the vertices into your formula to see this: you won’t get $(0,0)$, $(1,0)$ or $(1,1)$. The transformation in the paper goes in the correct direction. In fact, it’s precisely the inverse of yours. To get from your solution to the correct one, solve the two equations that it represents for $x$ and $y$. (Their roles are reversed in the two formulas.) Alternatively, start from scratch with the correct direction: From $(s1,t1)\to(0,0)$ you get $$s_1 a_{11}+t_1 a_{12}+a_{31} = 0 \\ s_1 a_{21} + t_1 a_{22} + a_{32} = 0$$ and so on for the other three point pairs. Solve the resulting system of 6 equations as you did before.
As for the $J$ in that formula, it’s the determinant of the matrix in your formula, which appears naturally when that matrix is inverted. The $a$’s in the definition of $J$ are meant to be elements of a generic $2\times2$ matrix. In this particular instance, they’re the elements of the matrix in your formula, i.e., $a_{11}=s_2-s_1$ and so on, giving $$J = (s_2-s_1)(t_3-t_2-t_1)-(t_2-t_1)(s_3-s_2-s_1).$$
If you’re familiar with matrices, it’s fairly easy to invert your formula directly. That transformation consists of a linear transformation followed by a translation, i.e., it has the form $\mathbf p = M\mathbf x+\mathbf p_1$, so to invert it you undo each of those components in reverse order: $\mathbf x = M^{-1}(\mathbf p-\mathbf p_1) = M^{-1}\mathbf p-M^{-1}\mathbf p_1$ Applying this to your transformation after swapping $(x,y)$ and $(s,t)$, we translate back: $$\begin{bmatrix}x\\y\end{bmatrix} - \begin{bmatrix}s_1\\t_1\end{bmatrix} = \begin{bmatrix}s_2-s_1&s_3-s_2\\t_2-t_1&t_3-t_2\end{bmatrix}\begin{bmatrix}s\\t\end{bmatrix}$$ then invert the linear part of the transformation $$\begin{bmatrix}s_2-s_1&s_3-s_2\\t_2-t_1&t_3-t_2\end{bmatrix}^{-1} \left( \begin{bmatrix}x\\y\end{bmatrix} - \begin{bmatrix}s_1\\t_1\end{bmatrix} \right) = \begin{bmatrix}s\\t\end{bmatrix}.$$ Now invert the matrix and distribute the multiplication: $$\begin{bmatrix}s\\t\end{bmatrix} = \frac1J\begin{bmatrix} (t_3-t_2) & (s_2-s_3) \\ (t_1-t_2) & (s_2-s_1) \end{bmatrix} \begin{bmatrix}x\\y\end{bmatrix} - \frac1J\begin{bmatrix} (t_3-t_2)s_1 + (s_2-s_3)t_1 \\ (t_1-t_2)s_1 + (s_2-s_1)t_1 \end{bmatrix},$$ with $J$ as above.
If you use homogeneous coordinates, then there’s a conceptually simple way to construct the required transformation. Recalling that the columns of a transformation matrix are the images of the basis vectors, we can see that the matrix $$\begin{bmatrix} x_1 & x_2 & x_3 \\ y_1 & y_2 & y_3 \\ 1&1&1\end{bmatrix}$$ maps the standard basis onto the points $(x_1,y_1)$, $(x_2,y_2)$ and $(x_3,y_3)$. So, to map the given triangle onto the basic one, we can first map its vertices onto the standard basis, then map that onto the standard triangle. The resulting transformation is given by the matrix product $$\begin{bmatrix}0&1&1\\0&0&1\\1&1&1\end{bmatrix} \begin{bmatrix}s_1&s_2&s_3\\t_1&t_2&t_3\\1&1&1\end{bmatrix}^{-1}.$$ If you do this correctly, the last row of the resulting matrix will be $[0,0,1]$, which tells you that you have an affine transformation as required. You can use this same method to construct the affine transformation between any two triangles: just put the appropriate destination vertex coordinates into the left-hand matrix.
† Actually, there’s a mistake somewhere in your calculations because your transformation doesn’t map $(1,1)$ to $(s_3,t_3)$, but that’s not the important thing here.