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