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@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
  24 Vector
  25 Spring_spacer::default_solution () const
  26 {
  27   return try_initial_solution () ;
  28 }
  29
  30 Score_column*
  31 Spring_spacer::scol_l (int i)
  32 {
  33   return (Score_column*)cols_[i].pcol_l_;
  34 }
  35
  36 const Real COLFUDGE=1e-3;
  37 template class P<Real>;         // ugh.
  38
  39 bool
  40 Spring_spacer::contains_b (Paper_column const *w)
  41 {
  42   for (int i=0; i< cols_.size (); i++)
  43     if (cols_[i].pcol_l_ == w)
  44       return true;
  45   return false;
  46 }
  47
  48
  49 void
  50 Spring_spacer::OK () const
  51 {
  52 #ifndef NDEBUG
  53   for (int i = 1; i < cols_.size (); i++)
  54     assert (cols_[i].rank_i_ > cols_[i-1].rank_i_);
  55   for (int i = 1; i < loose_col_arr_.size (); i++)
  56     assert (loose_col_arr_[i].rank_i_ > loose_col_arr_[i-1].rank_i_);
  57 #endif
  58 }
  59
  60 /**
  61   Make sure no unconnected columns happen.
  62  */
  63 void
  64 Spring_spacer::handle_loose_cols ()
  65 {
  66   Union_find connected (cols_.size ());
  67   Array<int> fixed;
  68   for (PCursor<Idealspacing*> i (ideal_p_list_.top ()); i.ok (); i++)
  69     {
  70       connected.connect (i->left_i_,i->right_i_);
  71     }
  72   for (int i = 0; i < cols_.size (); i++)
  73     if (cols_[i].fixed_b ())
  74       fixed.push (i);
  75   for (int i=1; i < fixed.size (); i++)
  76     connected.connect (fixed[i-1], fixed[i]);
  77
  78   for (int i = cols_.size (); i--;)
  79     {
  80       if (! connected.equiv (fixed[0], i))
  81         {
  82           warning (_f ("unconnected column: %d", i));
  83           loosen_column (i);
  84         }
  85     }
  86   OK ();
  87 }
  88
  89
  90 /**
  91   Guess a stupid position for loose columns.  Put loose columns at
  92   regular distances from enclosing calced columns
  93   */
  94 void
  95 Spring_spacer::position_loose_cols (Vector &sol_vec) const
  96 {
  97   if (!loose_col_arr_.size ())
  98     return ;
  99   assert (sol_vec.dim ());
 100   Array<bool> fix_b_arr;
 101   fix_b_arr.set_size (cols_.size () + loose_col_arr_.size ());
 102   Real utter_right_f=-infinity_f;
 103   Real utter_left_f =infinity_f;
 104   for (int i=0; i < loose_col_arr_.size (); i++)
 105     {
 106       fix_b_arr[loose_col_arr_[i].rank_i_] = false;
 107     }
 108   for (int i=0; i < cols_.size (); i++)
 109     {
 110       int r= cols_[i].rank_i_;
 111       fix_b_arr[r] = true;
 112       utter_right_f = utter_right_f >? sol_vec (i);
 113       utter_left_f = utter_left_f <? sol_vec (i);
 114     }
 115   Vector v (fix_b_arr.size ());
 116   int j =0;
 117   int k =0;
 118   for (int i=0; i < v.dim (); i++)
 119     {
 120       if (fix_b_arr[i])
 121         {
 122           assert (cols_[j].rank_i_ == i);
 123           v (i) = sol_vec (j++);
 124         }
 125       else
 126         {
 127           Real left_pos_f =
 128             (j>0) ?sol_vec (j-1) : utter_left_f;
 129           Real right_pos_f =
 130             (j < sol_vec.dim ()) ? sol_vec (j) : utter_right_f;
 131           int left_rank = (j>0) ? cols_[j-1].rank_i_ : 0;
 132           int right_rank = (j<sol_vec.dim ()) ? cols_[j].rank_i_ : sol_vec.dim ();
 133
 134           int d_r = right_rank - left_rank;
 135           Column_info loose=loose_col_arr_[k++];
 136           int r = loose.rank_i_ ;
 137           assert (r > left_rank && r < right_rank);
 138
 139           v (i) =  (r - left_rank)*left_pos_f/ d_r +
 140             (right_rank - r) *right_pos_f /d_r;
 141         }
 142     }
 143   sol_vec = v;
 144 }
 145
 146 bool
 147 Spring_spacer::check_constraints (Vector v) const
 148 {
 149   int dim=v.dim ();
 150   assert (dim == cols_.size ());
 151   DOUT << "checking " << v;
 152   for (int i=0; i < dim; i++)
 153     {
 154       if (cols_[i].fixed_b () &&
 155           abs (cols_[i].fixed_position () - v (i)) > COLFUDGE)
 156         {
 157           DOUT << "Fixpos broken\n";
 158           return false;
 159         }
 160       Array<Spacer_rod> const &rods (cols_[i].rods_[RIGHT]);
 161       for (int j =0; j < rods.size (); j++)
 162         {
 163           int other =rods[j].other_idx_;
 164           Real diff =v (other) - v (i) ;
 165           if (COLFUDGE +diff <  rods[j].distance_f_)
 166             {
 167               DOUT << "i, other_i: " << i << "  " << other << '\n';
 168               DOUT << "dist, minimal = " << diff << " "
 169                    << rods[j].distance_f_ << '\n';
 170               return false;
 171             }
 172         }
 173
 174     }
 175   return true;
 176 }
 177
 178 /** try to generate a solution which obeys the min distances and fixed positions
 179  */
 180 Vector
 181 Spring_spacer::try_initial_solution () const
 182 {
 183   Vector v;
 184   if (!try_initial_solution_and_tell (v))
 185     {
 186       warning (_ ("I'm too fat; call Oprah"));
 187     }
 188   return v;
 189
 190 }
 191
 192 bool
 193 Spring_spacer::try_initial_solution_and_tell (Vector &v) const
 194 {
 195   int dim=cols_.size ();
 196   bool succeeded = true;
 197   Vector initsol (dim);
 198
 199   assert (cols_[0].fixed_b ());
 200   DOUT << "fixpos 0 " << cols_[0].fixed_position ();
 201   for (int i=0; i < dim; i++)
 202     {
 203       Real min_x = i ?  initsol (i-1) : cols_[0].fixed_position ();
 204       Array<Spacer_rod> const &sr_arr (cols_[i].rods_[LEFT]);
 205       for (int j=0; j < sr_arr.size (); j++)
 206         {
 207           min_x = min_x >? (initsol (sr_arr[j].other_idx_) + sr_arr[j].distance_f_);
 208         }
 209       initsol (i) = min_x;
 210
 211       if (cols_[i].fixed_b ())
 212         {
 213           initsol (i)=cols_[i].fixed_position ();
 214           if (initsol (i) < min_x )
 215             {
 216               DOUT << "failing: init, min : " << initsol (i) << " " << min_x << '\n';
 217               initsol (i) = min_x;
 218               succeeded = false;
 219             }
 220         }
 221     }
 222   v = initsol;
 223
 224   DOUT << "tried and told solution: " << v;
 225   if (!succeeded)
 226     DOUT << " (failed)\n";
 227   return succeeded;
 228 }
 229
 230
 231
 232 // generate the matrices
 233 void
 234 Spring_spacer::make_matrices (Matrix &quad, Vector &lin, Real &c) const
 235 {
 236   quad.fill (0);
 237   lin.fill (0);
 238   c = 0;
 239
 240   for (PCursor<Idealspacing*> i (ideal_p_list_.top ()); i.ok (); i++)
 241     {
 242       int l = i->left_i_;
 243       int r = i->right_i_;
 244
 245       quad (r,r) += i->hooke_f_;
 246       quad (r,l) -= i->hooke_f_;
 247       quad (l,r) -= i->hooke_f_;
 248       quad (l,l) += i->hooke_f_;
 249
 250       lin (r) -= i->space_f_*i->hooke_f_;
 251       lin (l) += i->space_f_*i->hooke_f_;
 252
 253       c += sqr (i->space_f_);
 254     }
 255
 256   if (quad.dim () > 10)
 257     quad.set_band ();
 258
 259
 260 }
 261
 262 void
 263 Spring_spacer::set_fixed_cols (Mixed_qp &qp) const
 264 {
 265   for (int j=0; j < cols_.size (); j++)
 266     if (cols_[j].fixed_b ())
 267       qp.add_fixed_var (j,cols_[j].fixed_position ());
 268 }
 269
 270 // put the constraints into the LP problem
 271 void
 272 Spring_spacer::make_constraints (Mixed_qp& lp) const
 273 {
 274   int dim=cols_.size ();
 275
 276   for (int j=0; j < dim -1; j++)
 277     {
 278       Array<Spacer_rod> const&rod_arr (cols_[j].rods_[RIGHT]);
 279       for (int i = 0; i < rod_arr.size (); i++)
 280         {
 281           Vector c1 (dim);
 282           c1 (rod_arr[i].other_idx_)=1.0 ;
 283           c1 (j)=-1.0 ;
 284
 285           lp.add_inequality_cons (c1, rod_arr[i].distance_f_);
 286         }
 287     }
 288 }
 289
 290
 291 Real
 292 Spring_spacer::calculate_energy_f (Vector solution) const
 293 {
 294   Real e = 0.0;
 295   for (PCursor<Idealspacing*> i (ideal_p_list_.top ()); i.ok (); i++)
 296     {
 297       e += i->energy_f (solution (i->right_i_) - solution (i->left_i_));
 298     }
 299
 300   return e;
 301 }
 302 void
 303 Spring_spacer::lower_bound_solution (Column_x_positions*positions) const
 304 {
 305   Mixed_qp lp (cols_.size ());
 306   make_matrices (lp.quad_,lp.lin_, lp.const_term_);
 307   set_fixed_cols (lp);
 308
 309   Vector start (cols_.size ());
 310   start.fill (0.0);
 311   Vector solution_vec (lp.solve (start));
 312
 313   DOUT << "Lower bound sol: " << solution_vec;
 314   positions->energy_f_ = calculate_energy_f (solution_vec);
 315   positions->config = solution_vec;
 316   positions->satisfies_constraints_b_ = check_constraints (solution_vec);
 317 }
 318
 319 Spring_spacer::Spring_spacer ()
 320 {
 321   energy_normalisation_f_ = 1.0;
 322 }
 323
 324 void
 325 Spring_spacer::solve (Column_x_positions*positions) const
 326 {
 327
 328   DOUT << "Spring_spacer::solve ()...";
 329   Vector solution_try;
 330
 331   bool constraint_satisfaction = try_initial_solution_and_tell (solution_try);
 332   if  (constraint_satisfaction)
 333     {
 334       Mixed_qp lp (cols_.size ());
 335       make_matrices (lp.quad_,lp.lin_, lp.const_term_);
 336       make_constraints (lp);
 337       set_fixed_cols (lp);
 338
 339       Vector solution_vec (lp.solve (solution_try));
 340
 341       positions->satisfies_constraints_b_ = check_constraints (solution_vec);
 342       if (!positions->satisfies_constraints_b_)
 343         {
 344           WARN << _ ("solution doesn't satisfy constraints") << '\n' ;
 345         }
 346       position_loose_cols (solution_vec);
 347       positions->energy_f_ = calculate_energy_f (solution_vec);
 348       positions->config = solution_vec;
 349       positions->error_col_l_arr_ = error_pcol_l_arr ();
 350     }
 351   else
 352     {
 353       positions->set_stupid_solution (solution_try);
 354     }
 355   DOUT << "Finished Spring_spacer::solve ()...";
 356 }
 357
 358 /**
 359   add one column to the problem.
 360 */
 361 void
 362 Spring_spacer::add_column (Paper_column  *col, bool fixed, Real fixpos)
 363 {
 364   Column_info c (col, (fixed)? &fixpos :  0);
 365   int this_rank =  cols_.size ();
 366   c.rank_i_ = this_rank;
 367
 368   for (int i=0; i < col->minimal_dists_arr_drul_[LEFT].size (); i++)
 369     {
 370       Column_rod &cr = col->minimal_dists_arr_drul_[LEFT][i];
 371       int left_idx = cr.other_l_->rank_i () - cols_[0].pcol_l_->rank_i ();
 372       if (left_idx < 0)
 373         continue;
 374
 375       if (cols_[left_idx].pcol_l_ != cr.other_l_)
 376         continue;
 377
 378       Spacer_rod l_rod;
 379       l_rod.distance_f_ = cr.distance_f_;
 380       l_rod.other_idx_ = left_idx;
 381       c.rods_[LEFT].push (l_rod);
 382
 383       Spacer_rod r_rod;
 384       r_rod.distance_f_ = cr.distance_f_;
 385       r_rod.other_idx_ = this_rank;
 386       cols_[left_idx].rods_[RIGHT].push (r_rod);
 387     }
 388
 389   cols_.push (c);
 390 }
 391
 392 Line_of_cols
 393 Spring_spacer::error_pcol_l_arr () const
 394 {
 395   Array<Paper_column*> retval;
 396   for (int i=0; i< cols_.size (); i++)
 397     if (cols_[i].ugh_b_)
 398       retval.push (cols_[i].pcol_l_);
 399   for (int i=0;  i < loose_col_arr_.size (); i++)
 400     {
 401       retval.push (loose_col_arr_[i].pcol_l_);
 402     }
 403   return retval;
 404 }
 405
 406 void
 407 Spring_spacer::loosen_column (int i)
 408 {
 409   Column_info c=cols_.get (i);
 410   for (PCursor<Idealspacing*> j (ideal_p_list_.top ()); j.ok (); j++)
 411     {
 412       if (j->left_i_ == i|| j->right_i_ == i)
 413         j.del ();
 414       else
 415         j++;
 416     }
 417   c.ugh_b_ = true;
 418
 419   int j=0;
 420   for (; j < loose_col_arr_.size (); j++)
 421     {
 422       if (loose_col_arr_[j].rank_i_ > c.rank_i_)
 423         break;
 424     }
 425   loose_col_arr_.insert (c,j);
 426 }
 427
 428
 429 void
 430 Spring_spacer::print () const
 431 {
 432 #ifndef NPRINT
 433   for (int i=0; i < cols_.size (); i++)
 434     {
 435       DOUT << "col " << i << " ";
 436       cols_[i].print ();
 437     }
 438   for (PCursor<Idealspacing*> i (ideal_p_list_.top ()); i.ok (); i++)
 439     {
 440       i->print ();
 441     }
 442 #endif
 443 }
 444
 445
 446 void
 447 Spring_spacer::connect (int i, int j, Real d, Real h)
 448 {
 449   assert (d >= 0 && d <= 100 CM);
 450   assert (h >=0);
 451
 452   Idealspacing * s = new Idealspacing;
 453
 454   s->left_i_ = i ;
 455   s->right_i_ = j;
 456   s->space_f_ = d;
 457   s->hooke_f_ = h;
 458
 459   ideal_p_list_.bottom ().add (s);
 460 }
 461
 462
 463
 464
 465 void
 466 Spring_spacer::prepare ()
 467 {
 468   DOUT << "Preparing..";
 469   calc_idealspacing ();
 470   handle_loose_cols ();
 471   print ();
 472   DOUT << "finished preparing.\n";
 473 }
 474
 475 Line_spacer*
 476 Spring_spacer::constructor ()
 477 {
 478   return new Spring_spacer;
 479 }
 480
 481
 482
 483 /**
 484   get the shortest_playing running note at a time. */
 485 void
 486 Spring_spacer::get_ruling_durations (Array<Moment> &shortest_playing_arr,
 487                                     Array<Moment> &context_shortest_arr)
 488 {
 489   for (int i=0; i < cols_.size (); i++)
 490     {
 491       scol_l (i)->preprocess ();
 492       scol_l (i)->print ();
 493     }
 494   int start_context_i=0;
 495   Moment context_shortest;
 496   context_shortest.set_infinite (1);
 497   context_shortest_arr.set_size (cols_.size ());
 498
 499   for (int i=0; i < cols_.size (); i++)
 500     {
 501       Moment now = scol_l (i)->when ();
 502       Moment shortest_playing;
 503       shortest_playing.set_infinite (1);
 504
 505       if (scol_l (i)->breakable_b_)
 506         {
 507           for (int ji=i; ji >= start_context_i; ji--)
 508             context_shortest_arr[ji] = context_shortest;
 509           start_context_i = i;
 510           context_shortest.set_infinite (1);
 511         }
 512       if (scol_l (i)->durations.size ())
 513         {
 514           context_shortest = context_shortest <? scol_l (i)->durations[0];
 515         }
 516
 517       // ji was j, but triggered ICE
 518       for (int ji=i+1; ji --;)
 519         {
 520           if (scol_l (ji)->durations.size () &&
 521               now - scol_l (ji)->when () >= shortest_playing)
 522             break;
 523
 524           for (int k =  scol_l (ji)->durations.size ();
 525                k-- && scol_l (ji)->durations[k] + scol_l (ji)->when () > now;
 526                )
 527             {
 528               shortest_playing = shortest_playing <? scol_l (ji)->durations[k];
 529             }
 530         }
 531       shortest_playing_arr.push (shortest_playing);
 532     }
 533
 534 #ifndef NPRINT
 535   DOUT << "shortest_playing/:[ ";
 536   for (int i=0; i < shortest_playing_arr.size (); i++)
 537     {
 538       DOUT << shortest_playing_arr[i] << " ";
 539       DOUT << context_shortest_arr[i] << ", ";
 540     }
 541   DOUT << "]\n";
 542 #endif
 543 }
 544
 545 /*
 546   TODO: take out the refs to width
 547  */
 548 /**
 549   generate springs between columns.
 550
 551   TODO: This needs rethinking.
 552
 553   *  Spacing should take optical
 554   effects into account
 555
 556   *  Should be decentralised
 557
 558   The algorithm is taken from :
 559
 560   John S. Gourlay. ``Spacing a Line of Music,'' Technical Report
 561   OSU-CISRC-10/87-TR35, Department of Computer and Information
 562   Science, The Ohio State University, 1987.
 563
 564   */
 565 void
 566 Spring_spacer::calc_idealspacing ()
 567 {
 568   Array<Moment> shortest_playing_arr;
 569   Array<Moment> context_shortest_arr;
 570   get_ruling_durations (shortest_playing_arr, context_shortest_arr);
 571
 572   Real interline_f = paper_l ()->interline_f ();
 573
 574
 575   Array<Real> ideal_arr_;
 576   Array<Real> hooke_arr_;
 577   for (int i=0; i < cols_.size () - 1; i++){
 578     ideal_arr_.push (-1.0);
 579     hooke_arr_.push (1.0);
 580   }
 581
 582   /*
 583      First do all non-musical columns
 584   */
 585   for (int i=0; i < cols_.size (); i++)
 586     {
 587       if (!scol_l (i)->musical_b () && i+1 < cols_.size ())
 588         {
 589           Real symbol_distance =cols_[i].width_[RIGHT] + 2 PT;
 590           Real durational_distance = 0;
 591
 592
 593           Moment delta_t =  scol_l (i+1)->when () - scol_l (i)->when () ;
 594
 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 ()->duration_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 ()->duration_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             [Ross]:
 644             when spacing gets real tight, a smaller fixed value may be
 645             used, so that there are two discrete amounts of whitespace
 646             possible at the begin of a bar; but this is not implemented
 647             right now.
 648
 649             * whitespace at the end of the bar is the normal amount of
 650             "hinterfleish" that would have been used, had there been
 651             yet another note in the bar.
 652             [Ross]:
 653             some editors argue that the bar line should not take any
 654             space, not to hinder the flow of music spaced around a bar
 655             line.
 656             [Ross] and [Wanske] do not suggest this, however.  Further,
 657             it introduces some spacing problems and think that it is ugly
 658             too.
 659             [jcn]
 660           */
 661
 662           /*
 663              first musical column of bar
 664           */
 665           if (i && scol_l (i - 1)->breakable_b_)
 666             {
 667               // fixed: probably should set minimum (rod/spring)?
 668               cols_[i-1].width_[RIGHT] += interline_f;
 669               // should adjust dist too?
 670               ideal_arr_[i-1] = ideal_arr_[i-1] >? (2 * interline_f);
 671             }
 672
 673           /*
 674              last musical column of bar
 675           */
 676           if (i + 1 < cols_.size () && scol_l (i+1)->breakable_b_)
 677             {
 678               // hmm, how bout?
 679               dist = dist >? interline_f;
 680
 681               /*
 682                 uhuh, this code looks fine, already?
 683                 someone was junking this last "hinterfleisch" whitespace?!
 684
 685                 but this seems to be fixed now :-)
 686               */
 687               // set minimum rod
 688               cols_[i].width_[RIGHT] += interline_f;
 689             }
 690
 691           // ugh, do we need this?
 692           if (i < cols_.size () - 1 && !scol_l (i + 1)->musical_b ())
 693             {
 694               Real minimum = -cols_[i + 1].width_[LEFT] + cols_[i].width_[RIGHT]
 695                 + interline_f / 2;
 696               dist = dist >? minimum;
 697             }
 698           ideal_arr_[i] = dist;
 699         }
 700     }
 701
 702   for (int i=0; i < ideal_arr_.size (); i++)
 703     {
 704       assert (ideal_arr_[i] >=0 && hooke_arr_[i] >=0);
 705       connect (i, i+1, ideal_arr_[i], hooke_arr_[i]);
 706     }
 707 }