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, 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_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->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<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->left_i_;
 244       int r = i->right_i_;
 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   // experimental
 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->right_i_) - solution(i->left_i_));
 299     }
 300
 301   return e;
 302 }
 303 void
 304 Spring_spacer::lower_bound_solution (Col_hpositions*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 void
 321 Spring_spacer::solve (Col_hpositions*positions) const
 322 {
 323
 324   DOUT << "Spring_spacer::solve ()...";
 325   Vector solution_try;
 326
 327   bool constraint_satisfaction = try_initial_solution_and_tell (solution_try);
 328   if  (constraint_satisfaction)
 329     {
 330       Mixed_qp lp (cols_.size());
 331       make_matrices (lp.quad_,lp.lin_, lp.const_term_);
 332       make_constraints (lp);
 333       set_fixed_cols (lp);
 334
 335       Vector solution_vec (lp.solve (solution_try));
 336
 337       positions->satisfies_constraints_b_ = check_constraints (solution_vec);
 338       if (!positions->satisfies_constraints_b_)
 339         {
 340           WARN << _("solution doesn't satisfy constraints.\n") ;
 341         }
 342       position_loose_cols (solution_vec);
 343       positions->energy_f_ = calculate_energy_f (solution_vec);
 344       positions->config = solution_vec;
 345       positions->error_col_l_arr_ = error_pcol_l_arr();
 346     }
 347   else
 348     {
 349       positions->set_stupid_solution (solution_try);
 350     }
 351   DOUT << "Finished Spring_spacer::solve ()...";
 352 }
 353
 354 /**
 355   add one column to the problem.
 356 */
 357 void
 358 Spring_spacer::add_column (Paper_column  *col, bool fixed, Real fixpos)
 359 {
 360   Colinfo c (col,(fixed)? &fixpos :  0);
 361   int this_rank =  cols_.size();
 362   c.rank_i_ = this_rank;
 363
 364   for (int i=0; i < col->minimal_dists_arr_drul_[LEFT].size (); i++)
 365     {
 366       Column_rod &cr = col->minimal_dists_arr_drul_[LEFT][i];
 367       int left_idx = cr.other_l_->rank_i () - cols_[0].pcol_l_->rank_i ();
 368       if (left_idx < 0)
 369         continue;
 370
 371       if (cols_[left_idx].pcol_l_ != cr.other_l_)
 372         continue;
 373
 374       Spacer_rod l_rod;
 375       l_rod.distance_f_ = cr.distance_f_;
 376       l_rod.other_idx_ = left_idx;
 377       c.rods_[LEFT].push (l_rod);
 378
 379       Spacer_rod r_rod;
 380       r_rod.distance_f_ = cr.distance_f_;
 381       r_rod.other_idx_ = this_rank;
 382       cols_[left_idx].rods_[RIGHT].push (r_rod);
 383     }
 384
 385   cols_.push (c);
 386 }
 387
 388 Line_of_cols
 389 Spring_spacer::error_pcol_l_arr() const
 390 {
 391   Array<Paper_column*> retval;
 392   for (int i=0; i< cols_.size(); i++)
 393     if (cols_[i].ugh_b_)
 394       retval.push (cols_[i].pcol_l_);
 395   for (int i=0;  i < loose_col_arr_.size(); i++)
 396     {
 397       retval.push (loose_col_arr_[i].pcol_l_);
 398     }
 399   return retval;
 400 }
 401
 402 void
 403 Spring_spacer::loosen_column (int i)
 404 {
 405   Colinfo c=cols_.get (i);
 406   for (PCursor<Idealspacing*> j (ideal_p_list_.top()); j.ok (); j++)
 407     {
 408       if (j->left_i_ == i|| j->right_i_ == i)
 409         j.del();
 410       else
 411         j++;
 412     }
 413   c.ugh_b_ = true;
 414
 415   int j=0;
 416   for (; j < loose_col_arr_.size(); j++)
 417     {
 418       if (loose_col_arr_[j].rank_i_ > c.rank_i_)
 419         break;
 420     }
 421   loose_col_arr_.insert (c,j);
 422 }
 423
 424
 425 void
 426 Spring_spacer::print() const
 427 {
 428 #ifndef NPRINT
 429   for (int i=0; i < cols_.size(); i++)
 430     {
 431       DOUT << "col " << i<<' ';
 432       cols_[i].print();
 433     }
 434   for (PCursor<Idealspacing*> i (ideal_p_list_.top()); i.ok (); i++)
 435     {
 436       i->print();
 437     }
 438 #endif
 439 }
 440
 441
 442 void
 443 Spring_spacer::connect (int i, int j, Real d, Real h)
 444 {
 445   assert(d >= 0 && d <= 100 CM);
 446   assert(h >=0);
 447
 448   Idealspacing * s = new Idealspacing;
 449
 450   s->left_i_ = i ;
 451   s->right_i_ = j;
 452   s->space_f_ = d;
 453   s->hooke_f_ = h;
 454
 455   ideal_p_list_.bottom().add (s);
 456 }
 457
 458
 459
 460
 461 void
 462 Spring_spacer::prepare()
 463 {
 464   DOUT << "Preparing..";
 465   calc_idealspacing();
 466   handle_loose_cols();
 467   print();
 468   DOUT << "finished preparing.\n";
 469 }
 470
 471 Line_spacer*
 472 Spring_spacer::constructor()
 473 {
 474   return new Spring_spacer;
 475 }
 476
 477
 478
 479 /**
 480   get the shortest_playing running note at a time. */
 481 void
 482 Spring_spacer::get_ruling_durations(Array<Moment> &shortest_playing_arr,
 483                                     Array<Moment> &context_shortest_arr)
 484 {
 485   for (int i=0; i < cols_.size(); i++)
 486     {
 487       scol_l (i)->preprocess();
 488       scol_l (i)->print ();
 489     }
 490   int start_context_i=0;
 491   Moment context_shortest;
 492   context_shortest.set_infinite (1);
 493   context_shortest_arr.set_size(cols_.size());
 494
 495   for (int i=0; i < cols_.size(); i++)
 496     {
 497       Moment now = scol_l (i)->when();
 498       Moment shortest_playing;
 499       shortest_playing.set_infinite (1);
 500
 501       if (scol_l (i)->breakable_b_)
 502         {
 503           for (int ji=i; ji >= start_context_i; ji--)
 504             context_shortest_arr[ji] = context_shortest;
 505           start_context_i = i;
 506           context_shortest.set_infinite (1);
 507         }
 508       if (scol_l (i)->durations.size())
 509         {
 510           context_shortest = context_shortest <? scol_l(i)->durations[0];
 511         }
 512
 513       // ji was j, but triggered ICE
 514       for (int ji=i+1; ji --;)
 515         {
 516           if (scol_l(ji)->durations.size() &&
 517               now - scol_l(ji)->when() >= shortest_playing)
 518             break;
 519
 520           for (int k =  scol_l (ji)->durations.size();
 521                k-- && scol_l(ji)->durations[k] + scol_l(ji)->when() > now;
 522                )
 523             {
 524               shortest_playing = shortest_playing <? scol_l(ji)->durations[k];
 525             }
 526         }
 527       shortest_playing_arr.push(shortest_playing);
 528     }
 529
 530 #ifndef NPRINT
 531   DOUT << "shortest_playing/:[ ";
 532   for (int i=0; i < shortest_playing_arr.size(); i++)
 533     {
 534       DOUT << shortest_playing_arr[i] << " ";
 535       DOUT << context_shortest_arr[i] << ", ";
 536     }
 537   DOUT << "]\n";
 538 #endif
 539 }
 540
 541 /*
 542   TODO: take out the refs to width
 543  */
 544 /**
 545   generate springs between columns.
 546
 547   TODO: This needs rethinking.  Spacing should take optical
 548   effects into account
 549
 550   The algorithm is taken from :
 551
 552   John S. Gourlay. ``Spacing a Line of Music,'' Technical Report
 553   OSU-CISRC-10/87-TR35, Department of Computer and Information
 554   Science, The Ohio State University, 1987.
 555
 556   */
 557 void
 558 Spring_spacer::calc_idealspacing()
 559 {
 560   Array<Moment> shortest_playing_arr;
 561   Array<Moment> context_shortest_arr;
 562   get_ruling_durations(shortest_playing_arr, context_shortest_arr);
 563
 564   Real interline_f = paper_l ()->interline_f ();
 565   Real nw_f = paper_l ()->note_width ();
 566
 567   Array<Real> ideal_arr_;
 568   Array<Real> hooke_arr_;
 569   for (int i=0; i < cols_.size() - 1; i++){
 570     ideal_arr_.push (-1.0);
 571     hooke_arr_.push (1.0);
 572   }
 573
 574   /*
 575      First do all non-musical columns
 576   */
 577   for (int i=0; i < cols_.size(); i++)
 578     {
 579       if (!scol_l (i)->musical_b() && i+1 < cols_.size())
 580         {
 581           Real symbol_distance =cols_[i].width_[RIGHT] + 2 PT;
 582           Real durational_distance = 0;
 583
 584
 585           Moment delta_t =  scol_l (i+1)->when() - scol_l (i)->when () ;
 586
 587           Real k=  paper_l()->arithmetic_constant (context_shortest_arr[i]);
 588           /*
 589             ugh should use shortest_playing distance
 590           */
 591           if (delta_t)
 592             durational_distance =  paper_l()->duration_to_dist (delta_t,k);
 593           symbol_distance += -cols_[i+1].width_[LEFT];
 594
 595
 596           ideal_arr_[i] = symbol_distance >? durational_distance;
 597           hooke_arr_[i] = 1; //2.0;
 598         }
 599     }
 600
 601   /*
 602      Then musicals
 603   */
 604   for (int i=0; i < cols_.size(); i++)
 605     {
 606       if (scol_l (i)->musical_b())
 607         {
 608           Moment shortest_playing_len = shortest_playing_arr[i];
 609           Moment context_shortest = context_shortest_arr[i];
 610           if (! shortest_playing_len)
 611             {
 612               warning (_("Can't find a ruling note at ")
 613                        +scol_l (i)->when().str ());
 614               shortest_playing_len = 1;
 615             }
 616           if (! context_shortest)
 617             {
 618               warning(_("No minimum in measure at ")
 619                       + scol_l (i)->when().str ());
 620               context_shortest = 1;
 621             }
 622           Moment delta_t = scol_l (i+1)->when() - scol_l (i)->when ();
 623           Real k=  paper_l()->arithmetic_constant(context_shortest);
 624           Real dist = paper_l()->duration_to_dist (shortest_playing_len, k);
 625           dist *= (double)(delta_t / shortest_playing_len);
 626
 627           /*
 628             According to [Ross] and [Wanske], and from what i've seen:
 629
 630             * whitespace at the begin of the bar should be fixed at
 631             (about) one interline.
 632             [Ross]:
 633             when spacing gets real tight, a smaller fixed value may be
 634             used, so that there are two discrete amounts of whitespace
 635             possible at the begin of a bar; but this is not implemented
 636             right now.
 637
 638             * whitespace at the end of the bar is the normal amount of
 639             "hinterfleish" that would have been used, had there been
 640             yet another note in the bar.
 641             [Ross]:
 642             some editors argue that the bar line should not take any
 643             space, not to hinder the flow of music spaced around a bar
 644             line.
 645             [Ross] and [Wanske] do not suggest this, however.  Further,
 646             it introduces some spacing problems and think that it is ugly
 647             too.
 648             [jcn]
 649           */
 650
 651           /*
 652              first musical column of bar
 653           */
 654           if (i && scol_l (i - 1)->breakable_b_)
 655             {
 656               // fixed: probably should set minimum (rod/spring)?
 657               cols_[i-1].width_[RIGHT] += interline_f;
 658               // should adjust dist too?
 659               ideal_arr_[i-1] = ideal_arr_[i-1] >? interline_f;
 660             }
 661
 662           /*
 663              last musical column of bar
 664           */
 665           if (i + 1 < cols_.size () && scol_l(i+1)->breakable_b_)
 666             {
 667               // hmm, how bout?
 668               dist = dist >? interline_f;
 669
 670               /*
 671                 uhuh, this code looks fine, already?
 672                 someone was junking this last "hinterfleisch" whitespace?!
 673
 674                 but this seems to be fixed now :-)
 675               */
 676               // set minimum rod
 677               cols_[i].width_[RIGHT] += interline_f;
 678             }
 679
 680           // ugh, do we need this?
 681           if (i < cols_.size () - 1 && !scol_l (i + 1)->musical_b ())
 682             {
 683               Real minimum = -cols_[i + 1].width_[LEFT] + cols_[i].width_[RIGHT]
 684                 + interline_f / 2;
 685               dist = dist >? minimum;
 686             }
 687
 688           // ugh: never let columns touch... try to set over here...
 689           // ugh: use j iso i triggers ice in gcc-2.7.2.3
 690           cols_[i].width_[LEFT] -= nw_f / 4;
 691           ideal_arr_[i] = dist;
 692         }
 693     }
 694
 695   for (int i=0; i < ideal_arr_.size(); i++)
 696     {
 697       assert (ideal_arr_[i] >=0 && hooke_arr_[i] >=0);
 698       connect (i, i+1, ideal_arr_[i], hooke_arr_[i]);
 699     }
 700 }