97
$\begingroup$

I'm working on a project using Chrome - JS and Webkit 3D CSS3 transform matrix.

The final goal is to create a tool for artistic projects using projectors and animation - somewhat far away from using maths...

I'm using a projector to project several squares over several shapes - as seen in the picture.

What I would like to do is for the user to draw 4 points on the screen (2D x and y) and from there extract a matrix object that I could apply to a regular DIV element of a dimension of 100px by 100px.

By finding scaleX, scaleY, rotation, rotationX, rotationZ and probably some perspective that I could apply to the div to relatively match the surface.

I'm not really familiar with geometry beyond sin and cos, and 3D in general and don't even know if that is something doable. If anyone could help me get started or point me in the right direction, I would greatly appreciate.

Here is an animated gif (click to enlarge), hoping it makes it more clear to understand.

http://www.michael-iriarte.com/code/duncan.gif

$\endgroup$
10
  • $\begingroup$ As far as I can tell, you can do this with a transformation matrix only if the 4 points form a parallelogram. Are we allowed to make that assumption? $\endgroup$ Feb 7, 2013 at 1:47
  • $\begingroup$ I'm not sure what I'm gonna say is correct but wouldn't perspective(depth) break that assumption? $\endgroup$
    – mika
    Feb 7, 2013 at 1:48
  • 2
    $\begingroup$ @PeterOlson The transformation matrix is acting on 4D homogeneous coordinates (real projective space), so perspective transforms should be possible, no? $\endgroup$
    – Erick Wong
    Feb 7, 2013 at 2:04
  • 1
    $\begingroup$ @mika If it's possible to directly modify the matrix3d property, it might be easier to calculate the matrix than to extract the individual scaleX, scaleY, etc. Would this be acceptable? $\endgroup$
    – Erick Wong
    Feb 7, 2013 at 2:08
  • 1
    $\begingroup$ For anyone else finding this years later, I tried many different JS libraries before finally finding one that worked: npmjs.com/package/simple-homography (yes, with 0 weekly downloads) $\endgroup$ Aug 1 at 23:32

4 Answers 4

138
$\begingroup$

Computing a projective transformation

A projective transformation of the (projective) plane is uniquely defined by four projected points, unless three of them are collinear. Here is how you can obtain the $3\times 3$ transformation matrix of the projective transformation.

Step 1: Starting with the 4 positions in the source image, named $(x_1,y_1)$ through $(x_4,y_4)$, you solve the following system of linear equations:

$$\begin{pmatrix} x_1 & x_2 & x_3 \\ y_1 & y_2 & y_3 \\ 1 & 1 & 1 \end{pmatrix}\cdot \begin{pmatrix}\lambda\\\mu\\\tau\end{pmatrix}= \begin{pmatrix}x_4\\y_4\\1\end{pmatrix}$$

The colums form homogenous coordinates: one dimension more, created by adding a $1$ as the last entry. In subsequent steps, multiples of these vectors will be used to denote the same points. See the last step for an example of how to turn these back into two-dimensional coordinates.

Step 2: Scale the columns by the coefficients you just computed:

$$A=\left(\begin{array}{lll} \lambda\cdot x_1 & \mu\cdot x_2 & \tau\cdot x_3 \\ \lambda\cdot y_1 & \mu\cdot y_2 & \tau\cdot y_3 \\ \lambda & \mu & \tau \end{array}\right)$$

This matrix will map $(1,0,0)$ to a multiple of $(x_1,y_1,1)$, $(0,1,0)$ to a multiple of $(x_2,y_2,1)$, $(0,0,1)$ to a multiple of $(x_3,y_3,1)$ and $(1,1,1)$ to $(x_4,y_4,1)$. So it will map these four special vectors (called basis vectors in subsequent explanations) to the specified positions in the image.

Step 3: Repeat steps 1 and 2 for the corresponding positions in the destination image, in order to obtain a second matrix called $B$.

This is a map from basis vectors to destination positions.

Step 4: Invert $A$ to obtain $A^{-1}$ (or use the adjugate as discussed below).

$A$ maps from basis vectors to the source positions, so the inverse matrix maps in the reverse direction.

Step 5: Compute the combined Matrix $C = B\cdot A^{-1}$.

$A^{-1}$ maps from source positions to basis vectors, while $B$ maps from there to destination positions. So the combination maps source positions to destination positions. This is the matrix of the transformation you were requesting.

Step 6: To map a location $(x,y)$ from the source image to its corresponding location in the destination image, compute the product

$$\begin{pmatrix}x'\\y'\\z'\end{pmatrix} = C\cdot\begin{pmatrix}x\\y\\1\end{pmatrix}$$

These are the homogenous coordinates of your transformed point.

Step 7: Compute the position in the destination image like this:

\begin{align*} x'' &= \frac{x'}{z'} \\ y'' &= \frac{y'}{z'} \end{align*}

This is called dehomogenization of the coordinate vector.

How to use this projective transformation with CSS

In general such a transformation will not be an affine transformation, so you cannot express this in terms of affine transformations like scaling, rotating and shearing, since these cannot express perspectivity. You might however try to simply set the first two entries of the last row to zero, so you get an affine transformation which might be close enough to your desired transformation.

If on the other hand you can use a matrix3d transformation, then you can take the 2D projective transformation matrix $C$ computed as described above, and use its entries to build a 3D projective transformation matrix like this:

$$\begin{pmatrix} C_{1,1} & C_{1,2} & 0 & C_{1,3} \\ C_{2,1} & C_{2,2} & 0 & C_{2,3} \\ 0 & 0 & 1 & 0 \\ C_{3,1} & C_{3,2} & 0 & C_{3,3} \end{pmatrix}$$

This transformation will transform $x$ and $y$ coordinate as above, but leave the $z$ coordinates of the homogenous coordinate vectors alone. Dehomogenization might still change the value of the $z$ coordinate in space, but as you don't really care about these, this should be good enough.

I've written a proof-of-concept implementation. The user interface is pretty crude, but the math works well enough. The implementation there uses the adjugate matrix instead of the inverse, both in solving the linear equations in step 1 and for the reverse transform in step 4. The result differs only by a scalar factor, which is irrelevant for homogenous coordinates. The benefit is that this avoids computing a bunch of determinants and performing a bunch of divisions.

If you wanted to, you could play the same game for five points in 3D space, in order to compute the full spatial projective transformation matrix. But that only makes sense if you actually have depth, sice no four of the five points may be coplanar.

$\endgroup$
21
  • 4
    $\begingroup$ This answer is based on a similar post on SO, although the math formating here is a big bonus. This Math Stackexchange post shows another interesting application of determining transformation matrices in this way. It really is a powerful operation. $\endgroup$
    – MvG
    Mar 23, 2013 at 19:45
  • 2
    $\begingroup$ Wow this is really working nicely! Thanks so much for the help, this is really great! I will keep you posted on my project progress. Thanks again for your time! $\endgroup$
    – mika
    Mar 25, 2013 at 17:45
  • 1
    $\begingroup$ Very, very helpful explanation. I got stuck for a bit in my implementation, because I didn't see the transform-origin: 0 0; in the css, so things were weird. But it works now! flickr.com/photos/forresto/8759741112 $\endgroup$
    – forresto
    May 20, 2013 at 22:06
  • 6
    $\begingroup$ I think this is one of the best answers I've encountered on StackExchange. The math formatting and the explanations are priceless, worked as a charm. Thanks a lot! $\endgroup$
    – MeLight
    Oct 18, 2013 at 22:53
  • 2
    $\begingroup$ I just learned that robjohn wrote a similar answer prior to the above post, and although I prefer my own answer, some readers might gain insight from comparing it with that answer as well. $\endgroup$
    – MvG
    Apr 5, 2014 at 19:47
12
+100
$\begingroup$

I am fairly certain there is no closed-form general solution for this problem, which leaves you with numerical approximations. One simplifying technique would be to eliminate perspective from your problem and imagine the four points your visitors draw to be the shadow cast by a light shining from infinity. You could then, basically, guess and check, using guesses of whatever sophistication you desire.

I've written a really rough demo of what I'm talking about containing some unsophisticated assumptions. Because it removes perspective, it doesn't precisely solve your question, but see if the results might be satisfactory.

The user enters four points onto an HTML canvas with his or her mouse. The script then tries to iteratively converge on a CSS transform of a square to match the shape.

I've linked to some sample output. On the left, the yellow quadrilateral is the original hand drawing, the greys are the successive approximations, and the red is the final estimate. On the right, you see a square div styled with the CSS transformation.

Script output screenshot

An obvious upgrade would be a better convergence function, perhaps using Newton's Method or something of its ilk, but I haven't taken the time to figure out the partial differential equations this would require.

(The code runs in-browser in synchronous Javascript, and locks the browser on my computer for between 5 and 20 seconds on average, so be careful.)

$\endgroup$
2
  • $\begingroup$ Wow i tested your demo on real projections and it really blew my mind! Unfortunately the parallelogram approach theoretically doesn't meet my objective at 100%. it is a really convincing answer but I'm a believer and still hope someone can come up with the perfect approach. Thank you so much for digging into it! $\endgroup$
    – mika
    Feb 9, 2013 at 4:57
  • 6
    $\begingroup$ There is a closed form, if you can use projective transformations. In case you are interested, see my answer. $\endgroup$
    – MvG
    Mar 23, 2013 at 22:22
7
$\begingroup$

This isn't my solution, just a link to what, for me, was the perfect solution:

http://franklinta.com/2014/09/08/computing-css-matrix3d-transforms/

The way it's made, you can paste the JS into the page you're working on and line up the points exactly how you want, then copy the CSS from the inspector.

As far as I can tell (which is only superficially), this does the same thing as MvG's JS Fiddle, but it's packaged in a way that was more useful to me. HTH!

$\endgroup$
2
  • 1
    $\begingroup$ This is perfect for a quick prototype and then the first answer for explanations. Thank you so much for this link $\endgroup$ Jan 22, 2020 at 17:23
  • $\begingroup$ If I'm not mistaken, the method on that web page isn't as good as @MvG 's, since it constrains one of the coefficients to be 1; it will blow up if that coefficient is in fact 0 or close to it. MvG 's method doesn't seem to suffer from that problem, as far as I can see. $\endgroup$
    – Don Hatch
    Jun 21 at 11:32
1
$\begingroup$

I could be wrong, but I believe the transform should be a projective transformation of the plane; i.e. a Möbius transform.

Any Möbius transform is completely determined by three points; the wikipedia link should give you enough information to obtain the transform.

Since you are asking the user to provide four points, it is possible that he could provide an impossible set of points. Ideally, the distortion is minor, and a reasonable strategy might be to compute all four possible transforms (there are four ways of selecting corners) and averaging them.

Another possibility is to try and correct the four endpoints, finding a small perturbation that has cross ratio 2, which (if I've calculated correctly) is the cross ratio of the default square with vertices 0, 1, 1+i, i. (All transformations of squares should have the same cross ratio!) Then use the transformation corresponding to the corrected endpoints.

Or you could only allow them to select 3 endpoints and fill in the fourth endpoint for them, and allow the user to adjust the corners until he's happy.

$\endgroup$
1
  • 4
    $\begingroup$ A Möbius transformation is a projective transformation of $\mathbb C\mathrm P^1$, not $\mathbb R\mathrm P^2$. Or in other words, Möbius transformations may map lines to circles and vice versa, whereas projective transformations of the real plane will preserve lines as lines, but may map circles to other conics. $\endgroup$
    – MvG
    Mar 23, 2013 at 22:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .