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         DOUT << "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 void
 371 Spring_spacer::connect (int i, int j, Real d, Real h)
 372 {
 373     Idealspacing * s = new Idealspacing;
 374     s->left_i_ = i;
 375     s->right_i_ = j;
 376     s->space_f_ = d;
 377     s->hooke_f_ = h;
 378
 379     ideal_p_list_.bottom().add (s);
 380 }
 381
 382 /**
 383   generate springs between columns.
 384
 385   UNDER DESTRUCTION
 386
 387   TODO: This needs rethinking.  Spacing should take optical
 388   effects into account, and should be local (measure wide)
 389
 390   The algorithm is taken from :
 391
 392   John S. Gourlay. ``Spacing a Line of Music,'' Technical Report
 393   OSU-CISRC-10/87-TR35, Department of Computer and Information
 394   Science, The Ohio State University, 1987.
 395
 396   */
 397 void
 398 Spring_spacer::calc_idealspacing()
 399 {
 400
 401     for (int i=0; i < cols.size(); i++)
 402         scol_l (i)->preprocess();
 403
 404     /* get the shortest running note at a time. */
 405     Array<Moment> shortest_arr;
 406     for (int i=0; i < cols.size(); i++) {
 407         Moment now = scol_l (i)->when();
 408         Moment shortest = infinity_mom;
 409         // ji was j, but triggered ICE
 410         for (int ji=i+1; ji --; ) {
 411             if (scol_l(ji)->durations.size() &&
 412                  now - scol_l(ji)->when() >= shortest)
 413                 break;
 414
 415             for (int k =  scol_l (ji)->durations.size();
 416                  k-- && scol_l(ji)->durations[k] + scol_l(ji)->when() > now;
 417                 )
 418             {
 419                 shortest = shortest <? scol_l(ji)->durations[k];
 420             }
 421         }
 422         shortest_arr.push(shortest);
 423     }
 424
 425 #ifndef NPRINT
 426     DOUT << "shortest:[ ";
 427     for (int i=0; i < shortest_arr.size(); i++)
 428         DOUT << shortest_arr[i] << " ";
 429     DOUT << "]\n";
 430 #endif
 431
 432     Array<Real> ideal_arr_;
 433     Array<Real> hooke_arr_;
 434     for (int i=0; i < cols.size(); i++){
 435         ideal_arr_.push (-1.0);
 436         hooke_arr_.push (1.0);
 437     }
 438
 439     for (int i=0; i < cols.size(); i++) {
 440         if ( !scol_l (i)->musical_b()) {
 441             Real symbol_distance =cols[i].minright() + 2 PT;
 442             Real durational_distance = 0;
 443
 444             if (i+1 < cols.size()) {
 445                 Moment delta_t =  scol_l (i+1)->when() - scol_l (i)->when () ;
 446                 /*
 447                   ugh should use shortest distance
 448                  */
 449                 if (delta_t)
 450                     durational_distance =  paper_l()->duration_to_dist (delta_t) ;
 451                 symbol_distance += cols[i+1].minleft();
 452             }
 453
 454             ideal_arr_[i] = symbol_distance >? durational_distance;
 455             hooke_arr_[i] = 2.0;
 456         }
 457     }
 458     for (int i=0; i < cols.size(); i++) {
 459         if (scol_l (i)->musical_b()) {
 460             Moment shortest_len = shortest_arr[i];
 461             if ( ! shortest_len) {
 462                 warning ("Can't find a ruling note at "
 463                          +String (scol_l (i)->when()));
 464                 shortest_len = 1;
 465             }
 466             Moment delta_t = scol_l (i+1)->when() - scol_l (i)->when ();
 467             Real dist = paper_l()->duration_to_dist (shortest_len);
 468             dist *= delta_t / shortest_len;
 469             if (!scol_l (i+1)->musical_b()) {
 470
 471                 Real minimum_dist =   cols[i+1].minleft() + 2 PT + cols[i].minright () ;
 472                 if (ideal_arr_[i+1] + minimum_dist < dist) {
 473                     ideal_arr_[i] = dist - ideal_arr_[i+1];
 474                     // hooke_arr_[i+1] =1.0;
 475                 } else {
 476                     ideal_arr_[i] = minimum_dist;
 477                 }
 478
 479             } else
 480                 ideal_arr_[i] = dist;
 481         }
 482     }
 483
 484     for (int i=0; i < ideal_arr_.size()-1; i++) {
 485         assert (ideal_arr_[i] >=0 && hooke_arr_[i] >=0);
 486         connect (i, i+1, ideal_arr_[i], hooke_arr_[i]);
 487     }
 488 }
 489
 490
 491
 492 void
 493 Spring_spacer::prepare()
 494 {
 495     calc_idealspacing();
 496     handle_loose_cols();
 497     print();
 498 }
 499
 500 Line_spacer*
 501 Spring_spacer::constructor()
 502 {
 503     return new Spring_spacer;
 504 }
 505