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 "spring-spacer.hh"
  12 #include "p-col.hh"
  13 #include "debug.hh"
  14 #include "qlp.hh"
  15 #include "unionfind.hh"
  16 #include "idealspacing.hh"
  17 #include "pointer.tcc"
  18 #include "score-column.hh"
  19 #include "paper-def.hh"
  20 #include "dimen.hh"
  21 #include "minterval.hh"
  22
  23 Vector
  24 Spring_spacer::default_solution()const
  25 {
  26         return try_initial_solution() ;
  27 }
  28
  29 Score_column*
  30 Spring_spacer::scol_l(int i)
  31 {
  32     return (Score_column*)cols[i].pcol_l_;
  33 }
  34
  35 const Real COLFUDGE=1e-3;
  36 template class P<Real>;         // ugh.
  37
  38 bool
  39 Spring_spacer::contains(PCol const *w)
  40 {
  41     for (int i=0; i< cols.size(); i++)
  42         if (cols[i].pcol_l_ == w)
  43             return true;
  44     return false;
  45 }
  46
  47
  48 void
  49 Spring_spacer::OK() const
  50 {
  51 #ifndef NDEBUG
  52     for (int i = 1; i < cols.size(); i++)
  53         assert(cols[i].rank_i_ > cols[i-1].rank_i_);
  54     for (int i = 1; i < loose_col_arr_.size(); i++)
  55         assert(loose_col_arr_[i].rank_i_ > loose_col_arr_[i-1].rank_i_);
  56 #endif
  57 }
  58
  59 /**
  60   Make sure no unconnected columns happen.
  61  */
  62 void
  63 Spring_spacer::handle_loose_cols()
  64 {
  65     Union_find connected(cols.size());
  66     Array<int> fixed;
  67     for (PCursor<Idealspacing*> i(ideal_p_list_.top()); i.ok(); i++){
  68         connected.connect(i->left_i_,i->right_i_);
  69     }
  70     for (int i = 0; i < cols.size(); i++)
  71         if (cols[i].fixed())
  72             fixed.push(i);
  73     for (int i=1; i < fixed.size(); i++)
  74         connected.connect(fixed[i-1], fixed[i]);
  75
  76     for (int i = cols.size(); i--; ) {
  77         if (! connected.equiv(fixed[0], i)) {
  78             warning("unconnected column: " + String(i));
  79             loosen_column(i);
  80         }
  81     }
  82     OK();
  83 }
  84
  85
  86 /**
  87   Guess a stupid position for loose columns.  Put loose columns at
  88   regular distances from enclosing calced columns
  89   */
  90 void
  91 Spring_spacer::position_loose_cols(Vector &sol_vec)const
  92 {
  93     if (!loose_col_arr_.size())
  94         return ;
  95     assert(sol_vec.dim());
  96     Array<bool> fix_b_arr;
  97     fix_b_arr.set_size(cols.size() + loose_col_arr_.size());
  98     Real utter_right_f=-INFTY;
  99     Real utter_left_f =INFTY;
 100     for (int i=0; i < loose_col_arr_.size(); i++) {
 101         fix_b_arr[loose_col_arr_[i].rank_i_] = false;
 102     }
 103     for (int i=0; i < cols.size(); i++) {
 104         int r= cols[i].rank_i_;
 105         fix_b_arr[r] = true;
 106         utter_right_f = utter_right_f >? sol_vec(i);
 107         utter_left_f = utter_left_f <? sol_vec(i);
 108     }
 109     Vector v(fix_b_arr.size());
 110     int j =0;
 111     int k =0;
 112     for (int i=0; i < v.dim(); i++) {
 113         if (fix_b_arr[i]) {
 114             assert(cols[j].rank_i_ == i);
 115             v(i) = sol_vec(j++);
 116         } else {
 117             Real left_pos_f =
 118                 (j>0) ?sol_vec(j-1) : utter_left_f;
 119             Real right_pos_f =
 120                 (j < sol_vec.dim()) ? sol_vec(j) : utter_right_f;
 121             int left_rank = (j>0) ? cols[j-1].rank_i_ : 0;
 122             int right_rank = (j<sol_vec.dim()) ? cols[j].rank_i_ : sol_vec.dim();
 123
 124             int d_r = right_rank - left_rank;
 125             Colinfo loose=loose_col_arr_[k++];
 126             int r = loose.rank_i_ ;
 127             assert(r > left_rank && r < right_rank);
 128
 129             v(i) =  (r - left_rank)*left_pos_f/ d_r +
 130                 (right_rank - r) *right_pos_f /d_r;
 131         }
 132     }
 133     sol_vec = v;
 134 }
 135
 136 bool
 137 Spring_spacer::check_constraints(Vector v) const
 138 {
 139     int dim=v.dim();
 140     assert(dim == cols.size());
 141
 142     for (int i=0; i < dim; i++) {
 143
 144         if (cols[i].fixed()&&
 145             abs(cols[i].fixed_position() - v(i)) > COLFUDGE)
 146             return false;
 147
 148         if (!i)
 149             continue;
 150
 151         Real mindist=cols[i-1].minright()
 152             +cols[i].minleft();
 153
 154         // ugh... compares
 155         Real dif =v(i) - v(i-1)- mindist;
 156         bool b = (dif > - COLFUDGE);
 157
 158
 159         if (!b)
 160             return false;
 161
 162     }
 163     return true;
 164 }
 165
 166 bool
 167 Spring_spacer::check_feasible() const
 168 {
 169     Vector sol(try_initial_solution());
 170     return check_constraints(sol);
 171 }
 172
 173 /// generate a solution which obeys the min distances and fixed positions
 174 Vector
 175 Spring_spacer::try_initial_solution() const
 176 {
 177     int dim=cols.size();
 178     Vector initsol(dim);
 179     for (int i=0; i < dim; i++) {
 180         if (cols[i].fixed()) {
 181             initsol(i)=cols[i].fixed_position();
 182
 183             if (i > 0) {
 184                 Real r =initsol(i-1)  + cols[i-1].minright();
 185                 if (initsol(i) < r ) {
 186                     warning("overriding fixed position");
 187                     initsol(i) =r;
 188                 }
 189             }
 190
 191         } else {
 192             Real mindist=cols[i-1].minright()
 193                 +cols[i].minleft();
 194             if (mindist < 0.0)
 195                 warning("Excentric column");
 196             initsol(i)=initsol(i-1)+mindist;
 197         }
 198     }
 199
 200     return initsol;
 201 }
 202
 203
 204
 205 Vector
 206 Spring_spacer::find_initial_solution() const
 207 {
 208     Vector v(try_initial_solution());
 209     assert(check_constraints(v));
 210     return v;
 211 }
 212
 213 // generate the matrices
 214 void
 215 Spring_spacer::make_matrices(Matrix &quad, Vector &lin, Real &c) const
 216 {
 217     quad.fill(0);
 218     lin.fill(0);
 219     c = 0;
 220
 221     for (PCursor<Idealspacing*> i(ideal_p_list_.top()); i.ok(); i++) {
 222         int l = i->left_i_;
 223         int r = i->right_i_;
 224
 225         quad(r,r) += i->hooke_f_;
 226         quad(r,l) -= i->hooke_f_;
 227         quad(l,r) -= i->hooke_f_;
 228         quad(l,l) += i->hooke_f_;
 229
 230         lin(r) -= i->space_f_*i->hooke_f_;
 231         lin(l) += i->space_f_*i->hooke_f_;
 232
 233         c += sqr(i->space_f_);
 234     }
 235 }
 236
 237 // put the constraints into the LP problem
 238 void
 239 Spring_spacer::make_constraints(Mixed_qp& lp) const
 240 {
 241     int dim=cols.size();
 242     for (int j=0; j < dim; j++) {
 243         Colinfo c=cols[j];
 244         if (c.fixed()) {
 245             lp.add_fixed_var(j,c.fixed_position());
 246         }
 247         if (j > 0){
 248             Vector c1(dim);
 249
 250             c1(j)=1.0 ;
 251             c1(j-1)=-1.0 ;
 252             lp.add_inequality_cons(c1, cols[j-1].minright() +
 253                                    cols[j].minleft());
 254         }
 255     }
 256 }
 257
 258 Array<Real>
 259 Spring_spacer::solve() const
 260 {
 261     assert(check_feasible());
 262
 263     Mixed_qp lp(cols.size());
 264     make_matrices(lp.quad,lp.lin, lp.const_term);
 265     make_constraints(lp);
 266     Vector start=find_initial_solution();
 267     Vector sol(lp.solve(start));
 268     if (!check_constraints(sol)) {
 269         WARN << "solution doesn't satisfy constraints.\n" ;
 270     }
 271     Real energy_f =lp.eval(sol);
 272     position_loose_cols(sol);
 273
 274     Array<Real> posns(sol);
 275
 276     posns.push(energy_f);
 277     return posns;
 278 }
 279
 280 /**
 281     add one column to the problem.
 282 */
 283 void
 284 Spring_spacer::add_column(PCol  *col, bool fixed, Real fixpos)
 285 {
 286     Colinfo c(col,(fixed)? &fixpos :  0);
 287     if (cols.size())
 288         c.rank_i_ = cols.top().rank_i_+1;
 289     else
 290         c.rank_i_ = 0;
 291     cols.push(c);
 292 }
 293
 294 Array<PCol*>
 295 Spring_spacer::error_pcol_l_arr()const
 296 {
 297     Array<PCol*> retval;
 298     for (int i=0; i< cols.size(); i++)
 299         if (cols[i].ugh_b_)
 300             retval.push(cols[i].pcol_l_);
 301     for (int i=0;  i < loose_col_arr_.size(); i++) {
 302         retval.push(loose_col_arr_[i].pcol_l_);
 303     }
 304     return retval;
 305 }
 306
 307 void
 308 Spring_spacer::loosen_column(int i)
 309 {
 310     Colinfo c=cols.get(i);
 311     for (PCursor<Idealspacing*> j(ideal_p_list_.top()); j.ok(); j++){
 312         if (j->left_i_ == i|| j->right_i_ == i)
 313             j.del();
 314         else
 315             j++;
 316     }
 317     c.ugh_b_ = true;
 318
 319     int j=0;
 320     for (; j < loose_col_arr_.size(); j++) {
 321         if (loose_col_arr_[j].rank_i_ > c.rank_i_)
 322             break;
 323     }
 324     loose_col_arr_.insert(c,j);
 325 }
 326
 327
 328 void
 329 Spring_spacer::print() const
 330 {
 331 #ifndef NPRINT
 332     for (int i=0; i < cols.size(); i++) {
 333         mtor << "col " << i<<' ';
 334         cols[i].print();
 335     }
 336     for (PCursor<Idealspacing*> i(ideal_p_list_.top()); i.ok(); i++){
 337         i->print();
 338     }
 339 #endif
 340
 341 }
 342
 343
 344 void
 345 Spring_spacer::connect(int i, int j, Real d, Real h)
 346 {
 347     Idealspacing * s = new Idealspacing;
 348     s->left_i_ = i;
 349     s->right_i_ = j;
 350     s->space_f_ = d;
 351     s->hooke_f_ = h;
 352
 353     ideal_p_list_.bottom().add(s);
 354 }
 355
 356 /**
 357   walk through all durations in all Score_columns
 358  */
 359 struct Durations_iter
 360 {
 361     Spring_spacer * sp_l_;
 362     int col_i_;
 363     int d_i_;
 364
 365     Durations_iter(Spring_spacer*);
 366
 367     Moment duration()const;
 368     Moment when()const;
 369
 370     bool ok()const;
 371     void next();
 372 };
 373
 374 Durations_iter::Durations_iter(Spring_spacer * s)
 375 {
 376     col_i_ =0;
 377     d_i_ =0;            // ugh
 378
 379     sp_l_ = s;
 380     if (! sp_l_->scol_l(col_i_)->durations.size() )
 381         next();
 382 }
 383
 384 Moment
 385 Durations_iter::duration() const
 386 {
 387     return sp_l_->scol_l(col_i_)->durations[d_i_];
 388 }
 389
 390 bool
 391 Durations_iter::ok()const{
 392     return col_i_ < sp_l_->cols.size();
 393 }
 394
 395 Moment
 396 Durations_iter::when()const{
 397     return sp_l_->scol_l(col_i_)->when();
 398 }
 399
 400 void
 401 Durations_iter::next()
 402 {
 403     d_i_ ++;
 404     while ( col_i_ < sp_l_->cols.size()
 405             && d_i_ >= sp_l_->scol_l(col_i_)->durations.size()){
 406         col_i_ ++;
 407         d_i_ =0;
 408     }
 409 }
 410
 411
 412 /**
 413   generate springs between columns.
 414
 415   UNDER DESTRUCTION
 416
 417   TODO: This needs rethinking.  Spacing should take optical
 418   effects into account, and should be local (measure wide)
 419
 420   The algorithm is taken from :
 421
 422   John S. Gourlay. ``Spacing a Line of Music,'' Technical Report
 423   OSU-CISRC-10/87-TR35, Department of Computer and Information
 424   Science, The Ohio State University, 1987.
 425
 426   */
 427 void
 428 Spring_spacer::calc_idealspacing()
 429 {
 430
 431     for (int i=0; i < cols.size(); i++)
 432         scol_l(i)->preprocess();
 433
 434     /* get the shortest running note at a time. */
 435     Array<Moment> shortest_arr_;
 436     {
 437         Durations_iter d_iter(this);
 438         for (int i=0; i < cols.size(); i++) {
 439             Moment now = scol_l(i)->when();
 440             while (  d_iter.ok() && now >= d_iter.when() ) {
 441                 if ( now < d_iter.when() + d_iter.duration())
 442                     break;
 443                 d_iter.next();
 444             }
 445             if ( d_iter.ok() && now >= d_iter.when()) {
 446                 Durations_iter d2 = d_iter;
 447                 Moment shortest = INFTY;
 448                 while (d2.ok() && d2.when() <= now) {
 449                     shortest = shortest <? d2.duration();
 450                     d2.next();
 451                 }
 452                 shortest_arr_.push( shortest );
 453             } else
 454                 shortest_arr_.push(0);
 455         }
 456
 457     }
 458 #ifndef NPRINT
 459     mtor << "shortest:[ ";
 460     for (int i=0; i < shortest_arr_.size(); i++)
 461         mtor << shortest_arr_[i] << " ";
 462     mtor << "]\n";
 463 #endif
 464
 465     Array<Real> ideal_arr_;
 466     Array<Real> hooke_arr_;
 467     for (int i=0; i < cols.size(); i++){
 468         ideal_arr_.push(  -1.0);
 469         hooke_arr_.push(1.0);
 470     }
 471
 472     for (int i=0; i < cols.size(); i++) {
 473         if ( !scol_l(i)->musical_b()) {
 474             ideal_arr_[i] = cols[i].minright() + 2 PT;
 475             hooke_arr_[i] = 2.0;
 476             if (i+1 < cols.size()) {
 477                 Moment delta_t =  scol_l(i+1)->when() - scol_l(i)->when() ;
 478                 Real dist = delta_t ? paper_l()->duration_to_dist(delta_t) : 0;
 479                 if (delta_t && dist > ideal_arr_[i])
 480                     ideal_arr_[i] = dist;
 481             }
 482         }
 483     }
 484     for (int i=0; i < cols.size(); i++) {
 485         if (scol_l(i)->musical_b()) {
 486             Moment shortest_len = shortest_arr_[i];
 487             if ( ! shortest_len ) {
 488                 warning( "Can't find a ruling note at "
 489                          +String( scol_l(i)->when()));
 490                 shortest_len = 1;
 491             }
 492             Moment delta_t = scol_l(i+1)->when() - scol_l(i)->when();
 493             Real dist = paper_l()->duration_to_dist(shortest_len);
 494             dist *= delta_t / shortest_len;
 495             if (!scol_l(i+1)->musical_b() ) {
 496
 497                 if (ideal_arr_[i+1] + cols[i+1].minleft() < dist) {
 498                     ideal_arr_[i+1] = dist/2 + cols[i+1].minleft();
 499                     hooke_arr_[i+1] =1.0;
 500                 }
 501                 ideal_arr_[i] = dist/2;
 502             } else
 503                 ideal_arr_[i] = dist;
 504         }
 505     }
 506
 507     for (int i=0; i < ideal_arr_.size()-1; i++) {
 508         assert (ideal_arr_[i] >=0 && hooke_arr_[i] >=0);
 509         connect(i, i+1, ideal_arr_[i], hooke_arr_[i]);
 510     }
 511
 512 }
 513
 514
 515
 516 void
 517 Spring_spacer::prepare()
 518 {
 519     calc_idealspacing();
 520     handle_loose_cols();
 521     print();
 522 }
 523
 524 Line_spacer*
 525 Spring_spacer::constructor()
 526 {
 527     return new Spring_spacer;
 528 }
 529
 530 #if 0
 531 void obsolete()
 532 {
 533     for (int i=0; i < cols.size(); i++) {
 534         if (!scol_l(i)->used_b())
 535             continue;
 536
 537
 538         int j = i+1;
 539
 540         if (scol_l(i)->musical_b()) {
 541             assert ( j < cols.size());
 542
 543             for (int n=0; n < scol_l(i)->durations.size(); n++) {
 544                 Moment d = scol_l(i)->durations[n];
 545                 Real dist = paper_l()->duration_to_dist(d);
 546                 Real strength =  scol_l(i)->durations[0]/scol_l(i)->durations[n];
 547                 assert(strength <= 1.0);
 548
 549                 while (j < cols.size()) {
 550                     if (scol_l(j)->used_b()
 551                         && scol_l(j)->when() >= d + scol_l(i)->when() )
 552                         break;
 553                     j++;
 554                 }
 555                 if ( j < cols.size() ){
 556                     Moment delta_desired = scol_l(j)->when() - (d+scol_l(i)->when());
 557                     dist += paper_l()->duration_to_dist(delta_desired);
 558                     if (scol_l(j)->musical_b()) {
 559                         dist += cols[j].minleft() + 2 PT;
 560                     }
 561                     connect(i, j, dist, strength);
 562                 }
 563             }
 564         } else if (j < cols.size()) {
 565             while  (!scol_l(j)->used_b())
 566                 j++;
 567
 568             /* attach i to the next column in use. This exists, since
 569               the last col is breakable, and therefore in use
 570               */
 571
 572             Moment d = scol_l(j)->when() - scol_l(i)->when();
 573             Real minimal_f = cols[i].minright()  +cols[j].minleft() + 2 PT;
 574             Real durdist_f = (d) ? paper_l()->duration_to_dist(d) : 0; // todo
 575
 576             connect(i, j, minimal_f <? durdist_f, (d) ? 1.0:1.0);
 577         }
 578         // !j.ok() might hold if we're at the last col.
 579     }
 580 }
 581 #endif