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--2004 Han-Wen Nienhuys <hanwen@cs.uu.nl>
   7
   8   TODO:
   9   - add support for different stretch/shrink constants?
  10
  11 */
  12
  13 #include "simple-spacer.hh"
  14
  15 #include <cstdio>
  16 #include <cmath>
  17
  18 #include <libc-extension.hh>    // isinf
  19
  20 #include "paper-column.hh"
  21 #include "spring.hh"
  22 #include "warn.hh"
  23 #include "column-x-positions.hh"
  24 #include "spaceable-grob.hh"
  25 #include "dimensions.hh"
  26
  27 /*
  28    A simple spacing constraint solver. The approach:
  29
  30    Stretch the line uniformly until none of the constraints (rods)
  31    block.  It then is very wide.
  32
  33       Compress until the next constraint blocks,
  34
  35       Mark the springs over the constrained part to be non-active.
  36
  37    Repeat with the smaller set of non-active constraints, until all
  38    constraints blocked, or until the line is as short as desired.
  39
  40    This is much simpler, and much much faster than full scale
  41    Constrained QP. On the other hand, a situation like this will not
  42    be typeset as dense as possible, because
  43
  44    c4                   c4           c4                  c4
  45    veryveryverylongsyllable2         veryveryverylongsyllable2
  46    " "4                 veryveryverylongsyllable2        syllable4
  47
  48
  49    can be further compressed to
  50
  51
  52    c4    c4                        c4   c4
  53    veryveryverylongsyllable2       veryveryverylongsyllable2
  54    " "4  veryveryverylongsyllable2      syllable4
  55
  56
  57    Perhaps this is not a bad thing, because the 1st looks better anyway.  */
  58
  59
  60 /*
  61
  62   positive force = expanding, negative force = compressing.
  63
  64 */
  65
  66 Simple_spacer::Simple_spacer ()
  67 {
  68   /*
  69     Give an extra penalty for compression. Needed to avoid compressing
  70     tightly spaced lines.
  71   */
  72   active_count_ = 0;
  73   force_ = 0.;
  74   indent_ =0.0;
  75   default_space_ = 20 PT;
  76 }
  77
  78 void
  79 Simple_spacer::add_rod (int l, int r, Real dist)
  80 {
  81   if (isinf (dist) || isnan (dist))
  82     {
  83       programming_error ("Weird minimum distance. Ignoring");
  84       return;
  85     }
  86
  87   Real c = range_stiffness (l,r);
  88   if (isinf (c))
  89     {
  90       /*
  91         If a spring is fixed, we have to do something here:
  92         we let the rod override the spring.
  93        */
  94       Real total_dist = 0.;
  95       for (int i = l ; i < r; i++)
  96         total_dist += springs_[i].ideal_;
  97
  98       if (total_dist < dist)
  99         for (int i = l ; i < r; i++)
 100           springs_[i].ideal_ *= dist/total_dist;
 101
 102       return;
 103     }
 104
 105   Real d = range_ideal_len (l,r);
 106   Real block_stretch = dist - d;
 107
 108   Real block_force = c * block_stretch;
 109   force_ = force_ >? block_force;
 110
 111   for (int i=l; i < r; i++)
 112     springs_[i].block_force_ = block_force >?
 113       springs_[i].block_force_ ;
 114 }
 115
 116 Real
 117 Simple_spacer::range_ideal_len (int l, int r)   const
 118 {
 119   Real d =0.;
 120   for (int i=l; i < r; i++)
 121     d += springs_[i].ideal_;
 122   return d;
 123 }
 124
 125 Real
 126 Simple_spacer::range_stiffness (int l, int r) const
 127 {
 128   Real den =0.0;
 129   for (int i=l; i < r; i++)
 130     {
 131       if (springs_[i].is_active_)
 132         den += 1 / springs_[i].hooke_;
 133     }
 134
 135   return 1 / den;
 136 }
 137
 138 Real
 139 Simple_spacer::active_blocking_force () const
 140 {
 141   Real bf = - infinity_f;
 142   for (int i=0; i < springs_.size (); i++)
 143     if (springs_[i].is_active_)
 144       {
 145         bf = bf >? springs_[i].block_force_;
 146       }
 147   return bf;
 148 }
 149
 150 Real
 151 Simple_spacer::active_springs_stiffness () const
 152 {
 153   Real  stiff =  range_stiffness (0, springs_.size ());
 154   if (isinf (stiff))
 155     {
 156       /*
 157         all springs are inactive. Take the stiffness of the
 158         latest spring to block.
 159        */
 160
 161       Real max_block_force = -infinity_f;
 162       int max_i = -1;
 163       for (int i=0; i < springs_.size (); i++)
 164         {
 165           if (springs_[i].block_force_ > max_block_force)
 166             {
 167               max_i = i;
 168               max_block_force = springs_[i].block_force_;
 169             }
 170         }
 171
 172       stiff = springs_[max_i].hooke_;
 173     }
 174   return stiff;
 175 }
 176
 177 void
 178 Simple_spacer::set_active_states ()
 179 {
 180   /* float comparison is safe, since force is only copied.  */
 181   for (int i=0 ; i <springs_.size (); i++)
 182     if (springs_[i].is_active_
 183         && springs_[i].block_force_ >= force_)
 184       {
 185         springs_[i].is_active_ = false;
 186         active_count_ --;
 187       }
 188 }
 189
 190 Real
 191 Simple_spacer::configuration_length () const
 192 {
 193   Real l =0.;
 194   for (int i=0; i < springs_.size (); i++)
 195     l += springs_[i].length (force_);
 196
 197   return l;
 198 }
 199
 200 bool
 201 Simple_spacer::is_active () const
 202 {
 203   return active_count_;
 204 }
 205
 206 void
 207 Simple_spacer::my_solve_linelen ()
 208 {
 209   while (is_active ())
 210     {
 211       force_ = active_blocking_force ();
 212       Real conf = configuration_length ();
 213
 214       if (conf < line_len_)
 215         {
 216           force_ += (line_len_ - conf) * active_springs_stiffness ();
 217           break;
 218         }
 219       else
 220         set_active_states ();
 221     }
 222 }
 223
 224
 225 void
 226 Simple_spacer::my_solve_natural_len ()
 227 {
 228   Real line_len_force = 0.0;
 229
 230   while (is_active ())
 231     {
 232       force_ = active_blocking_force () >? 0.0;
 233       Real conf = configuration_length ();
 234
 235       if (conf < line_len_)
 236         {
 237           line_len_force = force_
 238             + (line_len_ - conf)
 239             * active_springs_stiffness();
 240         }
 241
 242       if (force_ < 1e-8) // ugh.,
 243         break;
 244
 245       set_active_states ();
 246     }
 247
 248   force_ = line_len_force;
 249 }
 250
 251 LY_DEFINE(ly_solve_spring_rod_problem, "ly:solve-spring-rod-problem",
 252           4, 1, 0, (SCM springs, SCM rods, SCM length, SCM ragged),
 253           "Solve a spring and rod problem for @var{count} objects, that "
 254           "are connected by @var{count-1} springs, and an arbitrary number of rods "
 255           "Springs have the format (ideal, hooke) and rods (idx1, idx2, distance) "
 256           "@var{length} is a number, @var{ragged} a boolean "
 257           "Return: a list containing the force (positive for stretching, "
 258           "negative for compressing and #f for non-satisfied constraints) "
 259           "followed by the @var{spring-count}+1 positions of the objects. "
 260           )
 261 {
 262   int len = scm_ilength (springs);
 263   if (len == 0)
 264     return scm_list_2 (scm_from_double (0.0), scm_from_double (0.0));
 265
 266   SCM_ASSERT_TYPE (len >= 0, springs, SCM_ARG1, __FUNCTION__, "list of springs");
 267   SCM_ASSERT_TYPE (scm_ilength (rods) >= 0, rods, SCM_ARG2, __FUNCTION__, "list of rods");
 268   SCM_ASSERT_TYPE (scm_is_number (length) || length == SCM_BOOL_F,
 269                    length, SCM_ARG3, __FUNCTION__, "number or #f");
 270
 271
 272   bool is_ragged = ragged == SCM_BOOL_T;
 273   Simple_spacer spacer;
 274   for (SCM s = springs; scm_is_pair (s); s = scm_cdr (s))
 275     {
 276       Real ideal = scm_to_double (scm_caar (s));
 277       Real hooke = scm_to_double (scm_cadar (s));
 278
 279       spacer.add_spring (ideal, hooke);
 280     }
 281
 282   for (SCM s = rods; scm_is_pair (s); s = scm_cdr (s))
 283     {
 284       SCM entry = scm_car (s);
 285       int l = scm_to_int (scm_car (entry));
 286       int r = scm_to_int (scm_cadr (entry));
 287       entry = scm_cddr (entry);
 288
 289       Real distance = scm_to_double (scm_car (entry));
 290       spacer.add_rod (l, r, distance);
 291     }
 292
 293   spacer.line_len_ = scm_to_double (length);
 294
 295   if (is_ragged)
 296     spacer.my_solve_natural_len ();
 297   else
 298     spacer.my_solve_linelen ();
 299
 300   Array<Real> posns;
 301   posns.push (0.0);
 302   for (int i = 0; i < spacer.springs_.size(); i++)
 303     {
 304       Real l = spacer.springs_[i].length ((is_ragged) ? 0.0 : spacer.force_);
 305       posns.push (posns.top() + l);
 306     }
 307
 308
 309
 310   SCM force_return = SCM_BOOL_F;
 311   if (!isinf (spacer.force_)
 312       && (spacer.is_active () || is_ragged))
 313     {
 314       force_return = scm_from_double (spacer.force_);
 315     }
 316
 317   if (is_ragged
 318       && posns.top () > spacer.line_len_)
 319     {
 320       force_return = SCM_BOOL_F;
 321     }
 322
 323   SCM retval= SCM_EOL;
 324   for (int i = posns.size(); i--;)
 325     {
 326       retval = scm_cons (scm_from_double (posns[i]), retval);
 327     }
 328
 329   retval = scm_cons (force_return, retval);
 330   return retval;
 331 }
 332
 333
 334 /****************************************************************/
 335
 336 Spring_description::Spring_description ()
 337 {
 338   ideal_ =0.0;
 339   hooke_ =0.0;
 340   is_active_ = true;
 341   block_force_ = 0.0;
 342 }
 343
 344
 345 bool
 346 Spring_description::is_sane () const
 347 {
 348   return (hooke_ > 0)
 349     && ideal_ > 0
 350     && !isinf (ideal_) && !isnan (ideal_);
 351 }
 352
 353 Real
 354 Spring_description::length (Real f) const
 355 {
 356   if (!is_active_)
 357     f = block_force_;
 358   return ideal_ + f / hooke_ ;
 359 }
 360 /****************************************************************/
 361
 362
 363 /*
 364
 365   TODO: should a add penalty for widely varying spring forces (caused
 366   by constraints, eg.
 367
 368
 369          =====
 370          |   |
 371   o|o|  x ##x
 372
 373
 374   The ## forces the notes apart; we shouldn't allow the O's to touch
 375   this closely.
 376
 377  */
 378 void
 379 Simple_spacer_wrapper::solve (Column_x_positions *positions, bool ragged)
 380 {
 381   if (ragged)
 382     spacer_->my_solve_natural_len ();
 383   else
 384     spacer_->my_solve_linelen ();
 385
 386   positions->force_ = spacer_->force_;
 387
 388   /*
 389     We used to have a penalty for compression, no matter what, but that
 390     fucked up wtk1-fugue2 (taking 3 full pages.)
 391   */
 392   positions->config_.push (spacer_->indent_);
 393   for (int i=0; i < spacer_->springs_.size (); i++)
 394     {
 395       Real  l = spacer_->springs_[i].length ((ragged) ? 0.0 : spacer_->force_);
 396       positions->config_.push (positions->config_.top () + l);
 397       /*
 398         we have l>= 0 here, up to rounding errors
 399       */
 400     }
 401
 402   /*
 403     For raggedright, we must have a measure of music density: this is
 404     to prevent lots of short lines (which all have force = 0).
 405     */
 406   if (ragged)
 407     {
 408       positions->satisfies_constraints_ =
 409         positions->config_.top () < spacer_->line_len_ ;
 410     }
 411
 412
 413   positions->cols_ = spaced_cols_;
 414   positions->loose_cols_ = loose_cols_;
 415   positions->satisfies_constraints_ =
 416     positions->satisfies_constraints_ && spacer_->is_active ();
 417
 418   /*
 419     Check if breaking constraints are met.
 420    */
 421   bool break_satisfy = true;
 422   int sz =  positions->cols_.size ();
 423   for (int i = sz; i--; )
 424     {
 425       SCM p = positions->cols_[i]->get_property ( "penalty");
 426       if (scm_is_number (p))
 427         {
 428           if (scm_to_double (p) < -9999)
 429             break_satisfy = break_satisfy && (i == 0 || i == sz -1);
 430           if (scm_to_double (p) > 9999)
 431             break_satisfy = break_satisfy && !(i == 0 || i == sz -1);
 432         }
 433
 434     }
 435
 436   positions->satisfies_constraints_ =
 437     positions->satisfies_constraints_ && break_satisfy;
 438 }
 439
 440 void
 441 Simple_spacer::add_spring (Real ideal, Real hooke)
 442 {
 443   Spring_description desc;
 444
 445   desc.ideal_ = ideal;
 446   desc.hooke_ = hooke;
 447   if (!desc.is_sane ())
 448     {
 449       programming_error ("Insane spring found. Setting to unit spring.");
 450
 451       desc.hooke_ = 1.0;
 452       desc.ideal_ = 1.0;
 453     }
 454
 455   if (isinf (hooke))
 456     {
 457       desc.is_active_ = false;
 458     }
 459   else
 460     {
 461       /*
 462         desc.is_active_ ?
 463       */
 464       desc.block_force_ = - desc.hooke_ * desc.ideal_; // block at distance 0
 465
 466       active_count_ ++;
 467     }
 468   springs_.push (desc);
 469 }
 470
 471 void
 472 Simple_spacer_wrapper::add_columns (Link_array<Grob> const &icols)
 473 {
 474   Link_array<Grob> cols (icols);
 475
 476   for (int i =  cols.size (); i--;)
 477     if (scm_is_pair (cols[i]->get_property ("between-cols")))
 478       {
 479         loose_cols_.push (cols[i]);
 480         cols.del (i);
 481       }
 482
 483   spaced_cols_ = cols;
 484   for (int i=0; i < cols.size () - 1; i++)
 485     {
 486       Spring_smob *spring = 0;
 487
 488       for (SCM s = cols[i]->get_property ("ideal-distances");
 489            !spring && scm_is_pair (s);
 490            s = scm_cdr (s))
 491         {
 492           Spring_smob *sp = unsmob_spring (scm_car (s));
 493
 494
 495           if (sp->other_ == cols[i+1])
 496             spring = sp;
 497         }
 498
 499       if (!spring)
 500         programming_error (_f ("No spring between column %d and next one",
 501                                Paper_column::get_rank (cols[i])
 502                                ));
 503
 504       Real ideal = (spring) ? spring->distance_ : spacer_->default_space_;
 505       Real hooke = (spring) ? spring->strength_ : 1.0;
 506
 507       spacer_->add_spring (ideal, hooke);
 508     }
 509
 510   for (int i=0; i < cols.size () - 1; i++)
 511     {
 512       for (SCM s = Spaceable_grob::get_minimum_distances (cols[i]);
 513            scm_is_pair (s); s = scm_cdr (s))
 514         {
 515           Grob * other = unsmob_grob (scm_caar (s));
 516           int oi = cols.find_index (other);
 517           if (oi >= 0)
 518             {
 519               spacer_->add_rod (i, oi, scm_to_double (scm_cdar (s)));
 520             }
 521         }
 522     }
 523 }
 524
 525 Simple_spacer_wrapper::Simple_spacer_wrapper ()
 526 {
 527   spacer_ = new Simple_spacer ();
 528 }
 529
 530 Simple_spacer_wrapper::~Simple_spacer_wrapper ()
 531 {
 532   delete spacer_;
 533 }
 534
 535
 536 Simple_spacer_wrapper::Simple_spacer_wrapper (Simple_spacer_wrapper const&)
 537 {
 538 }