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--1999, 1998 Han-Wen Nienhuys <hanwen@cs.uu.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 "dimensions.hh"
  16 #include "qlp.hh"
  17 #include "unionfind.hh"
  18 #include "idealspacing.hh"
  19 #include "pointer.tcc"
  20 #include "score-column.hh"
  21 #include "paper-def.hh"
  22 #include "colhpos.hh"
  23 #include "main.hh"
  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 dynamic_cast<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_b (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->cols_drul_[LEFT],i->cols_drul_[RIGHT]);
  72     }
  73   for (int i = 0; i < cols_.size(); i++)
  74     if (cols_[i].fixed_b())
  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 (_f ("unconnected column: %d", 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           Column_info 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   DOUT << "checking " << v;
 153   for (int i=0; i < dim; i++)
 154     {
 155       if (cols_[i].fixed_b() &&
 156           abs (cols_[i].fixed_position() - v (i)) > COLFUDGE)
 157         {
 158           DOUT << "Fixpos broken\n";
 159           return false;
 160         }
 161       Array<Spacer_rod> const &rods (cols_[i].rods_[RIGHT]);
 162       for (int j =0; j < rods.size (); j++)
 163         {
 164           int other =rods[j].other_idx_;
 165           Real diff =v (other) - v (i) ;
 166           if (COLFUDGE +diff <  rods[j].distance_f_)
 167             {
 168               DOUT << "i, other_i: " << i << "  " << other << '\n';
 169               DOUT << "dist, minimal = " << diff << " "
 170                    << rods[j].distance_f_ << '\n';
 171               return false;
 172             }
 173         }
 174
 175     }
 176   return true;
 177 }
 178
 179 /** try to generate a solution which obeys the min distances and fixed positions
 180  */
 181 Vector
 182 Spring_spacer::try_initial_solution() const
 183 {
 184   Vector v;
 185   if (!try_initial_solution_and_tell (v))
 186     {
 187       warning (_ ("I'm too fat; call Oprah"));
 188     }
 189   return v;
 190
 191 }
 192
 193 bool
 194 Spring_spacer::try_initial_solution_and_tell (Vector &v) const
 195 {
 196   int dim=cols_.size();
 197   bool succeeded = true;
 198   Vector initsol (dim);
 199
 200   assert (cols_[0].fixed_b ());
 201   DOUT << "fixpos 0 " << cols_[0].fixed_position ();
 202   for (int i=0; i < dim; i++)
 203     {
 204       Real min_x = i ?  initsol (i-1) : cols_[0].fixed_position ();
 205       Array<Spacer_rod> const &sr_arr(cols_[i].rods_[LEFT]);
 206       for (int j=0; j < sr_arr.size (); j++)
 207         {
 208           min_x = min_x >? (initsol (sr_arr[j].other_idx_) + sr_arr[j].distance_f_);
 209         }
 210       initsol (i) = min_x;
 211
 212       if (cols_[i].fixed_b())
 213         {
 214           initsol (i)=cols_[i].fixed_position();
 215           if (initsol (i) < min_x )
 216             {
 217               DOUT << "failing: init, min : " << initsol (i) << " " << min_x << '\n';
 218               initsol (i) = min_x;
 219               succeeded = false;
 220             }
 221         }
 222     }
 223   v = initsol;
 224
 225   DOUT << "tried and told solution: " << v;
 226   if (!succeeded)
 227     DOUT << "(failed)\n";
 228   return succeeded;
 229 }
 230
 231
 232
 233 // generate the matrices
 234 void
 235 Spring_spacer::make_matrices (Matrix &quad, Vector &lin, Real &c) const
 236 {
 237   quad.fill (0);
 238   lin.fill (0);
 239   c = 0;
 240
 241   for (PCursor<Idealspacing*> i (ideal_p_list_.top()); i.ok (); i++)
 242     {
 243       int l = i->cols_drul_[LEFT];
 244       int r = i->cols_drul_[RIGHT];
 245
 246       quad (r,r) += i->hooke_f_;
 247       quad (r,l) -= i->hooke_f_;
 248       quad (l,r) -= i->hooke_f_;
 249       quad (l,l) += i->hooke_f_;
 250
 251       lin (r) -= i->space_f_*i->hooke_f_;
 252       lin (l) += i->space_f_*i->hooke_f_;
 253
 254       c += sqr (i->space_f_);
 255     }
 256
 257   if (quad.dim() > 10)
 258     quad.set_band();
 259
 260
 261 }
 262
 263 void
 264 Spring_spacer::set_fixed_cols (Mixed_qp &qp) const
 265 {
 266   for (int j=0; j < cols_.size(); j++)
 267     if (cols_[j].fixed_b())
 268       qp.add_fixed_var (j,cols_[j].fixed_position());
 269 }
 270
 271 // put the constraints into the LP problem
 272 void
 273 Spring_spacer::make_constraints (Mixed_qp& lp) const
 274 {
 275   int dim=cols_.size();
 276
 277   for (int j=0; j < dim -1; j++)
 278     {
 279       Array<Spacer_rod> const&rod_arr (cols_[j].rods_[RIGHT]);
 280       for (int i = 0; i < rod_arr.size (); i++)
 281         {
 282           Vector c1(dim);
 283           c1(rod_arr[i].other_idx_)=1.0 ;
 284           c1(j)=-1.0 ;
 285
 286           lp.add_inequality_cons (c1, rod_arr[i].distance_f_);
 287         }
 288     }
 289 }
 290
 291
 292 Real
 293 Spring_spacer::calculate_energy_f (Vector solution) const
 294 {
 295   Real e = 0.0;
 296   for (PCursor<Idealspacing*> i (ideal_p_list_.top()); i.ok(); i++)
 297     {
 298       e += i->energy_f(solution(i->cols_drul_[RIGHT]) - solution(i->cols_drul_[LEFT]));
 299     }
 300
 301   return e;
 302 }
 303 void
 304 Spring_spacer::lower_bound_solution (Column_x_positions*positions) const
 305 {
 306   Mixed_qp lp (cols_.size());
 307   make_matrices (lp.quad_,lp.lin_, lp.const_term_);
 308   set_fixed_cols (lp);
 309
 310   Vector start (cols_.size());
 311   start.fill (0.0);
 312   Vector solution_vec (lp.solve (start));
 313
 314   DOUT << "Lower bound sol: " << solution_vec;
 315   positions->energy_f_ = calculate_energy_f (solution_vec);
 316   positions->config = solution_vec;
 317   positions->satisfies_constraints_b_ = check_constraints (solution_vec);
 318 }
 319
 320 Spring_spacer::Spring_spacer ()
 321 {
 322   energy_normalisation_f_ = 1.0;
 323 }
 324
 325 void
 326 Spring_spacer::solve (Column_x_positions*positions) const
 327 {
 328   DOUT << "Spring_spacer::solve ()...";
 329
 330   Vector solution_try;
 331
 332   bool constraint_satisfaction = try_initial_solution_and_tell (solution_try);
 333   if  (constraint_satisfaction)
 334     {
 335       Mixed_qp lp (cols_.size());
 336       make_matrices (lp.quad_,lp.lin_, lp.const_term_);
 337       make_constraints (lp);
 338       set_fixed_cols (lp);
 339
 340       Vector solution_vec (lp.solve (solution_try));
 341
 342       positions->satisfies_constraints_b_ = check_constraints (solution_vec);
 343       if (!positions->satisfies_constraints_b_)
 344         {
 345           WARN << _ ("solution doesn't satisfy constraints") << '\n' ;
 346         }
 347       position_loose_cols (solution_vec);
 348       positions->energy_f_ = calculate_energy_f (solution_vec);
 349       positions->config = solution_vec;
 350       positions->error_col_l_arr_ = error_pcol_l_arr();
 351     }
 352   else
 353     {
 354       positions->set_stupid_solution (solution_try);
 355     }
 356
 357   DOUT << "Finished Spring_spacer::solve ()...";
 358 }
 359
 360 /**
 361   add one column to the problem.
 362 */
 363 void
 364 Spring_spacer::add_column (Paper_column  *col, bool fixed, Real fixpos)
 365 {
 366   Column_info c (col,(fixed)? &fixpos :  0);
 367   int this_rank =  cols_.size();
 368   c.rank_i_ = this_rank;
 369
 370   for (int i=0; i < col->minimal_dists_arr_drul_[LEFT].size (); i++)
 371     {
 372       Column_rod &cr = col->minimal_dists_arr_drul_[LEFT][i];
 373       int left_idx = cr.other_l_->rank_i () - cols_[0].pcol_l_->rank_i ();
 374       if (left_idx < 0)
 375         continue;
 376
 377       if (cols_[left_idx].pcol_l_ != cr.other_l_)
 378         continue;
 379
 380       Spacer_rod l_rod;
 381       l_rod.distance_f_ = cr.distance_f_;
 382       l_rod.other_idx_ = left_idx;
 383       c.rods_[LEFT].push (l_rod);
 384
 385       Spacer_rod r_rod;
 386       r_rod.distance_f_ = cr.distance_f_;
 387       r_rod.other_idx_ = this_rank;
 388       cols_[left_idx].rods_[RIGHT].push (r_rod);
 389     }
 390
 391   cols_.push (c);
 392 }
 393
 394 Line_of_cols
 395 Spring_spacer::error_pcol_l_arr() const
 396 {
 397   Link_array<Paper_column> retval;
 398   for (int i=0; i< cols_.size(); i++)
 399     if (cols_[i].ugh_b_)
 400       retval.push (cols_[i].pcol_l_);
 401   for (int i=0;  i < loose_col_arr_.size(); i++)
 402     {
 403       retval.push (loose_col_arr_[i].pcol_l_);
 404     }
 405   return retval;
 406 }
 407
 408 void
 409 Spring_spacer::loosen_column (int i)
 410 {
 411   Column_info c=cols_.get (i);
 412   for (PCursor<Idealspacing*> j (ideal_p_list_.top()); j.ok (); j++)
 413     {
 414       if (j->cols_drul_[LEFT] == i|| j->cols_drul_[RIGHT] == i)
 415         j.del();
 416       else
 417         j++;
 418     }
 419   c.ugh_b_ = true;
 420
 421   int j=0;
 422   for (; j < loose_col_arr_.size(); j++)
 423     {
 424       if (loose_col_arr_[j].rank_i_ > c.rank_i_)
 425         break;
 426     }
 427   loose_col_arr_.insert (c,j);
 428 }
 429
 430
 431 void
 432 Spring_spacer::print() const
 433 {
 434 #ifndef NPRINT
 435   for (int i=0; i < cols_.size(); i++)
 436     {
 437       DOUT << "col " << i << " ";
 438       cols_[i].print();
 439     }
 440   for (PCursor<Idealspacing*> i (ideal_p_list_.top()); i.ok (); i++)
 441     {
 442       i->print();
 443     }
 444 #endif
 445 }
 446
 447
 448 void
 449 Spring_spacer::connect (int i, int j, Real d, Real h)
 450 {
 451   assert(d >= 0 && d <= 100 CM);
 452   assert(h >=0);
 453
 454   Idealspacing * s = new Idealspacing;
 455
 456   s->cols_drul_[LEFT] = i ;
 457   s->cols_drul_[RIGHT] = j;
 458   s->space_f_ = d;
 459   s->hooke_f_ = h;
 460
 461   ideal_p_list_.bottom().add (s);
 462 }
 463
 464
 465
 466
 467 void
 468 Spring_spacer::prepare()
 469 {
 470   DOUT << "Preparing..";
 471   calc_idealspacing();
 472   handle_loose_cols();
 473   print();
 474   DOUT << "finished preparing.\n";
 475 }
 476
 477 Line_spacer*
 478 Spring_spacer::constructor()
 479 {
 480   return new Spring_spacer;
 481 }
 482
 483
 484
 485 /**
 486   get the shortest_playing running note at a time. */
 487 void
 488 Spring_spacer::get_ruling_durations(Array<Moment> &shortest_playing_arr,
 489                                     Array<Moment> &context_shortest_arr)
 490 {
 491   for (int i=0; i < cols_.size(); i++)
 492     {
 493       scol_l (i)->preprocess();
 494       scol_l (i)->print ();
 495     }
 496   int start_context_i=0;
 497   Moment context_shortest;
 498   context_shortest.set_infinite (1);
 499   context_shortest_arr.set_size(cols_.size());
 500
 501   for (int i=0; i < cols_.size(); i++)
 502     {
 503       Moment now = scol_l (i)->when();
 504       Moment shortest_playing;
 505       shortest_playing.set_infinite (1);
 506
 507       if (scol_l (i)->breakable_b_)
 508         {
 509           for (int ji=i; ji >= start_context_i; ji--)
 510             context_shortest_arr[ji] = context_shortest;
 511           start_context_i = i;
 512           context_shortest.set_infinite (1);
 513         }
 514       if (scol_l (i)->durations.size())
 515         {
 516           context_shortest = context_shortest <? scol_l(i)->durations[0];
 517         }
 518
 519       // ji was j, but triggered ICE
 520       for (int ji=i+1; ji --;)
 521         {
 522           if (scol_l(ji)->durations.size() &&
 523               now - scol_l(ji)->when() >= shortest_playing)
 524             break;
 525
 526           for (int k =  scol_l (ji)->durations.size();
 527                k-- && scol_l(ji)->durations[k] + scol_l(ji)->when() > now;
 528                )
 529             {
 530               shortest_playing = shortest_playing <? scol_l(ji)->durations[k];
 531             }
 532         }
 533       shortest_playing_arr.push(shortest_playing);
 534     }
 535
 536 #ifndef NPRINT
 537   DOUT << "shortest_playing/:[ ";
 538   for (int i=0; i < shortest_playing_arr.size(); i++)
 539     {
 540       DOUT << shortest_playing_arr[i] << " ";
 541       DOUT << context_shortest_arr[i] << ", ";
 542     }
 543   DOUT << "]\n";
 544 #endif
 545 }
 546
 547 /*
 548   TODO: take out the refs to width
 549
 550  */
 551 /**
 552   generate springs between columns.
 553
 554   TODO: This needs rethinking.......
 555
 556   *  Spacing should take optical
 557   effects into account
 558
 559   *  Should be decentralised
 560
 561   The algorithm is taken from :
 562
 563   John S. Gourlay. ``Spacing a Line of Music,'' Technical Report
 564   OSU-CISRC-10/87-TR35, Department of Computer and Information
 565   Science, The Ohio State University, 1987.
 566
 567   */
 568 void
 569 Spring_spacer::calc_idealspacing()
 570 {
 571   Array<Moment> shortest_playing_arr;
 572   Array<Moment> context_shortest_arr;
 573   get_ruling_durations(shortest_playing_arr, context_shortest_arr);
 574
 575   Real interline_f = paper_l ()->interline_f ();
 576
 577
 578   Array<Real> ideal_arr;
 579   Array<Real> hooke_arr;
 580   for (int i=0; i < cols_.size() - 1; i++){
 581     ideal_arr.push (-1.0);
 582     hooke_arr.push (1.0);
 583   }
 584
 585   /*
 586      First do all non-musical columns
 587   */
 588   for (int i=0; i < cols_.size(); i++)
 589     {
 590       if (!scol_l (i)->musical_b() && i+1 < cols_.size())
 591         {
 592           Real symbol_distance =cols_[i].width_[RIGHT] + 2 PT;
 593           Real durational_distance = 0;
 594           Moment delta_t =  scol_l (i+1)->when() - scol_l (i)->when () ;
 595
 596           /*
 597             ugh should use shortest_playing distance
 598           */
 599           if (delta_t)
 600             {
 601               Real k=  paper_l()->arithmetic_constant (context_shortest_arr[i]);
 602               durational_distance =  paper_l()->length_mom_to_dist (delta_t,k);
 603             }
 604           symbol_distance += -cols_[i+1].width_[LEFT];
 605
 606
 607           ideal_arr[i] = symbol_distance >? durational_distance;
 608           hooke_arr[i] = 1; //2.0;
 609         }
 610     }
 611
 612   /*
 613      Then musicals
 614   */
 615   for (int i=0; i < cols_.size(); i++)
 616     {
 617       if (scol_l (i)->musical_b())
 618         {
 619           Moment shortest_playing_len = shortest_playing_arr[i];
 620           Moment context_shortest = context_shortest_arr[i];
 621           if (! shortest_playing_len)
 622             {
 623               warning (_f ("can't find a ruling note at %s",
 624                 scol_l (i)->when().str ()));
 625               shortest_playing_len = 1;
 626             }
 627           if (! context_shortest)
 628             {
 629               warning (_f ("no minimum in measure at %s",
 630                       scol_l (i)->when().str ()));
 631               context_shortest = 1;
 632             }
 633           Moment delta_t = scol_l (i+1)->when() - scol_l (i)->when ();
 634           Real k=  paper_l()->arithmetic_constant(context_shortest);
 635           Real dist = paper_l()->length_mom_to_dist (shortest_playing_len, k);
 636           dist *= (double)(delta_t / shortest_playing_len);
 637
 638           /*
 639             According to [Ross] and [Wanske], and from what i've seen:
 640
 641             * whitespace at the begin of the bar should be fixed at
 642             (about) one interline.
 643
 644             [Ross]:
 645             when spacing gets real tight, a smaller fixed value may be
 646             used, so that there are two discrete amounts of whitespace
 647             possible at the begin of a bar; but this is not implemented
 648             right now.
 649
 650             * whitespace at the end of the bar is the normal amount of
 651             "hinterfleish" that would have been used, had there been
 652             yet another note in the bar.
 653
 654             [Ross]:
 655             some editors argue that the bar line should not take any
 656             space, not to hinder the flow of music spaced around a bar
 657             line.
 658
 659             [Ross] and [Wanske] do not suggest this, however.  Further,
 660             it introduces some spacing problems and I think that it is ugly
 661             too.
 662
 663             [jcn]
 664           */
 665
 666           /*
 667              first musical column of bar
 668           */
 669           if (i && scol_l (i - 1)->breakable_b_)
 670             {
 671               // one interline minimum at start of bar
 672
 673               // cols_[i].width_[RIGHT] += interline_f;
 674               cols_[i].width_[RIGHT] = cols_[i].width_[RIGHT] >? interline_f;
 675
 676               // should adjust dist too?
 677               ideal_arr[i-1] = ideal_arr[i-1] >? (2 * interline_f);
 678             }
 679
 680           /*
 681              last musical column of bar
 682           */
 683           if (i + 1 < cols_.size () && scol_l(i+1)->breakable_b_)
 684             {
 685               // two interline minimum ok for last column?
 686               dist = dist >? 2 * interline_f;
 687
 688               // set minimum rod
 689               /*
 690                 urg: simply *adding* an interline leaves big gaps at
 691                 end of measure in star-spangled-banner (after lyrics
 692                 at eom).
 693
 694                    cols_[i].width_[RIGHT] += interline_f; // before
 695
 696                 having a minimum of one interline solves this problem
 697                 in most (but not all??) cases.
 698
 699                 for music without lyrics (esp. when set very tightly),
 700                 adding an interline looks good: probably because this
 701                 hides a bug that allows the last note's "hinterfleish"
 702                 to be removed (e.g., see wtk1-fugue2: that's ugly now).
 703                 -- jcn
 704                */
 705
 706               cols_[i].width_[RIGHT] = cols_[i].width_[RIGHT] >? 2 * interline_f;
 707             }
 708
 709           // ugh, do we need this?
 710           if (i < cols_.size () - 1 && !scol_l (i + 1)->musical_b ())
 711             {
 712               Real minimum = -cols_[i + 1].width_[LEFT] + cols_[i].width_[RIGHT]
 713                 + interline_f / 2;
 714               dist = dist >? minimum;
 715             }
 716           ideal_arr[i] = dist;
 717         }
 718     }
 719
 720   /*
 721     shorter distances should stretch less.
 722
 723     (and how bout
 724
 725       hooke[i] = 2 * max_ideal_space - ideal[i]
 726
 727     ?)
 728   */
 729   for (int i=0; i < ideal_arr.size(); i++)
 730     hooke_arr[i] = 1/ideal_arr[i];
 731
 732   for (int i=0; i < ideal_arr.size(); i++)
 733     {
 734       assert (ideal_arr[i] >=0 && hooke_arr[i] >=0);
 735       connect (i, i+1, ideal_arr[i], hooke_arr[i]);
 736     }
 737 }