Thursday 24 May 2007
The Glyph Bounds Problem
New textframe is looking pretty good. I'm dogfooding it and so are a few other people. The list of regressions is fairly short. We should be able to turn it on as soon as the tree opens for alpha6.
In the meantime I'm thinking about the glyph bounds problem. This is the problem of certain characters in certain fonts having glyphs that are particularly large, and fall outside the "font box" for the glyph: i.e. the glyph extends above the font's specified ascent, below the font's specified descent, to the left of the glyph origin ("left bearing"), or to the right of the glyph advance ("right bearing"). When a text frame contains such glyphs, we need to carefully compute the "overflow area" --- the union of the extents of the (positioned) glyphs --- when we lay out the text. That lets us redraw the correct area efficiently if the text moves or changes. Since time immemorial we have assumed no glyphs overflow their font boxes, which is plain wrong and getting more wrong as fonts get fancier...
The hard part (as often in the world of browser text) is performance. For example, the Mac implementation of cairo_glyph_extents gets the glyph extents by retrieving the glyph outline curves from ATS and computing their bounding boxes with grim mathematics. There's no way in the world we could apply that to each glyph, even with caching. The other Mac APIs aren't better, I'm told, and the other platforms aren't looking good performance-wise either.
One possible approach is to exploit the fact that normally we only care about glyph bounds if they overflow the font box. If we could examine the font and determine cheaply for each glyph if it's guaranteed to not overflow the font box, we'd be fast on most fonts and pages, where these check will succeed and we won't need the exact bounds for the glyphs. Looking at the OpenType/TrueType font format, the 'glyf' table contains, for each glyph, min/max x and y coordinates for the glyph. But this data does not take hinting into account. Hinting could make the glyph larger than that box.
Perhaps we can be a little conservative and assume that hinting will make the glyph at most ascend one more pixel, and descend one more pixel. We could also assume that hinting will not increase the left bearing and will not increase the glyph right bearing (because its hinted advance should increase if the glyph width does). Of course these are just heuristics, and it would be a good idea test them against a large collection of fonts to see if they hold. But if they hold, we should be able to use the 'glyf' data to quickly rule out overflow for a large number of glyphs.
There is one more problem: when we actually compute the bounding box approximation for a string of glyphs, our glyph advances may include kerning. The font box definition above assumed no kerning. This probably won't worry us in practice because we generally measure substrings that end with spaces or have no characters following them, so there is no kerning across the end of the substring.
Grabbing and analyzing these tables could still be expensive. I wish there was a better way, but I can't see one right now. Possibly the way to go, if it was practical, would be to abandon "overflow areas" in Gecko, but then we repaint a lot more than we have to when documents change dynamically.
One remaining card we can play is to identify common fonts that have no overflowing glyphs and hardcode that knowledge into Gecko to avoid looking up tables. That would be ugly, but expedient.
Comments
Excluding the letter "f"? That optimization won't get very far otherwise; almost every font in existence has an overflowing "f".
"I just read about another interresting initiative that aims at " providing a single place in the free desktop software stack to add support for new complex languages and provide consistent behavior across applications when it comes to text shaping."
http://labs.trolltech.com/blogs/2007/03/30/working-towards-a-unified-text-layout-engine-for-the-free-desktop-software-stack/
(Long time no talk, by the way! Brendan Eich mentioned your blog and I've been reading for a couple of week.)
Per glyph bounds calculations on the Mac, I presume there's a reason you can't use ATSUGlyphGetScreenMetrics in ATSUnicodeGlyphs.h? You can pass in a list of glyph IDs, and description of the style being used to render the glyphs, and get back the "the specified glyphs' advance and side bearings, top left, height, and width".
If you have an ATS layout object, there are also low-level APIs in ATSUnicodeDirectAccess.h that allow you to get into the low-level datastructures used to render each layout.
If these APIs aren't sufficient for you, drop me a line and I'd be happy to help work through the details.
Thank you
Presumably *some* piece of code must know that at that point, because some piece of code just drew the pixels that didn't lie within those boxes. But the question is whether that knowledge is available at a layer where you can make use of the information.
If so, you could keep a table at runtime of which fonts have ever overflowed their boxes in any string that has ever been rendered / laid out since the program was launched, updating that table if a font that previously had never overflowed suddenly does so. That way you don't need any ugly hardcoded knowledge, and while it's possible to have a font which might overflow that's not in the table, by definition that doesn't matter, because it hasn't overflowed on any string you've ever seen yet...
> almost every font in existence has an overflowing
> "f".
It does? I'd be surprised, since then I think we'd see bugs about f-related garbage in Gecko.
pagalmes: yes, I know about it. Since we're using Pango on Linux, we benefit from it. One day it might be interesting to consider using it directly.
Jim: Looong time no see. Thanks for the info. ATSUGlyphGetScreenMetrics didn't work when Brian Ewins tried to use it in cairo. I'll follow up in email, thanks! We are using the direct access APIs but you can't get glyph boudns that way.
Peter: yes, soft hyphens work with the new textframe.
Stuart: right, this information must exist at least by the time the glyph is drawn. But we need it at layout time and it would be nice to get it without having to rasterize every glyph, since typically we render fewer glyphs than we measure.
One complication with the scheme I presented in this blog post is that it can't handle situations where the font engine is manipulating the outlines in ways that could cause overflow. For example, italicization using a shear matrix. So maybe this scheme won't be very useful :-(.
I'm sure there are at least a couple bugs; I can't find them at the moment. There aren't many bugs filed because it's only a few pixels for normal font sizes and we normally invalidate more than the absolute minimum.
Simple testcase:
data:text/html,<body style="font-family: sans-serif; font-size: 150px"><div style="overflow:hidden"><div style="overflow:hidden;float:left">asdf</div></div><div id="hide" style="border: solid; width: 0px">asdf</div><div><button onclick="document.getElementById('hide').style.visibility='hidden';">hide div</button></div>
On Windows at least, clicking the button leaves junk for many fonts; the problem is a lot worse for serif fonts. (Times New Roman leaves a garbage pixels even at 16px font-size; Arial doesn't start leaving garbage until a little under 30px.) The problems get worse with italics.
Opacity makes things worse; it cuts off an additional pixel.
But perhaps I'm misunderstanding the issue - your comment about needing the tighter bounding boxes for when text is moved or redrawn implies they high-quality metrics can be delayed until then to me, but then again, I've got no real idea about how Gecko works...
(I was thinking about the technique of delaying any and all optimisations until they are actually needed from a couple of videos I've just been watching about Smalltalk/Self and Java JIT engines, and how one of the most successful approaches has been to JIT nothing, but have a counter on everything - and only after a certain threshold is hit, JIT that fragment into a LRU code cache.)
Edouard: you're really asking whether glyph bounding boxes can be computed lazily. That's something I've thought about. It might be possible but it might require significant changes to Gecko, changes that we don't have resources to make for Gecko 1.9.
And/or it could be pre-calculated in a separate thread with characters actually required being put in front of the list.
Or you could hardcode that if there's not Zapf in the name it will never extend more than some reasonable value like 1 em ;-)
There is at least one bug for "f"s.