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