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