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