lily/spring-spacer.cc

   1 /*
   2   spring-spacer.cc -- implement Spring_spacer
   3
   4   source file of the GNU LilyPond music typesetter
   5
   6   (c) 1996,1997 Han-Wen Nienhuys <hanwen@stack.nl>
   7 */
   8
   9
  10 #include <math.h>
  11 #include <limits.h>
  12 #include "spring-spacer.hh"
  13 #include "p-col.hh"
  14 #include "debug.hh"
  15 #include "qlp.hh"
  16 #include "unionfind.hh"
  17 #include "idealspacing.hh"
  18 #include "pointer.tcc"
  19 #include "score-column.hh"
  20 #include "paper-def.hh"
  21 #include "dimen.hh"
  22 #include "colhpos.hh"
  23 #include "main.hh"              // experimental_fietsers
  24
  25 Vector
  26 Spring_spacer::default_solution() const
  27 {
  28   return try_initial_solution() ;
  29 }
  30
  31 Score_column*
  32 Spring_spacer::scol_l (int i)
  33 {
  34   return (Score_column*)cols[i].pcol_l_;
  35 }
  36
  37 const Real COLFUDGE=1e-3;
  38 template class P<Real>;         // ugh.
  39
  40 bool
  41 Spring_spacer::contains (Paper_column const *w)
  42 {
  43   for (int i=0; i< cols.size(); i++)
  44     if (cols[i].pcol_l_ == w)
  45       return true;
  46   return false;
  47 }
  48
  49
  50 void
  51 Spring_spacer::OK() const
  52 {
  53 #ifndef NDEBUG
  54   for (int i = 1; i < cols.size(); i++)
  55     assert (cols[i].rank_i_ > cols[i-1].rank_i_);
  56   for (int i = 1; i < loose_col_arr_.size(); i++)
  57     assert (loose_col_arr_[i].rank_i_ > loose_col_arr_[i-1].rank_i_);
  58 #endif
  59 }
  60
  61 /**
  62   Make sure no unconnected columns happen.
  63  */
  64 void
  65 Spring_spacer::handle_loose_cols()
  66 {
  67   Union_find connected (cols.size());
  68   Array<int> fixed;
  69   for (PCursor<Idealspacing*> i (ideal_p_list_.top()); i.ok (); i++)
  70     {
  71       connected.connect (i->left_i_,i->right_i_);
  72     }
  73   for (int i = 0; i < cols.size(); i++)
  74     if (cols[i].fixed())
  75       fixed.push (i);
  76   for (int i=1; i < fixed.size(); i++)
  77     connected.connect (fixed[i-1], fixed[i]);
  78
  79   for (int i = cols.size(); i--;)
  80     {
  81       if (! connected.equiv (fixed[0], i))
  82         {
  83           warning (_("unconnected column: ") + String (i));
  84           loosen_column (i);
  85         }
  86     }
  87   OK();
  88 }
  89
  90
  91 /**
  92   Guess a stupid position for loose columns.  Put loose columns at
  93   regular distances from enclosing calced columns
  94   */
  95 void
  96 Spring_spacer::position_loose_cols (Vector &sol_vec) const
  97 {
  98   if (!loose_col_arr_.size())
  99     return ;
 100   assert (sol_vec.dim());
 101   Array<bool> fix_b_arr;
 102   fix_b_arr.set_size (cols.size() + loose_col_arr_.size ());
 103   Real utter_right_f=-infinity_f;
 104   Real utter_left_f =infinity_f;
 105   for (int i=0; i < loose_col_arr_.size(); i++)
 106     {
 107       fix_b_arr[loose_col_arr_[i].rank_i_] = false;
 108     }
 109   for (int i=0; i < cols.size(); i++)
 110     {
 111       int r= cols[i].rank_i_;
 112       fix_b_arr[r] = true;
 113       utter_right_f = utter_right_f >? sol_vec (i);
 114       utter_left_f = utter_left_f <? sol_vec (i);
 115     }
 116   Vector v (fix_b_arr.size());
 117   int j =0;
 118   int k =0;
 119   for (int i=0; i < v.dim(); i++)
 120     {
 121       if (fix_b_arr[i])
 122         {
 123           assert (cols[j].rank_i_ == i);
 124           v (i) = sol_vec (j++);
 125         }
 126       else
 127         {
 128           Real left_pos_f =
 129             (j>0) ?sol_vec (j-1) : utter_left_f;
 130           Real right_pos_f =
 131             (j < sol_vec.dim()) ? sol_vec (j) : utter_right_f;
 132           int left_rank = (j>0) ? cols[j-1].rank_i_ : 0;
 133           int right_rank = (j<sol_vec.dim()) ? cols[j].rank_i_ : sol_vec.dim ();
 134
 135           int d_r = right_rank - left_rank;
 136           Colinfo loose=loose_col_arr_[k++];
 137           int r = loose.rank_i_ ;
 138           assert (r > left_rank && r < right_rank);
 139
 140           v (i) =  (r - left_rank)*left_pos_f/ d_r +
 141             (right_rank - r) *right_pos_f /d_r;
 142         }
 143     }
 144   sol_vec = v;
 145 }
 146
 147 bool
 148 Spring_spacer::check_constraints (Vector v) const
 149 {
 150   int dim=v.dim();
 151   assert (dim == cols.size());
 152
 153   for (int i=0; i < dim; i++)
 154     {
 155
 156       if (cols[i].fixed()&&
 157           abs (cols[i].fixed_position() - v (i)) > COLFUDGE)
 158         return false;
 159
 160       if (!i)
 161         continue;
 162
 163       Real mindist=cols[i-1].width_[RIGHT]
 164         -cols[i].width_[LEFT];
 165
 166       // ugh... compares
 167       Real dif =v (i) - v (i-1)- mindist;
 168       bool b = (dif > - COLFUDGE);
 169
 170
 171       if (!b)
 172         return false;
 173
 174     }
 175   return true;
 176 }
 177
 178 /// try to generate a solution which obeys the min distances and fixed
 179 /// positions
 180 Vector
 181 Spring_spacer::try_initial_solution() const
 182 {
 183   int dim=cols.size();
 184   Vector initsol (dim);
 185   for (int i=0; i < dim; i++)
 186     {
 187       if (cols[i].fixed())
 188         {
 189           initsol (i)=cols[i].fixed_position();
 190
 191           if (i > 0)
 192             {
 193               Real r =initsol (i-1)  + cols[i-1].width_[RIGHT];
 194               if (initsol (i) < r)
 195                   initsol (i) =r;
 196             }
 197
 198         }
 199       else
 200         {
 201           Real mindist=cols[i-1].width_[RIGHT]
 202             - cols[i].width_[LEFT];
 203           if (mindist < 0.0)
 204             warning (_("Excentric column"));
 205           initsol (i)=initsol (i-1)+mindist;
 206         }
 207     }
 208
 209   return initsol;
 210 }
 211
 212
 213
 214 // generate the matrices
 215 void
 216 Spring_spacer::make_matrices (Matrix &quad, Vector &lin, Real &c) const
 217 {
 218   quad.fill (0);
 219   lin.fill (0);
 220   c = 0;
 221
 222   for (PCursor<Idealspacing*> i (ideal_p_list_.top()); i.ok (); i++)
 223     {
 224       int l = i->left_i_;
 225       int r = i->right_i_;
 226
 227       quad (r,r) += i->hooke_f_;
 228       quad (r,l) -= i->hooke_f_;
 229       quad (l,r) -= i->hooke_f_;
 230       quad (l,l) += i->hooke_f_;
 231
 232       lin (r) -= i->space_f_*i->hooke_f_;
 233       lin (l) += i->space_f_*i->hooke_f_;
 234
 235       c += sqr (i->space_f_);
 236     }
 237 }
 238
 239 void
 240 Spring_spacer::set_fixed_cols (Mixed_qp &qp) const
 241 {
 242   for (int j=0; j < cols.size(); j++)
 243     if (cols[j].fixed())
 244       qp.add_fixed_var (j,cols[j].fixed_position());
 245 }
 246
 247 // put the constraints into the LP problem
 248 void
 249 Spring_spacer::make_constraints (Mixed_qp& lp) const
 250 {
 251   int dim=cols.size();
 252   for (int j=0; j < dim; j++)
 253     {
 254       Colinfo c=cols[j];
 255       if (j > 0)
 256         {
 257           Vector c1(dim);
 258
 259           c1(j)=1.0 ;
 260           c1(j-1)=-1.0 ;
 261
 262           lp.add_inequality_cons (c1, cols[j-1].width_[RIGHT]
 263                                   - cols[j].width_[LEFT]);
 264         }
 265     }
 266 }
 267
 268
 269 Real
 270 Spring_spacer::calculate_energy_f (Vector solution) const
 271 {
 272   Real e = 0.0;
 273   for (PCursor<Idealspacing*> i (ideal_p_list_.top()); i.ok(); i++)
 274     {
 275       e += i->energy_f(solution(i->right_i_) - solution(i->left_i_));
 276     }
 277
 278   return e;
 279 }
 280 void
 281 Spring_spacer::lower_bound_solution (Col_hpositions*positions) const
 282 {
 283   Mixed_qp lp (cols.size());
 284   make_matrices (lp.quad,lp.lin, lp.const_term);
 285   set_fixed_cols (lp);
 286
 287   Vector start (cols.size());
 288   start.fill (0.0);
 289   Vector solution_vec (lp.solve (start));
 290
 291   DOUT << "Lower bound sol: " << solution_vec;
 292   positions->energy_f_ = calculate_energy_f (solution_vec);
 293   positions->config = solution_vec;
 294   positions->satisfies_constraints_b_ = check_constraints (solution_vec);
 295 }
 296
 297 void
 298 Spring_spacer::solve (Col_hpositions*positions) const
 299 {
 300   Vector solution_try (try_initial_solution());
 301
 302   if  (check_constraints (solution_try))
 303     {
 304       Mixed_qp lp (cols.size());
 305       make_matrices (lp.quad,lp.lin, lp.const_term);
 306       make_constraints (lp);
 307       set_fixed_cols (lp);
 308
 309       Vector solution_vec (lp.solve (solution_try));
 310
 311
 312       positions->satisfies_constraints_b_ = check_constraints (solution_vec);
 313       if (!positions->satisfies_constraints_b_)
 314         {
 315           WARN << _("solution doesn't satisfy constraints.\n") ;
 316         }
 317       position_loose_cols (solution_vec);
 318       positions->energy_f_ = calculate_energy_f (solution_vec);
 319       positions->config = solution_vec;
 320       positions->error_col_l_arr_ = error_pcol_l_arr();
 321     }
 322   else
 323     {
 324       positions->set_stupid_solution (solution_try);
 325     }
 326 }
 327
 328 /**
 329   add one column to the problem.
 330 */
 331 void
 332 Spring_spacer::add_column (Paper_column  *col, bool fixed, Real fixpos)
 333 {
 334   Colinfo c (col,(fixed)? &fixpos :  0);
 335   if (cols.size())
 336     c.rank_i_ = cols.top().rank_i_+1;
 337   else
 338     c.rank_i_ = 0;
 339   cols.push (c);
 340 }
 341
 342 Line_of_cols
 343 Spring_spacer::error_pcol_l_arr() const
 344 {
 345   Array<Paper_column*> retval;
 346   for (int i=0; i< cols.size(); i++)
 347     if (cols[i].ugh_b_)
 348       retval.push (cols[i].pcol_l_);
 349   for (int i=0;  i < loose_col_arr_.size(); i++)
 350     {
 351       retval.push (loose_col_arr_[i].pcol_l_);
 352     }
 353   return retval;
 354 }
 355
 356 void
 357 Spring_spacer::loosen_column (int i)
 358 {
 359   Colinfo c=cols.get (i);
 360   for (PCursor<Idealspacing*> j (ideal_p_list_.top()); j.ok (); j++)
 361     {
 362       if (j->left_i_ == i|| j->right_i_ == i)
 363         j.del();
 364       else
 365         j++;
 366     }
 367   c.ugh_b_ = true;
 368
 369   int j=0;
 370   for (; j < loose_col_arr_.size(); j++)
 371     {
 372       if (loose_col_arr_[j].rank_i_ > c.rank_i_)
 373         break;
 374     }
 375   loose_col_arr_.insert (c,j);
 376 }
 377
 378
 379 void
 380 Spring_spacer::print() const
 381 {
 382 #ifndef NPRINT
 383   for (int i=0; i < cols.size(); i++)
 384     {
 385       DOUT << "col " << i<<' ';
 386       cols[i].print();
 387     }
 388   for (PCursor<Idealspacing*> i (ideal_p_list_.top()); i.ok (); i++)
 389     {
 390       i->print();
 391     }
 392 #endif
 393 }
 394
 395
 396 void
 397 Spring_spacer::connect (int i, int j, Real d, Real h)
 398 {
 399   assert(d >= 0 && d <= 100 CM);
 400   assert(h >=0);
 401
 402   Idealspacing * s = new Idealspacing;
 403
 404   s->left_i_ = i ;
 405   s->right_i_ = j;
 406   s->space_f_ = d;
 407   s->hooke_f_ = h;
 408
 409   ideal_p_list_.bottom().add (s);
 410 }
 411
 412
 413
 414
 415 void
 416 Spring_spacer::prepare()
 417 {
 418   calc_idealspacing();
 419   handle_loose_cols();
 420   print();
 421 }
 422
 423 Line_spacer*
 424 Spring_spacer::constructor()
 425 {
 426   return new Spring_spacer;
 427 }
 428
 429
 430
 431 /**
 432   get the shortest_playing running note at a time. */
 433 void
 434 Spring_spacer::get_ruling_durations(Array<Moment> &shortest_playing_arr,
 435                                     Array<Moment> &context_shortest_arr)
 436 {
 437   for (int i=0; i < cols.size(); i++)
 438     {
 439       scol_l (i)->preprocess();
 440       scol_l (i)->print ();
 441     }
 442   int start_context_i=0;
 443   Moment context_shortest = infinity_mom;
 444   context_shortest_arr.set_size(cols.size());
 445
 446   for (int i=0; i < cols.size(); i++)
 447     {
 448       Moment now = scol_l (i)->when();
 449       Moment shortest_playing = infinity_mom;
 450
 451       if (scol_l (i)->breakable_b_)
 452         {
 453           for (int ji=i; ji >= start_context_i; ji--)
 454             context_shortest_arr[ji] = context_shortest;
 455           start_context_i = i;
 456           context_shortest = infinity_mom;
 457         }
 458       if (scol_l (i)->durations.size())
 459         {
 460           context_shortest = context_shortest <? scol_l(i)->durations[0];
 461         }
 462
 463       // ji was j, but triggered ICE
 464       for (int ji=i+1; ji --;)
 465         {
 466           if (scol_l(ji)->durations.size() &&
 467               now - scol_l(ji)->when() >= shortest_playing)
 468             break;
 469
 470           for (int k =  scol_l (ji)->durations.size();
 471                k-- && scol_l(ji)->durations[k] + scol_l(ji)->when() > now;
 472                )
 473             {
 474               shortest_playing = shortest_playing <? scol_l(ji)->durations[k];
 475             }
 476         }
 477       shortest_playing_arr.push(shortest_playing);
 478     }
 479
 480 #ifndef NPRINT
 481   DOUT << "shortest_playing/:[ ";
 482   for (int i=0; i < shortest_playing_arr.size(); i++)
 483     {
 484       DOUT << shortest_playing_arr[i] << " ";
 485       DOUT << context_shortest_arr[i] << ", ";
 486     }
 487   DOUT << "]\n";
 488 #endif
 489 }
 490
 491 /**
 492   generate springs between columns.
 493
 494   UNDER DESTRUCTION
 495
 496   TODO: This needs rethinking.  Spacing should take optical
 497   effects into account, and should be local (measure wide)
 498
 499   The algorithm is taken from :
 500
 501   John S. Gourlay. ``Spacing a Line of Music,'' Technical Report
 502   OSU-CISRC-10/87-TR35, Department of Computer and Information
 503   Science, The Ohio State University, 1987.
 504
 505   */
 506 void
 507 Spring_spacer::calc_idealspacing()
 508 {
 509   Array<Moment> shortest_playing_arr;
 510   Array<Moment> context_shortest_arr;
 511   get_ruling_durations(shortest_playing_arr, context_shortest_arr);
 512
 513   Real interline_f = paper_l ()->interline_f ();
 514   Real nw_f = paper_l ()->note_width ();
 515
 516   Array<Real> ideal_arr_;
 517   Array<Real> hooke_arr_;
 518   for (int i=0; i < cols.size() - 1; i++){
 519     ideal_arr_.push (-1.0);
 520     hooke_arr_.push (1.0);
 521   }
 522
 523   /*
 524      First do all non-musical columns
 525    */
 526   for (int i=0; i < cols.size(); i++)
 527     {
 528       if (!scol_l (i)->musical_b() && i+1 < cols.size())
 529         {
 530           Real symbol_distance =cols[i].width_[RIGHT] + 2 PT;
 531           Real durational_distance = 0;
 532
 533
 534           Moment delta_t =  scol_l (i+1)->when() - scol_l (i)->when () ;
 535
 536           Real k=  paper_l()->arithmetic_constant(context_shortest_arr[i]);
 537           /*
 538             ugh should use shortest_playing distance
 539           */
 540           if (delta_t)
 541             durational_distance =  paper_l()->duration_to_dist (delta_t,k);
 542           symbol_distance += -cols[i+1].width_[LEFT];
 543
 544
 545           ideal_arr_[i] = symbol_distance >? durational_distance;
 546           hooke_arr_[i] = 1; //2.0;
 547         }
 548     }
 549
 550   /*
 551      Then musicals
 552      */
 553   for (int i=0; i < cols.size(); i++)
 554     {
 555       if (scol_l (i)->musical_b())
 556         {
 557           Moment shortest_playing_len = shortest_playing_arr[i];
 558           Moment context_shortest = context_shortest_arr[i];
 559           if (! shortest_playing_len)
 560             {
 561               warning (_("Can't find a ruling note at ")
 562                        +String (scol_l (i)->when()));
 563               shortest_playing_len = 1;
 564             }
 565           if (! context_shortest)
 566             {
 567               warning(_("No minimum in measure at ")
 568                       + String (scol_l (i)->when()));
 569               context_shortest = 1;
 570             }
 571           Moment delta_t = scol_l (i+1)->when() - scol_l (i)->when ();
 572           Real k=  paper_l()->arithmetic_constant(context_shortest);
 573           Real dist = paper_l()->duration_to_dist (shortest_playing_len, k);
 574           dist *= delta_t / shortest_playing_len;
 575
 576           /*
 577             According to [Ross] and [Wanske], and from what i've seen:
 578
 579             * whitespace at the begin of the bar should be fixed at
 580             (about) one interline.
 581             [Ross]:
 582             when spacing gets real tight, a smaller fixed value may be
 583             used, so that there are two discrete amounts of whitespace
 584             possible at the begin of a bar; but this is not implemented
 585             right now.
 586
 587             * whitespace at the end of the bar is the normal amount of
 588             "hinterfleish" that would have been used, had there been
 589             yet another note in the bar.
 590             [Ross]:
 591             some editors argue that the bar line should not take any
 592             space, not to hinder the flow of music spaced around a bar
 593             line.
 594             [Ross] and [Wanske] do not suggest this, however.  Further,
 595             it introduces some spacing problems and think that it is ugly
 596             too.
 597             [jcn]
 598           */
 599
 600           /*
 601              first musical column of bar
 602           */
 603           if (i && scol_l (i - 1)->breakable_b_)
 604             {
 605               // fixed: probably should set minimum (rod/spring)?
 606               cols[i-1].width_[RIGHT] += interline_f;
 607               // should adjust dist too?
 608               ideal_arr_[i-1] = ideal_arr_[i-1] >? interline_f;
 609             }
 610
 611           /*
 612              last musical column of bar
 613           */
 614           if (i + 1 < cols.size () && scol_l(i+1)->breakable_b_)
 615             {
 616               // hmm, how bout?
 617               dist = dist >? interline_f;
 618
 619               /*
 620                 uhuh, this code looks fine, already?
 621                 someone was junking this last "hinterfleisch" whitespace?!
 622
 623                 but this seems to be fixed now :-)
 624               */
 625               // set minimum rod
 626               cols[i].width_[RIGHT] += interline_f;
 627             }
 628
 629           // ugh, do we need this?
 630           if (i < cols.size () - 1 && !scol_l (i + 1)->musical_b ())
 631             {
 632               Real minimum = -cols[i + 1].width_[LEFT] + cols[i].width_[RIGHT]
 633                 + interline_f / 2;
 634               dist = dist >? minimum;
 635             }
 636
 637           // ugh: never let columns touch... try to set over here...
 638           // ugh: use j iso i triggers ice in gcc-2.7.2.3
 639           cols[i].width_[LEFT] -= nw_f / 4;
 640           ideal_arr_[i] = dist;
 641         }
 642     }
 643
 644   for (int i=0; i < ideal_arr_.size(); i++)
 645     {
 646       assert (ideal_arr_[i] >=0 && hooke_arr_[i] >=0);
 647       connect (i, i+1, ideal_arr_[i], hooke_arr_[i]);
 648     }
 649 }