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