lily/simple-spacer.cc

   1 /*
   2   simple-spacer.cc -- implement Simple_spacer
   3
   4   source file of the GNU LilyPond music typesetter
   5
   6   (c) 1999--2003 Han-Wen Nienhuys <hanwen@cs.uu.nl>
   7
   8   TODO:
   9   - add support for different stretch/shrink constants?
  10
  11 */
  12 #include <stdio.h>
  13 #include <math.h>
  14 #include <libc-extension.hh>    // isinf
  15
  16 #include "simple-spacer.hh"
  17 #include "paper-column.hh"
  18 #include "spring.hh"
  19 #include "rod.hh"
  20 #include "warn.hh"
  21 #include "column-x-positions.hh"
  22 #include "spaceable-grob.hh"
  23 #include "dimensions.hh"
  24
  25
  26 /*
  27    A simple spacing constraint solver. The approach:
  28
  29    Stretch the line uniformly until none of the constraints (rods)
  30    block.  It then is very wide.
  31
  32       Compress until the next constraint blocks,
  33
  34       Mark the springs over the constrained part to be non-active.
  35
  36    Repeat with the smaller set of non-active constraints, until all
  37    constraints blocked, or until the line is as short as desired.
  38
  39    This is much simpler, and much much faster than full scale
  40    Constrained QP. On the other hand, a situation like this will not
  41    be typeset as dense as possible, because
  42
  43    c4                   c4           c4                  c4
  44    veryveryverylongsyllable2         veryveryverylongsyllable2
  45    " "4                 veryveryverylongsyllable2        syllable4
  46
  47
  48    can be further compressed to
  49
  50
  51    c4    c4                        c4   c4
  52    veryveryverylongsyllable2       veryveryverylongsyllable2
  53    " "4  veryveryverylongsyllable2      syllable4
  54
  55
  56    Perhaps this is not a bad thing, because the 1st looks better anyway.  */
  57
  58
  59 Simple_spacer::Simple_spacer ()
  60 {
  61   /*
  62     Give an extra penalty for compression. Needed to avoid compressing
  63     tightly spaced lines.
  64   */
  65   compression_penalty_b_ = false;
  66   active_count_ = 0;
  67   force_ = 0.;
  68   indent_ =0.0;
  69   default_space_ = 20 PT;
  70 }
  71
  72 void
  73 Simple_spacer::add_rod (int l, int r, Real dist)
  74 {
  75   if (isinf (dist) || isnan (dist))
  76     {
  77       programming_error ("Weird minimum distance. Ignoring");
  78       return;
  79     }
  80
  81   Real c = range_stiffness (l,r);
  82   if (isinf (c))
  83     {
  84       /*
  85         If a spring is fixed, we have to do something here:
  86         we let the rod override the spring.
  87        */
  88       Real total_dist = 0.;
  89       for (int i = l ; i < r; i++)
  90         total_dist += springs_[i].ideal_;
  91
  92       if (total_dist < dist)
  93         for (int i = l ; i < r; i++)
  94           springs_[i].ideal_ *= dist/total_dist;
  95
  96       return;
  97     }
  98
  99   Real d = range_ideal_len (l,r);
 100   Real block_stretch = dist - d;
 101
 102   Real block_force = c * block_stretch;
 103   force_ = force_ >? block_force;
 104
 105   for (int i=l; i < r; i++)
 106     springs_[i].block_force_ = block_force >?
 107       springs_[i].block_force_ ;
 108 }
 109
 110 Real
 111 Simple_spacer::range_ideal_len (int l, int r)   const
 112 {
 113   Real d =0.;
 114   for (int i=l; i < r; i++)
 115     d += springs_[i].ideal_;
 116   return d;
 117 }
 118
 119 Real
 120 Simple_spacer::range_stiffness (int l, int r) const
 121 {
 122   Real den =0.0;
 123   for (int i=l; i < r; i++)
 124     {
 125       if (springs_[i].active_b_)
 126         den += 1 / springs_[i].hooke_;
 127     }
 128
 129   return 1 / den;
 130 }
 131
 132 Real
 133 Simple_spacer::active_blocking_force () const
 134 {
 135   Real bf = - infinity_f;
 136   for (int i=0; i < springs_.size (); i++)
 137     if (springs_[i].active_b_)
 138       {
 139         bf = bf >? springs_[i].block_force_;
 140       }
 141   return bf;
 142 }
 143
 144 Real
 145 Simple_spacer::active_springs_stiffness () const
 146 {
 147   range_stiffness (0, springs_.size ());
 148 }
 149
 150 void
 151 Simple_spacer::set_active_states ()
 152 {
 153   /* float comparison is safe, since force is only copied.  */
 154   for (int i=0 ; i <springs_.size (); i++)
 155     if (springs_[i].active_b_
 156         && springs_[i].block_force_ >= force_)
 157       {
 158         springs_[i].active_b_ = false;
 159         active_count_ --;
 160       }
 161 }
 162
 163 Real
 164 Simple_spacer::configuration_length () const
 165 {
 166   Real l =0.;
 167   for (int i=0; i < springs_.size (); i++)
 168     l += springs_[i].length (force_);
 169
 170   return l;
 171 }
 172
 173 bool
 174 Simple_spacer::active_b () const
 175 {
 176   return active_count_;
 177 }
 178
 179 void
 180 Simple_spacer::my_solve_linelen ()
 181 {
 182   while (active_b ())
 183     {
 184       force_ = active_blocking_force ();
 185       Real conf = configuration_length ();
 186
 187       if (conf < line_len_)
 188         {
 189           force_ += (line_len_  - conf) * active_springs_stiffness ();
 190           break;
 191         }
 192       else
 193         set_active_states ();
 194     }
 195 }
 196
 197
 198 void
 199 Simple_spacer::my_solve_natural_len ()
 200 {
 201   while (active_b ())
 202     {
 203       force_ = active_blocking_force () >? 0.0;
 204
 205       if (force_ < 1e-8) // ugh.,
 206         break;
 207
 208       set_active_states ();
 209     }
 210 }
 211
 212 void
 213 Simple_spacer::add_columns (Link_array<Grob> const &icols)
 214 {
 215   Link_array<Grob> cols(icols);
 216
 217   for (int i =  cols.size (); i--;)
 218     if (gh_pair_p (cols[i]->get_grob_property ("between-cols")))
 219       {
 220         loose_cols_.push (cols[i]);
 221         cols.del (i);
 222       }
 223
 224   spaced_cols_ = cols;
 225   for (int i=0; i < cols.size () - 1; i++)
 226     {
 227       Spring_smob *spring = 0;
 228
 229       for (SCM s = cols[i]->get_grob_property ("ideal-distances");
 230            !spring && gh_pair_p (s);
 231            s = ly_cdr (s))
 232         {
 233           Spring_smob *sp = unsmob_spring (ly_car (s));
 234
 235
 236           if (sp->other_ == cols[i+1])
 237             spring = sp;
 238         }
 239
 240       Spring_description desc;
 241       if (spring)
 242         {
 243           desc.ideal_ = spring->distance_;
 244           desc.hooke_ = spring->strength_;
 245         }
 246       else
 247         {
 248           programming_error (_f("No spring between column %d and next one",
 249                                 Paper_column::get_rank (cols[i])
 250                                 ));
 251           desc.hooke_ = 1.0;
 252           desc.ideal_ = default_space_;
 253
 254           continue;
 255         }
 256
 257       if (!desc.sane_b ())
 258         {
 259           programming_error ("Insane spring found. Setting to unit spring.");
 260
 261           desc.hooke_ = 1.0;
 262           desc.ideal_ = 1.0;
 263         }
 264
 265       if (isinf (desc.hooke_))
 266         {
 267           desc.active_b_ = false;
 268           springs_.push (desc);
 269         }
 270       else
 271         {
 272           desc.block_force_ = - desc.hooke_ * desc.ideal_; // block at distance 0
 273           springs_.push (desc);
 274
 275           active_count_ ++;
 276         }
 277
 278       if (spring->expand_only_b_)
 279         {
 280           compression_penalty_b_ = true;
 281         }
 282
 283     }
 284
 285   for (int i=0; i < cols.size () - 1; i++)
 286     {
 287       for (SCM s = Spaceable_grob::get_minimum_distances (cols[i]);
 288            gh_pair_p (s); s = ly_cdr (s))
 289         {
 290           Grob * other = unsmob_grob (ly_caar (s));
 291           int oi = cols.find_index (other);
 292           if (oi >= 0)
 293             {
 294               add_rod (i, oi, gh_scm2double (ly_cdar (s)));
 295             }
 296         }
 297     }
 298
 299
 300 }
 301
 302 /*
 303
 304   TODO: should a add penalty for widely varying spring forces (caused
 305   by constraints, eg.
 306
 307
 308          =====
 309          |   |
 310   o|o|  x ##x
 311
 312
 313   The ## forces the notes apart; we shouldn't allow the O's to touch
 314   this closely.
 315
 316  */
 317 void
 318 Simple_spacer::solve (Column_x_positions *positions, bool ragged)
 319 {
 320   /*
 321     TODO: should support natural length on only the last line.
 322    */
 323   ragged = ragged || (line_len_ < 0) ;
 324   if (ragged)
 325     my_solve_natural_len ();
 326   else
 327     my_solve_linelen ();
 328
 329
 330   positions->force_ = force_;
 331   if ((force_ < 0))
 332     {
 333
 334       /*
 335         We used to have a penalty for compression, no matter what, but that
 336         fucked up wtk1-fugue2 (taking 3 full pages.)
 337
 338         maybe this should be tunable?
 339        */
 340       if (compression_penalty_b_)
 341         ; //    positions->force_ *= 2; //  hmm.
 342     }
 343
 344   positions->config_.push (indent_);
 345   for (int i=0; i <springs_.size (); i++)
 346     {
 347       Real  l = springs_[i].length ((ragged) ? 0.0 : force_);
 348       positions->config_.push (positions->config_.top () + l);
 349       /*
 350         we have l>= 0 here, up to rounding errors
 351       */
 352     }
 353   positions->cols_ = spaced_cols_;
 354   positions->loose_cols_ = loose_cols_;
 355
 356   positions->satisfies_constraints_b_ = (line_len_ < 0) || active_b ();
 357
 358
 359   /*
 360     Check if breaking constraints are met.
 361    */
 362   bool break_satisfy = true;
 363   int sz =  positions->cols_.size ();
 364   for (int i = sz; i--; )
 365     {
 366       SCM p = positions->cols_[i]->get_grob_property( "penalty");
 367       if (gh_number_p (p))
 368         {
 369           if (gh_scm2double (p) < -9999)
 370             break_satisfy = break_satisfy && (i == 0 || i == sz -1);
 371           if (gh_scm2double (p) > 9999)
 372             break_satisfy = break_satisfy && !(i == 0 || i == sz -1);
 373         }
 374
 375     }
 376
 377   positions->satisfies_constraints_b_ =
 378     positions->satisfies_constraints_b_ && break_satisfy;
 379
 380   if (ragged && force_ < 0)
 381     positions->satisfies_constraints_b_ = false;
 382 }
 383
 384 /****************************************************************/
 385
 386 Spring_description::Spring_description ()
 387 {
 388   ideal_ =0.0;
 389   hooke_ =0.0;
 390   active_b_ = true;
 391   block_force_ = 0.0;
 392 }
 393
 394
 395 bool
 396 Spring_description::sane_b () const
 397 {
 398   return (hooke_ > 0) &&  !isinf (ideal_) && !isnan (ideal_);
 399 }
 400
 401 Real
 402 Spring_description::length (Real f) const
 403 {
 404   if (!active_b_)
 405     f = block_force_;
 406   return ideal_ + f / hooke_ ;
 407 }