Computing CSS matrix3d transforms

I was cleaning out some old notes from my previous job and found some math scribbles for computing CSS transforms and thought I would share it. For some context, I was working on a page which had an image that looked like this:

I wanted to add an easter egg where I could use the screens of those devices to display arbitrary things. I thought it would just be a simple matter of pixel pushing with translate/rotate/scale/etc using CSS transforms but couldn't really get things to line up perfectly.

Frustrated, I started trying to solve it analytically instead. That means for any given shape, I need to solve for the perspective transform that warps an element into that shape. Once that is solved, it is easy to write a WYSIWYG helper script for outputting the CSS. Here's the final result:

See the coffeescript tab for the code. Or paste this gist into console to try it out on any page that has jQuery. You will need to change the selector to whatever element you want to add the dots to.

Using that you can drag things into whatever (convex quadrilateral) shape you want:

I ended up not using this for anything but hope someone else will find it useful!

The rest of this post will explain how to derive the equation for the transform since I remember not being able to find much about it back then. Looking at the code you will see that the core logic is just a few lines to set up and solve a system of linear equations. We will now see how to derive that system.

So let's say we have the 4 corners of the element we want to transform, $(x_i,y_i)$ where $i\in 0,1,2,3$ and we want to map each $(x_i,y_i)$ to some $(u_i,v_i)$. From the docs of matrix3d, the transform we want is a homogeneous matrix so we have to represent each point using homogeneous coordinates. In homogenous coordinates, a point $(x,y)$ is represented by $(kx,ky,k)$ for any $k\ne 0$. For example $(3,2,1)$ and $(6,4,2)$ both represent the point $(3,2)$.

Thus the transformation matrix $H$ that we want to solve for must satisfy

$$\underset{H}{\underset{}{\left(\begin{array}{ccc}{h}_0& h_1& h_2\\ h_3& h_4& h_5\\ h_6& h_7& h_8\end{array}\right)}}\left(\begin{array}{c}{x}_i\\ y_i\\ 1\end{array}\right)=k_i\left(\begin{array}{c}{u}_i\\ v_i\\ 1\end{array}\right)$$

for each $i$, where the knowns are $x_i,y_i,u_i,v_i$.

Notice that the $H$ that can satisfy this is not unique. For example you can scale $H$ by some constant and the resulting matrix will still map the points correctly (since you can also scale the $k_i$ by the same amount and still represent the same homogeneous point). So assuming $h_8\ne 0$ (see footnote^[1]), we should always be able to scale both sides until $h_8=1$, which will simplify the problem for us a little bit:

$$\left(\begin{array}{ccc}{h}_0& h_1& h_2\\ h_3& h_4& h_5\\ h_6& h_7& 1\end{array}\right)\left(\begin{array}{c}{x}_i\\ y_i\\ 1\end{array}\right)=k_i\left(\begin{array}{c}{u}_i\\ v_i\\ 1\end{array}\right)$$

Now we should try to get it into a form that we can solve. Multiplying out we get:

$$\begin{array}{cc}{x}_i{h}_0+y_i{h}_1+h_2& =k_i{u}_i\\ x_i{h}_3+y_i{h}_4+h_5& =k_i{v}_i\\ x_i{h}_6+y_i{h}_7+1& =k_i\end{array}$$

We can get rid of $k_i$ by substituting it from the third into the first two equations:

$$\begin{array}{cc}{x}_i{h}_0+y_i{h}_1+h_2& =u_i{x}_i{h}_6+u_i{y}_i{h}_7+u_i\\ x_i{h}_3+y_i{h}_4+h_5& =v_i{x}_i{h}_6+v_i{y}_i{h}_7+v_i\end{array}$$

Remember we are trying to solve for $h_i$ so we should try to separate them out:

$$\begin{array}{ccc}{x}_i{h}_0+y_i{h}_1+h_2& & -u_i{x}_i{h}_6-u_i{y}_i{h}_7=u_i\\ & x_i{h}_3+y_i{h}_4+h_5& -v_i{x}_i{h}_6-v_i{y}_i{h}_7=v_i\end{array}$$

Which in matrix notation is:

$$\left(\begin{array}{cccccccc}{x}_i& y_i& 1& 0& 0& 0& -u_i{x}_i& -u_i{y}_i\\ 0& 0& 0& x_i& y_i& 1& -v_i{x}_i& -v_i{y}_i\end{array}\right)\left(\begin{array}{c}{h}_0\\ h_1\\ h_2\\ h_3\\ h_4\\ h_5\\ h_6\\ h_7\end{array}\right)=\left(\begin{array}{c}{u}_i\\ v_i\end{array}\right)$$

Since we have 4 of these mappings we can write them like this:

$$\left(\begin{array}{cccccccc}{x}_0& y_0& 1& 0& 0& 0& -u_0{x}_0& -u_0{y}_0\\ 0& 0& 0& x_0& y_0& 1& -v_0{x}_0& -v_0{y}_0\\ x_1& y_1& 1& 0& 0& 0& -u_1{x}_1& -u_1{y}_1\\ 0& 0& 0& x_1& y_1& 1& -v_1{x}_1& -v_1{y}_1\\ x_2& y_2& 1& 0& 0& 0& -u_2{x}_2& -u_2{y}_2\\ 0& 0& 0& x_2& y_2& 1& -v_2{x}_2& -v_2{y}_2\\ x_3& y_3& 1& 0& 0& 0& -u_3{x}_3& -u_3{y}_3\\ 0& 0& 0& x_3& y_3& 1& -v_3{x}_3& -v_3{y}_3\end{array}\right)\left(\begin{array}{c}{h}_0\\ h_1\\ h_2\\ h_3\\ h_4\\ h_5\\ h_6\\ h_7\end{array}\right)=\left(\begin{array}{c}{u}_0\\ v_0\\ u_1\\ v_1\\ u_2\\ v_2\\ u_3\\ v_3\end{array}\right)$$

At this point we are done because it is in $Ah=b$ form so we can just throw this at a matrix algebra library to solve for $h$. It should spit back out the $h_i$ which will let us recover the transform we want:

$$H=\left(\begin{array}{ccc}{h}_0& h_1& h_2\\ h_3& h_4& h_5\\ h_6& h_7& h_8\end{array}\right)$$

One last wrinkle is that matrix3d actually takes in a 4 by 4 matrix rather than a 3 by 3. Since we don't care about $z$ values (because all our points are on the same plane, $z=0$) we can just make $z$ map back to itself. Like so:

$$\left(\begin{array}{cccc}{h}_0& h_1& 0& h_2\\ h_3& h_4& 0& h_5\\ 0& 0& 1& 0\\ h_6& h_7& 0& h_8\end{array}\right)$$

And that's the final matrix you use for matrix3d. Remember to specify it in column major order and also set the transform-origin to whatever you measured your points with respect to.

I didn't know what to google when I first did this so I had to derive this by hand. I have recently been reading a book on computer vision and it turns out this problem is actually a basic problem in that field (see getPerspectiveTransform in opencv) and the technique for solving this is called direct linear transformation.

EDIT (2016-11-09): As mentioned by Alexander in the comments, matrix3d used to be incorrect on Chrome under page zoom. I contributed a fix to chromium so it should be fine now.

---

1. If you want to solve this rigorously without making the assumption that $h_8\ne 0$ you can still follow the same steps outlined in this post. You will just end up with a homogeneous system $Ah=0$ instead (where $A$ is now a 8 by 9 matrix and $h$ is a 9-vector). This can be solved by doing a singular value decomposition and then finding the singular vector corresponding with a singular value of zero. Then any scalar multiple of that singular vector will be a solution. The js library I was using for math didn't support SVD very well though! ↩︎