xmlgraphics-fop-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Apache Wiki <wikidi...@apache.org>
Subject [Xmlgraphics-fop Wiki] Update of "GoogleSummerOfCode2006/FloatsImplementationProgress/ImplementingSideFloats" by VincentHennebert
Date Fri, 11 Aug 2006 10:53:46 GMT
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/ImplementingSideFloats

The comment on the change is:
Difficulties around side-floats

------------------------------------------------------------------------------
   6. idem
   7. a start-float is pulled towards the before until it touches one of the 3 guide-lines;
if this is the start-guide this corresponds to the triggering of this rule:
  
- http://atvaark.dyndns.org/~vincent/side-floats_placement-rule7.png
+  http://atvaark.dyndns.org/~vincent/side-floats_placement-rule7.png
  
   8.#8 the side-float is pulled towards the before as much as possible
   9. the side-float is pulled towards the start/end as much as possible, but after having
been pulled towards the before
@@ -183, +183 @@

  
  So this model should provide a rather simple way to place side-floats. The most difficult
part will be to find a suitable data structure for representing the guide snagged line, in
order to easily compute it and update it.
  
- Now I have to look at how to integrate such a model into Fop's code.
+ 
+ == Side-floats and the Knuth Approach ==
+ We saw that the previous algorithm makes it easy to place side-floats while following the
placement rules. However, there is one thing which is unknown when lines are typeset: the
bottom of the page.
+ 
+ In the current code paragraphs are broken into lines without having even started to think
about page breaks. This works well excepted in the case where pages may have differing widths
(see PageLayout/InfluenceOfPageSizesOnAlgorithm). Now there is an additional difficulty: how
to know if there will be enough room on the page to place a side-float? And if there isn't
enough room, what should be done? Split the side-float? Defer it to the next page?
+ 
+ The resulting layout may be quite different then, as may be seen on the following figure:
+ 
+ http://atvaark.dyndns.org/~vincent/side-floats_page-break.png
+ 
+ We may choose to either differ a side-float, or shrink it so that it fits on the page, or
split it to put one piece on each page.
+ 
+ We could try to combine in some way the informations about line-breaking as well as page-breaking.
For each feasible line-break we would also store informations regarding page breaking: does
it also represent a legal page-break? If yes, is it a feasible page-break? And then the following
line is computed in two different situations: whether the previous line-break was also chosen
as a page-break (in which case the available width is the ipd of the following page), or not
(and the available width is the ipd of the current page).
+ 
+ http://atvaark.dyndns.org/~vincent/mixing-line-page-breaks.png
+ 
+ This situation leads to approximately doubling the Knuth nodes for the rest of the paragraph:
one set for the case where the line is on the current page, one other set for the case where
the line is put on the following page. Of course the nodes don't represent the same feasible
breaks, as line widths are different. But there are approximately as many in each case.
+ 
+ If the current page may contain up to two additional lines of the paragraph, this leads
to three times as many nodes. If n lines may be put on the current page, there will be (n+1)
times as many nodes.
+ 
+ For side-floats, the handling would be similar: when placing a side-float we consider the
location of the current line: if it is at the "bottom" of the page (first possibility above),
there may be no room for the float which would be placed on the following page. If it is at
the "top" of the following page, then there is room for the float. If the float is shrinkable
or stretchable, this leads to additional possibilities. If there are more than one float to
handle, this may well lead to a combinatorial explosion...
+ 
+ There is another problem in this model regarding orphans: when we have found a feasible
break for a paragraph, we don't know yet whether the corresponding line will be the next to
last or not. If this is the case then the line-break is not a legal page-break. We would thus
have to implement some backtracking mechanism, to disable the page-break possibility if it
turns out that the line was the next to last in the paragraph. There may well be similar problems
with keep-with-previous settings.
+ 
+ One thing we could do is place all the side-floats without considering page boundaries,
and then generate legal page-breaks afterwards, where possible. This is pretty like is currently
done, IIC. This approach would have the following limitations:
+  * the float shrinkability would not be taken into account, only the optimal dimension would
be considered (but anyway, in real-life use-cases there would be probably few elastic side-floats);
+  * a legal page-break inside a side-float would be considered only if it coincides with
a normal line's legal page-break (also a minor issue);
+  * and most of all, we would never consider to defer a side-float on a following page to
permit a page-break. This might lead to very large chunks of text without any break possibility:
+ 
+  http://atvaark.dyndns.org/~vincent/side-floats_no-break-poss.png
+ 
+ That said, such situations should be rather uncommon and this method should work in most
cases. It might be a good solution for a first implementation.
+ 
  
  
  '''Credits'''

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


Mime
View raw message