Home 
 1. programming language 
 1.1 \ifincsname 
 1.2 Oldenburg notes 
 2. grid typesetting 
 2.1 already existing ideas and app...  
 2.2 working along 
 3. other topics discussed 
 3.1 reconsider paragraph 
 3.2 unjustified paragraphs 
 3.3 \everyleftline 
 4. topics not discussed 
 4.1 fonts 
 4.2 color 
 4.3 hyphenation 
 4.4 math typesetting 
 4.5 superglue 
 5. summary of results 
 5.1 new implemented primitive 
 5.2 priority sorting Oldenburg not...  
 5.3 algorithms for grid typesettin...  
 5.4 mixed results 
2.2 working along
what do people want? do we need sub-grids? grid setting a \vbox grid setting on the MVL
Here are the notes from the sessions while we worked out way through and into grids. The final outcome box for grid typesetting within a vbox and for a grid on the MVL (main vertical list) are approaches and algorithms that we felt are worth exploring further, i.e., implementing and experimenting with.
2.2.1 what do people want?
A big question and I don't think we came to any conclusions (or if we did I unfortunately didn't find enough space in the margin to record them :-). But we certainly talked about it a lot and it certainly influenced the later discussions.
2.2.2 do we need sub-grids?
A sub grid is a grid structure that is deployed in an area which is otherwise off the outer grid, e.g., a list might move off the grid but within it the paragraphs and items may well be on a grid by their own.
No conclusion ... time will tell (perhaps).
2.2.3 grid setting a \vbox
The first real result: an algorithm for typesetting text in a \vbox which has an underlying grid. As the mathematician says, some questions are left open for the interested reader, but they look solvable or even only need a technical decision.
2.2.3.1 natural \vbox
Base algorithm:
Rather than setting the glue for the whole box at the very end, do the following while building the box:
  • one adds up the glue up to the next snapping point
  • calculates the natural size to that point
  • and determines the badness for moving the snapping point to the grid points before or after (unless it is by chance already on a grid point)
  • the one with the smallest badness is then chosen and the glue setting is recorded in the previous snapping point (for the first block in the box node as currently).
  • then repeat this process looking at the next interval.
The final badness is defined by the normal formula for
  \vbox to <final height due to above process>

Variation:
Rather than always looking only at individual segments and determining the best solution (minimal badness for each segment) one could record both solutions (snap to above and below) and make the final selection at the end taking into account variables like
  • difference to natural height
  • incompatibility of adjcent segments (i.e.. one choosing the above next choosing the below snap point)
TeX program involved is §688 vpackage
the routine to change is vpackage §688 and it is required to define a new snapping node which holds the glue setting to use if the next block for alignment is set.
2.2.3.2 \vbox to ...
Similar to natural solution, but needs a clear definition which settings are considered best when different distributions are able to reach the target size!
This might call for implementing the variant solution generally.
Needs further thoughts.
question: how to define "best solution"?
The best solution is really a simplified paragraph breaking algorithm exercise:
  • the snapping point can be moved backwards only a finite amount
  • it can only be moved forward a finite amount since at a certain point it will otherwise move more than the total amount of extra space that we need to reach our target size (compared to the natural size)
  • the concept of visual classes would also apply as one would want to avoid to shrink a certain block while stretching others. Actually there is one difference here: while the paragraph breaking considers essentially only consecutive lines, this algorithm better tries to keep the stretching factor overall as identically as possible.

Try again ...
In the line breaking algorithm we try to minimize the total demerits, which are build from the various line badness, penalty costs (and implicitly from the number of lines produced).
In the algorithm here we try to minimize the derivation of the glue setting of the various block from the ideal glue setting that we would apply if there are no snapping points.

Note:
all this would also apply to the \vbox case if we implement the variant solution.
2.2.3.3 questions:
A couple of questions that need answering or a technical decision.
where does the grid start?
As the grid is mostly about baselines, it seems reasonable to have the grid start at the baseline of the first box put on the current vertical list. This also applies to the situations where the first object in a \vbox is another \vbox.
If the \vbox starts out with say, a rule or something, all we can really do is to hope whoever put in that rule knows what he/she is doing.
Is this good enough given that TeX has \topskip?
how is the grid data structure defined?
The grid structure should essentially be a local structure consisting of a few parameters controlling the grid unit.
One way of implementation would be to have a register that holds the gridsize, e.g., \gridsize=12pt.
This register would be used for all box constructions (and on the MVL) unless changed within the scope of such a box to 0 or negative then no grid is produced (proposal). The alternative would be some other flag that indicates no grid for a certain box.
This is different from request that in the input some parts should not be affected by a grid even if they contain (for some reason) snapping points.
The latter should probably be implemented as a whatsit node that actually lives within the galley content.
2.2.4 grid setting on the MVL
Doing grid typesetting on the main vertical list is probably slightly different than doing the same within a single box. On the other hand the general principles should be the same as far as possible.
So this would our guiding principle while working our way through this.
what is the right algorithm?
2.2.4.1 some initial comments/ideas
That could perhaps become more or less an application of the \vbox to ... case.
On the MVL we stop calculating the costs for a page break, but simply check if the newly contributed line/object would still fit on the page (which is easy as we know  ...)

big question mark on whether or not this is true!   ???
2.2.4.2 a later approach Wichtig
So here is what we came up with on Sunday:
  • let TeX do the MVL collection like it does today, except that we don't bother to calculate costs. So the only thing to do really is to check if the newly contributed material still fits on the current page.
  • Once it doesn't (i.e., when b=*) we pass this to a new algorithm which then determines at which place to actually break the page.
  • This would sit sort of just before the routine fire_up(p).

The algorithm would have two guiding principles:
    • more stretch -> higher badness
    • more evenly distributed ratios (for the different blocks between snapping points) -> less badness
Possible function candidate: 
r^2 + (r_1 -r)^2 + (r_2 - r)^2 +...
where r is the overall ratio and r_i is the ratio in block i.

In case of the MVL the algorithm may leave a residue at the tail (i.e., may decide not to use everything)


Comment:
Depending on the function this may or may not be solvable with dynamic programming but the number of cases to consider will in reality be fairly small so we can probably survive even O(n^2).

Recent comment by Thanh:
I think there is at least one place that needs correction:
that's the time complexity of the (proposed) extended vbreak algorithm. It's not O(n^2), but O(m^n) where n is the number of breakpoints and m the maximum number of grid points around a breakpoint (which is usually small).
Back to Top