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