17 Jun 2002 raph   » (Master)

Fitz replies

kai: I'm unaware of the node design in OpenGL display lists, but they sound interesting. The OpenGL folks seem quite performance oriented. Do you by chance have a good reference?

For normal horizontally placed text, the default will be 1/4 pixel horizontally, and a whole pixel in the vertical direction. These defaults are based on fairly careful empirical study. 1/4 pixel horizontal positioning is nearly indistinguishable in quality from ultraprecise positioning, while 1/2 pixel is not quite enough. Vertically, alignment with the baseline helps rendering quality. The only real downside is that line spacing may become slightly irregular. I doubt this will be much of a problem in practice, though.

For vertically oriented text, I'll probably just switch the axes, but I'm not sure, as I haven't done any kind of careful study.

Finally, for rotated text (not aligned with either axis), I'll turn off caching altogether, because the hit rate is likely to be low.

As for progressive rendering, it's not high on my list of interests. I don't expect that the difference in performance between low quality and high quality modes will be enough to justify the complexity. And, as you suggest, it becomes less interesting as systems get faster.

mslicker writes: raph, I have to ask, what problem are you trying to solve?

This is absolutely the right question. I haven't written it down explicitly, and for that I apologize. The top-level problem is rendering a 2D graphics images provided by the client. At first, the main client will be Ghostscript, so the images will be PostScript and PDF files, but I expect interactive applications will use the library as well.

Then, there are several subgoals. Performance is critical. Memory utilization is also very important in some applications (especially embedded printers, which have very limited hardware). Even on desktops, using less memory is usually a big win, because of memory hierarchy effects. Quality of rendering is critical, but doesn't directly affect the tree API.

Given these constraints, I'd also like the client API to be clean and simple, even when the implementation does sophisticated things under the hood. I want to do a extensive unit and regression testing, and I feel that Python is a good language for these, so Python bindings are also important.

So why am I arriving at a general tree infrastructure? For one, the imaging model includes PDF 1.4 transparency, which has a very strong tree structure. Optimized rendering requires analysis of the tree. The painter's algorithm won't work as well.

And the simplest tree implementation, one in-memory object per node, is far too expensive in memory utilization when the tree is very large, or the available memory is limited. Thus, it's important to store the tree in a concise format, competitive with Ghostscript's existing "command list" at the least. I can easily envision multiple tree implementations tuned for different tasks. The simple, in-memory one will be implemented first anyway, because of its simplicity. I am not a fan of gratuitous virtualization, but when you have two different implementations of the same conceptual interfact, it's often a good idea.

At this point, I'm exploring the design space. This exploration is informed by thinking about more general problems, lots of them from my DOM experience. When a general approach is good, I'll use it. However, when generality forces unpleasant tradeoffs, within Fitz it will be a casualty. I am spending time thinking about more general trees so I know which is which.

I haven't written up Fitz in any real detail yet. In some ways, it's unfair to be blogging it, because you see the raw thinking without needed context. When I get to start work on Fitz in earnest, I will do much writing, and it will all be very accessible. But I have to concentrate on several hard problems for the upcoming Ghostscript 8.0 release first.

Latest blog entries     Older blog entries

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!