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 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
  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())
  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
 153   for (int i=0; i < dim; i++)
 154     {
 155
 156       if (cols[i].fixed()&&
 157           abs (cols[i].fixed_position() - v (i)) > COLFUDGE)
 158         return false;
 159
 160       if (!i)
 161         continue;
 162
 163       Real mindist=cols[i-1].minright()
 164         +cols[i].minleft();
 165
 166       // ugh... compares
 167       Real dif =v (i) - v (i-1)- mindist;
 168       bool b = (dif > - COLFUDGE);
 169
 170
 171       if (!b)
 172         return false;
 173
 174     }
 175   return true;
 176 }
 177
 178 bool
 179 Spring_spacer::check_feasible() const
 180 {
 181   Vector sol (try_initial_solution());
 182   return check_constraints (sol);
 183 }
 184
 185 /// generate a solution which obeys the min distances and fixed positions
 186 Vector
 187 Spring_spacer::try_initial_solution() const
 188 {
 189   int dim=cols.size();
 190   Vector initsol (dim);
 191   for (int i=0; i < dim; i++)
 192     {
 193       if (cols[i].fixed())
 194         {
 195           initsol (i)=cols[i].fixed_position();
 196
 197           if (i > 0)
 198             {
 199               Real r =initsol (i-1)  + cols[i-1].minright();
 200               if (initsol (i) < r)
 201                 {
 202                   warning ("overriding fixed position");
 203                   initsol (i) =r;
 204                 }
 205             }
 206
 207         }
 208       else
 209         {
 210           Real mindist=cols[i-1].minright()
 211             +cols[i].minleft();
 212           if (mindist < 0.0)
 213             warning ("Excentric column");
 214           initsol (i)=initsol (i-1)+mindist;
 215         }
 216     }
 217
 218   return initsol;
 219 }
 220
 221
 222
 223 Vector
 224 Spring_spacer::find_initial_solution() const
 225 {
 226   Vector v (try_initial_solution());
 227   assert (check_constraints (v));
 228   return v;
 229 }
 230
 231 // generate the matrices
 232 void
 233 Spring_spacer::make_matrices (Matrix &quad, Vector &lin, Real &c) const
 234 {
 235   quad.fill (0);
 236   lin.fill (0);
 237   c = 0;
 238
 239   for (PCursor<Idealspacing*> i (ideal_p_list_.top()); i.ok (); i++)
 240     {
 241       int l = i->left_i_;
 242       int r = i->right_i_;
 243
 244       quad (r,r) += i->hooke_f_;
 245       quad (r,l) -= i->hooke_f_;
 246       quad (l,r) -= i->hooke_f_;
 247       quad (l,l) += i->hooke_f_;
 248
 249       lin (r) -= i->space_f_*i->hooke_f_;
 250       lin (l) += i->space_f_*i->hooke_f_;
 251
 252       c += sqr (i->space_f_);
 253     }
 254 }
 255
 256 void
 257 Spring_spacer::set_fixed_cols (Mixed_qp &qp) const
 258 {
 259   for (int j=0; j < cols.size(); j++)
 260     if (cols[j].fixed())
 261       qp.add_fixed_var (j,cols[j].fixed_position());
 262
 263
 264 }
 265
 266 // put the constraints into the LP problem
 267 void
 268 Spring_spacer::make_constraints (Mixed_qp& lp) const
 269 {
 270   int dim=cols.size();
 271   for (int j=0; j < dim; j++)
 272     {
 273       Colinfo c=cols[j];
 274       if (j > 0)
 275         {
 276           Vector c1(dim);
 277
 278           c1(j)=1.0 ;
 279           c1(j-1)=-1.0 ;
 280           lp.add_inequality_cons (c1, cols[j-1].minright() +
 281                                   cols[j].minleft());
 282         }
 283     }
 284 }
 285
 286 void
 287 Spring_spacer::lower_bound_solution (Col_hpositions*positions) const
 288 {
 289   Mixed_qp lp (cols.size());
 290   make_matrices (lp.quad,lp.lin, lp.const_term);
 291   set_fixed_cols (lp);
 292
 293   Vector start (cols.size());
 294   start.fill (0.0);
 295   Vector solution_vec (lp.solve (start));
 296
 297   positions->energy_f_ = lp.eval (solution_vec);
 298   positions->config = solution_vec;
 299   positions->satisfies_constraints_b_ = check_constraints (solution_vec);
 300 }
 301
 302 void
 303 Spring_spacer::solve (Col_hpositions*positions) const
 304 {
 305   assert (check_feasible());
 306
 307   Mixed_qp lp (cols.size());
 308   make_matrices (lp.quad,lp.lin, lp.const_term);
 309   make_constraints (lp);
 310   set_fixed_cols (lp);
 311   Vector start=find_initial_solution();
 312   Vector solution_vec (lp.solve (start));
 313
 314
 315   positions->satisfies_constraints_b_ = check_constraints (solution_vec);
 316   if (!positions->satisfies_constraints_b_)
 317     {
 318       WARN << "solution doesn't satisfy constraints.\n" ;
 319     }
 320   position_loose_cols (solution_vec);
 321   positions->energy_f_ = lp.eval (solution_vec);
 322   positions->config = solution_vec;
 323   positions->error_col_l_arr_ = error_pcol_l_arr();
 324
 325 }
 326
 327 /**
 328   add one column to the problem.
 329 */
 330 void
 331 Spring_spacer::add_column (Paper_column  *col, bool fixed, Real fixpos)
 332 {
 333   Colinfo c (col,(fixed)? &fixpos :  0);
 334   if (cols.size())
 335     c.rank_i_ = cols.top().rank_i_+1;
 336   else
 337     c.rank_i_ = 0;
 338   cols.push (c);
 339 }
 340
 341 Line_of_cols
 342 Spring_spacer::error_pcol_l_arr() const
 343 {
 344   Array<Paper_column*> retval;
 345   for (int i=0; i< cols.size(); i++)
 346     if (cols[i].ugh_b_)
 347       retval.push (cols[i].pcol_l_);
 348   for (int i=0;  i < loose_col_arr_.size(); i++)
 349     {
 350       retval.push (loose_col_arr_[i].pcol_l_);
 351     }
 352   return retval;
 353 }
 354
 355 void
 356 Spring_spacer::loosen_column (int i)
 357 {
 358   Colinfo c=cols.get (i);
 359   for (PCursor<Idealspacing*> j (ideal_p_list_.top()); j.ok (); j++)
 360     {
 361       if (j->left_i_ == i|| j->right_i_ == i)
 362         j.del();
 363       else
 364         j++;
 365     }
 366   c.ugh_b_ = true;
 367
 368   int j=0;
 369   for (; j < loose_col_arr_.size(); j++)
 370     {
 371       if (loose_col_arr_[j].rank_i_ > c.rank_i_)
 372         break;
 373     }
 374   loose_col_arr_.insert (c,j);
 375 }
 376
 377
 378 void
 379 Spring_spacer::print() const
 380 {
 381 #ifndef NPRINT
 382   for (int i=0; i < cols.size(); i++)
 383     {
 384       DOUT << "col " << i<<' ';
 385       cols[i].print();
 386     }
 387   for (PCursor<Idealspacing*> i (ideal_p_list_.top()); i.ok (); i++)
 388     {
 389       i->print();
 390     }
 391 #endif
 392 }
 393
 394
 395 void
 396 Spring_spacer::connect (int i, int j, Real d, Real h)
 397 {
 398   assert(d >= 0 && d <= 100 CM);
 399   assert(h >=0);
 400
 401   Idealspacing * s = new Idealspacing;
 402   s->left_i_ = i;
 403   s->right_i_ = j;
 404   s->space_f_ = d;
 405   s->hooke_f_ = h;
 406
 407   ideal_p_list_.bottom().add (s);
 408 }
 409
 410
 411
 412
 413 void
 414 Spring_spacer::prepare()
 415 {
 416   calc_idealspacing();
 417   handle_loose_cols();
 418   print();
 419 }
 420
 421 Line_spacer*
 422 Spring_spacer::constructor()
 423 {
 424   return new Spring_spacer;
 425 }
 426
 427
 428
 429 /**
 430   get the shortest_playing running note at a time. */
 431 void
 432 Spring_spacer::get_ruling_durations(Array<Moment> &shortest_playing_arr,
 433                                     Array<Moment> &context_shortest_arr)
 434 {
 435   for (int i=0; i < cols.size(); i++)
 436     scol_l (i)->preprocess();
 437
 438   int start_context_i=0;
 439   Moment context_shortest = infinity_mom;
 440   context_shortest_arr.set_size(cols.size());
 441
 442   for (int i=0; i < cols.size(); i++)
 443     {
 444       Moment now = scol_l (i)->when();
 445       Moment shortest_playing = infinity_mom;
 446
 447       if (scol_l (i)->breakable_b_)
 448         {
 449           for (int ji=i; ji >= start_context_i; ji--)
 450             context_shortest_arr[ji] = context_shortest;
 451           start_context_i = i;
 452           context_shortest = infinity_mom;
 453         }
 454       if (scol_l (i)->durations.size())
 455         {
 456           context_shortest = context_shortest <? scol_l(i)->durations[0];
 457         }
 458       // ji was j, but triggered ICE
 459       for (int ji=i+1; ji --;)
 460         {
 461           if (scol_l(ji)->durations.size() &&
 462               now - scol_l(ji)->when() >= shortest_playing)
 463             break;
 464
 465           for (int k =  scol_l (ji)->durations.size();
 466                k-- && scol_l(ji)->durations[k] + scol_l(ji)->when() > now;
 467                )
 468             {
 469               shortest_playing = shortest_playing <? scol_l(ji)->durations[k];
 470             }
 471         }
 472       shortest_playing_arr.push(shortest_playing);
 473     }
 474
 475 #ifndef NPRINT
 476   DOUT << "shortest_playing/:[ ";
 477   for (int i=0; i < shortest_playing_arr.size(); i++)
 478     {
 479       DOUT << shortest_playing_arr[i] << " ";
 480       DOUT << context_shortest_arr[i] << ", ";
 481     }
 482   DOUT << "]\n";
 483 #endif
 484 }
 485
 486 /**
 487   generate springs between columns.
 488
 489   UNDER DESTRUCTION
 490
 491   TODO: This needs rethinking.  Spacing should take optical
 492   effects into account, and should be local (measure wide)
 493
 494   The algorithm is taken from :
 495
 496   John S. Gourlay. ``Spacing a Line of Music,'' Technical Report
 497   OSU-CISRC-10/87-TR35, Department of Computer and Information
 498   Science, The Ohio State University, 1987.
 499
 500   */
 501 void
 502 Spring_spacer::calc_idealspacing()
 503 {
 504   Array<Moment> shortest_playing_arr;
 505   Array<Moment> context_shortest_arr;
 506   get_ruling_durations(shortest_playing_arr, context_shortest_arr);
 507
 508
 509   Array<Real> ideal_arr_;
 510   Array<Real> hooke_arr_;
 511   for (int i=0; i < cols.size(); i++){
 512     ideal_arr_.push (-1.0);
 513     hooke_arr_.push (1.0);
 514   }
 515
 516   for (int i=0; i < cols.size(); i++)
 517     {
 518       if (!scol_l (i)->musical_b())
 519         {
 520           Real symbol_distance =cols[i].minright() + 2 PT;
 521           Real durational_distance = 0;
 522
 523           if (i+1 < cols.size())
 524             {
 525               Moment delta_t =  scol_l (i+1)->when() - scol_l (i)->when () ;
 526
 527               Real k=  paper_l()->arithmetic_constant(context_shortest_arr[i]);
 528               /*
 529                 ugh should use shortest_playing distance
 530                 */
 531               if (delta_t)
 532                 durational_distance =  paper_l()->duration_to_dist (delta_t,k);
 533               symbol_distance += cols[i+1].minleft();
 534             }
 535
 536           ideal_arr_[i] = symbol_distance >? durational_distance;
 537           hooke_arr_[i] = 2.0;
 538         }
 539     }
 540   for (int i=0; i < cols.size(); i++)
 541     {
 542       if (scol_l (i)->musical_b())
 543         {
 544           Moment shortest_playing_len = shortest_playing_arr[i];
 545           Moment context_shortest = context_shortest_arr[i];
 546           if (! shortest_playing_len)
 547             {
 548               warning ("Can't find a ruling note at "
 549                        +String (scol_l (i)->when()));
 550               shortest_playing_len = 1;
 551             }
 552           if (! context_shortest)
 553             {
 554               warning("No minimum in measure at "
 555                       + String (scol_l (i)->when()));
 556               context_shortest = 1;
 557             }
 558           Moment delta_t = scol_l (i+1)->when() - scol_l (i)->when ();
 559           Real k=  paper_l()->arithmetic_constant(context_shortest);
 560           Real dist = paper_l()->duration_to_dist (shortest_playing_len, k);
 561           dist *= delta_t / shortest_playing_len;
 562
 563           /* all sorts of ugliness to avoid running into bars/clefs, but not taking
 564              extra space if this is not needed */
 565           if (!scol_l (i+1)->musical_b())
 566             {
 567               Real minimum_dist =   cols[i+1].minleft() + 2 PT + cols[i].minright () ;
 568               if (ideal_arr_[i+1] + minimum_dist < dist)
 569                 {
 570                   ideal_arr_[i] = dist - ideal_arr_[i+1];
 571                   // hooke_arr_[i+1] =1.0;
 572                 } else {
 573                   ideal_arr_[i] = minimum_dist;
 574                 }
 575
 576             } else
 577               ideal_arr_[i] = dist;
 578         }
 579     }
 580
 581   for (int i=0; i < ideal_arr_.size()-1; i++)
 582     {
 583       assert (ideal_arr_[i] >=0 && hooke_arr_[i] >=0);
 584       connect (i, i+1, ideal_arr_[i], hooke_arr_[i]);
 585     }
 586 }