神刀安全网

OpenType MATH in HarfBuzz

TL;DR:

In the context of Igalia browser team effort to implement MathML support using TeX rules and OpenType features , I have started implementation of OpenType MATH support in HarfBuzz . This table from the OpenType standard is made of three subtables:

Code to parse this table was added to Gecko and WebKit two years ago. The existing code to build glyph assembly in these Web engines was adapted to use the MathVariants data instead of only private tables. However, as we will see below the MathVariants data to build glyph assembly is more general, with arbitrary number of glyphs or with additional constraints on glyph overlaps. Also there are various fallback mechanisms for old fonts and other bugs that I think we could get rid of when we move to OpenType MATH fonts only.

In order to add MathML support in Blink, it is very easy to import the OpenType MATH parsing code from WebKit . However, after discussions with some Google developers, it seems that the best option is to directly add support for this table in HarfBuzz. Since this library is used by Gecko, by WebKit (at least the GTK port) and by many other applications such as Servo, XeTeX or LibreOffice it make senses to share the implementation to improve math rendering everywhere.

The idea for HarfBuzz is to add an API to

It is then up to a higher-level math rendering engine (e.g. TeX or MathML rendering engines) to beautifully display mathematical formulas using this API. The design choice for exposing MathConstants and MathGlyphInfo is almost obvious from the reading of the MATH table specification. The choice for the shaping API is a bit more complex and discussions is still in progress. For example because we want to accept stretching after glyph-level mirroring (e.g. to draw RTL clockwise integrals) we should accept any glyph and not just an input Unicode strings as it is the case for other HarfBuzz shaping functions. This shaping also depends on a stretching direction (horizontal/vertical) or on a target size (and Gecko even currently has various ways to approximate that target size). Finally, we should also have a way to expose italic correction for a glyph assembly or to approximate preferred width for Web rendering engines.

As I mentioned at the beginning, the data and algorithm to build glyph assembly is the most complex part of the OpenType MATH and deserves a special interest. The idea is that you have a list of
n 1

glyphs available to build the assembly. For each
0 i n 1

, the glyph
g i

has advance
a i

in the stretch direction. Each
g i

has straight connector part at its start (of length
s i

) and at its end (of length
e i

) so that we can align the glyphs on the stretch axis and glue them together. Also, some of the glyphs are “extenders” which means that they can be repeated 0, 1 or more times to make the assembly as large as possible. Finally, the end/start connectors of consecutive glyphs must overlap by at least a fixed value
o min

to avoid gaps at some resolutions but of course without exceeding the length of the corresponding connectors. This gives some flexibility to adjust the size of the assembly and get closer to the target size
t

.

g i

s i

e i

a i

g i + 1

s i + 1

e i + 1

a i + 1

o i , i + 1

Figure 0.1: Two adjacent glyphs in an assembly

To ensure that the width/height is distributed equally and the symmetry of the shape is preserved, the MATH table specification suggests the following iterative algorithm to determine the number of extenders and the connector overlaps to reach a minimal target size
t

:

We note that at each step, each extender is repeated the same number of times
r 0

. So if
I Ext

(respectively
I NonExt

) is the set of indices
0 i n 1

such that
g i

is an extender (respectively is not an extender) we have
r i = r

(respectively
r i = 1

). The size we can reach at step
r

is at most the one obtained with the minimal connector overlap
o min

that is

i = 0 N 1 ( j = 0 r i a i o min ) + o min = ( i I Ext a i o min ) + ( i I NonExt r ( a i o min ) ) + o min

We let
N Ext = | I Ext |

and
N NonExt = | I NonExt |

be the number of extenders and non-extenders. We also let
S Ext = i I Ext a i

and
S NonExt = i I NonExt a i

be the sum of advances for extenders and non-extenders. If we want the advance of the glyph assembly to reach the minimal size
t

then

S NonExt o min ( N NonExt 1 ) + r ( S Ext o min N Ext ) t

We can assume
r r min = max ( 0 , t S NonExt + o min ( N NonExt 1 ) S Ext o min N Ext )

This provides a first simplification of the algorithm sketched in the MATH table specification: Directly start iteration at step
r min

. Note that at each step we start at possibly different maximum overlaps and decrease all of them by a same value. It is not clear what to do when one of the overlap reaches
o min

while others can still be decreased. However, the sketched algorithm says all the connectors should reach minimum overlap before the next increment of
r

, which means the target size will indeed be reached at step
r min

.

One possible interpretation is to stop overlap decreasing for the adjacent connectors that reached minimum overlap and to continue uniform decreasing for the others until all the connectors reach minimum overlap. In that case we may lose equal distribution or symmetry. In practice, this should probably not matter much. So we propose instead the dual option which should behave more or less the same in most cases: Start with all overlaps set to
o min

and increase them evenly to reach a same value
o

. By the same reasoning as above we want the inequality

S NonExt o ( N NonExt 1 ) + r min ( S Ext o N Ext ) t

which can be rewritten

S NonExt + r min S Ext o ( N NonExt + r min N Ext 1 ) t

We note that
N = N NonExt + r min N Ext

is just the exact number of glyphs used in the assembly. If there is only a single glyph, then the overlap value is irrelevant so we can assume
N NonExt + r N Ext 1 = N 1 1

. This provides the greatest theorical value for the overlap
o

:

o min o o max theorical = S NonExt + r min S Ext t N NonExt + r min N Ext 1

Of course, we also have to take into account the limit imposed by the start and end connector lengths. So
o max

must also be at most
min ( e i , s i + 1 )

for
0 i n 2

. But if
r min 2

then extender copies are connected and so
o max

must also be at most
min ( e i , s i )

for
i I Ext

. To summarize,
o max

is the minimum of
o max theorical

, of
e i

for
0 i n 2

, of
s i 1 i n 1

and possibly of
e 0

(if
0 I Ext

) and of of
s n 1

(if
n 1 I Ext

).

With the algorithm described above
N Ext

,
N NonExt

,
S Ext

,
S NonExt

and
r min

and
o max

can all be obtained using simple loops on the glyphs
g i

and so the complexity is
O ( n )

. In practice
n

is small: For existing fonts, assemblies are made of at most three non-extenders and two extenders that is
n 5

(incidentally, Gecko and WebKit do not currently support larger values of
n

). This means that all the operations described above can be considered to have constant complexity. This is much better than a naive implementation of the iterative algorithm sketched in the OpenType MATH table specification which seems to require at worst

r = 0 r min 1 N NonExt + r N Ext = N NonExt r min + r min ( r min 1 ) 2 N Ext = O ( n × r min 2 )

and at least
Ω ( r min )

.

One of issue is that the number of extender repetitions
r min

and the number of glyphs in the assembly
N

can become arbitrary large since the target size
t

can take large values e.g. if one writes /underbrace{/hspace{65535em}} in LaTeX. The improvement proposed here does not solve that issue since setting the coordinates of each glyph in the assembly and painting them require
Θ ( N )

operations as well as (in the case of HarfBuzz) a glyph buffer of size
N

. However, such large stretchy operators do not happen in real-life mathematical formulas. Hence to avoid possible hangs in Web engines a solution is to impose a maximum limit
N max

for the number of glyph in the assembly so that the complexity is limited by the size of the DOM tree. Currently, the proposal for HarfBuzz is
N max = 128

. This means that if each assembly glyph is 1em large you won’t be able to draw stretchy operators of size more than 128em, which sounds a quite reasonable bound. With the above proposal,
r min

and so
N

can be determined very quickly and the cases
N N max

rejected, so that we avoid losing time with such edge cases…

Finally, because in our proposal we use the same overlap
o

everywhere an alternative for HarfBuzz would be to set the output buffer size to
n

(i.e. ignore
r 1

copies of each extender and only keep the first one). This will leave gaps that the client can fix by repeating extenders as long as
o

is also provided. Then HarfBuzz math shaping can be done with a complexity in time and space of just
O ( n )

and it will be up to the client to optimize or limit the painting of extenders for large values of
N

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » OpenType MATH in HarfBuzz

分享到:更多 ()

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

© 2016 神刀安全网   网站地图 蜀ICP备14009168号-1

分享按钮