I’ve been playing around with using 2D transformations to enable 3D effects, even (or especially) in browsers without support for the latter. There have been a few examples of this kind—putting text and images and even video on isometric cubes, for the most part—but I think we, as a community, have not gone far enough in the pursuit of the hideous. I’m here to help.

This demo does border on abuse of the format—probably better done with SVG or not at all—but as an outputted, interactive image it (vaguely) suggests something important. Before a particular problem, before identifying the needs of our users, before creating elegant interfaces, and before good visual design, I believe we need to ensure the delivery of that first promise of techno-utopianism: putting whatever the hell we want to on the screen.

To be perfectly clear, all the things I listed first are far more important than that ability, but we shouldn’t be limited before we begin. Limits inspire creativity, but they also circumscribe what is possible; I want to be in charge of that. If I want a giant blinking triangle covering half my text, then by golly, there should be a giant blinking triangle there. Just because something shouldn’t be done doesn’t mean it shouldn’t be doable.

Demo: Isometry

Interaction

Browser interaction techniques have historically been so poor that we are still astounded when the simplest of interfaces match some intuitive sense of physicality. Luckily, things are changing. There is an increasing belief in a kind of manifest destiny for the web, the idea that we can make any kind of interface that we set our mind to, but we’re just now getting around to it (we might also have been waiting for the right local storage api).

Deluded or not, I’m of this mind as well, and I was interested in experimenting with the mechanics of interacting with three-dimensional objects, specifically through the web browser. All interfaces are abstractions and therefore lossy (surjective, if you’re into that), but the 2D interface to a 3D scene ends up serving two masters, since the whole point is to mimic a physical interaction through a mouse and keyboard. A qualitatively-optimized mapping still needs to be made between data and interface, something as expressive as possible within the parameters available, but here it has to not only convince us that those degrees of freedom are sufficient for the task at hand, it has to simultaneously match our sense of the way things actually move in the real world. Otherwise: frustration.

Which is all a long way of saying that most 3D interfaces are terrible. If it’s just decoration, fine, but if you’re trying to perfectly map a physical task to the mouse, you’re doing computers wrong, and if mouse movements relate inconsistently to what’s happening on screen, your users hate you.

This demo just plays around with some ideas—there is no real task to accomplish—but it’s easy to see where it is not entirely successful. However, meaningful criticism would require a program that was meant to do something, which this one wasn’t. I will say, though, that the technical side of things is easier than you might think. So embrace our collective destiny, don’t be afraid of creating the next blink tag or flash banner ad, and stop waiting for the perfect version of local storage.

Also, those native-app developers told me you guys look like dorks, so you’d better get on that.

Projection

While waiting for the WebGL promised land to arrive, I wanted a reliable way of making 3D transformations work at interactive rates across all the major browsers, even accounting for those aging software renderers. The process turns out to be pretty simple and without any real hacks; every frame created dynamically here can be recreated statically with some plain, vendor-prefixed CSS. Now, “real hacks” is relative—especially depending on how you feel about “-ms-filter”—and I don’t explicitly support IE versions prior to 8, but it’s a start.

The key is the orthographic projection, one way of projecting a three-dimensional scene onto a two-dimensional surface (in this case, the screen). Since orthographic projections map 3D parallel lines to 2D parallel lines, objects do not shrink as they recede from a viewer. This can cause a somewhat unsettling effect—a pretty cool testament to the sophistication of our visual system—but is also one more tool to be exploited by artists. In a nutshell, the animation system keeps track of the 3D transformations per element, then does a simple projection before applying it to that element’s style property. I’ll post more on the math and implementation details shortly.

Known Issues

I want to make the core feature set work across browsers as reliably as possible. If you have an issue, please let me know about it and the platform it happened on.

[IE]

• Internet Explorer’s matrix filter has proven surprisingly stable and performant, but this demo appears to be pushing it to its limit. Transformations nested three or four deep, especially on elements with untransformed siblings, cause background colors to bleed through in some circumstances. This is not an issue in IE9 Preview 2.

  

• Unfortunately, the nested transform necessary for the recursive side is ignored altogether. This is not corrected in IE9. The transform is there, but unperformed, even though transforms nested within that transform are executed correctly. I’m hopeful that a knock in the right place will get it working.
• Like most of us, IE9 Preview 3 isn’t a big fan of filters and won’t run this. If filters are removed from IE9 permanently (when in standards mode) and CSS3 transforms are not added, I don’t believe there is a replacement.

[Embedacube™]

• The Embedacube™ feature saves the state of the cube just before you press the button; press it again to save the state after the first press (but before the second press).
• An Embedacube™ cube currently only works in the browser version (Firefox, IE, etc) in which it was created.
• Some style information is currently lost in the Embedacube™ process.

[Webkit]

• Safari on the Mac and Chromium on Windows (with startup flag) both support hardware accelerated 3D transforms. Unfortunately, this demo interacted with -webkit-transform-style and the subsequent stacking order differently than I anticipated, so I’ve forced them back to 2D for now. Performance suffers a bit, but their software renderer is pretty good, especially for such a simple scene. I am investigating how deeply I have to change things in order to get accelerated 3D transforms working properly, and hope to have the change pushed soon.
• CSS transitions are another feature currently unused that should map well to this demo and provide a good performance boost.

[Mobile]

• In a few tests, mobile performance on this page has been good. However, my testing equipment is limited, so touch events, for instance, are not currently acted upon.

It’s so bad

Once again, I needed to write a simple demo for a module, something obvious in effect, intent, and execution. I’m usually terrible at these—hemming and hawing over details irrelevant to the point of a piece—so I gave myself two hours to come up with something and code it. I didn’t quite make it (there was some hemming and hawing), but it was close.

I don’t remember exactly how some initial thoughts on nested spinning boxes lead to this, but I think it turned out pretty well, if a little crude. Conveniently, it ended up using the major parts of the library that most need demonstrating—creation, element transformation, and the use of standalone transforms—which I’ll talk about below. There was also only a single browser workaround needed: current versions of IE don’t support border-radius, so the shadows needed some slight repositioning.

But I’ll get to all that. Go look. Firefox ends up winning for rendering quality (and was used for most of these screenshots), but all the browsers do pretty well keeping up:

Demo: Transforming Trees

If it doesn’t really strike a chord, try running this in the background at the same time. Hey, I never said it was going to change someone’s life or scrub oil off the wetlands. Two (and a half) hours, remember?

Overview

The source for the demo is over in the usual place, but I’ll go through the important parts here, concentrating on the actual application of transforms.

Most everything happens in TreesWidget.java, except for this line in the gwt.xml module file:

<inherits name="gwt.ns.transformedelement.TransformedElement"/>

The project also needs to inherit from the Transforms module, but in this case TransformedElement has already done so.

Execution is divided up into initialization and an animation loop. The TransformedElements are created in the Widget’s constructor. In order to animate transforms efficiently in Internet Explorer, several data points about an element need to persist across frames, and so are kept in a TransformedElement object. See these posts for more about how this works. For a static transformation, the object can be discarded after creation; the transform will persist like any other style.

An update() method is then called from a timer, updating as often as it can.

Trees: TransformedElement

TreesWidget initializes the two tree DIV elements by wrapping them with TransformedElement objects:

bigTree = TransformedElement.wrap(bigTreeDiv);
littleTree = TransformedElement.wrap(littleTreeDiv);

As with all dancing trees, movement starts at the trunk, so the transform origin should be located there. The helpful folks writing and implementing the CSS3 transform spec have seen fit to give a built-in property to position the origin for just such a purpose. In this case, the origins need to remain in the middle of each tree, but moved to their base:

bigTree.setOriginPercentage(50, 100);
littleTree.setOriginPercentage(50, 100);

That’s all the initialization the trees need. In the animation loop, the trees sway back and forth while simultaneously crouching down and stretching up (is there a good antonym for crouching?). The parameters for each cycle are calculated and, since they are not cumulative, applied to the tree after its transform is reset to the identity.

public void update() {
  // calculate scaleX, scaleY, bigSkewAngle...
 
  bigTree.setToIdentityTransform();
  bigTree.scale(scaleX, scaleY);
  bigTree.skewX(bigSkewAngle);
 
  // animate littleTree
  // ...
}

That’s it.

Shadows: TransformedElement + Standalone Transform

A shadow can go a long way toward tying objects to each other and the background, giving a sense of physicality where there is none. Shadows often don’t have to be anywhere near realistic to fill that role, but in this case the limits of border-radius prevented me from creating simple blob shadows. Since the shadows were squished, the radii allowed by the browser were rather small, and so the shadows were less blobular and more rectangular.

Nothing a little over-engineering can’t solve!

The shadows used are actually exact style copies of the trees (except that, since all browsers that currently support browser-radius do so with obvious rendering cracks, expanded heights and widths are used in lieu of borders). The shadows are initialized just like the trees, since they too will transform about the trees’ bases.

bigShadow = TransformedElement.wrap(bigShadowDiv);
littleShadow = TransformedElement.wrap(littleShadowDiv);
 
bigShadow.setOriginPercentage(50, 100);
littleShadow.setOriginPercentage(50, 100);

Looks a bit like box-shadow.

Now for the trickery. We want a shadow at the base of the trees, coming toward the viewer at a slight angle, and squished to fit in the space available at the bottom (short because our trees do their best dancing at mid-day). That’s the more literal interpretation of the transform that is about to be applied. However—if you’re into this sort of thing—the transform can also be thought of as projecting the shape of the tree toward the viewer onto a slightly tilted plane.

The two descriptions are equivalent. I usually take any excuse I can get to play around with matrices for an afternoon, but in this case I only cared about the general effect, so I just flubbed around with the numbers until the scene looked right.

The shadows are going to dance with the trees, but the shadow positioning transform is never going to change. This gives a good excuse to create a canned transform that we can apply at any time. This saves a good bit of computation in each frame, but also allows the creation of this “shadow space” to be kept out of the animation method, where we don’t really care about its specifics any longer.

Like TransformedElements, Transforms are created from a factory method. This allows the library to delegate to native objects like WebKitCSSMatrix on platforms which support them. While the math will never come for free, some operations will be performed much more quickly in mobile browsers, for instance.

Transform shadowTransform = Transform.create();
 
// small translation so overlapping with trees
shadowTransform.translate(0, -10);
// angled
shadowTransform.skewX(-1.122);
// squished and toward the viewer (reflected)
shadowTransform.scale(1, -.12);

Finally, the transform and animation are applied to the shadows. At some point, everybody has difficulty with the order in which transforms should be applied. There are several ways to conceptualize the process: some like the idea that they are applied in “reverse order,” but I like to think of each transform as applied in the coordinate space created by the previous transformation.

In this case, we want to add the skew and scale animation to the shadows within the shadow space. If you’re a reverse-order kind of person, this means that the shadows are first skewed and scaled, just like the trees, and then projected onto the “ground.” It’s the same thing:

public void update() {
  // animate trees
 
  bigShadow.setTransform(shadowTransform);
  bigShadow.scale(scaleX, scaleY);
  bigShadow.skewX(bigSkewAngle);
 
  // animate littleShadow
}

The source is, again, all in the project repository, but here are the pertinent files. I’m linking to the versions as of this writing so things don’t get confusing; be sure to check if there are more recent revisions:

TransformTree.gwt.xml
TreesWidget.java
TreesWidget.ui.xml

Hall of Shame

I can’t resist comparing the rendering results between browsers. The actual transforms hold up well across platforms, which is nice, but border-radius results definitely leave something to be desired.

Internet Explorer remains kind of cute in its differently-abledness. WebKit and Opera are lagging Firefox in quality here, to varying degrees. Some of the disparity can be attributed to using a different radius for each corner, but gaps rear their ugly heads everywhere. This can be more than a little distracting when light colors are peaking around dark borders, or vice versa.

Please note that all of these screenshots come from a Windows machine. I hear that Snow Leopard’s Safari can fully hardware accelerate transforms, and I’m sure it also renders border-radius flawlessly and spends idle cycles scrubbing the wetlands*. Regardless, there are enough errant pixels here to drive anyone crazy.

Chrome 6.0.401.1 dev

Firefox 3.6.4

Internet Explorer 8

Internet Explorer 9 Platform Preview 2 (v1.9.7.7.66.6000)

Opera 10.53

Safari 4.0.5 (531.22.7)

*though I read in a forum post that Opera could do that before WebKit even filed a bug for it.

I have to add a corollary, of sorts: apparently my work is a lot more interesting when I’m using matrix operations in one way but the browser thinks I’m using them in another.

There’s a lesson in there somewhere.

Just about every little application I’ve written using transforms needs to be recompiled and rereleased, but these are the dangers of using still-developing standards. In the meantime, you’ll get some entertaining results (perhaps more so than before) in a nightly WebKit or nightly/dev Chrome release. They recently switched the order of WebKitCSSMatrix multiplication to the “right” way (unless you did computer graphics in the 80s), but kept matrix entry access the same (e.g. “m14″ is the entry in the fourth row, first column).

The result is that a simple transform is unaffected (I*M = M*I), a more complex transform is kind of backwards but recognizable, and a transform where I get tricky—manipulating a matrix directly and then mixing it with one of the first two—goes satisfyingly nuts.

Some back story: about two and a half weeks ago, I sent an email to a W3C mailing list asking for clarification on what the SVG- and CSSMatrix notation/order “should” be. I got no response on the list. Too long winded? Probably, but it turns out it was because some WebKit developers recognized the issue as a bug in their implementation, filed it, and—before I even thought to check Bugzilla a few days later—had landed the change.

Here we should all thank Simon Fraser and Chris Marrin over at Apple, not only for fixes like this, but for their involvement (with others, of course) in making CSS transforms exist in the first place. But not only are they quick, they have also been incredibly open (if a bit busy) to discussing how to get the standard right. I may be the only developer using this object outside of a mobile browser (it’s probable), but I’m still a nobody; it’s nice for that not to matter.

If you’re actually using my library and are worried about the unstable behavior: existing code will continue to work perfectly with all officially released browsers. As of yesterday, the latest version also takes care of pre-release browsers, on top of adding a bunch of new and faster features you’ll want to use anway. There is one last WebKit bug I’m waiting on, which will change either the spec or their implementation. CSSMatrix is a pretty small interface—there’s not much left to clarify—so I’m hopeful that things will settle down after that.

This is the price we pay for riding the bleeding edge, but don’t discount the fact that your project really might be better a little broken. Thumbnails help, too.

On to the actual topic of the day.

That Crashing Thing

[Update added at bottom of post.]

I’m happy to report that I have been unable to crash Firefox 3.6.4 beta 1 [only once] using my Blocks worker test. I originally noticed the change in one of the 3.7 nightlies, but it’s nice that it landed earlier. Unfortunately, I’ve been unable to track down the bug that fixed it, even after spending way too long with Bugzilla yesterday.

Part of the problem is that the stack traces from the crashes were never definitive (to my eyes, at least). All of them were on account of an “EXCEPTION_ACCESS_VIOLATION,” but it sometimes happened in TraceMonkey’s TraceRecorder, indicating my earlier guesses were correct, and sometimes in the JS string code, indicating not so much.

One factor that I actually forgot to mention in my last post is that the worker object running the physics simulation is actually discarded and reloaded from file every time the test level is changed or reset. In a real application, you’d want to avoid this if at all possible (depending on the browser, the script file might have to be re-parsed, re-compiled, or—serious horrors—re-downloaded). In this case, however, it was a great way to put the worker emulation code through its paces: the old, “frustrated-user-quadruple-button-click” stability test. It actually helped me find a nice little NPE that only occurred in the unlikely event that a terminate() call came after an emulated worker was created but before it actually started running.

I’m going to wildly speculate—with the very real chance that I’ve missed something on Bugzilla—that something similar was happening with Firefox. The facts:

1. an “EXCEPTION_ACCESS_VIOLATION”
2. the page would only crash after the worker was reloaded at least once (though often, when restoring, it would crash again immediately)
3. the crash frequently occurred with a call to JS_MakeStringImmutable(), which, MDC tells us, “applications must call…before sharing a JSString among threads”

Thinking what I’m thinking?

The weird thing is that nothing in the complete list of changes really matches the situation. The closest I can find is Bug 547399, “Don’t let worker messages run if the worker is suspended,” but the patch doesn’t touch any of the files I was combing through, nor do the developers involved think that the bug could trigger something as serious as a crash. It does, however, prevent a possible race condition dealing with passing strings between threads, so, who knows? Maybe my crash didn’t get enough hits and the fix is just a side effect of something else.

Still, it’s a welcome development. Thanks, Mozilla.

In Their Slowness

When I wrote the Blocks test, Firefox 3.6.0 really was as fast as the second test level would indicate, though there were hints that it was losing a lot of speed due to the way it got along with TraceMonkey. What I didn’t realize was that TraceMonkey wasn’t involed at all; JIT compilation was disabled in web workers until 3.6.2 and this bug. Imagine my surprise a month later: I finally have the time to post the test and Firefox can’t even manage the IE8 level. There was some frustration.

Our clues:

1. It’s happened before. I think. Some code just doesn’t take to the way TraceMonkey traces, so the engine needs a set of heuristics to determine when to just give up and interpret. Scripts will sometimes be misclassified, and this seems to be just such a case. There was a really interesting example of this discovered and diagnosed in front of a live audience (I love you, open development) and the bug is still open. The code involved is rather different than this case, but the connection is too nice to think too much about confirmation biases.
2. I mentioned this before, but just disable JIT compilation and try the test. This can be done in about:config, but it’s a lot easier to just turn on the console or script panels in Firebug. While it’s not as fast as it once was (Firebug is running, after all), you’ll usually see the blocks speed up rather comically.

The really humorous part of this whole situation is that I got exactly what I wanted: a performance update rolled out in a point release. I still agree with the sentiment, and this is undoubtedly an on-average win for performance. But, seriously, can I just have my interpreter back?

[Update: Almost immediately after publishing this post, I was able to crash 3.6.4; let's just say it will crash only rarely. Notably, the crash had nothing to do with JSString and occurred, once again, in TraceRecorder.

There is a bug: Bug 562455, but I am a total Bugzilla noob, so expect it to be duped or something in 3...2... =]

That original proof of concept gwtBox2d demo has slowly evolved along with the rest of the GWTns library. Though only a small portion of the original code remains, it has ended up being a pretty great stress test for new and tweaked library functionality; no matter how much performance improves, there can always be more blocks.

While the program itself doesn’t really do anything useful in a meaningful sense, or even help move Web Workers beyond a useful-for-simulated-annealing-while-animating-a-png demo reputation, I think it does have its own demonstrative value. And really, I have enough fun poking at it that I figured I might as well just gussy up the styling a bit and let other people have a turn.

Apologies First

• If you’ve run the worker version of the demo without reading this, and were running (pre-3.6.4) Firefox, I probably crashed your browser. And on reopening, promptly did it again. Sorry about that (hi SUMO!). This isn’t a problem inherent to workers or this library (see TraceMonkey tear it up in The Rationals) but (probably) due to branch heavy/poorly traceable physics code. I’ll write more about Firefox below.
• Stacking boxes turns out to be a good stressor, but Box2d can do much cooler things than this, often requiring more forgiving levels of computing power. For more examples, see the JBox2d demos or some of the many Flash/Alchemy demos out there.

The Demo

Now that you’ve been warned, here are the links. Return (or keep reading) for more on the application, your favorite browser, and some thoughts on using web workers in GWT.

• Blocks, native web workers where available (may crash Firefox < 3.6.4)
• Blocks, worker emulation in all browsers (safe)

Please Press That

First, the basics. Browsers that can run the physics engine in a web worker will do so, those that can’t, won’t, and which is happening should be obvious. If you’d like to force worker-emulation mode no matter what support is available, there’s a link for that at the bottom right.

Also on the right, you can select four different stress levels; the first three are named for the level at which that particular browser can regularly keep the blocks stacked, a mark of a stable simulation. Note that “Firefox 3.6″ is really 3.6, not the here-slower 3.6.3 (the security updates are a net positive, though). Unfortunately, my Windows-browser-centrism is on full display, but feel free to mentally insert “Safari” in the list above or below “Chrome,” whichever tickles your personal fanatical tendencies. I’m also hoping that UI purists can forgive my use of radio buttons and that redundant “reset” button. In some impromptu testing, users tended to be reluctant to click on things (maybe from all that “crash your browser” talk), so those elements function as a bit of a hack to ease users into a first click.

Finally, while we’re discussing sins: yes, those are all divs. I was originally going to use this opportunity to check out Hydro4GE’s Raphael wrapper, but testing and optimizing the transform module in something approaching a real application (i.e. transforming elements when you want to be spending execution time doing anything but transforming elements) was too great an opportunity to pass up.

Test Background

A physics engine is, at least in this case, an ideal match for a web worker. Once the simulator and display models are initialized, only a very small delta needs to be passed to keep them synchronized ([position + orientation] * number of bodies). Since you want to update the display as often as possible, but total message-passing cost must be kept to a minimum for performance, frequent small payloads work well.

Using Box2d in this particular, “one-code-fits-all” approach also works nicely because there is a natural “chunking” point between simulation steps. Though it may be possible to wring out a little more responsiveness in the non-worker case by further dividing these steps, the natural split is convenient and even the slowest browser released in the last 1.05 years can handle this code without throwing a slow script warning.

Much like many of the worker demos that came out about a year ago, this one aims to clearly demonstrate the benefits of taking a computation-heavy script out of the main execution thread. I think this one is a little more fair, though, because I actually try to make it run well in browsers without web worker support.

Let’s look at the emulated-worker mode first.

The Emulation Test

This is an “Emulation Test” and not, say, a “Regular Test,” because every component interacts with the simulator as if it were really running within a web worker. While this does introduce some overhead into the normal timer/callback setup, the worker specification is so simple that it ends up being pretty minimal, especially in the face of the benefits of a unified code base.

As a result of the aforementioned “not trying to be a jerk to older browsers” approach, most UAs acquit themselves fairly well in worker emulation mode. At the lower stress levels, there will likely be little difference between the worker and non-worker versions.

As the stress level is increased, though, it should be clear that the “Physics Rate” (the number of simulation steps per second) and the “Animation Rate” (the number of display updates per second) become tightly coupled. Even though the physics engine is updating as often as it can and the interface is only requesting 30 refreshes per second, when the rate of both fall below 30Hz, there is no effective difference betwen what they want (John Resig explains this really well in his timer tutorial).

The end result is obvious to anyone who has used a sluggish website (i.e. everyone). Since the two are tightly coupled, if the physics step takes longer, the interface will be proportionally less responsive. Moreover, since most current browsers refresh styling on the main thread, nothing is safe.

That’s what the fourth and highest stress level is for. Try it again, in even the fastest browser (unless you’re from the future). Move your mouse over anything blue, which will trigger a color change via a :hover pseudo-class (typically much faster than doing the switch in Javascript). Try clicking and dragging to use the slingshot block. If your site’s interface responds in any way approaching that sluggishness, you are alienating your users and are most likely losing a number of them.

The Native Test

The native-worker mode will use web workers for the physics engine if available; if not, the emulated-worker mode will automatically be used as a fallback. The benefit is simple, as long as more processing power is available. With the physics simulator off the main thread, no matter how long its time steps take, it won’t be able to dominate interface refreshes.

Once again, at lower stress levels the improvement might be slight, but try the test again (may crash Firefox) and set it to the highest stress level. Then test the UI. Though all the current browsers are still unable to keep up with the physics step, this fact has significantly less impact on the interaction responsiveness. The slingshot seems connected to your mouse drag. The blocks immediately change color when you hover over them. The standard form elements respond to your cursor. It’s nice when your website isn’t acting like Sonic 2 when you just lost all your rings.

The point isn’t a new one, but it also doesn’t have much to do with a physics engine, either. If you move your heavy scripts to a worker, you’ll have a lot less worrying to do about keeping an interface that is snappy and responsive, which is in many ways our first responsibility. Let the newer browsers do the heavy lifting for you, and let libraries pick up the older ones’ slack. Workers really are easier than you think.

Browser quirks

Chrome. So very fast. The only minor complaints I have are that :hover does not update without a mouse move (even if the hovered element itself moves), and that, in terms of apparent sane behavior, -moz-user-select beats the pants off of -webkit-user-select.

Firefox. Again, the worker version will likely crash the browser. This particular type of code is just not conducive to tracing and turns out to be a bit of a pathological case for TraceMonkey’s current tracing heuristics. Note that this might not actually be the cause of the crashes, but it is similar enough to TraceMonkey bugs fixed in 3.5 that I’m going to assume it to be the case. However, TM’s issues with my code are made more clear since worker scripts are now JITed; Firefox 3.6.x (with x>1) can no longer meet the performance level I set for it. Disable JIT compilation (or just turn on the Firebug Script or Console panels) and performance will double or triple. The entire situation is amusing enough that I think I’m going to write a post dedicated to it. Update: I can’t get recent 3.7 nightlies to crash. Hooray! Still slow.

Internet Explorer 8. Obviously IE is going to be at the shallow end of the performance pool, but I’ve been surprised at how well it performs, actually. Matrix filter transforms are still somewhat slow even after my earlier work, but they seem more fill-bound than geometry-bound. Small rectangles and no overdraw help, too. Finally, Page Speed warns about possible problems with :hover on non-anchors with a strict doctype, but I haven’t detected this in practice.

IE9 Platform Preview. Unfortunately there appears to be some bug that is preventing the JSON payload of worker messages from initializing properly in the Preview, which then causes an error when they are deserialized. However, setting breakpoints where the messages are created causes the Preview to crash, so I’m not pursuing the problem at this time.

Mobile. I have limited mobile browser testing means, but I’m proud to say that the newest mobile Safari on an old iPod touch runs the app at a rock-solid 1fps. Since most (all?) current mobile devices have only one core for Javascript execution, the UI and simulation threads will compete for processor time and there will be no real win for using workers in this way. For now, workers might only allow you something like a blocking http request in the mobile space, but the future will undoutedly bring multiple logical cores. In the meantime, if you want physics, far better to look at something brought to you by Objective-C or the NDK.

Opera. 10.5 came out after I finished this project, but since I was already adding transform support for the browser, a simple recompile enabled an Opera permutation. Opera seems to be actively developing their web worker implementation (and making some very helpful clarifications on the WHATWG mailing list), but no functionality appears available in the current release. In this example, 10.5′s Carakan Javascript engine is very fast and acquits itself well, but unfortunately odd bugs are manifesting, usually in the form of disappearing or non-interacting blocks. While I’m willing to concede that the problem probably lies in GWT or my own code, it is annoying, to say the least, that when I activate the Dragonfly debugger—and Javascript is interpreted—the program starts behaving correctly. I haven’t been able to dedicate the time needed to debug without the debugger yet, so full Opera support will have to wait. I would appreciate any insight anyone has on this problem.

Safari. On Windows, Safari is pretty much like Chrome with a few more ways to crash it thrown in (mostly via the inspector). On the Mac, Safari really is a class act. A shiny new 3.06GHz MacBook Pro runs the highest test level in something approaching interactive (though not fast enough for a stable timestep, yet). Perhaps more impressive: an old 800MHz dual G4 is able to handle the IE8 level easily, and is able to update the interface faster than 28fps even while the simulation is at the highest setting. I don’t advocate always using all available processing power for rendering a web page, but if the alternative is an unresponsive interface and an impatient user, use what you have.

On Workers and GWT

These thoughts apply to using workers in general, but I’ll focus on GWT in particular. Once again, I’m not sure that this example fully supports my call for wider worker use, but in using them, I’m increasingly convinced that they will soon be considered an essential part of building a faster web.

The GWT compilation process is not currently a perfect fit for generating web workers, but web workers are in many ways a perfect fit for the current trends in GWT development. As the cult of Ray Ryan has spread, the MVP pattern and event buses have become the poster children for structuring large GWT applications. This is the world that workers were made for.

Worker requirements, again:

1. No shared state except where created and maintained by message passing.
2. No DOM access.

I don’t think the connection could be much clearer. Hook up a worker object to your event bus, finish pulling the view out of model and presenter code, done.

Pragmatically, there is of course more to consider. Code with truly separated logic and presentation will need little change; code otherwise structured will likely need non-trivial work. The point isn’t that the addition of workers will come free, but that—if you’re already using these patterns—the barrier to entry is lowered enough that even modest potential performance gains can justify a day or two spent benchmarking.

Opportunities

The purpose often given for web workers is that they allow certain kinds of scripts to be written more naturally, without worrying about program flow disrupting the user experience. Blocking I/O and long-running calculations are usually then given as examples. While these are now possible in platform-specific applications—like a (modern) browser extension—the reality is that IE6, 7, and 8 are going to be with us for a long time. Moreover, as good GWT developers, we are already disciples of asynchrony (in addition to that whole Ray Ryan thing); let’s not regress.

The most obvious worker candidates are anywhere an IncrementalCommand is found, as long it’s needed for more than updating the DOM (and even then, there is always innerHTML string creation). But in fact, any long-running background process that reduces interface responsiveness should be strongly considered for extraction to a worker. Try the emulated worker test again. If the physics rate is 5fps, that means a step takes only 200ms, nowhere near long enough to trigger a slow script warning. But notice again the effect that has on the interface. Just because something can be done without triggering an error doesn’t mean that your application doesn’t suffer for it, especially if you have to do it more than once.

Finally, I don’t know what the guerilla-GWT-developer demographic is like, but workers are also good for tasks that might normally be performed with a server roundtrip but become limited by bandwidth, throughput, or latency. Local image editing has become a prominent example of this, but really any transformation of a large data set (geometric or otherwise) would qualify, as long as security issues were carefully addressed.

Potential Results

Like any multi-threaded approach, there will be trade-offs. There will always be overhead. Gains will be sublinear. With no way to discover the number of processes/threads that can be executed in parallel (as limited by the particular hardware and browser), blind guesses will have to be made. This is mitigated by the fact that extra workers just devolve to same-core native context switching, but before you start writing that worker-based MapReduce implementation, stop being ridiculous and remember that single- and dual-core processors are going to be the (client) norm for a few years yet.

I don’t want to sound too dour, though. Once again, you should be using web workers. The point of the module I wrote for GWTns was to make this as easy as possible (though it certainly isn’t the only approach available). While it enables, by design, only a proper subset of worker functionality, this allows developers to use the exact same code for all browsers. I covered this pretty well in the post about The Rationals worker example, but I wanted to go over the end result again.

Older browsers will get an application where the worker object is constructed normally, the only strange behavior being that all messages passed to it are done so asynchronously. Overhead is designed to be as minimal as possible, though there is still more work to be done there. Newer browsers will be able to load the code as a true worker and all execution will be done asynchronously. Script execution that was causing the interface to lag is now off the UI thread. Perhaps most importantly, though, this scheme allows for full dev mode debugging; no need to change your workflow. This last part was pretty much essential for working out the kinks in the blocks demo, but from a larger perspective, development mode is itself the key to not going crazy doing GWT development (Step 1: use dev mode. Step 2: use workers).

I would be remiss if I didn’t mention that, while I’ve found my own code to be very stable, it is very much in an alpha-state and feature-incomplete. There aren’t many other options right now, but you could certainly write a worker script by hand or compile one from a module and then load it manually. SpeedTracer’s web worker code might help you get started with this approach.

However you go about it, try workers out. I think you’ll be pleasantly surprised with the results.

Unsurprisingly, the last post ran overlong. I’ll endeavor to stick to code and equations wherever possible, as they are generally faster for me to write and you to parse. Amateur-hour Illustrator work takes a little longer.

All previous provisos still apply.

Implementation

If you’ve waded through that enormity of a post, you now know everything you need to get transformations working in Internet Explorer. To review:

1. Keep an internal augmented matrix to represent the current transformation. Manipulate it through some combination of programmatic access and the parsing of CSS-like transform functions.
2. Apply the linear portion of the affine transformation (the top 2×2 entries of the matrix) to the element through IE’s Matrix Filter
3. Use “auto expand” as the SizingMethod so the element can venture beyond its original confines.
4. Determine the shift that IE has automatically applied through its “bounding box behavior.”
5. Translate the element by increasing its left and top attributes by the translation from the internal matrix, less the shift found in step (4).
6. Work around minor problems like the limits of integer translations and problems due to altering layout via repositioning.

I’ll run through each of these items in turn, sharing implementation details and some of the interesting behavior I ran across in testing. If you’re the impatient type (or the “I don’t care” type), source is here.

1: Internal Representation

The biggest win from this approach comes from the standard model/view split of the representation of the transformation and the actual DOM style of the element. For one, this means that all transformation DOM access is one way: nothing needs to be read. This also allows transformation-changing methods to alter only the matrix representation, which can happen in superfast JavaScript-land, leaving a single style-setting DOM access (or as few as possible) until just before the execution context is yielded.

My module uses GWT’s scheduleFinally() mechanism to automate this process, accumulating transformation changes as they occur; each change only flags the need for a style update and doesn’t actually make one. Usually this means that the actual layout of an element is only updated once per animation frame—in a method named commitTransform()—and only if its transformation was actually changed. Combined with the fact that authors don’t have to intervene in this process (though it’s possible to do so), this is about as good as it gets.

For the update, I’ve given up using internal 4×4 matrices on platforms (IE, Firefox) with no 3d transform support. I originally chose to use them out of hope for the future and to maybe do some tricksy things with projections, but the tradeoff—for now—isn’t worth it. Obviously the 4×4 implementation will remain, lying in wait, but for the present IE and Firefox will default to 3×3 matrices and the > 50% savings in matrix multiplications. It’s no DOM access optimization, but in complicated transformations, the ops add up quickly.

(It’s worth noting that Chrome and Safari use a totally different 4×4 matrix implementation, which is built around their native WebKitCSSMatrix. Due to its design (instances are immutable) memory use is quite a bit higher, but the tradeoff is that all matrix ops take place in native code. I’m planning on moving Firefox to its version of MozCSSMatrix (or even MozSVGMatrix) when it’s available.)

A note for anyone doing this in straight JavaScript: please use a matrix library optimized for 2d or 3d transforms. I’ve noticed that the Sylvester library is widely used. While it is a great library, my understanding is that it was written for general matrix support, so you’ll get things like loop-based matrix multiplication, generalized inversion methods, and a lot of utilities that you’ll never use. When you only have 9 (or 16) matrix entries, a lot of these things can be massively sped up through special-case algorithms. Check out Vladimir Vukićević’s mjs library for something specifically intended for this purpose.

Finally, I currently only support procedural access to manipulating an element’s transformation, but this means that any transform set in a stylesheet will be clobbered. See Transformie for a good example of the parsing of an existing (and changing) list of transformation functions.

2: Applying the Linear Transformation

Interestingly, I’ve found that setting the Matrix Filter’s properties individually (and numerically) ends up causing significantly longer layout delays than setting the whole thing as a string. That is, this:

var matFilter = target.filters['DXImageTransform.Microsoft.Matrix'];
matFilter.M11 = a;
matFilter.M21 = b;
matFilter.M12 = c;
matFilter.M22 = d;

tends to somehow be much slower than the more naive

var filt = 'progid:DXImageTransform.Microsoft.Matrix(M11=' + a;
filt += ', M21=' + b;
filt += ', M12=' + c;
filt += ', M22=' + d + ')';
target.style['filter'] = filt;

Obviously the access method is different, so perhaps the matrix-filter object has been deprecated internally and it all goes through string parsing anyway. Or perhaps every set variable triggers an internal DOM change rather than using one lazy write. I’m not sure of the reason, but I’ve found that the first approach takes almost twice as long as the second, so I no longer use it. I’d be interested if anyone has other data points on the subject.

Unlike the current CSS3 implementations, IE will happily accept scientific notation in either case; don’t worry about number formatting through toFixed() or the like.

3: “auto expand”

I’m still convinced that whoever wrote SizingMethod didn’t like other humans and/or didn’t use their own browser.

4: The Bounding-Box Shift, Take 1

As a reminder, here again is the shifting behavior of an element under a pure rotation in Internet Explorer:

• View example: uncorrected rotation (previously posted)

In the previous post, I assumed that we knew the dimensions of the transformed element’s axis-aligned bounding box when calculating IE’s bonus translation. By far the easiest way to find this information is to first set the linear portion of the transformation to the element’s matrix filter, then ask the element for its current offsetWidth and offsetHeight. IE faithfully updates these values to give the distance between the extremities of the transformed element in each dimension.

As determined last time, the x-shift we need to remove is just half the original width, subtracted from half the bounding width. The same pattern applies vertically.

// original layout
var x = target.offsetLeft;
var y = target.offsetTop;
var w = target.offsetWidth;
var h = target.offsetHeight;
 
...
 
setInterval(function(){
// matrix filter applied
...
 
// find bounding box dimensions
// IE has updated these values based on transform set above
var wb = target.offsetWidth;
var hb = target.offsetHeight;
 
// determine how far origin has shifted
var sx = (wb - w) / 2;
var sy = (hb - h) / 2;
 
// translation, corrected for origin shift
// rounding helps, but doesn't eliminate, integer jittering
target.style.left = Math.round(x + e - sx) + 'px';
target.style.top = Math.round(y + f - sy) + 'px';
 
}, 30);

• View example: slow corrected rotation (via offsetWidth/Height)

Well done, theory. This works, and since it works, this is essentially how I left my original implementation. I knew this approach was inherently slow, but (as I wrote before) I didn’t need to animate transformations so I didn’t worry about it.

The reason this method is slow is hopefully obvious. To describe its actions in a different way, it writes to an element’s style, reads computed values from its updated style—forcing at least a limited reflow—then writes to it again, all within the same execution context. Certain DOM disaster.

I ran head-on into this problem when I started to fling little boxes across the screen. Even with a full 2d physics library simulating the boxes, geometric transformations being calculated per box, and each box’s element being positioned absolutely to keep it out of the document flow, these four lines of code took up a full 40% of execution time.

A different approach is needed.

4a. Better Box Bounds

The straightforward way to calculate the size of the minimum axis-aligned bounding box of a transformed rectangle is to apply the linear transformation to each corner of the rectangle in turn. From the resulting points, find the minimum and maximum x- and y-coordinates, subtract, et voilà.

But that’s boring, redundant, and the nuns used to tell me that extra conditionals are the path to wickedness. Let’s see if we can do better.

First, we don’t care about the bounding box’s actual coordinates, we just need its width and height.

Second, because we only care about the width and height, we can translate the element and its bounding box in any way we wish. A translation affects all points in the same way, so the distance between two points is invariant under a translation. If we translate the element in such a way that its top left corner is moved to the origin, we will only have to transform 3 points, since linear transformations leave the origin in place.

The specific translation needed is irrelevant; conceptually, the element is now just a conveniently positioned rectangle with width w and height h.

The non-origin corners of the rectangle have also been simplified. Their positions:

(We’re still in screen coordinates, so positive y points down).

Now let’s look at the same rectangle, under some transformation T. Since we’re still in step (4), T is just a linear transformation (and so is represented by a 2×2 matrix). Here is an image of the rectangle under one possible T

In general, if

then the coordinates of the transformed corners are

For the example transformed rectangle, now with a projected bounding box:

it should be clear that in this case the width of the bounding box is

By substitution,

Incidentally, because ch is negative (see image), this is equivalent to

(hint, wink, nudge, etc).

The height of this bounding box is

We need to determine the difference between the greatest and the least of the x-coordinates and the y-coordinates, for all transformations. Rather than trying to enumerate all the possible geometric situations, it’s easier to consider sign combinations. Beginning with the x-coordinates, we have four values: 0, ch, aw, and (aw + ch). a and c can be any real number, while w and h will always be non-negative.

• Case 1: aw and ch are positive. 0 is clearly the minimum x-value and (aw + ch) is both the maximum and the width of the bounding box.
• Case 2: aw and ch are negative. 0 is now the maximum and (aw + ch) the minimum, but the bounding box’s width—the distance from the maximum to the minimum x-value—is still |(aw + ch)|.
• Case 3: aw and ch have opposite signs. 0 cannot be a max or a min, as it is bounded by these values. Likewise, (aw + ch) will also be bounded by the two. It does not matter which value is positive and which negative, since the subtraction of the negative value will yield the addition of its magnitude; the width is (|aw| + |ch|) either way.
• Finally, careful consideration of the cases where aw or ch is equal to 0 (always be careful with your 0s) will find that their outcomes fall under the results listed above.

Since w and h are always non-negative, we only have to worry about the signs of the entries in T. While half the time it is a waste of an abs() call, it is always safe to say that

Therefore, if s_x is the horizontal distance between the ideal origin and IE’s shifted origin, then, using our shift equation and substituting the new w_b

Similarly,

All Together Now

You have a 2d affine transformation, represented by an augmented matrix of the form

To transform an element by this matrix in some future, standards-compliant browser, the following is sufficient:

target.style.transform = "matrix(a, b, c, d, e, f)";

Today, just substitute the vendor-extended version for “transform,” and add <length> units to e and f for Firefox (which doesn’t really make any sense, but for now: fine).

To do the same in Internet Explorer, here is our assembled JavaScript routine. In spite of some minor math optimizations, it does end up being fairly straightforward. Feel free to substitute your favorite IE string concatenation method.

// set linear transformation via Matrix Filter
var filt = 'progid:DXImageTransform.Microsoft.Matrix(';
filt +=   'M11=' + a;
filt += ', M21=' + b;
filt += ', M12=' + c;
filt += ', M22=' + d;
filt += ', SizingMethod="auto expand")';
target.style['filter'] = filt;
 
// assuming a-d are local variables
// and halfW and halfH are initialized properly
 
// horizontal shift
a = Math.abs(a); // or go ternary
c = Math.abs(c);
var sx = (a - 1)*halfW + c*halfH;
 
// vertical shift
b = Math.abs(b);
d = Math.abs(d);
var sy = b*halfW + (d - 1)*halfH;
 
// translation, corrected for origin shift
// rounding helps--but doesn't eliminate--integer jittering
target.style.left = Math.round(x + e - sx) + 'px';
target.style.top = Math.round(y + f - sy) + 'px';

• View example: fast corrected rotation (via calculation)

The shift correction is not exactly self-documenting code, but it is kind of pretty. The dimensions of the bounding box are computed—not queried—from the current linear transformation and used to correct the position of the element’s origin. commitTransform() now treats the DOM as write-only.

From some empirical testing, I’ve found that for a pure rotation this method will vary from the slow version by no more than a pixel in each dimension, and usually by much less. This error seems to grow at a quarter of the scale factor: for example, an element scaled by a factor of 20 will be at most 5 pixels off from where the slow method would place it. Based on the performance improvement, outlined below, I find this to be an acceptable trade-off (and without further testing, I’m not sure I would conclusively say that the slow method is more correct, anyway).

And there you have it; a mostly foolproof, efficient transformation method for Internet Explorer. If you can express your desired 2d affine transform in terms of a 2×3 matrix, and it’s not hard to do so, this code will take care of the rest.

The GWT Code

I originally wasn’t going to include this—everything one needs to implement IE support is found above—but I think it’s interesting to see what the GWT compiler does with the code. This snippet comes straight from the IE permutation of my test program, but has been complied using the “PRETTY” compiler option so it is somewhat comprehensible. I’ve inserted some extra comments for additional explanation.

Keep in mind that, even though this is the less-minified “pretty” output, it is meant to be an end-product and not an intermediate one. As such, syntax normally considered to be unfriendly (like the comma operator) is fine in this context.

// this$static is object scope
function $commitTransform(this$static){
 
var finalTransform, m11, m12, m21, m22, tarStyle, xAdj, yAdj;
 
// init dimensions if this is the first time transforming element
if (!this$static.elementInitialized) {
  if ($isOrHasChild(($clinit_22() , $doc.body), this$static.target)) {
    $initElementLayout(this$static);
  } else {
    return;
  }
}
 
// only hint that compiler removed unused origin-changing code
finalTransform = this$static.transform;
 
// horizontal shift (using 'a' and 'c')
m11 = finalTransform.m11;
m11 = m11 < 0?-m11:m11;
m12 = finalTransform.m12;
m12 = m12 < 0?-m12:m12;
xAdj = (1 - m11) * this$static.halfOrigWidth - m12 * this$static.halfOrigHeight;
 
// vertical shift (using 'b' and 'd')
m21 = finalTransform.m21;
m21 = m21 < 0?-m21:m21;
m22 = finalTransform.m22;
m22 = m22 < 0?-m22:m22;
yAdj = -m21 * this$static.halfOrigWidth + (1 - m22) * this$static.halfOrigHeight;
 
// translation from matrix ('e' and 'f')
xAdj += finalTransform.m13;
yAdj += finalTransform.m23;
 
tarStyle = this$static.target.style;
 
// I use Array.join, but doesn't make a huge difference
tarStyle['filter'] = (filterArray[1] = finalTransform.m11 , filterArray[3] = finalTransform.m12 , filterArray[5] = finalTransform.m21 , filterArray[7] = finalTransform.m22 , filterArray.join(''));
 
tarStyle['left'] = this$static.originalLeft + xAdj + 'px';
tarStyle['top'] = this$static.originalTop + yAdj + 'px';
}

The GWT compiler doesn’t really have a chance to work its magic here; the java code was purposefully written to be straightforward, so the output is close to what was input. What’s interesting is actually what you don’t see. There’s barely a hint that the compiler was able to remove the code for handling setOrigin(), which is nicely inlined if it is used. There is also no trace of the completely different code that is used in Firefox, or Chrome, or Opera, etc.

Incidentally, this little gem takes care of everything found above in the Webkit permutation:

function $commitTransform(this$static){
  this$static.target.style.WebkitTransform = this$static.transform;
}

I’m trying to think of the appropriate cliche to sum up poor old IE’s situation—something about bailing water or running in place—but I just don’t have the heart.

DOM is the animation-killer

It can be difficult to get exact numbers for code that affects reflow and repainting. Beyond the usual “measuring JavaScript with JavaScript” problems, other style-changing code can have a huge impact on execution time, and the non-deterministic order in which they all may interleave can have disproportionate effects. As a result, I’ve tried to rely on numbers from my stress-test program, which in some ways resembles a real web application. The results come from the built-in IE8 profiler, so specific values shouldn’t be treated as absolute.

In addition to the changes already mentioned, I’ve made a few other efficiency improvements. I restructured the initialization of internal “scratch” matrices to avoid GWT’s clinit()s (Firefox shows a 75% reduction in null method calls). Combined with the switch to 3×3 matrices, optimization of the bounding box routine, and other small changes, I managed to cut the execution time of the write-only version of commitTransform() by about 50%.

For all my bluster about numerical and algebraic improvements, though, this amounts to about a tenth of a millisecond, depending on how it’s measured. This is a big savings and the faster commitTransform() can yield sooner and let other code run more often. But it is nothing compared to the elimination of reading DOM attributes.

In the example files, averaged over 20,000 calls, the offsetWidth/Height transformation method takes 2.5ms. On the other hand, the final transformation method claims to take 0.0ms, but my division finds an average of .03ms per call (though I could imagine an uncertainty approaching .1ms). But that’s just a toy example.

As I mentioned above, in an already intensive app, commitTransform() on 40 elements just 10 times per second was using around 40% of total execution time on a maxed-out processor. The new version drops this below 4%. To emphasize the point:

Keep in mind that “setting transform” isn’t calculating the transform, it isn’t changing it, it isn’t making a new one; it is only setting the transform style from an existing matrix. Note also that “everything else” is everything else, including the time the app spends responding to user input, which is its only reason for existing in the first place.

Now, transforming and positioning elements correctly is important, but I think the second bar better reflects the time that should be devoted to just setting the transform style on 40 elements.

Two take-aways:

1. USE THE SECOND METHOD. Unless you’re certain that the original bounds of the elements have changed (and there are event listeners for that sort of thing), cache the bounds and calculate the bounding box.
2. If you aren’t paying attention to the way you access the DOM, your application will be slow. This is certainly nowhere near an original statement, but it deserves to be repeated yet again. Firebug, SpeedTracer, and IE’s surprisingly handy profiler will help.

Internet Explorer’s commitTransform() is now on par with Firefox’s (IE actually profiles quite a bit faster, but with way too many variables to control, I’ll stick with “on par”). Limiting agents are now elsewhere.

Future Work

Overall, it’s been interesting to get back into this code. As I wrote at the beginning, this module didn’t get the full attention it needed, so the code isn’t exactly a paragon of software design (or good code formatting). Part of the problem was that encapsulating transformations in a way that matches the behavior of CSS3 transforms—the forward-thinking approach—is made difficult by the particulars of the IE implementation.

For instance, I still think a transform shouldn’t be tied to a particular element; it is, after all, just a style (even if I tend to use transformed elements as logical entities). But to do transformations in IE quickly, the original size of an element can only be read and cached once, so a particular transform is bound to a particular element and the abstraction is lost. This can be worked around (and to an extent already is in the Transforms/TransformedElement split), but currently there is a conceptual gap between the exposed interface and what it gives access to. It’s fine, but it’s not elegant.

For now, however, the IE code is working well and speedily (according to the browser’s ability). In the months since I started this project, I’ve developed a better sense for the GWT UI idioms (and some thoughts on integrating with UiBinder), so a rewrite is definitely overdue. However, writing this post gave me an idea for yet another way one might abuse the transform system, so I’ll probably put off any redesign until I have a better idea of all use cases. For the time being, feel free to check out and use the current module and provide any feedback on how it could better suit your needs.

All the source code is here: gwt-ns project page.

Examples, Again

First: Pure Rotation
Slow: Fixed Rotation
Fast: Final Rotation

In my work on the box2d and web worker modules in gwtns, I’ve needed the ability to put things up on the screen. To really make sure I was doing the word “overkill” justice, I decided to use my old TransformedElement module for that purpose. This has given me the opportunity to go back and ruminate over my original implementation.

Though it was only a few months ago, I originally took it on as more of a way to get to know the GWT deferred binding system than to write the perfect transformation library, and I wrote it in definite haste. I would probably not structure it the same way a second time. It’s not bad, but the differences between the underlying IE and CSS3 implementations are enough to make the unifying API a little less straightforward than it should be.

What was terrible, though, was the speed of the Internet Explorer version. The trial and error process to get IE’s matrix filter fully operational was annoying enough that I didn’t spend much longer on it than I had to. It helped that I only needed to position elements, not animate them, but that’s no longer true. As a result, I took a day last week to profile and revamp the IE implementation. The performance is actually now on par with the Firefox version, since the majority of execution time is taken up by DOM access.

But I’ll write more about the changes I made in my next post. For now, I really want to address how to get Internet Explorer transforming elements in almost the exact same way as all the “modern” browsers that support the CSS 2D Transforms (draft) specification. I’ve been surprised at the lack of support for IE as plugins and tools have started popping up to let authors easily transform elements. In fact, many explicitly state that IE support seems possible, but it hasn’t been implemented yet due to the pain of figuring out the different format.

But there’s no reason to repeat ourselves as a community. Supporting IE is actually pretty straightforward, you just have to be a little tricky to get around a few problems. With this done—if you’re willing to forsake Firefox users prior to 3.5 and Opera users prior to 10.5—essentially every browser in use is capable of applying geometric transformations to HTML elements. In writing this, I’m hoping that I can at least set a baseline of understanding of how transformations work in IE. That way, those that don’t want to figure it out from scratch won’t need to, and those that do will be able to concentrate on creating tools more elegant and sophisticated than I have here.

A few caveats

• Unless otherwise stated, this post will be strictly about two dimensional transformations. So when I talk about “affine transformations” or “translations,” just read “2d affine transformations” or “2d translations.”
• I’m going to assume some familiarity with basic linear algebra and transforms. I’m hoping, though, that I can provide enough context so that the proper Wikipedia or MathWorld search will be clear even for unfamiliar concepts. Please let me know if and where I confuse or gloss over an important detail.
• This will only cover support for the equivalent of the matrix transformation function. i.e. transform: matrix(a, b, c, d, e, f); rather than the list of transformation functions: transform: rotate(<angle>) scale(<number>) ...;. I’m primarily interested in transforms through scripting—so I concatenate transformations into an internal matrix representation—but it’s trivial to find the matrix form of any list of transformations. This has implications for animation, but that will have to fall outside the scope of this post.
• All listed code was tested only in Internet Explorer 8. The Matrix Filter was added in IE5.5, but the accessor syntax was slightly changed in the latest version to better comply with the standard way of extending CSS. The syntax changes should be trivial, but layout changes are probably not. If you work it out, please let me know so I can put up a link.
• Finally, if all of this isn’t your cup of tea, I’ll have the final code posted next. Don’t worry; it’ll be JavaScript.

UA Background

The type of transform we’re interested in is called an affine transform, which describes most of the ways one would want to move or change an object: scaling it, rotating it, shearing it, translating it, etc. There used to be no standard way to transform DOM elements, but a few years ago Apple started pushing for their format (which started life on the iPhone) to be adopted. From there, it spread to the desktop version of Safari and then eventually to Firefox, Chrome, and Opera. It’s now close to being finalized.

But it turns out that Internet Explorer has been well ahead of the pack for years, supporting the transformation of elements through its CSS “filter” extension since at least 2000. A quick Google search will actually find mention of it all over the place in old DHTML tutorials, but I can’t think of any time I’ve seen it in the wild. Like the existence of Flashblock, the fact that spinning webpages aren’t more widespread is probably evidence of divine providence and existing barriers shouldn’t be trifled with. But in the end, I prefer tools that will cheerfully help you shoot yourself in the foot (or your users in the eyes). We’re just going to have to rely on collective good taste.

A still forthcoming blog post better compares the results of IE’s matrix transform filter to the results of current CSS3 implementations, but, in theory, they are close to identical in what they support.

Math Digression: Linear Transformations

An affine transformation is actually a combination of a linear transformation and a translation. In our case, the linear transformation takes linear combinations of a point’s x and y coordinates to map them to new coordinates. In other words, for point x

linear transformation T produces the new point

or, in matrix form:

By using specific values for the entries of the transformation matrix, here represented as a through d, a single linear transform can express a rotation, a scale, a shear, or even an ordered sequence of these operations combined. It can be very illuminating to work out what these specific matrices are for yourself, but as a simple example, an expansion by a factor of two would be represented like this

This transformation would map every point to a new point at twice the distance from the origin, except the origin itself.

In fact, no linear transformation can move the origin. Rotations provide another easy example: no matter how many times a wheel is rotated, there is no rotation that will change the center of the wheel; that point is fixed. If we want to be more precise:

At the origin, the values of a, b, c, and d are irrelevant; a linear transformation always maps the origin to itself.

Further Math Digression: Translations

Translations are what allow objects to move around without distortion. There are a few different ways to think of a translation, but the end effect is that all points (including the origin) are shifted in the same direction by the same amount. As noted, there is no way to do this with a simple linear transformation matrix because (among other things) there is no way for it to move the origin.

We’d really like to express the full affine transform as a matrix, though. Why would this be desirable? For our purposes, the main benefit is transform concatenation. Since matrix multiplication is associative, a chain of transformations applied consecutively to an object is equivalent to the application of the single product of each transformation’s matrix. Instead of an unbounded list of transformations, each requiring yet more operations to find an end result, each transformation can be multiplied into an intermediate matrix, requiring no more storage than the entries in that matrix.

If we can represent a linear transformation and a translation in a single matrix, more sophisticated behavior also becomes possible. For example, objects would be able to rotate about any specific point rather than always rotating about the origin. Our job also becomes easier; rather than dealing with a bunch of bookkeeping to keep two separate data structures geometrically synchronized, we keep only one structure (a matrix) and one very simple operation (multiplication). The problem remains, though, that matrices can only represent linear transformations, and a translation is not a linear transformation.

We cheat this by augmenting the matrix used so that we are now applying a linear transformation to a 2d plane in a 3d space. By convention, we add a z-coordinate of 1 to all of our 2d points, which guarantees we always have a non-zero coordinate with which we can play. Since the origin is no longer the actual origin (it’s now at (0, 0, 1)), we can shift it. We are actually shearing in 3d space, but when we discard the extraneous z-coordinates and look again at just our original 2d points, it appears as if a translation was applied.

If that’s not your kind of explanation, maybe the arithmetic will be a little clearer. Again, we augment our points so they are now in 3-space, and our matrix needs to likewise be upgraded to a 3×3 version:

Comparing this result to the linear-transformation matrix multiplication in the previous section, it should be easy to see both the linear transform and the added translation at work. The e and the f entries, since they will always be multiplied by 1, move all points e-units horizontally and f-units vertically.

I purposefully left the bottom row of that matrix as [0, 0, 1]. Some really cool and interesting things can be done by altering the entries there, but without being careful with them, some sticky mathematical situations can arise (especially with invertibility). All the current browsers avoid this (in 2d land, at least) by only accepting transformations specified by the top 2×3 entries of the transformation matrix.

The form is more limited, but for our goals it is sufficient.

This briefest of reviews will have to do for now. If you’d like to learn more, I suggest basically anything by Jim Blinn (in particular, his A Trip Down the Graphics Pipeline and its treatment of homogeneous coordinates). For more immediate gratification, Wikipedia does a pretty good job here.

And Back to IE

As mentioned earlier, Internet Explorer accepts a transformation matrix through its filter extension to CSS; in Javascript you might set the filter from a matrix like this:

element.style.filter="progid:DXImageTransform.Microsoft.Matrix(M11=a, M12=c, M21=b, M22=d, Dx=e, Dy=f, SizingMethod = sMethod)";


where a, b, c, and d still represent a linear transformation, and e and f represent a translation. These could be hardcoded values or dynamic ones, varying due to time and user input.

The SizingMethod property tells IE how to deal with elements that exceed their original bounds when transformed. If SizingMethod is left at its default value—the string “clip to original”—everything works and the element is transformed correctly. However, the rendering of it usually leaves something to be desired. If it was rotated or translated or scaled in a way that takes part of it outside of its original bounds, that part will be clipped. For example, a simple translation of 35 pixels to the right yields:

• View example: SizingMethod = “clip to original” (in IE only, obviously).

So the default SizingMethod ends up being not very useful, but this isn’t unexpected given “clip to original;” everything seems sane.

The other possible value for SizingMethod is “auto expand,” which allows the transformed element to take up as much room as it needs (notably, without changing layout, just like the CSS3 rec). This would seem like the key, but it comes with a catch: if SizingMethod is set to “auto expand,” then all translation values will simply be ignored:

• View example: SizingMethod = “auto expand”.

I have absolutely no idea what the reasoning was here, or how anyone thought that this behavior would be functionally useful. The MSDN documentation states it so matter of factly that I feel like I must be missing something (or taking crazy pills), but I haven’t run across anything that actually explains the behavior. Fortunately, there are ways to work around this problem. Mostly.

Workaround 1

As other people have also realized, the solution is to re-split the desired affine transformation. An augmented matrix is still used throughout the transformation process to allow transforms to be combined, but when it comes time to write the transform to an element’s style, the linear transformation and the translation are separated once again. The matrix filter (and “auto expand”) is used for the linear portion of the transformation. Since the translation is useless there, the element is instead translated as any other element would be: by altering its ‘left’ and ‘top’ attributes.

There are a few minor regressions inherent to this approach. First, translations now alter layout: as an element is translated around the page, any elements positioned relative to it will also have their positions altered. Currently I work around this by either only transforming absolutely positioned elements, or by wrapping an absolutely positioned element with a relatively positioned one, set to the same original dimensions. This has the effect of keeping the rest of the layout stable as the transformed element moves at will. It’s not pretty, but it works.

The other minor problem is that elements are now limited to integer pixel positioning instead of the nice floating point values they could use before. Smart rounding can mitigate the effect, but some object jittering will always be present, especially in slow movements or with small elements.

But there’s a more fundamental hurdle. As stated earlier, by its very nature a linear transformation leaves the origin of an element unaffected. A compliant CSS3 transform with no translation does this: origins stay put. IE is different; it transforms an element, calculates a bounding box for it, and then places that box’s top left corner at the specified ‘top’ and ‘left’ coordinates, origin be damned. Hasty info-graphic ahoy:

The default origin for both the CSS3 Transforms spec and IE is found at the center of an element (given here in screen coordinates). When a pure linear transform is applied to it (in this case a rotation of 30 degrees), CSS3 keeps the origin fixed. IE’s bounding box routine will instead ensure that an element’s left-most point is at its ‘left’ value, and its top-most point is at its ‘top’ value. While this may seem straightforward in its description, in practice you just end up with bouncy boxes. No point is fixed. This becomes clear when you see it in action:

• View example: pure rotation behavior

Again, I have no idea how someone implemented this, tested it, and thought it useful, but not all things are revealed to me.

(In a rotation, the origin’s movement can be described by two catenary curves. That is cool. But not useful.)

Workaround 2

Since IE keeps no point fixed under a linear transformation, if a translation is then just naively applied, an element’s final position will have shifted not by the translation value but by (translation + (some origin shift)). We need to compute that shift and remove it every time.

Take horizontal positioning first: Let x be the ‘left’ position of the original (untransformed) element, let w be its original width. The element’s horizontal midpoint is at

Finding the midpoint of the bounding box can have serious impacts on performance, but we will only concern ourselves with the theory for now and assume we already know its dimensions. What follows wouldn’t really be a proof, relying on an appeal to intuition with one visual example, but for one simple fact: a rectangle under a 2d linear transform shares its center with its minimum axis-aligned bounding box. The proof of this is straightforward, so I’ll leave it as an exercise for the reader.

Let w_b be the width of the bounding box of the transformed element. Note that w_b is not a transformed version of the vector (w, 0). This is obvious under a 90° rotation, as w_b would have length 0, while the bounding box would actually have a width equal to the height of the original element.

Since it shares its center with its bounding box, and we’ve assumed that we know the width of that box, the transformed element’s midpoint has moved to

Since we want the bounding box (and thus the transformed element) to be horizontally centered at m_x, not m’_x, we subtract the difference of the two from the translation value before we apply it to the element. If we call the horizontal shift s_x

The vertical shift is found similarly.

In JavaScript, the shift would then be removed when applying the translation to the element:

element.style.left = x + e - sx + 'px';
element.style.top = y + f - sy + 'px';

Finally, while I’m not going to go in depth on support for changing the origin, it’s just an additional adjustment, this time by the transformed difference between the center of the original element and the requested new origin. If you’d like to take a look at my solution, it’s located here. The code is somewhat obfuscated for performance, but it shouldn’t take long to figure out (yes, that’s Java. It’s still weird for me too).

Next

That’s it for now. If you just want the code, or you’re dying to know how the replacement of two lines of code with twelve resulted in an order of magnitude speedup, stay tuned for the next post, entitled, “The DOM,” or, “The API Only a Mother Could Love.”

Links Cited

Example pages. These only work in Internet Explorer, and probably only in IE8.

SizingMethod: ‘clip to original’
SizingMethod: ‘auto expand’
Bounding box positioning.

Outside resources.

The gwtns library
CSS 2D Transforms Module Level 3
MSDN: Matrix Filter
SVG 1.1: Coordinate Systems, Transformations, and Units
MSDN: SizingMethod Property
A Trip Down the Graphics Pipeline
Paul Bakaus’s Transformie
Zachary Johnson’s jQuery Patch
Jon Combe’s css clocks

It’s great to see so much work going into workers and the tracing engine, though, and to hear that changes will start rolling out in point releases. I feel for corporate deployments, and I hate when it’s done through ever-present update services, but in terms of browser security and iterating/testing standards-to-be, this seems to be the release model to follow. It’s a huge relief to not have to work around Chrome 2′s Worker problems, and it will be interesting to see if something similar happens with Chrome 3 in the next month or two. But I worry constantly about Firefox 3.0 vs 3.5 vs 3.6.

I don’t have a clear idea of where the balance should be between AUTO-UPDATE and developers waiting 5 years for implementations to converge (or at least settle). “Make all things easier for the user” is a good starting ideal—as long as “declining our help” is first on the list—but the effect in aggregate would not be linear.

Rambling finished. Flash 9 it is.

But it might work for us. So, here’s a ridiculously unrealistic task, coded in the most straightforward way possible, and that runs perfectly well in Internet Explorer (8) without any Worker support. The reality is that instructive examples are of course necessary, so I’m going to trust to other demos to inspire excitement. In the meantime, I get another chance to play around with hyperbinary numbers. I’ve mentioned this sequence and its connection to the rational numbers before, but to recap: I first came across it on Division by Zero (still waiting for the rest of that series) and the original paper by Calkin and Wilf is here.

The example application calculates and displays a succession of rational numbers (fractions), as ordered by the Calkin-Wilf enumeration of the rationals. That sequence has several very interesting properties, but notably it contains every single (positive) rational number, in reduced form, exactly once. The example page doesn’t quite live up to the “every” part, but it does go on for a while. You can see it here: An Enumeration of the Rational Numbers.

By default, it actually starts at the 10-millionth rational number to make the demonstration a little more computationally taxing, but that can be changed if you want to see how it all begins (for the less motivated: “1″).

The GWT-y details

Right… Anyway, the “Rationals” GWT project is divided into two modules. The Worker module (RationalsWorker) extends a special Worker EntryPoint. It repeatedly calculates a new hyperbinary number, combines it with the last, and returns the result to the parent script:

public class RationalsWorker extends IterativeWorkerEntryPoint {
  @Override
  public void onWorkerLoad() {
    // nothing to initialize
  }
 
  @Override
  public int execute() {
    // calculate numerator and denominator...
    postRational(numerator, denominator);
    return DELAY_MS;
  }
 
  /**
   * Creates a message containing calculated numerator and denominator and
   * send to parent context.
  */
  public void postRational(int numerator, int denominator) {
    String data = Json.strigify(RationalNumber.create(numerator, denominator));
    postMessage(data);
  }
}

The main module (Rationals) creates a Worker object out of the RationalsWorker module and then just waits to receive new numbers, inserting them into the page as they arrive:

public class Rationals implements EntryPoint, MessageHandler {
  Element numerator;
  Element denominator;
 
  // Worker module definition
  @WorkerModuleDef("gwt.ns.sample.rationals.RationalsWorker")
  interface RationalWorkerFactory extends WorkerFactory { }
 
  @Override
  public void onModuleLoad() {
    numerator = RootPanel.get("numerator").getElement();
    denominator = RootPanel.get("denominator").getElement();
 
    // Worker creation
    RationalWorkerFactory factory = GWT.create(RationalWorkerFactory.class);
    Worker worker = factory.createAndStart();
 
    worker.setMessageHandler(this);
  }
 
  @Override
  public void onMessage(MessageEvent event) {
    RationalNumber newNum = Json.parse(event.getData());
    numerator.setInnerHTML(newNum.getNumerator() + "");
    denominator.setInnerHTML(newNum.getDenominator() + "");
  }
}

The compilation process is better described in the design document (which I’ll be finishing real soon now), but I’ll describe it here in brief. When the Rationals module is compiled, the Web Worker library handles the loading of the Worker through the magic of deferred binding. In code destined for browsers with native Worker support, the Worker module is compiled using a special linker, and a URL for the resulting script is inserted into the parent module so the browser can load it at runtime. For browsers without Web Worker support, the Worker module’s entry point is actually inserted directly into the main module, along with some machinery to simulate the behavior of a Worker. In both cases, a “Worker” object is returned and the parent module can proceed in full ignorance of the implementation.

The Rationals example source code is available in the project repository. The host page is down in the war directory.

Benefits and Runtime Behavior

As I noted above, this example runs well in Internet Explorer 8. This comes down to how it was written. Even though code executed continuously inside a Worker would not block the main event loop, the same code run in a faux-Worker would. Authors are perfectly free to further differentiate by loading different code based on browser type. However, the first goal of this library was to provide a “thread-like” context for executing the same code regardless of browser—using a real Worker if available—in a way that requires only a minimum of boilerplate and provides full support for development-mode debugging.

So, if the same code is going to be run everywhere, it can’t be written in a way that disrupts responsiveness in older browsers. For this example, the calculation of rational numbers is divided by the usual setTimeout/callback scheme to keep the UI (fairly) responsive in IE, even though it is being done in the main event loop and nearly pegging one core on my old machine:

Chrome is a different story. The same code uses about the same execution resources (generating rationals at a greater rate) but this time it is running in a Web Worker:

As can be seen, this leaves the actual page (“Tab: …”) doing almost nothing. If we imagine that this is a script that must be run, regardless of platform, Chrome leaves the page free to do something else, at the author’s discretion, or to simply demonstrate the silky smoothness of the future while IE updates at 15 frames per second.

Stray Observations

In Firefox versions prior to 3.6, TraceMonkey seems to struggle with some scripts in a Worker context while having no problem when they are run normally. This really calls for a test page, with a reliable Worker on/off switch, to determine exactly which browsers (× which kinds of problems) should receive native or emulated implementations.

With that said, Firefox (and especially Minefield) eats this demo for breakfast. The inner loop is mostly simple arithmetic and array accesses, so I wonder if something else is holding v8 back. If there’s a way to profile a Web Worker using Firebug/Development Tools, I haven’t found it yet.

Demo: An Enumeration of the Rational Numbers

But enough about other people. Most importantly, my Twitter campaign for improving TraceMonkey performance in Web Workers has clearly paid off (actual events might not reflect that statement). 3.6rc1 showed nearly identical performance for gwtBox2d running in a page’s main loop as in a Worker script, and this has carried on through to the final release. I also haven’t had any crashes running any demos (yet), which were caused (I think) by an OOM from the tracing engine. The performance increase due to parallel execution isn’t quite what I was hoping for, but I need to build in some more sophisticated profiling hooks to see what exactly is going on. Also, as fun as Canvas is for some things (and I’m working on some pixel manipulation ideas that are actually suited for the format), the way I’m using it now is much better matched with something like SVGWeb or Raphael(js). I only wish the bindings already existed.

I’ve also been racing to put together some ideas I had on making Web Workers easy to use in any GWT project. That code is finally reaching a usable state and I’ve had the pleasure of learning far more about Generators, Linkers, and the GWT compiler than I thought I would ever have the impetus to. My approach is just about absolutely nuts, but between a js physics library and a fragment-shader mime type, clearly the Scary Door has already been breached. If this project works out at all, there will be a post here in the next day or two.