Tuesday, 14 October 2008

Hating Pixels

Drawing an image on the screen should be a simple operation. However, in a browser engine, things get complicated because there are a number of subtle requirements involving subpixel layout, scaling, tiling, and device pixels. We've had lots of bugs where visual artifacts appear in sites at certain zoom levels, and we've fixed most of them but the code got really messy and some bugs were still not fixed. So several days ago I sat down and worked out what all our known requirements for image rendering are. Then I worked out an approach that would satisfy those requirements, and implemented it. As is often the case, the implementation revealed that some of my requirements were not strong enough. The resulting patch seems to fix all the bugs and is much much simpler than our current code.

The problem at hand is to render a raster image to a pixel-based device at a specified subpixel-precise rectangle, possibly scaling or tiling the image to fill the rectangle. We control this by specifying two rectangles: a "fill rectangle" which is the area that should be filled with copies of the image, and an "initial rectangle" which specifies where one copy of the image is mapped to (thus establishing the entire grid of tiled images). There may also be a "dirty rectangle" outside of which we don't need to render. There are several requirements, the first three of which are actually more general than just image rendering:


  1. Horizontal or vertical edges (e.g., of background color, background image, border, foreground image, etc.) laid out so they're not precisely on pixel boundaries should generally be "snapped" during rendering to lie on pixel boundaries, so they look crisp and not fuzzy.
  2. All edges at the same subpixel location must be snapped (or not snapped) to the same pixel boundary. This includes multiple edges of the same element, edges of ancestor/descendant elements, and edges of elements without an ancestor/descendant relationship. Otherwise, you get nasty-looking seams or overlaps.
  3. Any two edges separated by a width that maps to an exact number of device pixels must snap to locations separated by the same amount (and in the same direction, of course). As far as possible, we want widths specified by the author to be honoured on the screen.

    In Gecko, we achieve the first three requirements by rounding the subpixel output rectangle top-left and bottom-right corners to device pixel boundaries, ensuring that the set of pixel centers remains unchanged.

  4. When content is rendered with different dirty rects, the pixel values where those rects overlap should be the same. Otherwise you get nasty visual artifacts when windows are partially repainted.
  5. Let the "ideal rendering" be what would be drawn to an "infinite resolution" device. This rendering would simply draw each image pixel as a rectangle on the device. Then image pixels which are not visible in the ideal rendering should not be sampled by the actual rendering. This requirement is important because in the real Web there's a lot of usage of background-position to slice a single image up into "sprites", and sampling outside the intended sprite produces really bad results. Note that a "sprite" could actually be a fixed number of copies of a tiled image...

    (This may need further explanation. Good image scaling algorithms compute output pixels by looking at a range of input pixels, not just a single image pixel. Thus, if you have an image that's half black and half white, and you use it as a CSS background for an element that should just be showing the half-black part, if you scale the whole thing naively the image scaling algorithm might look at some white pixels and you get some gray on an edge of your element.)

  6. The exact ratio of initial rectangle size in device pixels to image size in CSS pixels, along each axis, should be used as the scale factors when we transform the image for rendering. This is especially important when the ratios are 1; pixel-snapping logic should not make an image need scaling when it didn't already need scaling. It's also important for tiled images; a 5px-wide image that's filling a 50px-wide area should always get exactly 10 copies, no matter what scaling or snapping is happening.
  7. Here's a subtle one... Suppose we have an image that's being scaled to some fractional width, say 5.3px and we're extracting some 20px-wide area out of the tiled surface. We can only pixel-align one vertical edge of the image, but which one? It turns out that if the author specified "background-position:right" you want to pixel-align the right edge of a particular image tile, but if they specified "backgrond-position:left" you want to pixel-align the left edge of that image tile. So the image drawing algorithm needs an extra input parameter: an "anchor point" that when mapped back to image pixels is pixel-aligned in the final device output.

It turns out that given these requirements, extracting the simplest algorithm that satisfies them is pretty easy. For more details, see this wiki page. Our actual implementation is a little more complicated, mainly in the gfx layer where we don't have direct support for subimage sampling restrictions (a.k.a. "source clipping"), so we have to resort to cairo's EXTEND_PAD and/or temporary surfaces, with fast paths where possible and appropriate.

Note: this algorithm has not actually been checked in yet, so we don't have battle-tested experience with it. However, we have pretty good test coverage in this area and it passed all the trunk tests with no change to the design, as well as new tests I wrote, so I'm pretty confident.



9 comments:

  1. Yes, yes, yes - all very good and well... :-)
    But inquiring minds want to know about CSS bling :-) and the chances of all of that "totally rockin'" stuff has of making it into FF 3.1 :-).
    Great work on all of these pieces. You're making our lives too easy ;-).
    Cheers,
    - Bill

    ReplyDelete
  2. What bugs will this rewrite fix?
    In the long run, can we get "source clipping" added to the appropriate places, so we don't need a "slow path" in this code?

    ReplyDelete
  3. Robert O'Callahan14 October 2008 08:35

    Bill: the biggest piece of bling (SVG clip-path/mask/filter for HTML) landed on trunk a while ago:
    http://developer.mozilla.org/web-tech/2008/09/15/svg-effects-for-html-content/
    See also
    http://developer.mozilla.org/web-tech/2008/10/10/svg-external-document-references/
    I suppose I should do a little followup blog post about that.
    Jesse: The main user-visible bug that will be fixed is bug 446100.
    It's up to gfx guys like Joe and Jeff to figure out how to optimize the source clipping issues. I'm sure there are things we can do, but I don't know what the best approach will be.

    ReplyDelete
  4. Those effects are great, but I was also interested in using SVG gradient, et. al. as described here:
    http://weblogs.mozillazine.org/roc/archives/2008/07/svg_paint_serve.html
    Here's why: the three main effects used by developers are 1) rounded corners 2) drop shadows and 3) gradients. The first 2 are handled by Mozilla now, but the third is not.
    I'm assuming here that no one at Mozilla has decided to implement -webkit-gradient... ;-). Also, it seems like your 'use an SVG or canvas element as a background' approach is more flexible than -webkit-gradient, -webkit-..., etc. etc.
    Is it possible that the 'paint server' stuff is gonna make it into 3.1?
    Again, thanks for your work here and for time to answer my questions. Also, should you need a bribe of a fine wine, let me know :-D.
    Cheers,
    - Bill

    ReplyDelete
  5. Question: Have you tested this with animations? Say, moving an image by 10 pixels over the course of 5 seconds?
    Snapping to a grid always causes issues when you start to animate it. Flash makes this especially visible by animating lines, as those are snapped to the pixel grid in Flash < 8. Another bad example is fonts, where the size and the kerning depend on the pixel grid.
    Flash solves this problem by doing 4xAA and aligning to the resulting pixels, as this gives a mostly smooth animation and avoids seams. However, I have no clue if they really render 16x as many pixels and downscale or if they have some smartness for partial pixels involved.

    ReplyDelete
  6. Robert O'Callahan14 October 2008 10:49

    Bill, you inspired me to write a new blog post about the SVG effects status for FF3.1. Short answer: pushing the SVG paint-server stuff into 3.1/Gecko 1.9.1 is not a priority for me, and it's probably a bit too late. I'll probably do it in 3.2 instead along with SVG background-images.
    Benjamin: we've *always* snapped to the pixel grid in some way or another. This is just systematizing what we're doing. I don't think even 4xAA would be good enough for us, black lines that look gray are just unacceptable.
    There is indeed a quandary with regard to animation, but the fact is that all browsers pixel-align everything (in HTML at least), because most browsers don't even have subpixel layout internally, so we're not making things worse for animation. We don't pixel-align anything in SVG, and in theory you can use text-rendering:geometricPrecision there to turn off hinting and make text "safe for animation", so maybe that's one escape hatch. Maybe we could implement text-renering:geometricPrecision for HTML too. Also, currently when there's anything but a transform+scale in the matrix, we give up on pixel-snapping completely (as you'd expect).

    ReplyDelete
  7. I think it's brilliant how your heuristics extract "hints" from the CSS/SVG for what to do. Do you think that as the resolution of display devices approaches paper, that many of these techniques will simplify? I'm not saying low res devices will go away, just that the average person will be using at least one 300dpi or more monitor. When a real pixel is smaller than today's subpixels, most of the anti-aliasing techniques should be unnecessary, right? I mean, your careful rounding and snapping will still be required for correctly aligning elements, but possibly not for actually drawing them.
    Finally, will this also improve font kerning and spacing at certain (weird) zoom levels as well?
    If so, then I'm crossing my fingers this makes it into Gecko 1.9.1 (final).
    Thanks

    ReplyDelete
  8. Robert O'Callahan15 October 2008 03:09

    Yes, with very high-DPI devices snapping is much less important and we may be able to do away with per-pixel antialiasing.
    What kerning and spacing bugs are these? Are they on file in Bugzilla?

    ReplyDelete
  9. Sorry, wasn't expecting a reply. Thanks for it though. As for the bugs, in Fx 3.0 RELEASE, I would get weird font kerning at odd zoom levels on multiple computers (Windows only). Glyph spacing would be too close or too far apart when I set the browser.display.auto_quality_min_font_size to 0.
    I was going to check for font related regressions or bugs, but in Firefox 3.0.2 and higher, I am no longer able to reproduce these bugs. EVER. So, yeah, my bad.
    Still, thanks for all your (and others') hard work. Mozilla text rendering is now beautiful, and I PREFER min_font_size at 0. I can live with the perf hit.

    ReplyDelete