MuPdf / Fitz

[Raph Levien]

On Wed, Jul 10, 2002 at 08:43:40PM +0200, Tor Andersson wrote:
> Incoherent Rambling Thoughts on Fitz
> 
> For background, check my last advogato diary post,
> and the pages on my personal Wiki:
> 
> http://www.advogato.org/person/tor/diary.html?start=4
> http://spacecow.df.lth.se/wiki.cgi/AeKit
> http://spacecow.df.lth.se/wiki.cgi/LibRune
> http://spacecow.df.lth.se/wiki.cgi/RhoadsThor

Great. You and I have obviously covered a lot of the same ground. My
custom font is "LeBe": 

http://www.levien.com/~raph/lebe.ps

My reimplementation of the Tex H&J algorithms is LibHnj. You might be
interested in the code; it's has some thought put in to efficient
implementation. The whole-paragraph justification is based on a
priority queue, but the implementation actually in LibHnj is the dumb
O(n) one. I have O(log n) priority queue code in the new Libart
intersector. Even with the O(n) code, it's pretty fast.

> What I Want from Fitz

I'll respond to this by saying something about the priority of each
of your desiderata.

> * Resolution and device independent rendering of graphics + text

This is fairly central.

> * Good for both on-screen display and generating printable files

Raster rendering is a top priority. Higher level output is not an
immediate priority for me, but is obviously important. In any case,
the "display tree" in Fitz preserves the graphics structure at a
relatively high level, so outputting it to printable formats makes
sense. The big trick is (as always) putting an interface on the fonts
so they can be exported and embedded into PS and PDF files. There's
a ton of logic for this in GS's PS->PDF conversion code paths.

Over the longer term, it might make sense to switch GS over to the
Fitz display tree for PDF output in addition to rasterizing. But,
again, this isn't high on my priorities.

> * High-quality text: subpixel-positioned unhinted fonts

A given.

> * Good font handling, with all the meta information necessary for typography:
> kerning, contextual glyph replacement, ligatures, etc...

The meta information is beyond the scope of the PDF imaging model, and
thus probably beyond the scope of the Fitz core. It's a very worthwhile
project, and possibly deserves "brother" status.

Note that defining an API for text rendering is a Hard Problem. ATSUI
and Uniscribe are the leading proprietary API's now available. Both
are big, heavy beasts.

Probably the most advanced free layout engine is Pango. It's geared
for Gtk+ and fairly low-quality typographic rendering, but is quite
sophisticated when it comes to bidi, i18n, and so on.

> * Be able to drive a GUI toolkit: responsive speed.

Yes. This splits into two halves: fast RGB rendering, which is a
critical priority; and good support for incremental updates (Region of
Interest, caching of intermediate results, etc.). The latter isn't
commercially critical, but I would like to see it well designed.

> * API should fit with: interactive graphics and text editing as well as
> a foundation for a toolkit.

In general, I agree, but unfortunately as stated it's pretty vague.

> ----
> 
> Immediate mode -- for old-style procedural (Quickdraw/OpenGL) rendering
> 
> Editable display tree with automatic re-rendering -- when the app can be well
> integrated with Fitz' model

Yes, both immediate and display tree are critically important.

> Fonts ... personally I'd just skip hinting and be well rid of that extra
> layer of complexity. But for 1-bit rendering on low-res devices I suppose
> that it is a must. How common are they? Is it worth it? We still need
> sub-pixel correct widths when calculating, line breaks should not be
> dependent on output device/resolution.

I agree that unhinted should be the default for aa rendering. For non-aa,
hinting is a big win up to 300 dpi, and more or less optional at 600 dpi
and up. The res of printers is going up, but I'd still like to support
hinting.

The PDF imaging model has sub-pixel accurate widths. On the other hand,
the imaging model is not where "line breaks" happen.

But I fear this is not the whole story. The DynaLab TrueType fonts
(very common for CJK, as Microsoft ships them with Word and IE)
_require_ hinting to render correctly. Adobe Acrobat has a workaround
that interprets the hints well enough to correct the outlines, so that
the results can be rendered unhinted. We will probably implement this
workaround, as well.

Also, look at the Type1 font rendering in Acrobat Reader 5 (including
the Linux version). It does "subtle hinting", which increases
rendering contrast, but only through subtle distortions. It does not
quantize stroke widths to integers, for example. Over the long term,
I would like to support "subtle hinting".

> As for substituting fonts, my opinion is that it's a waste of time
> to put this in Fitz. If necessary, it's a job for Fontconfig or an external
> library. Fitz should deal with scalable outlines only. Other tools can deal
> with generating font outlines from various formats.

Good font substitution is critical for PDF rendering. Note that PDF
embeds a "Widths" array even when the glyph outlines are not present.
Thus, it's possible to synthesize reasonably good-looking output from
suitable multiple master fonts. GS can render MM fonts, but there are
no free ones available, and GS lacks the logic to automatically
instantiate the MM font from the Widths table. Over the longer term,
I'd like to see free MM fonts drawn.

Another critical area is CJK fonts. These actually _can_ substitute
with little loss of quality, because the metrics are so
straightforward (all Hanzi have the same metrics rectangle). In addition,
it's common to move files around without the CJK glyphs embedded. So,
in this context, substitution is both desirable and important. What
makes it particularly tricky is that, most often, the file specifies
a T1 font, but the font available for substitution is TT.

> If an application needs a certain font for good typesetting, a poor
> substitute is not an option. Look at TeX, it thrives on its predictability. If
> the same document were to generate different output depending on where it
> was run through TeX people would be most unhappy.

Yes, and TeX is amazing that way. Among other things, it does _all_
computation using fixed point, so that fp rounding errors can't affect
the result.

But, again, are we doing rendering or layout? PDF specifies the interface
after layout but before rendering. Thus, results are quite consistent,
even when a font has to get substituted.

> Are we sure we want to deal with supporting all the old drawing apis as
> backends? (GDI, Quartz, Quickdraw, X11)
> Sure, providing hooks for old renderers is nice in theory, but dealing
> with all the various quirks in font handling could prove to be more trouble
> than we are willing to put up with. But then, we could do our own font
> management and push bitmaps. XRender is going in the right direction,
> and is still young enough to fix if problems arise.

The priority is to get RGB rendering to be as fast as possible. Other
drawing API's are only justified as far as they provide a quantitative
improvement in rendering speed. In the absence of hardware acceleration,
I expect Fitz to be faster in most cases anyway.

Note, though, that a requirement above is to support PS and PDF as
output backends. Thus, we will _have_ to deal with impedance mismatch
in drawing models. In most cases, there will have to be an analysis
step to determine whether the tree can be drawn through the API, and
negotiate falling back to raster rendering in the cases when not.

> Do we use floats or fixed point math?

Big question. I'm still grappling with it.

> Analytic AA or supersampled? Supersampled is conceptually easier, but
> degenerate cases (horiz/vertical) lines are rather common.

I'm a big fan of analytic aa.

Even so, in display tree modes, I'm also interested in what I call
"exact" aa. In this mode, you do a little analysis phase to determine
whether edges from two or more objects cross a pixel. If so, you
render the entire display tree supersampled, and downsample at the
end. Otherwise, your analytical aa wins. This will get rid of the
"seams" from abutting objects in aa mode.

> Which color space internally? Gamma 1.0 is good for AA calcs, but when
> using 8-bit color components you lose on precision.

This is a complicated question. PDF mandates a fair amount of color
space conversion, including ICC profiles. I'm also interested in
providing 16 bit output for printing applications. But if you can
do the transforms 8-to-8 without losing too much precision, it's a
big efficiency win.

Doing aa in a luminance-linear space is not _always_ better than doing
it in a perceptually linear space.

> What is "stroke adjustment"? I never quite understood that.

In the goals doc, it should be both "stroke adjustment" and "fill adjust".

Basically, stroke adjustment is a simple form of hinting for the
"stroke" operator. The width is quantized so that both edges of a
diagonal line step in sync. If they step out of sync, then you
alternate between i and i+1 pixels in the rendering. This is, of
course, most critical when i is 1 or 2.

By far the most elegant presentation of stroke adjustment is the
polygonal pen of Metafont. I'm actually not too familiar with the
details of how Ghostscript's stroke adjustment works, but I wouldn't
be surprised if Metafont's was better.

The PS rendering model specifies that, in non-aa mode, any pixel
touched by a path is colored. This tends to darken rendering
considerably compared with the more common center-of-pixel rule. The
any-part-of-pixel rule has several important consequences: for one,
you don't get dropouts when filling delicate paths. For two, you don't
get a seam when rendering abutting objects. Both are critically
important in real non-aa rendering applications.

> I presume Fitz will be written in ANSI C.

That's where I'm leaning. C++ is also on the table, though.

> We should really really really get fonts right. It's one of the messiest
> problems in systems today. Fontconfig goes a long way to solve some issues,
> but is not panacea.

I agree, but within the context of Fitz, my feeling is just to render
all fonts required by PDF. I get the strong feeling that finding the
fonts available on your system, and laying out text using them, should
be the subject of another library.

Thanks for your input. I hope my answers have shed more light on
my thoughts for Fitz.

Raph