Differences between revisions 7 and 8
Revision 7 as of 2006-09-15 07:20:34
Size: 19538
Comment: Move the pictures to a more permanent location
Revision 8 as of 2009-09-20 23:52:15
Size: 19602
Editor: localhost
Comment: converted to 1.6 markup
Deletions are marked like this. Additions are marked like this.
Line 4: Line 4:
[[TableOfContents]] <<TableOfContents>>
Line 24: Line 24:
http://people.apache.org/~jeremias/fop/vincent/SideFloats/side-floats_coordinate-system.png {{http://people.apache.org/~jeremias/fop/vincent/SideFloats/side-floats_coordinate-system.png}}
Line 48: Line 48:
Here's a [http://people.apache.org/~jeremias/fop/vincent/SideFloats/side-floats.pdf pdf version] for those whose browser has difficulties displaying UTF-8 characters. Here's a [[http://people.apache.org/~jeremias/fop/vincent/SideFloats/side-floats.pdf|pdf version]] for those whose browser has difficulties displaying UTF-8 characters.
Line 134: Line 134:
http://people.apache.org/~jeremias/fop/vincent/SideFloats/side-floats_placement-start.png {{http://people.apache.org/~jeremias/fop/vincent/SideFloats/side-floats_placement-start.png}}
Line 140: Line 140:
http://people.apache.org/~jeremias/fop/vincent/SideFloats/side-floats_placement-float1_1.png
http://people.apache.org/~jeremias/fop/vincent/SideFloats/side-floats_placement-float1_2.png
http://people.apache.org/~jeremias/fop/vincent/SideFloats/side-floats_placement-float1_3.png
http://people.apache.org/~jeremias/fop/vincent/SideFloats/side-floats_placement-float1_4.png
{{http://people.apache.org/~jeremias/fop/vincent/SideFloats/side-floats_placement-float1_1.png}}
{{http://people.apache.org/~jeremias/fop/vincent/SideFloats/side-floats_placement-float1_2.png}}
{{http://people.apache.org/~jeremias/fop/vincent/SideFloats/side-floats_placement-float1_3.png}}
{{http://people.apache.org/~jeremias/fop/vincent/SideFloats/side-floats_placement-float1_4.png}}
Line 147: Line 147:
http://people.apache.org/~jeremias/fop/vincent/SideFloats/side-floats_placement-float2_1.png
http://people.apache.org/~jeremias/fop/vincent/SideFloats/side-floats_placement-float2_2.png
{{http://people.apache.org/~jeremias/fop/vincent/SideFloats/side-floats_placement-float2_1.png}}
{{http://people.apache.org/~jeremias/fop/vincent/SideFloats/side-floats_placement-float2_2.png}}
Line 154: Line 154:
http://people.apache.org/~jeremias/fop/vincent/SideFloats/side-floats_placement-float3.png {{http://people.apache.org/~jeremias/fop/vincent/SideFloats/side-floats_placement-float3.png}}
Line 158: Line 158:
http://people.apache.org/~jeremias/fop/vincent/SideFloats/side-floats_placement-float4.png {{http://people.apache.org/~jeremias/fop/vincent/SideFloats/side-floats_placement-float4.png}}
Line 163: Line 163:
http://people.apache.org/~jeremias/fop/vincent/SideFloats/side-floats_placement-shrink.png {{http://people.apache.org/~jeremias/fop/vincent/SideFloats/side-floats_placement-shrink.png}}
Line 175: Line 175:
 http://people.apache.org/~jeremias/fop/vincent/SideFloats/side-floats_placement-rule7.png  {{http://people.apache.org/~jeremias/fop/vincent/SideFloats/side-floats_placement-rule7.png}}
Line 192: Line 192:
http://people.apache.org/~jeremias/fop/vincent/SideFloats/side-floats_page-break.png {{http://people.apache.org/~jeremias/fop/vincent/SideFloats/side-floats_page-break.png}}
Line 198: Line 198:
http://people.apache.org/~jeremias/fop/vincent/SideFloats/mixing-line-page-breaks.png {{http://people.apache.org/~jeremias/fop/vincent/SideFloats/mixing-line-page-breaks.png}}
Line 213: Line 213:
 http://people.apache.org/~jeremias/fop/vincent/SideFloats/side-floats_no-break-poss.png  {{http://people.apache.org/~jeremias/fop/vincent/SideFloats/side-floats_no-break-poss.png}}
Line 221: Line 221:
A huge thanks to [http://www.inkscape.org/ Inkscape], who made the drawing of all those figures so easy. A huge thanks to [[http://www.inkscape.org/|Inkscape]], who made the drawing of all those figures so easy.

Contents

1. Formalizing the Problem

The specification of side-floats is in part taken from the CSS2 recommendation and adapted to XSL-FO. It may be useful to summarize and reformulate the spec to have a precise understanding of how side-floats should be handled.

An fo:float element with the "float" property set to "start" or "end":

  • generates a block-area of class "xsl-side-float", which also is a reference-area

  • is placed as a child of the nearest ancestor reference-area of the anchor-area or as a child of a later reference-area of the same chain
  • the length in the inline-progression-direction is the intrisic length of the area
  • border and padding should be set to zero on all edges of the side-float; the space properties don't apply to fo:float; as a consequence, the allocation-rectangle, border-rectangle, padding-rectangle and content-rectangle of a side-float area are the same
  • block-areas before and after the side-float flow in the block-progression-direction as if the float didn't exist. Line-areas are reduced to make room for the float

To formalize the rules of placement of side-floats, we will set up the following coordinate system:

  • the x-axis goes into the inline-progression-direction of the nearest ancestor reference-area;
  • the y-axis goes into the block-progression-direction;
  • the origin is the point of the reference-area's content-rectangle which is at the intersection of the start-edge and before-edge.

In such a coordinate-system, a side-float area is characterized by the (x,y) coordinates of its "start-before point", that is, the point of its allocation-rectangle (or border-rectangle, or padding-rectangle, or content-rectangle) which is at the intersection of the start-edge and before-edge.

http://people.apache.org/~jeremias/fop/vincent/SideFloats/side-floats_coordinate-system.png

1.1. Rules for Placing Side-floats

Some definitions:

  • we will call a start-float the block-area generated by an fo:float with "float"="start" or "left". Same for end-float
  • we will note start-float ≺ start-float' if start-float precedes start-float'; that is, the generating fo:float for start-float is before the generating fo:float for start-float' in the fo tree.

The nine rules given in the description of the "float" property may then be reformulated like the following:

  1. for a start-float, x ≥ 0

    for an end-float, x + ipd ≤ ipdref-area

  2. ∀ start-float' ≺ start-float, x > x' + ipd' or y > y' + bpd' ∀ end-float' ≺ end-float, x + ipd < x' or y > y' + bpd'

  3. ∀ start-float s, ∀ end-float e, [ys, ys + bpds] ∩ [ye, ye + bpde] ≠ ∅ ⇒ xs + ipds < xe

  4. y ≥ 0
  5. ∀ side-float' ≺ side-float, y ≥ y'

    ∀ block-area ≺ side-float, yside-float ≥ yblock-area, where yblock-area is the y-coordinate of the before-edge of the block-area's border-rectangle minus the block-area's space-before(.optimum?)

  6. ∀ line-area ≺ start-float, y ≥ y[before-edge of the line-area's allocation-rectangle]
  7. for a start-float, ipd ≤ ipdref-area ⇒ x + ipd ≤ ipdref-area for an end-float, ipd ≤ ipdref-area ⇒ x ≥ 0

  8. y should be minimized
  9. x should be minimized
  10. if "clear" = "left", "start", "both", ∀ start-float' ≺ side-float, y > y' + bpd' if "clear" = "right", "end", "both", ∀ end-float' ≺ side-float, y > y' + bpd'

Here's a pdf version for those whose browser has difficulties displaying UTF-8 characters.

1.2. Uncertainties

At the beginning of section 9.5 of the CSS2 recommendation, it is loosely explained how floats should be placed, and it is said that the precise placement rules should be found in the description of the "float" property.

Two hints are given at this place, of which only one may be retrieved in the precise rules:

  • the top of the floated box is aligned with the top of the current line box: this corresponds to rule 6
  • ... or bottom of the preceding block box if no line box exists.

This last point may occur in XSL-FO if the generated anchor area must be a block-area. AFAICT there is no rule for it in the description of the "float" property. Rule 5 would even let think that the top of the floated box should be aligned with the top of the previous block box. Moreover, in the CSS 2.1 candidate recommendation this sentence doesn't appear anymore.

That said, I think the behavior that most users would expect is to align the float with the bottom of the previous (non-floating) block box. This also is what is implemented by all the browsers I've tested (Konqueror, Safari, Firefox). So I think we may implement it like that too.

Another uncertainty is caused by the following sentence of section 9.5: "If there isn't enough horizontal room on the current line for the float, it is shifted downward, line by line, until a line has room for it." And what if the height of the float is less than the line-height? Should it still be shifted one entire line downward? This sentence is in contradiction with rule 8 (y should be minimized). In CSS 2.1 it has been rephrased such that "line by line" doesn't appear anymore. So I think we may go with CSS 2.1.

Finally, may side-floats be split on several pages? There is nothing about that in the XSL-FO spec. The chapter 13, "Page Media" of the CSS2 recommendation gives a small hint in section 13.3.6: we should "avoid breaking inside a floated element". If one uses side-floats to have margin notes, one can reasonably expect them to be split on several pages. Therefore, if it is simple enough to implement side-float breaking, I'll do it; if it involves too many changes or a too complicated algorithm, I'll leave it for now (note that Xep does not break side-floats, even if they are too big to fit on a page; they are simply discarded).

1.3. Computing Intrusion-adjustments

1.3.1. Definitions

Unless otherwise noted, the coordinates are those of the "start-before" vertex of the allocation-rectangle.

  • Let A be a side-float, B a block-area with the same nearest ancestor reference-area;
    • A, B inline-overlapping ⇔ [yA, yA + bpdA] ∩ [yB, yB + border-beforeB + padding-beforeB + bpdB + padding-afterB + border-afterB] ≠ ∅

  • Let A be a start-float, B a block-area with the same nearest ancestor reference-area;
    • A encroaches-upon B ⇔ A, B inline-overlapping and start-indentB < xA + ipdA Then start-encroachment(A,B) = xA + ipdA - start-indentB

  • Let A be an end-float, B a block-area with the same nearest ancestor reference-area;
    • A encroaches-upon B ⇔ A, B inline-overlapping and end-indentB < ipdA + end-indentA Then end-encroachment(A,B) = ipdA + end-indentA - end-indentB = ipdref-area - xA - end-indentB

1.3.2. Computation Rules

Let F be a formatting object to which the "intrusion-displace" property applies. Then:

  • if intrusion-displace = "none"
    • start-intrusion-adjustment = end-intrusion-adjustment = 0
  • if intrusion-displace = "line"
    • for each generated block-area B which is not a line-area:

      local-start-intrusion-adjustment =

      0 if parent-area = ref-area

      start-intrusion-adjustment of parent-area, otherwise

      Then start-intrusion-adjustmentB = max(local-start-intrusion-adjustmentB', B' normal block-area generated and returned by F)

    • for each generated line-area L

      start-intrusion-adjustment = max

      start-intrusion-adjustment(L parent)

      start-encroachment(A,L), A start-float such that A encroaches-upon L

  • if intrusion-displace="indent"
    • for each generated block-area B which is not a line-area:

      local-start-intrusion-adjustment =

      0 if parent-area = ref-area

      start-intrusion-adjustment of parent-area, otherwise

      Then start-intrusion-adjustmentB = max(local-start-intrusion-adjustmentB', B' normal block-area generated and returned by F)

    • for each generated line-area L

      start-intrusion-adjustment = max

      start-intrusion-adjustment(L parent)

      start-encroachment(A,L)

      A start-float such that A encroaches-upon L

      start-encroachment(A,B')

      A start-float such that A,L inline-overlapping

      B' block-area ancestor of L

      B' descendant of L nearest ancestor ref-area

      ∃ L' line-area child of B', A encroaches-upon L'

  • if intrusion-displace="block"
    • for each generated block-area B which is not a line-area:

      local-start-intrusion-adjustment = max

      0

      start-intrusion-adjustment(B parent)

      B parent is not a ref-area

      start-encroachment(A,B)

      A start-float

      generating-fo(A) is not a descendant of F

      ∃ L' line-area child of B, A encroaches-upon L'

      start-encroachment(A,B')

      A start-float such that A,B inline-overlapping

      B' block-area ancestor of B

      B' descendant of B nearest ancestor ref-area

      ∃ L line-area child of B', A encroaches-upon L

      Then start-intrusion-adjustmentB = max(local-start-intrusion-adjustmentB', B' normal block-area generated and returned by F)

    • for each generated line-area L

      start-intrusion-adjustment = max

      start-intrusion-adjustment(L parent)

      start-encroachment(A,L), A start-float such that A encroaches-upon L

I'll first implement the "line" value, as this is probably the most expected by users. I'll forget "block" and "indent" for now if after a quick look they turn out to be too complicated to implement.

2. An Algorithm for Placing Side-floats

Have you ever played with Legotm? Well, here's an opportunity.

We will use here the relative terms for area placement: before, after, start, end. As a convenience, we will use the words "beforer" (higher in lr-tb writing-mode), "beforest" (highest), "starter" (more on the left than), "startest" (the most on the left), etc., for comparing the placement of areas between each other.

We consider the common ancestor reference-area as a containing box in which bricks have to be placed. There is a jagged line (green, below) which will serve as a guide for placing floats. This jagged line will be made, among others, of three guide lines. The "before-guide" will correspond to:

  • the before-edge of the current line-area's allocation-rectangle, or
  • the after-edge of the previous block-area's, if there is no current line-area, or
  • the before-edge of the "afterest" placed side-float, if it is afterer than the previous lines.

There will also be one "start-guide", representing the afterest after-edge of start-floats, and one "end-guide", for the afterest after-edge of end-floats.

http://people.apache.org/~jeremias/fop/vincent/SideFloats/side-floats_placement-start.png

Now let's suppose we want to place a new start-float; the idea is to place it at the after-end corner of the reference-area. Then we pull it toward the before-edge until it touches one of the guide lines.

While continuing to pull towards the before, we will start pulling also towards the start; the float will progress along the jagged line until it is blocked; it has reached its final placement. The guide lines are updated as should be.

http://people.apache.org/~jeremias/fop/vincent/SideFloats/side-floats_placement-float1_1.png http://people.apache.org/~jeremias/fop/vincent/SideFloats/side-floats_placement-float1_2.png http://people.apache.org/~jeremias/fop/vincent/SideFloats/side-floats_placement-float1_3.png http://people.apache.org/~jeremias/fop/vincent/SideFloats/side-floats_placement-float1_4.png

Now we will place an end-float; there is no more place on the current line, so the float will be placed after the last placed start-float:

http://people.apache.org/~jeremias/fop/vincent/SideFloats/side-floats_placement-float2_1.png http://people.apache.org/~jeremias/fop/vincent/SideFloats/side-floats_placement-float2_2.png

Note that the before-guide no longer corresponds to the current line-area, as the last float has been placed afterer. Note also that there is a hole below the third end-float from the right: its after-edge no longer serves for the guide as there is an end-float placed to its start (left), whose after-edge is afterer. (This was the same case for the first start-float.)

Let's place a new start-float:

http://people.apache.org/~jeremias/fop/vincent/SideFloats/side-floats_placement-float3.png

And then a new end-float:

http://people.apache.org/~jeremias/fop/vincent/SideFloats/side-floats_placement-float4.png

Side-floats are boxes which may allow some shrinking/stretching in the block-progression-dimension. Me may take advantage of this possibility to place floats which otherwise wouldn't fit on the page. On the figure below, the second start-float has the "clear" property set to "start":

http://people.apache.org/~jeremias/fop/vincent/SideFloats/side-floats_placement-shrink.png

2.1. Properties of the Model

By nature, this model should respect all of the rules for side-floats placement:

  1. A start-float starts at the end-edge and is pulled to the start until it touches the start-edge of the ref-area's content-rectangle. So this rule is always followed. Same for end-floats.
  2. The guiding jagged line is designed to follow the afterest and endest edges of start-floats, and the afterest and startest edges of end-floats. So the area into which a start-float may evolve is such that all already placed start-floats are to its start or to its before. (That's why there may be holes above the start-guide or the end-guide, as showed above.)
  3. The model ensures that side-floats don't inter-penetrate each other.
  4. As for 1., the before-edge of the ref-area is the upper limit.
  5. This is ensured by the way the before-guide is computed.
  6. idem
  7. a start-float starts its movement at the end-edge of the ref-area, which acts like a wall, so it may not stick out of it (there will have to be a special handling for floats whose ipds are superior to the ref-area's ipd). If previous start-floats take too much place in the i-p-d, its movement towards the before will be stopped by the start-guide:

    http://people.apache.org/~jeremias/fop/vincent/SideFloats/side-floats_placement-rule7.png

  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
  10. if "clear" = "start" or "both", we place the before-guide at least at the level of the start-guide. if "clear" = "end" or "both", we place the before-guide at least at the level of the end-guide.

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.

2.2. 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://people.apache.org/~jeremias/fop/vincent/SideFloats/side-floats_page-break.png

We may choose to either defer 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://people.apache.org/~jeremias/fop/vincent/SideFloats/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://people.apache.org/~jeremias/fop/vincent/SideFloats/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

A huge thanks to Inkscape, who made the drawing of all those figures so easy.

GoogleSummerOfCode2006/FloatsImplementationProgress/ImplementingSideFloats (last edited 2009-09-20 23:52:15 by localhost)