Blog de Frédéric

To content | To menu | To search

Sunday, December 1 2013

Decomposition of 2D-transform matrices

Note: some parts of this blog post (especially the Javascript program) may be lost when exported to Planet or other feed aggregators. Please view it on the original page.

I recently took a look at the description of the CSS 2D / SVG transform matrix(a, b, c, d, e, f) on MDN and I added a concrete example showing the effect of such a transform on an SVG line, in order to make this clearer for people who are not familiar with affine transformations or matrices.

This also recalled me a small algorithm to decompose an arbitrary SVG transform into a composition of basic transforms (Scale, Rotate, Translate and Skew) that I wrote 5 years ago for the Amaya SVG editor. I translated it into Javascript and I make it available here. Feel free to copy it on MDN or anywhere else. The convention used to represent transforms as 3-by-3 matrices is the one of the SVG specification.

Live demo

Enter the CSS 2D transform you want to reduce and decompose or pick one example from the list . You can also choose between LU-like or QR-like decomposition: .


Here is the reduced CSS/SVG matrix as computed by your rendering engine ? and its matrix representation:

After simplification (and modulo rounding errors), an SVG decomposition into simple transformations is ? and it renders like this:


After simplification (and modulo rounding errors), a CSS decomposition into simple transformations is ? and it renders like this:


A matrix decomposition of the original transform is:

Mathematical Description

The decomposition algorithm is based on the classical LU and QR decompositions. First remember the SVG specification: the transform matrix(a,b,c,d,e,f) is represented by the matrix

(a c e b d f 0 0 1)

and corresponds to the affine transformation

(x y)(a c b d)(x y)+(e f)

which shows the classical factorization into a composition of a linear transformation (a c b d) and a translation (e f). Now let's focus on the matrix (a c b d) and denote Δ=adbc its determinant. We first consider the LDU decomposition. If a0, we can use it as a pivot and apply one step of Gaussian's elimination:

(1 0 b/a 1)(a c b d)=(a c 0 Δ/a)

and thus the LDU decomposition is

(a c b d)=(1 0 b/a 1)(a 0 0 Δ/a)(1 c/a 0 1)

Hence if a0, the transform matrix(a,b,c,d,e,f) can be written translate(e,f) skewY(atan(b/a)) scale(a, Δ/a) skewX(c/a). If a=0 and b0 then we have Δ=cb and we can write (this is approximately "LU with full pivoting"):

(0 c b d)=(0 1 1 0)(b d 0 c)=(cos(π/2) sin(π/2) sin(π/2) cos(π/2))(b 0 0 Δ/b)(1 d/b 0 1)

and so the transform becomes translate(e,f) rotate(90°) scale(b, Δ/b) skewX(d/b). Finally, if a=b=0, then we already have an LU decomposition and we can just write

(0 c 0 d)=(c 0 0 d)(1 1 0 1)(0 0 0 1)

and so the transform is translate(e,f) scale(c, d) skewX(45°) scale(0, 1).

As a consequence, we have proved that any transform matrix(a,b,c,d,e,f) can be decomposed into a product of simple transforms. However, the decomposition is not always what we want, for example scale(2) rotate(30°) will be decomposed into a product that involves skewX and skewY instead of preserving the nice factors.

We thus consider instead the QR decomposition. If Δ0, then by applying the Gram–Schmidt process to the columns (a b),(c d) we obtain

(a c b d)=(a/r b/r b/r a/r)(r (ac+bd)/r 0 Δ/r)=(a/r b/r b/r a/r)(r 0 0 Δ/r)(1 (ac+bd)/r 2 0 1)

where r=a 2+b 20. In that case, the transform becomes translate(e,f) rotate(sign(b) * acos(a/r)) scale(r, Δ/r) skewX(atan((a c + b d)/r^2)). In particular, a similarity transform preserves orthogonality and length ratio and so ac+bd=(a b)(c d)=0 and Δ=(a b)(c d)cos(π/2)=r 2. Hence for a similarity transform we get translate(e,f) rotate(sign(b) * acos(a/r)) scale(r) as wanted. We also note that it is enough to assume the weaker hypothesis r0 (that is a0 or b0) in the expression above and so the decomposition applies in that case too. Similarly, if we let s=c 2+d 2 and instead assume c0 or d0 we get

(a c b d)=(cos(π/2) sin(π/2) sin(π/2) cos(π/2))(c/s d/s d/s c/s)(Δ/s 0 0 s)(1 0 (ac+bd)/s 2 1)

Hence in that case the transform is translate(e,f) rotate(90° - sign(d) * acos(-c/s)) scale(Delta/s, s) skewY(atan((a c + b d)/s^2)). Finally if a=b=c=d=0, then the transform is just scale(0,0).

The decomposition algorithms are now easy to write. We note that none of them gives the best result in all the cases (compare for example how they factor Rotate2 and Skew1). Also, for completeness we have included the noninvertible transforms in our study (that is Δ=0) but in practice they are not really useful (try NonInvertible).

Friday, January 11 2013

MathML in Chrome, a couple of demos and some perspectives...

For those who missed the news, Google Chrome 24 has recently been released with native MathML support. I'd like to thank Dave Barton again for his efforts during the past year, that have allowed to make this happen. Obviously, some people may ironize on how long it took for Google to make this happen (Mozilla MathML project started in 1999) or criticize the bad rendering quality. However the MathML folks, aware of the history of the language in browsers, will tend to be more tolerant and appreciate this important step towards MathML adoption. After all, this now means that among the most popular browsers, Firefox, Safari and Chrome have MathML support and Opera a basic CSS-based implementation. This also means that about three people out of four will be able to read pages with MathML without the need of any third-party rendering engine.

After some testing, I think the Webkit MathML support is now good enough to be used on my Website. There are a few annoyances with stretchy characters or positioning, but in general the formulas are readable. Hence in order to encourage the use of MathML and let people report bugs upstream and hopefully help to fix them, I decided to rely on the native MathML support for Webkit-based browsers. I'll still keep MathJax for Internet Explorer (when MathPlayer is not installed) and Opera.

I had the chance to meet Dave Barton when I was at the Silicon Valley last October for the GSoC mentor summit. We could exchange our views on the MathML implementations in browsers and discuss the perspectives for the future of MathML. The history of MathML in Webkit is actually quite similar to Gecko's one: one volunteer Alex Milowski decided to write the initial implementation. This idea attracted more volunteers who joined the effort and helped to add new features and to conduct the project. Dave told me that the initial Webkit implementation did not pass the Google's security review and that's why MathML was not enabled in Chrome. It was actually quite surprising that Apple decided to enable it in Safari and in particular all Apple's mobile products. Dave's main achievement has been to fix all these security bugs so that MathML could finally appear in Chrome.

One of the idea I share with Dave is how important it is to have native MathML support in browsers, rather than to delegate the rendering to Javascript libraries like MathJax or browser plug-in like MathPlayer. That's always a bit sad to see that third-party tools are necessary to improve the native browser support of a language that is sometimes considered a core XML language for the Web together with XHTML and SVG. Not only native support is faster but also it integrates better in the browser environment: zooming text, using links, applying CSS style, mixing with SVG diagrams, doing dynamic updates with e.g. Javascript etc all of the features Web users are familiar with are immediately available. In order to illustrate this concretely, here is a couple of demos. Some of them are inspired from the Mozilla's MathML demo pages, recently moved to MDN. By the way, the famous MathML torture page is now here. Also, try this test page to quickly determine whether you need to install additional fonts.

MathML with CSS text-shadow & transform properties, href & dir attributes as well as Javascript events

det ( 1 2 3 4 5 6 7 8 9 ) = 45 + 84 + 96 ( 105 + 48 + 72 ) = 0 محدد ( ١‎ ٢ ٣ ٤ ٥ ٦ ٧‎ ٨ ٩ ) = ٤٥ + ٨٤ + ٩٦ ( ١‎٠٥ + ٤٨ + ٧‎٢ ) = ٠

HTML and animated SVG inside MathML tokens

tr ( ) n = = 0 π 2 θ θ

MathML inside animated SVG (via the <foreignObject> element):

n = 0 + α n n ! exp(α)

Note that although Dave was focused on improving MathML, the language naturally integrates with the rest of Webkit's technologies and almost all the demos above work as expected, without any additional efforts. Actually, Gecko's MathML support relies less on the CSS layout engine than Webkit does and this has been a recurrent source of bugs. For example in the first demo, the text-shadow property is not applied to some operators (bug 827039) while it is in Webkit.

In my opinion, one of the problem with MathML is that the browser vendors never really shown a lot of interest in this language and the standardization and implementation efforts were mainly lead and funded by organizations from the publishing industry or by volunteer contributors. As the MathML WG members keep repeating, they would love to get more feedback from the browser developers. This is quite a problem for a language that has among the main goal the publication of mathematics on the Web. This leads for example to MathML features (some of them are now deprecated) duplicating CSS properties or to the <mstyle> element which has most of its attributes unused and do similar things as CSS inheritance in an incompatible way. As a consequence, it was difficult to implement all MathML features properly in Gecko and this is the source of many bugs like the one I mention in the previous paragraph.

Hopefully, the new MathML support in Chrome will bring more interest to MathML from contributors or Web companies. Dave told me that Google could hire a full-time engineer to work on MathML. Apparently, this is mostly because of demands from companies working on Webkit-based mobile devices or involved in EPUB. Although I don't have the same impression from Mozilla Corporation at the moment, I'm confident that with the upcoming FirefoxOS release, things might change a bit.

Finally I also expect that we, at MathJax, will continue to accompany the MathML implementations in browsers. One of the ideas I proposed to the team was to let MathJax select the output mode according to the MathML features supported by the browser. Hence the native MathML support could be used if the page contains only basic mathematics while MathJax's rendering engine will be used when more advanced mathematical constructions are involved. Another goal to achieve will be to make MathJax the default rendering in Wikipedia, which will be much better than the current raster image approach and will allow the users to switch to their browser's MathML support if they wish...

Saturday, July 24 2010

Using Mozilla to print a scientific report based on Web formats

So I'm finally done with my Master's Project in Quantum Computing at Århus. My final report on The Hidden Subgroup Problem is now available in XHTML and pdf formats. There are also the slides I've made for the oral defense, although as always it is not really useful without the comments. This time, I've used the W3C's slidy tool and so my work is 100% based on Web formats :-)

The Hidden Subgroup Problem still remains difficult with our current knowledge, but I've very appreciated thinking on this challenging topic and I hope my work will help research in this area. As an advocate of the Web as a publishing medium for scientists, I've also found a meta-interest in seeing whether it is possible to use Web formats to produce documents readable both on the screen and on the paper (and in this latter case with the same quality as the more traditional methods). One way to do that is to use TeX-like documents and export them in Web/Printing formats using tools such that Tex4ht or GELLMU. Since my personal preference is to write Web contents by a hybrid method (mixing WYSIWYG and simple-syntax-parsers), I've rather considered how one can print these Web formats. One tool to do that is Prince but I'm not sure it is that good with SVG/MathML (there were some issues last time I tried it). Hence I've preferred to use a free layout engine and thus printed my report with Gecko :-).

One of the difficulty is to handle numbering (pages, sections, formulas, theorems...) and the corresponding references (HTML links or page numbers) either in the table of contents or inside the body of the report itself. Moreover, the report has to be split into several small pieces for otherwise it is too large to be edited easily (in my case, 1.1Mb on a single XHTML page for an amount of 99 pages). Hence at the beginning I had to quickly write once and for all an automated system. I'm not really prude of it - it is truly an usine à gaz involving CSS counters, Flex lexical analyzer and a command line print extension for Firefox - but at least it works almost as I expect. Ideally, it should be possible to print each piece separately before grouping them into one single pdf document. However, because of the choice of CSS counters and the lack of control on page numbering in Mozilla I could only print the whole large XHTML document. This was really not convenient and was one of the main annoying issue. The other one being that there is no access to the page numbers and so for the table of contents, I had to write them manually :-(. It seems that a way to overcome the page number issues would be to implement some CSS rules for printing although I don't know if it helps working on separate pieces.

The other problems are various bugs in Gecko. Thanks to the recent improvements in MathML (related to stretchy and fonts) , the mathematical formulas are now displayed with a good quality, or at least one of which I'm satisfied. One issue is the incorrect computation of dimension in mtable which is slightly visible for some split equations. I've also discovered a wrong thickness of bars which seems to be the only difference between print and screen renderings. However, I could workaround it and Karl gave me a hint that would hopefully allow to fix the bug. There are still some annoying bugs with linebreaking within mathematical expressions and around them. For the former I can avoid the problem by adding <mrow/>'s but the latter makes particularly weird effects. Typically, when some comma or period is placed just after an inline formula, a linebreak may happen and move the punctuation symbol to the beginning of the next line... Regarding quantum circuits and other schemas, the SVG code I use is very elementary. Hence I don't have any complaint to formulate, even if I'm among those who are expecting the possibility to use SVG images in the standard <img/> tag. Finally, I have some mysterious bugs with HTML tables printed on several pages and more issues with CSS page breaking, requiring me to do some small manual tweaking at two or three places.

As a conclusion, using Web formats to print a scientific report is not yet so easy. However, I'm quite satisfied of the result and I expect the issues above to be fixed in the near future...

Sunday, May 2 2010

Hacking Dotclear 2 for writing XHTML+MathML+SVG

Of course, the first thing I've checked after setting this blog is whether it is possible to have a XHTML+MathML+SVG page in dotclear. As indicated in the Mozilla MathML Project page, one has to:

  1. serve the page as application/xhtml+xml.

    This is simply done by editing the value of parameter $content_type in the function serveDocument of the file dotclear/inc/public/lib.urlhandlers.php.

  2. write well-formed XML document.

    Apparently, dotclear is good enough to do that. However, its editor does not seem to have any option for producing MathML or SVG. Personally, I don't use the wiki syntax and prefer to write the XHTML page myself with the tools I'm used to. As a consequence, this is not really a problem for me.

    It is also a good idea to write a valid XML document. By default, dotclear uses the doctype XHTML 1.0 Strict so I had to modify the files themes/name_of_your_theme/tpl/*.html to set XHTML+MathML+SVG instead.

Once this simple changes are made, you can insert MathML formulas such that this expression of a general Quantum Fourier Transform over a finite group: g G , F G g = 1 G ρ G ̂ d ρ i , j = 1 d ρ ρ i j ( g ) ρ i j

or SVG images such that this quantum circuit used in the famous Shor's algorithm:

0 n |0^n⟩ 0 n |0^n⟩ U f U_f F N F_N F N F_N


--update 30/01/2011: you can find my patch for Dotclear 2.2