Documentation/algorithms

   1 Date: Tue, 5 Nov 1996 00:01:32 +0100
   2 From: Werner Icking <Werner.Icking@gmd.de>
   3 To: hanwen@stack.urc.tue.nl
   4 Cc: dsimons@logicon.com
   5 Subject: Re: font sizes.
   6
   7 > Date: Mon, 4 Nov 1996 22:37:54 +0100 (MET)
   8 > From: Han-Wen Nienhuys <hanwen@stack.urc.tue.nl>
   9 > >
  10 > >There were different schemes when music was typeset by hand. If I remember
  11 > >right Harder uses another scheme that Gomberg. Both scheme may be used
  12 >
  13 > Who are Harder and Gomberg? Do you have references?
  14
  15 Both are mentioned in the master thesis by Steinbach & Schofer who
  16 invented M(u)TeX, the grandmother of all M...TeXs. The Musiclibrary
  17 in Bonn has the harder (printed in 1948?) and there are not many books
  18 I liked more to own.
  19
  20 The master thesis should be available at the CTAN archives under MuTeX
  21 or MTEX maybe subdirectory DIPL (for Diplom). I have the TEX-source
  22 and I may pack it to ftp.gmd.de if you are interested and can't find it
  23 on CTAN.
  24 ================================================================
  25
  26 [breaking lines]
  27 >
  28 >Incidentally, I use a different approach in PMX, starting with the
  29 >total number of systems for the piece instead of assuming a starting
  30 >physical value for \elemskip.  That's equivalent to setting the
  31 >physical length of the whole piece if laid out in one long line.
  32 >Knowing the total amount of scalable and fixed space I compute a
  33 >starting physical value for \elemskip.  I use that to get how many
  34 >bars go in the first line.  Then I force a line break there, remove
  35 >those bars and their scalable and fixed space from the accounting, and
  36 >start over with the second line, etc.
  37
  38
  39 Since you are getting into technical details, I will show mine too: I
  40 think my way  is the most elegant algorithm i've seen so far.  Some
  41 terminology: I call a vertical group of symbols (notes) which start at
  42 the same time a "column".  Each line of a score has notes in it,
  43 grouped in columns. The difference in starting time between those
  44 columns makes it possible to determine ideal distances between those
  45 columns.
  46
  47 Example:
  48
  49         time ----->
  50
  51         col1    col2    col3    col4
  52
  53
  54 voice1  1               1
  55
  56 voice2  2       2       2       2
  57
  58
  59 (1 is a whole note, 2 a half note.)
  60
  61 time_difference (col1 , col2) = 0.5 wholes,
  62 time_difference (col1 , col3) = 1 wholes,
  63 time_difference (col2 , col3) = 0.5 wholes,
  64 etc.
  65
  66 these differences are translated into ideal distances (these translations
  67 have been the subject of discussion in this thread).
  68
  69         distance (col1,col2) = 10 pt
  70         distance (col1,col3) = 14.1 pt
  71         distance (col2,col3) = 10 pt
  72         etc.
  73
  74 as you can see, these distance are conflicting. So instead of
  75 satisfying all those ideals simultaneously, a compromise is sought.
  76
  77 This is Columbus' egg: LilyPond attaches "springs" to each
  78 column-pair.  each spring has an equilibrium-position which is equal to
  79 the above mentioned distance, so
  80
  81         spring (col1, col2) and spring(col2,col3) try to push column 1
  82 and 3 away (to a distance of 20pt) from each other, whereas the spring
  83 between col 1 and col 3 tries to pull those two together (to a
  84 distance of 14.1 pt). The net result of this pushing and pulling is an
  85 equilibrium situation (the pushing cancels the pulling), which can be
  86 calculated as the solution of Quadratic program: it is the solution
  87 with minimum potential energy, for you physicists out there.
  88
  89 This algorithm for doing one line, gives a "badness" parameter for
  90 each line (the potential energy). Now one can use TeX's algorithm for
  91 making paragraphs (using this new version of "badness"): one should
  92 try to minimise the overall badness of a paragraph. LilyPond also uses the
  93 concept of pre- and post-breaks.
  94
  95 (actually, it is a bit more complicated: each column also has a
  96 minimum distance to other columns, to prevent symbols from running
  97 into symbols of other columns.)
  98