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--1999 Han-Wen Nienhuys <hanwen@cs.uu.nl>
   7 */
   8
   9
  10 #include <math.h>
  11 #include <limits.h>
  12 #include "killing-cons.tcc"
  13 #include "spring-spacer.hh"
  14 #include "p-col.hh"
  15 #include "debug.hh"
  16 #include "dimensions.hh"
  17 #include "qlp.hh"
  18 #include "unionfind.hh"
  19 #include "idealspacing.hh"
  20 #include "pointer.tcc"
  21 #include "score-column.hh"
  22 #include "paper-def.hh"
  23 #include "colhpos.hh"
  24 #include "main.hh"
  25
  26 Vector
  27 Spring_spacer::default_solution() const
  28 {
  29   return try_initial_solution();
  30 }
  31
  32 Score_column*
  33 Spring_spacer::scol_l (int i)
  34 {
  35   return dynamic_cast<Score_column*>(cols_[i].pcol_l_);
  36 }
  37
  38 const Real COLFUDGE=1e-3;
  39 template class P<Real>;         // ugh.
  40
  41 bool
  42 Spring_spacer::contains_b (Paper_column const *w)
  43 {
  44   for (int i=0; i< cols_.size(); i++)
  45     if (cols_[i].pcol_l_ == w)
  46       return true;
  47   return false;
  48 }
  49
  50
  51 void
  52 Spring_spacer::OK() const
  53 {
  54 #ifndef NDEBUG
  55   for (int i = 1; i < cols_.size(); i++)
  56     assert (cols_[i].rank_i_ > cols_[i-1].rank_i_);
  57   for (int i = 1; i < loose_col_arr_.size(); i++)
  58     assert (loose_col_arr_[i].rank_i_ > loose_col_arr_[i-1].rank_i_);
  59 #endif
  60 }
  61
  62 /**
  63   Make sure no unconnected columns happen.
  64  */
  65 void
  66 Spring_spacer::handle_loose_cols()
  67 {
  68   Union_find connected (cols_.size());
  69   Array<int> fixed;
  70
  71   for (Cons<Idealspacing> *i  = ideal_p_list_; i; i = i->next_)
  72     {
  73       connected.connect (i->car_->cols_drul_[LEFT],i->car_->cols_drul_[RIGHT]);
  74     }
  75   for (int i = 0; i < cols_.size(); i++)
  76     if (cols_[i].fixed_b())
  77       fixed.push (i);
  78   for (int i=1; i < fixed.size(); i++)
  79     connected.connect (fixed[i-1], fixed[i]);
  80
  81   for (int i = cols_.size(); i--;)
  82     {
  83       if (! connected.equiv (fixed[0], i))
  84         {
  85           warning (_f ("unconnected column: %d", i));
  86           loosen_column (i);
  87         }
  88     }
  89   OK();
  90 }
  91
  92
  93 /**
  94   Guess a stupid position for loose columns.  Put loose columns at
  95   regular distances from enclosing calced columns
  96   */
  97 void
  98 Spring_spacer::position_loose_cols (Vector &sol_vec) const
  99 {
 100   if (!loose_col_arr_.size())
 101     return ;
 102   assert (sol_vec.dim());
 103   Array<bool> fix_b_arr;
 104   fix_b_arr.set_size (cols_.size() + loose_col_arr_.size ());
 105   Real utter_right_f=-infinity_f;
 106   Real utter_left_f =infinity_f;
 107   for (int i=0; i < loose_col_arr_.size(); i++)
 108     {
 109       fix_b_arr[loose_col_arr_[i].rank_i_] = false;
 110     }
 111   for (int i=0; i < cols_.size(); i++)
 112     {
 113       int r= cols_[i].rank_i_;
 114       fix_b_arr[r] = true;
 115       utter_right_f = utter_right_f >? sol_vec (i);
 116       utter_left_f = utter_left_f <? sol_vec (i);
 117     }
 118   Vector v (fix_b_arr.size());
 119   int j =0;
 120   int k =0;
 121   for (int i=0; i < v.dim(); i++)
 122     {
 123       if (fix_b_arr[i])
 124         {
 125           assert (cols_[j].rank_i_ == i);
 126           v (i) = sol_vec (j++);
 127         }
 128       else
 129         {
 130           Real left_pos_f =
 131             (j>0) ?sol_vec (j-1) : utter_left_f;
 132           Real right_pos_f =
 133             (j < sol_vec.dim()) ? sol_vec (j) : utter_right_f;
 134           int left_rank = (j>0) ? cols_[j-1].rank_i_ : 0;
 135           int right_rank = (j<sol_vec.dim()) ? cols_[j].rank_i_ : sol_vec.dim ();
 136
 137           int d_r = right_rank - left_rank;
 138           Column_info loose=loose_col_arr_[k++];
 139           int r = loose.rank_i_ ;
 140           assert (r > left_rank && r < right_rank);
 141
 142           v (i) =  (r - left_rank)*left_pos_f/ d_r +
 143             (right_rank - r) *right_pos_f /d_r;
 144         }
 145     }
 146   sol_vec = v;
 147 }
 148
 149 bool
 150 Spring_spacer::check_constraints (Vector v) const
 151 {
 152   int dim=v.dim();
 153   assert (dim == cols_.size());
 154   DOUT << "checking " << v;
 155   for (int i=0; i < dim; i++)
 156     {
 157       if (cols_[i].fixed_b() &&
 158           abs (cols_[i].fixed_position() - v (i)) > COLFUDGE)
 159         {
 160           DOUT << "Fixpos broken\n";
 161           return false;
 162         }
 163       Array<Spacer_rod> const &rods (cols_[i].rods_[RIGHT]);
 164       for (int j =0; j < rods.size (); j++)
 165         {
 166           int other =rods[j].other_idx_;
 167           Real diff =v (other) - v (i) ;
 168           if (COLFUDGE +diff <  rods[j].distance_f_)
 169             {
 170               DOUT << "i, other_i: " << i << "  " << other << '\n';
 171               DOUT << "dist, minimal = " << diff << " "
 172                    << rods[j].distance_f_ << '\n';
 173               return false;
 174             }
 175         }
 176
 177     }
 178   return true;
 179 }
 180
 181 /** try to generate a solution which obeys the min
 182     distances and fixed positions
 183  */
 184 Vector
 185 Spring_spacer::try_initial_solution() const
 186 {
 187   Vector v;
 188   if (!try_initial_solution_and_tell (v))
 189     {
 190       warning (_ ("I'm too fat; call Oprah"));
 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
 203   assert (cols_[0].fixed_b ());
 204   DOUT << "fixpos 0 " << cols_[0].fixed_position ();
 205   for (int i=0; i < dim; i++)
 206     {
 207       Real min_x = i ?  initsol (i-1) : cols_[0].fixed_position ();
 208       Array<Spacer_rod> const &sr_arr(cols_[i].rods_[LEFT]);
 209       for (int j=0; j < sr_arr.size (); j++)
 210         {
 211           min_x = min_x >? (initsol (sr_arr[j].other_idx_) + sr_arr[j].distance_f_);
 212         }
 213       initsol (i) = min_x;
 214
 215       if (cols_[i].fixed_b())
 216         {
 217           initsol (i)=cols_[i].fixed_position();
 218           if (initsol (i) < min_x )
 219             {
 220               DOUT << "failing: init, min : " << initsol (i) << " " << min_x << '\n';
 221               initsol (i) = min_x;
 222               succeeded = false;
 223             }
 224         }
 225     }
 226   v = initsol;
 227
 228   DOUT << "tried and told solution: " << v;
 229   if (!succeeded)
 230     DOUT << "(failed)\n";
 231   return succeeded;
 232 }
 233
 234
 235
 236 // generate the matrices
 237 void
 238 Spring_spacer::make_matrices (Matrix &quad, Vector &lin, Real &c) const
 239 {
 240   quad.fill (0);
 241   lin.fill (0);
 242   c = 0;
 243
 244   for (Cons<Idealspacing> *p =ideal_p_list_; p; p = p->next_)
 245     {
 246       Idealspacing *i = p->car_;
 247       int l = i->cols_drul_[LEFT];
 248       int r = i->cols_drul_[RIGHT];
 249
 250       quad (r,r) += i->hooke_f_;
 251       quad (r,l) -= i->hooke_f_;
 252       quad (l,r) -= i->hooke_f_;
 253       quad (l,l) += i->hooke_f_;
 254
 255       lin (r) -= i->space_f_*i->hooke_f_;
 256       lin (l) += i->space_f_*i->hooke_f_;
 257
 258       c += sqr (i->space_f_);
 259     }
 260
 261   if (quad.dim() > 10)
 262     quad.set_band();
 263
 264
 265 }
 266
 267 void
 268 Spring_spacer::set_fixed_cols (Mixed_qp &qp) const
 269 {
 270   for (int j=0; j < cols_.size(); j++)
 271     if (cols_[j].fixed_b())
 272       qp.add_fixed_var (j,cols_[j].fixed_position());
 273 }
 274
 275 // put the constraints into the LP problem
 276 void
 277 Spring_spacer::make_constraints (Mixed_qp& lp) const
 278 {
 279   int dim=cols_.size();
 280
 281   for (int j=0; j < dim -1; j++)
 282     {
 283       Array<Spacer_rod> const&rod_arr (cols_[j].rods_[RIGHT]);
 284       for (int i = 0; i < rod_arr.size (); i++)
 285         {
 286           Vector c1(dim);
 287           c1(rod_arr[i].other_idx_)=1.0 ;
 288           c1(j)=-1.0 ;
 289
 290           lp.add_inequality_cons (c1, rod_arr[i].distance_f_);
 291         }
 292     }
 293 }
 294
 295
 296 Real
 297 Spring_spacer::calculate_energy_f (Vector solution) const
 298 {
 299   Real e = 0.0;
 300   for (Cons<Idealspacing>*p =ideal_p_list_; p; p = p->next_)
 301     {
 302       Idealspacing * i = p->car_;
 303       e += i->energy_f(solution(i->cols_drul_[RIGHT]) - solution(i->cols_drul_[LEFT]));
 304     }
 305
 306   return e;
 307 }
 308 void
 309 Spring_spacer::lower_bound_solution (Column_x_positions*positions) const
 310 {
 311   Mixed_qp lp (cols_.size());
 312   make_matrices (lp.quad_,lp.lin_, lp.const_term_);
 313   set_fixed_cols (lp);
 314
 315   Vector start (cols_.size());
 316   start.fill (0.0);
 317   Vector solution_vec (lp.solve (start));
 318
 319   DOUT << "Lower bound sol: " << solution_vec;
 320   positions->energy_f_ = calculate_energy_f (solution_vec);
 321   positions->config = solution_vec;
 322   positions->satisfies_constraints_b_ = check_constraints (solution_vec);
 323 }
 324
 325 Spring_spacer::Spring_spacer ()
 326 {
 327   ideal_p_list_ =0;
 328   energy_normalisation_f_ = 1.0;
 329 }
 330
 331 void
 332 Spring_spacer::solve (Column_x_positions*positions) const
 333 {
 334   DOUT << "Spring_spacer::solve ()...";
 335
 336   Vector solution_try;
 337
 338   bool constraint_satisfaction = try_initial_solution_and_tell (solution_try);
 339   if  (constraint_satisfaction)
 340     {
 341       Mixed_qp lp (cols_.size());
 342       make_matrices (lp.quad_,lp.lin_, lp.const_term_);
 343       make_constraints (lp);
 344       set_fixed_cols (lp);
 345
 346       Vector solution_vec (lp.solve (solution_try));
 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   DOUT << "Finished Spring_spacer::solve ()...";
 364 }
 365
 366 /**
 367   add one column to the problem.
 368 */
 369 void
 370 Spring_spacer::add_column (Paper_column  *col, bool fixed, Real fixpos)
 371 {
 372   Column_info c (col,(fixed)? &fixpos :  0);
 373   int this_rank =  cols_.size();
 374   c.rank_i_ = this_rank;
 375
 376   for (int i=0; i < col->minimal_dists_arr_drul_[LEFT].size (); i++)
 377     {
 378       Column_rod &cr = col->minimal_dists_arr_drul_[LEFT][i];
 379       int left_idx = cr.other_l_->rank_i () - cols_[0].pcol_l_->rank_i ();
 380       if (left_idx < 0)
 381         continue;
 382
 383       if (cols_[left_idx].pcol_l_ != cr.other_l_)
 384         continue;
 385
 386       Spacer_rod l_rod;
 387       l_rod.distance_f_ = cr.distance_f_;
 388       l_rod.other_idx_ = left_idx;
 389       c.rods_[LEFT].push (l_rod);
 390
 391       Spacer_rod r_rod;
 392       r_rod.distance_f_ = cr.distance_f_;
 393       r_rod.other_idx_ = this_rank;
 394       cols_[left_idx].rods_[RIGHT].push (r_rod);
 395     }
 396
 397   cols_.push (c);
 398 }
 399
 400 Line_of_cols
 401 Spring_spacer::error_pcol_l_arr() const
 402 {
 403   Link_array<Paper_column> retval;
 404   for (int i=0; i< cols_.size(); i++)
 405     if (cols_[i].ugh_b_)
 406       retval.push (cols_[i].pcol_l_);
 407   for (int i=0;  i < loose_col_arr_.size(); i++)
 408     {
 409       retval.push (loose_col_arr_[i].pcol_l_);
 410     }
 411   return retval;
 412 }
 413 /*
 414   Ugh. Should junk this.
 415  */
 416 void
 417 Spring_spacer::loosen_column (int idx)
 418 {
 419   Column_info c=cols_.get (idx);
 420
 421   Cons<Idealspacing> **pp = &ideal_p_list_;
 422
 423   while (*pp)
 424     {
 425       Idealspacing *j = (*pp)->car_;
 426       if (j->cols_drul_[LEFT] == idx|| j->cols_drul_[RIGHT] == idx)
 427         {
 428           delete remove_cons (pp);
 429         }
 430       else
 431         {
 432           pp = &(*pp)->next_;
 433         }
 434     }
 435   c.ugh_b_ = true;
 436
 437   int j=0;
 438   for (; j < loose_col_arr_.size(); j++)
 439     {
 440       if (loose_col_arr_[j].rank_i_ > c.rank_i_)
 441         break;
 442     }
 443   loose_col_arr_.insert (c,j);
 444 }
 445
 446
 447 void
 448 Spring_spacer::print() const
 449 {
 450 #ifndef NPRINT
 451   for (int i=0; i < cols_.size(); i++)
 452     {
 453       DOUT << "col " << i << " ";
 454       cols_[i].print();
 455     }
 456
 457   for (Cons<Idealspacing> *p =ideal_p_list_; p; p = p->next_)
 458     {
 459       p->car_->print();
 460     }
 461 #endif
 462 }
 463
 464
 465 void
 466 Spring_spacer::connect (int i, int j, Real d, Real h)
 467 {
 468   assert(d >= 0 && d <= 100 CM);
 469   assert(h >=0);
 470
 471   Idealspacing * s = new Idealspacing;
 472
 473   s->cols_drul_[LEFT] = i ;
 474   s->cols_drul_[RIGHT] = j;
 475   s->space_f_ = d;
 476   s->hooke_f_ = h;
 477
 478   ideal_p_list_ = new Killing_cons<Idealspacing> (s, ideal_p_list_);
 479 }
 480
 481 void
 482 Spring_spacer::prepare()
 483 {
 484   DOUT << "Preparing..";
 485   calc_idealspacing();
 486   handle_loose_cols();
 487   print();
 488   DOUT << "finished preparing.\n";
 489 }
 490
 491 Line_spacer*
 492 Spring_spacer::constructor()
 493 {
 494   return new Spring_spacer;
 495 }
 496
 497
 498
 499 /**
 500   get the shortest_playing running note at a time. */
 501 void
 502 Spring_spacer::get_ruling_durations(Array<Moment> &context_shortest_arr)
 503 {
 504   for (int i=0; i < cols_.size(); i++)
 505     {
 506       scol_l (i)->preprocess();
 507       scol_l (i)->print ();
 508     }
 509   int start_context_i=0;
 510   Moment context_shortest;
 511   context_shortest.set_infinite (1);
 512   context_shortest_arr.set_size(cols_.size());
 513
 514   for (int i=0; i < cols_.size(); i++)
 515     {
 516       Score_column * sc = scol_l(i);
 517
 518       if (sc->breakable_b () || sc->break_status_dir ())
 519         {
 520           for (int ji=i; ji >= start_context_i; ji--)
 521             context_shortest_arr[ji] = context_shortest;
 522           start_context_i = i;
 523           context_shortest.set_infinite (1);
 524         }
 525       else if (sc->musical_b ())
 526         context_shortest = context_shortest <? sc->shortest_starter_mom_;
 527     }
 528
 529 #ifndef NPRINT
 530   DOUT << "context shortest :[ ";
 531   for (int i=0; i < context_shortest_arr.size(); i++)
 532     {
 533       DOUT << context_shortest_arr[i] << ", ";
 534     }
 535   DOUT << "]\n";
 536 #endif
 537 }
 538
 539 /*
 540   TODO: take out the refs to width
 541
 542  */
 543 /**
 544   generate springs between columns.
 545
 546   TODO: This needs rethinking.......
 547
 548   * Spacing should take optical effects into account
 549
 550   * Should be decentralised
 551
 552   The algorithm is taken from :
 553
 554   John S. Gourlay. ``Spacing a Line of Music,'' Technical Report
 555   OSU-CISRC-10/87-TR35, Department of Computer and Information
 556   Science, The Ohio State University, 1987.
 557
 558   */
 559 void
 560 Spring_spacer::calc_idealspacing()
 561 {
 562   Array<Moment> context_shortest_arr;
 563   get_ruling_durations(context_shortest_arr);
 564
 565   Real interline_f = paper_l ()->get_realvar (interline_scm_sym);
 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           Moment delta_t =  scol_l (i+1)->when_mom () - scol_l (i)->when_mom () ;
 584
 585           /*
 586             ugh should use shortest_playing distance
 587           */
 588           if (delta_t)
 589             {
 590               Real k=  paper_l()->arithmetic_constant (context_shortest_arr[i]);
 591               durational_distance =  paper_l()->length_mom_to_dist (delta_t,k);
 592             }
 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 = scol_l(i)->shortest_playing_mom_;
 609           Moment context_shortest = context_shortest_arr[i];
 610           if (! shortest_playing_len)
 611             {
 612               warning (_f ("can't find a ruling note at %s",
 613                 scol_l (i)->when_mom ().str ()));
 614               shortest_playing_len = 1;
 615             }
 616           if (! context_shortest)
 617             {
 618               warning (_f ("no minimum in measure at %s",
 619                       scol_l (i)->when_mom ().str ()));
 620               context_shortest = 1;
 621             }
 622           Moment delta_t = scol_l (i+1)->when_mom () - scol_l (i)->when_mom ();
 623           Real k=  paper_l()->arithmetic_constant(context_shortest);
 624           Real dist = paper_l()->length_mom_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
 633             [Ross]:
 634             when spacing gets real tight, a smaller fixed value may be
 635             used, so that there are two discrete amounts of whitespace
 636             possible at the begin of a bar; but this is not implemented
 637             right now.
 638
 639             * whitespace at the end of the bar is the normal amount of
 640             "hinterfleish" that would have been used, had there been
 641             yet another note in the bar.
 642
 643             [Ross]:
 644             some editors argue that the bar line should not take any
 645             space, not to hinder the flow of music spaced around a bar
 646             line.
 647
 648             [Ross] and [Wanske] do not suggest this, however.  Further,
 649             it introduces some spacing problems and I think that it is ugly
 650             too.
 651
 652             [jcn]
 653           */
 654
 655           /*
 656              first musical column of bar
 657           */
 658           if (i && !scol_l (i - 1)->musical_b ())
 659             {
 660               // one interline minimum at start of bar
 661
 662               // cols_[i].width_[RIGHT] += interline_f;
 663               cols_[i].width_[RIGHT] = cols_[i].width_[RIGHT] >? interline_f;
 664
 665               // should adjust dist too?
 666               ideal_arr[i-1] = ideal_arr[i-1] >? (2 * interline_f);
 667             }
 668
 669           /*
 670              last musical column of bar
 671           */
 672           if (i + 1 < cols_.size () && !scol_l(i+1)->musical_b ())
 673             {
 674               // two interline minimum ok for last column?
 675               dist = dist >? 2 * interline_f;
 676
 677               // set minimum rod
 678               /*
 679                 urg: simply *adding* an interline leaves big gaps at
 680                 end of measure in star-spangled-banner (after lyrics
 681                 at eom).
 682
 683                    cols_[i].width_[RIGHT] += interline_f; // before
 684
 685                 having a minimum of one interline solves this problem
 686                 in most (but not all??) cases.
 687
 688                 for music without lyrics (esp. when set very tightly),
 689                 adding an interline looks good: probably because this
 690                 hides a bug that allows the last note's "hinterfleish"
 691                 to be removed (e.g., see wtk1-fugue2: that's ugly now).
 692                 -- jcn
 693                */
 694
 695               cols_[i].width_[RIGHT] = cols_[i].width_[RIGHT] >? 2 * interline_f;
 696             }
 697
 698           // ugh, do we need this?
 699           if (i < cols_.size () - 1 && !scol_l (i + 1)->musical_b ())
 700             {
 701               Real minimum = -cols_[i + 1].width_[LEFT] + cols_[i].width_[RIGHT]
 702                 + interline_f / 2;
 703               dist = dist >? minimum;
 704             }
 705           ideal_arr[i] = dist;
 706         }
 707     }
 708
 709   /*
 710     shorter distances should stretch less.
 711
 712     (and how bout
 713
 714       hooke[i] = 2 * max_ideal_space - ideal[i]
 715
 716     ?)
 717   */
 718   for (int i=0; i < ideal_arr.size(); i++)
 719     hooke_arr[i] = 1/ideal_arr[i];
 720
 721   for (int i=0; i < ideal_arr.size(); i++)
 722     {
 723       assert (ideal_arr[i] >=0 && hooke_arr[i] >=0);
 724       connect (i, i+1, ideal_arr[i], hooke_arr[i]);
 725     }
 726 }