Volume breaking behaving weirdly when volume-transition element is combined with marker in empty block

[bertfrees]

I have already been discussing this with Joel. Now I also created this Github issue for NLB to be able to track something.

The issue is demonstrated in this test. Note that the marker can not simply be moved to the first non-empty block because the Pipeline generates these empty blocks for a reason, which is described in https://github.com/brailleapps/dotify/issues/150. See also the tests in TakenFromDP2Test that start with "marker-reference-". Also related are braillespecs/obfl#65, #48 and #49.

Joel suggested that I am exploiting a bug, which could be true, but because there is no way to tell from the OBFL spec, and the explanation in https://github.com/brailleapps/dotify/issues/150#issuecomment-250465758 sounded reasonable to me and nobody questioned it, I think my use of OBFL can be called legitimate.

Joel would like to focus on getting the OBFL spec right first, which makes the most sense from a maintainer's point of view. On the other hand NLB would like to solve the volume breaking issue asap in order to get their tool in production. In any case, I think the two issues can and should be seen as separate (unrelated) issues. (But if it can help to understand the situation better I can see if I can make a test that covers the combination of the two.)

[joeha480]

There are three issues (at least):

1. Blocks with no text content are always attached to the following block (by use of the breakable property), related to Markers are sometimes attached to the wrong page #48. See also https://github.com/brailleapps/dotify.formatter.impl/blob/master/src/org/daisy/dotify/formatter/impl/page/RowGroupProvider.java#L118
2. The algorithm cannot handle a volume priority configuration that causes the number of volumes to increase.
3. There could potentially be a mismatch between the properties that are used when selecting a sheet for volume breaking and the subsequent volume breaking processing of that sheet. Specifically, the empty block discussed above is used when selecting the sheet as the last in the volume, but since it is attached to the following block it is impossible to break after it when processing that page.

[bertfrees]

In order to improve the volume breaking algorithm I think the code in EvenSizeVolumeSplitter and the code in VolumeProvider might have to talk more with each other. More specifically, the actual volume split as computed by the cost-based optimization in VolumeProvider should be fed back to EvenSizeVolumeSplitter. Currently EvenSizeVolumeSplitter only takes into account the actual total number of sheets and the number of sheets that could not be fit into the estimated volumes.

I've collected some data about the iterations:

     estim.  estim. actual              act.    rem.    total  next    next    
     sheets  vols   split               sheets  sheets  sheets offset  splitter
---  ------  -----  ------              ------  ------  -----  ------  ------  
1    12      3      [1, 4, 2]           7       5       12     1       [3, 3, 3, 3]
2    12      4      [1, 3, 3, 1]        8       6       14     2       [3, 3, 2, 2, 2, 2]
3    14      6      [1, 3, 3, 1, 2, 4]  14      0       14     1       [3, 3, 3, 3, 2]
4    14      5      [1, 3, 3, 1, 2]     10      4       14     2       [3, 3, 2, 2, 2, 2]
5    14      6      [1, 3, 3, 1, 2, 4]  14      0       14     2       [3, 3, 2, 2, 2, 2]

You can see for instance how the algorithm not taking into account the single sheet volumes may lead to too small target sizes of other volumes.

However this is not the main problem in this example. The expected result of this example is [4, 3, 4, 3] or something like that. Even if EvenSizeVolumeSplitter and VolumeProvider talk more with each other, this result can't be achieved because the optimization algorithm in SplitPointHandler is greedy. Better algorithms exist of course, but it almost inevitably means more computation, so it's not as simple as that. Of course we want a nice balance between quality of volume breaks and computation time.

[bertfrees]

Another idea: I think if we could somehow combine the iterations of EvenSizeVolumeSplitter (of which the purpose is to push the volume breaking result in the direction of equal volumes) with the iterations of SplitPointHandler, we could achieve a better efficiency than when these would stay separated (i.e. nested loops).

What EvenSizeVolumeSplitter does basically is 1) estimate the number of volumes, and 2) subtract an average overhead from the volume sizes and use the differences as the target sizes. However, the overhead can also be computed (more accurately) in the cost function. It even already does this in the current code. Now if we remove the restriction of the estimated volume count, and we enhance SplitPointHandler so that it optimizes the total cost, i.e. sum of costs of individual break points, we could eliminate EvenSizeVolumeSplitter completely.

Does that make sense?

[joeha480]

Sounds interesting.

[bertfrees]

Should be fixed by #97.