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   Real line_len_force = 0.0;
 222
 223   while (is_active ())
 224     {
 225       force_ = active_blocking_force () >? 0.0;
 226       Real conf = configuration_length ();
 227
 228       if (conf < line_len_)
 229         {
 230           line_len_force = force_
 231             + (line_len_ - conf)
 232             * active_springs_stiffness();
 233         }
 234
 235       if (force_ < 1e-8) // ugh.,
 236         break;
 237
 238       set_active_states ();
 239     }
 240
 241   force_ = line_len_force;
 242 }
 243
 244 LY_DEFINE(ly_solve_spring_rod_problem, "ly:solve-spring-rod-problem",
 245           4, 1, 0, (SCM springs, SCM rods, SCM length, SCM ragged),
 246           "Solve a spring and rod problem for @var{count} objects, that "
 247           "are connected by @var{count-1} springs, and an arbitrary number of rods "
 248           "Springs have the format (ideal, hooke) and rods (idx1, idx2, distance) "
 249           "@var{length} is a number, @var{ragged} a boolean "
 250           "Return: a list containing the force (#f for non-satisfied constraints) "
 251           "followed by the @var{spring-count}+1 positions of the objects. "
 252           )
 253 {
 254   int len = scm_ilength (springs);
 255   if (len == 0)
 256     return scm_list_2 (scm_from_double (0.0), scm_from_double (0.0));
 257
 258   SCM_ASSERT_TYPE (len >= 0, springs, SCM_ARG1, __FUNCTION__, "list of springs");
 259   SCM_ASSERT_TYPE (scm_ilength (rods) >= 0, rods, SCM_ARG2, __FUNCTION__, "list of rods");
 260   SCM_ASSERT_TYPE (scm_is_number (length) || length == SCM_BOOL_F,
 261                    length, SCM_ARG3, __FUNCTION__, "number or #f");
 262
 263
 264   bool is_ragged   = ragged == SCM_BOOL_T;
 265   Simple_spacer spacer;
 266   for (SCM s = springs; scm_is_pair (s); s = scm_cdr (s))
 267     {
 268       Real ideal = scm_to_double (scm_caar (s));
 269       Real hooke = scm_to_double (scm_cadar (s));
 270
 271       spacer.add_spring (ideal, hooke);
 272     }
 273
 274   for (SCM s = rods; scm_is_pair (s); s = scm_cdr (s))
 275     {
 276       SCM entry = scm_car (s);
 277       int l = scm_to_int (scm_car (entry));
 278       int r = scm_to_int (scm_cadr (entry));
 279       entry = scm_cddr (entry);
 280
 281       Real distance = scm_to_double (scm_car (entry));
 282       spacer.add_rod (l, r, distance);
 283     }
 284
 285   spacer.line_len_ = scm_to_double (length);
 286
 287   if (is_ragged)
 288     spacer.my_solve_natural_len ();
 289   else
 290     spacer.my_solve_linelen ();
 291
 292   Array<Real> posns;
 293   posns.push (0.0);
 294   for (int i = 0; i < spacer.springs_.size(); i++)
 295     {
 296       Real l = spacer.springs_[i].length ((is_ragged) ? 0.0 : spacer.force_);
 297       posns.push (posns.top() + l);
 298     }
 299
 300   SCM force_return = SCM_BOOL_F;
 301   if (!isinf (spacer.force_)
 302       && spacer.is_active ())
 303     {
 304       force_return = scm_from_double (spacer.force_);
 305     }
 306
 307   SCM retval= SCM_EOL;
 308   for (int i = posns.size(); i--;)
 309     {
 310       retval = scm_cons (scm_from_double (posns[i]), retval);
 311     }
 312
 313   retval = scm_cons (force_return, retval);
 314   return retval;
 315 }
 316
 317
 318 /****************************************************************/
 319
 320 Spring_description::Spring_description ()
 321 {
 322   ideal_ =0.0;
 323   hooke_ =0.0;
 324   is_active_ = true;
 325   block_force_ = 0.0;
 326 }
 327
 328
 329 bool
 330 Spring_description::is_sane () const
 331 {
 332   return (hooke_ > 0)
 333     && ideal_ > 0
 334     && !isinf (ideal_) && !isnan (ideal_);
 335 }
 336
 337 Real
 338 Spring_description::length (Real f) const
 339 {
 340   if (!is_active_)
 341     f = block_force_;
 342   return ideal_ + f / hooke_ ;
 343 }
 344 /****************************************************************/
 345
 346
 347 /*
 348
 349   TODO: should a add penalty for widely varying spring forces (caused
 350   by constraints, eg.
 351
 352
 353          =====
 354          |   |
 355   o|o|  x ##x
 356
 357
 358   The ## forces the notes apart; we shouldn't allow the O's to touch
 359   this closely.
 360
 361  */
 362 void
 363 Simple_spacer_wrapper::solve (Column_x_positions *positions, bool ragged)
 364 {
 365   if (ragged)
 366     spacer_->my_solve_natural_len ();
 367   else
 368     spacer_->my_solve_linelen ();
 369
 370   positions->force_ = spacer_->force_;
 371
 372   /*
 373     We used to have a penalty for compression, no matter what, but that
 374     fucked up wtk1-fugue2 (taking 3 full pages.)
 375   */
 376   positions->config_.push (spacer_->indent_);
 377   for (int i=0; i < spacer_->springs_.size (); i++)
 378     {
 379       Real  l = spacer_->springs_[i].length ((ragged) ? 0.0 : spacer_->force_);
 380       positions->config_.push (positions->config_.top () + l);
 381       /*
 382         we have l>= 0 here, up to rounding errors
 383       */
 384     }
 385
 386   /*
 387     For raggedright, we must have a measure of music density: this is
 388     to prevent lots of short lines (which all have force = 0).
 389     */
 390   if (ragged)
 391     {
 392       positions->satisfies_constraints_ =
 393         positions->config_.top () < spacer_->line_len_ ;
 394     }
 395
 396
 397   positions->cols_ = spaced_cols_;
 398   positions->loose_cols_ = loose_cols_;
 399   positions->satisfies_constraints_ =
 400     positions->satisfies_constraints_ && spacer_->is_active ();
 401
 402   /*
 403     Check if breaking constraints are met.
 404    */
 405   bool break_satisfy = true;
 406   int sz =  positions->cols_.size ();
 407   for (int i = sz; i--; )
 408     {
 409       SCM p = positions->cols_[i]->get_property ( "penalty");
 410       if (scm_is_number (p))
 411         {
 412           if (scm_to_double (p) < -9999)
 413             break_satisfy = break_satisfy && (i == 0 || i == sz -1);
 414           if (scm_to_double (p) > 9999)
 415             break_satisfy = break_satisfy && !(i == 0 || i == sz -1);
 416         }
 417
 418     }
 419
 420   positions->satisfies_constraints_ =
 421     positions->satisfies_constraints_ && break_satisfy;
 422 }
 423
 424 void
 425 Simple_spacer::add_spring (Real ideal, Real hooke)
 426 {
 427   Spring_description desc;
 428
 429   desc.ideal_ = ideal;
 430   desc.hooke_ = hooke;
 431   if (!desc.is_sane ())
 432     {
 433       programming_error ("Insane spring found. Setting to unit spring.");
 434
 435       desc.hooke_ = 1.0;
 436       desc.ideal_ = 1.0;
 437     }
 438
 439   if (isinf (hooke))
 440     {
 441       desc.is_active_ = false;
 442     }
 443   else
 444     {
 445       /*
 446         desc.is_active_ ?
 447       */
 448       desc.block_force_ = - desc.hooke_ * desc.ideal_; // block at distance 0
 449
 450       active_count_ ++;
 451     }
 452   springs_.push (desc);
 453 }
 454
 455 void
 456 Simple_spacer_wrapper::add_columns (Link_array<Grob> const &icols)
 457 {
 458   Link_array<Grob> cols (icols);
 459
 460   for (int i =  cols.size (); i--;)
 461     if (scm_is_pair (cols[i]->get_property ("between-cols")))
 462       {
 463         loose_cols_.push (cols[i]);
 464         cols.del (i);
 465       }
 466
 467   spaced_cols_ = cols;
 468   for (int i=0; i < cols.size () - 1; i++)
 469     {
 470       Spring_smob *spring = 0;
 471
 472       for (SCM s = cols[i]->get_property ("ideal-distances");
 473            !spring && scm_is_pair (s);
 474            s = scm_cdr (s))
 475         {
 476           Spring_smob *sp = unsmob_spring (scm_car (s));
 477
 478
 479           if (sp->other_ == cols[i+1])
 480             spring = sp;
 481         }
 482
 483       if (!spring)
 484         programming_error (_f ("No spring between column %d and next one",
 485                                Paper_column::get_rank (cols[i])
 486                                ));
 487
 488       Real ideal = (spring) ? spring->distance_ : spacer_->default_space_;
 489       Real hooke = (spring) ? spring->strength_ : 1.0;
 490
 491       spacer_->add_spring (ideal, hooke);
 492     }
 493
 494   for (int i=0; i < cols.size () - 1; i++)
 495     {
 496       for (SCM s = Spaceable_grob::get_minimum_distances (cols[i]);
 497            scm_is_pair (s); s = scm_cdr (s))
 498         {
 499           Grob * other = unsmob_grob (scm_caar (s));
 500           int oi = cols.find_index (other);
 501           if (oi >= 0)
 502             {
 503               spacer_->add_rod (i, oi, scm_to_double (scm_cdar (s)));
 504             }
 505         }
 506     }
 507 }
 508
 509 Simple_spacer_wrapper::Simple_spacer_wrapper ()
 510 {
 511   spacer_ = new Simple_spacer ();
 512 }
 513
 514 Simple_spacer_wrapper::~Simple_spacer_wrapper ()
 515 {
 516   delete spacer_;
 517 }
 518
 519
 520 Simple_spacer_wrapper::Simple_spacer_wrapper (Simple_spacer_wrapper const&)
 521 {
 522 }