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