[Xmlgraphics-fop Wiki] Update of "GoogleSummerOfCode2006/FloatsImplementationProgress" by VincentHennebert

[Apache Wiki <wi...@apache.org>]

Dear Wiki user,

You have subscribed to a wiki page or wiki category on "Xmlgraphics-fop Wiki" for change notification.

The following page has been changed by VincentHennebert:
http://wiki.apache.org/xmlgraphics-fop/GoogleSummerOfCode2006/FloatsImplementationProgress

The comment on the change is:
Progress informations about the implementation of floats.

New page:
This page will contain various informations about how the project progresses: thoughts, issues, design decisions, etc.

= Phase 1: Documentation =
I'm planning to read the following literature:
 * "Digital Typography", Knuth: glue/box/penalty model, optimal line-breaking algorithm
 * "Pagination Reconsidered", Brüggemann-Klein, Klein, Wohlfeil: a better algorithm for placing floating objects than TeX's one.
 * Pages of this Wiki related to the Knuth Approach
 * Have a look at Simon Pepping's generalized glue/box/penalty model.

== "Digital Typography": Breaking Paragraphs into Lines ==
Some very early thoughts after a quick reading of this article.

The algorithm works when each line of the paragraph has a different length. This may be interesting for implementing side-floats, provided that we know in advance which height each line will have. And I think this may depend on the line-stacking strategy.

AFAICT from what I've read, we may decompose the algorithm in three rather independant parts:
 * building a sequence of glue/box/penalty elements from some input data;
 * defining a somewhat arbitrary formula used to compute the demerit of each break, and which is to be minimized;
 * the algorithm itself, which corresponds to a shortest path finding algorithm in a graph.

Regarding (before-)floats:
 * the fo:float element (with the "float" property set to "before") will have to be converted to a sequence of glue/box/penalty elements, which themselves will have to be inserted at the beginning of certain pages;
 * the formula used to determine the optimality of floats placements should be retrieved from the "Pagination Reconsidered" paper;
 * the line-breaking algorithm isn't designed to handle a floating sequence of g/b/p items. So it will have to be extended, probably by the algorithm found in "Pagination Reconsidered";
 * All what have been stated so far may be invalidated by further readings...

---------------------------------------------------------------------
To unsubscribe, e-mail: fop-commits-unsubscribe@xmlgraphics.apache.org
For additional commands, e-mail: fop-commits-help@xmlgraphics.apache.org