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--1999 Han-Wen Nienhuys <hanwen@cs.uu.nl>
   7 */
   8
   9
  10 #include <math.h>
  11 #include <limits.h>
  12 #include "killing-cons.tcc"
  13 #include "spring-spacer.hh"
  14 #include "paper-column.hh"
  15 #include "debug.hh"
  16 #include "dimensions.hh"
  17 #include "qlp.hh"
  18 #include "unionfind.hh"
  19 #include "idealspacing.hh"
  20 #include "pointer.tcc"
  21 #include "score-column.hh"
  22 #include "paper-def.hh"
  23 #include "column-x-positions.hh"
  24 #include "main.hh"
  25
  26 Vector
  27 Spring_spacer::default_solution() const
  28 {
  29   return try_initial_solution();
  30 }
  31
  32 Score_column*
  33 Spring_spacer::scol_l (int i)
  34 {
  35   return dynamic_cast<Score_column*>(cols_[i].pcol_l_);
  36 }
  37
  38 const Real COLFUDGE=1e-3;
  39 template class P<Real>;         // ugh.
  40
  41 bool
  42 Spring_spacer::contains_b (Paper_column const *w)
  43 {
  44   for (int i=0; i< cols_.size(); i++)
  45     if (cols_[i].pcol_l_ == w)
  46       return true;
  47   return false;
  48 }
  49
  50
  51 void
  52 Spring_spacer::OK() const
  53 {
  54 #ifndef NDEBUG
  55   for (int i = 1; i < cols_.size(); i++)
  56     assert (cols_[i].rank_i_ > cols_[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
  69   for (Cons<Idealspacing> *i  = ideal_p_list_; i; i = i->next_)
  70     {
  71       connected.connect (i->car_->cols_drul_[LEFT],i->car_->cols_drul_[RIGHT]);
  72     }
  73   for (int i = 0; i < cols_.size(); i++)
  74     if (cols_[i].fixed_b())
  75       fixed.push (i);
  76   for (int i=1; i < fixed.size(); i++)
  77     connected.connect (fixed[i-1], fixed[i]);
  78
  79   /*
  80     If columns do not have spacing information set, we need to supply our own.
  81    */
  82   Real d = default_space_f_;
  83   for (int i = cols_.size(); i--;)
  84     {
  85       if (! connected.equiv (fixed[0], i))
  86         {
  87           connected.connect (i-1, i);
  88           connect (i-1, i, d, 1.0);
  89         }
  90     }
  91 }
  92
  93 bool
  94 Spring_spacer::check_constraints (Vector v) const
  95 {
  96   int dim=v.dim();
  97   assert (dim == cols_.size());
  98   DOUT << "checking " << v;
  99   for (int i=0; i < dim; i++)
 100     {
 101       if (cols_[i].fixed_b() &&
 102           abs (cols_[i].fixed_position() - v (i)) > COLFUDGE)
 103         {
 104           DOUT << "Fixpos broken\n";
 105           return false;
 106         }
 107       Array<Spacer_rod> const &rods (cols_[i].rods_[RIGHT]);
 108       for (int j =0; j < rods.size (); j++)
 109         {
 110           int other =rods[j].other_idx_;
 111           Real diff =v (other) - v (i) ;
 112           if (COLFUDGE +diff <  rods[j].distance_f_)
 113             {
 114               DOUT << "i, other_i: " << i << "  " << other << '\n';
 115               DOUT << "dist, minimal = " << diff << " "
 116                    << rods[j].distance_f_ << '\n';
 117               return false;
 118             }
 119         }
 120
 121     }
 122   return true;
 123 }
 124
 125 /** try to generate a solution which obeys the min
 126     distances and fixed positions
 127  */
 128 Vector
 129 Spring_spacer::try_initial_solution() const
 130 {
 131   Vector v;
 132   if (!try_initial_solution_and_tell (v))
 133     {
 134       warning (_ ("I'm too fat; call Oprah"));
 135     }
 136   return v;
 137
 138 }
 139
 140 bool
 141 Spring_spacer::try_initial_solution_and_tell (Vector &v) const
 142 {
 143   int dim=cols_.size();
 144   bool succeeded = true;
 145   Vector initsol (dim);
 146
 147   assert (cols_[0].fixed_b ());
 148   DOUT << "fixpos 0 " << cols_[0].fixed_position ();
 149   for (int i=0; i < dim; i++)
 150     {
 151       Real min_x = i ?  initsol (i-1) : cols_[0].fixed_position ();
 152       Array<Spacer_rod> const &sr_arr(cols_[i].rods_[LEFT]);
 153       for (int j=0; j < sr_arr.size (); j++)
 154         {
 155           min_x = min_x >? (initsol (sr_arr[j].other_idx_) + sr_arr[j].distance_f_);
 156         }
 157       initsol (i) = min_x;
 158
 159       if (cols_[i].fixed_b())
 160         {
 161           initsol (i)=cols_[i].fixed_position();
 162           if (initsol (i) < min_x )
 163             {
 164               DOUT << "failing: init, min : " << initsol (i) << " " << min_x << '\n';
 165               initsol (i) = min_x;
 166               succeeded = false;
 167             }
 168         }
 169     }
 170   v = initsol;
 171
 172   DOUT << "tried and told solution: " << v;
 173   if (!succeeded)
 174     DOUT << "(failed)\n";
 175   return succeeded;
 176 }
 177
 178
 179
 180 // generate the matrices
 181 void
 182 Spring_spacer::make_matrices (Matrix &quad, Vector &lin, Real &c) const
 183 {
 184   quad.fill (0);
 185   lin.fill (0);
 186   c = 0;
 187
 188   for (Cons<Idealspacing> *p =ideal_p_list_; p; p = p->next_)
 189     {
 190       Idealspacing *i = p->car_;
 191       int l = i->cols_drul_[LEFT];
 192       int r = i->cols_drul_[RIGHT];
 193
 194       quad (r,r) += i->hooke_f_;
 195       quad (r,l) -= i->hooke_f_;
 196       quad (l,r) -= i->hooke_f_;
 197       quad (l,l) += i->hooke_f_;
 198
 199       lin (r) -= i->space_f_*i->hooke_f_;
 200       lin (l) += i->space_f_*i->hooke_f_;
 201
 202       c += sqr (i->space_f_);
 203     }
 204
 205   if (quad.dim() > 10)
 206     quad.set_band();
 207
 208
 209 }
 210
 211 void
 212 Spring_spacer::set_fixed_cols (Mixed_qp &qp) const
 213 {
 214   for (int j=0; j < cols_.size(); j++)
 215     if (cols_[j].fixed_b())
 216       qp.add_fixed_var (j,cols_[j].fixed_position());
 217 }
 218
 219 // put the constraints into the LP problem
 220 void
 221 Spring_spacer::make_constraints (Mixed_qp& lp) const
 222 {
 223   int dim=cols_.size();
 224
 225   for (int j=0; j < dim -1; j++)
 226     {
 227       Array<Spacer_rod> const&rod_arr (cols_[j].rods_[RIGHT]);
 228       for (int i = 0; i < rod_arr.size (); i++)
 229         {
 230           Vector c1(dim);
 231           c1(rod_arr[i].other_idx_)=1.0 ;
 232           c1(j)=-1.0 ;
 233
 234           lp.add_inequality_cons (c1, rod_arr[i].distance_f_);
 235         }
 236     }
 237 }
 238
 239
 240 Real
 241 Spring_spacer::calculate_energy_f (Vector solution) const
 242 {
 243   Real e = 0.0;
 244   for (Cons<Idealspacing>*p =ideal_p_list_; p; p = p->next_)
 245     {
 246       Idealspacing * i = p->car_;
 247       e += i->energy_f(solution(i->cols_drul_[RIGHT]) - solution(i->cols_drul_[LEFT]));
 248     }
 249
 250   return e;
 251 }
 252 void
 253 Spring_spacer::lower_bound_solution (Column_x_positions*positions) const
 254 {
 255   Mixed_qp lp (cols_.size());
 256   make_matrices (lp.quad_,lp.lin_, lp.const_term_);
 257   set_fixed_cols (lp);
 258
 259   Vector start (cols_.size());
 260   start.fill (0.0);
 261   Vector solution_vec (lp.solve (start));
 262   for (int i=0; i < solution_vec.dim (); i++)
 263     solution_vec(i) += indent_f_;
 264
 265   DOUT << "Lower bound sol: " << solution_vec;
 266   positions->energy_f_ = calculate_energy_f (solution_vec);
 267   positions->config_ = solution_vec;
 268   positions->satisfies_constraints_b_ = check_constraints (solution_vec);
 269 }
 270
 271 Spring_spacer::Spring_spacer ()
 272 {
 273   ideal_p_list_ =0;
 274   energy_normalisation_f_ = 1.0;
 275 }
 276
 277 void
 278 Spring_spacer::solve (Column_x_positions*positions) const
 279 {
 280   Vector solution_try;
 281
 282   bool constraint_satisfaction = try_initial_solution_and_tell (solution_try);
 283   if  (constraint_satisfaction)
 284     {
 285       Mixed_qp lp (cols_.size());
 286       make_matrices (lp.quad_,lp.lin_, lp.const_term_);
 287       make_constraints (lp);
 288       set_fixed_cols (lp);
 289
 290
 291       Vector solution_vec (lp.solve (solution_try));
 292       for (int i=0; i < solution_vec.dim (); i++)
 293         solution_vec(i) += indent_f_;
 294
 295
 296       positions->satisfies_constraints_b_ = check_constraints (solution_vec);
 297       if (!positions->satisfies_constraints_b_)
 298         {
 299           warning (_("Solution doesn't satisfy constraints"));
 300         }
 301
 302       positions->energy_f_ = calculate_energy_f (solution_vec);
 303       positions->config_ = solution_vec;
 304     }
 305   else
 306     {
 307       positions->set_stupid_solution (solution_try);
 308     }
 309
 310 }
 311
 312 /**
 313   add one column to the problem.
 314
 315   TODO: ugh merge with add_columns.
 316 */
 317 void
 318 Spring_spacer::add_column (Paper_column  *col, bool fixed, Real fixpos)
 319 {
 320   Column_info c (col,(fixed)? &fixpos :  0);
 321   int this_rank =  cols_.size();
 322   c.rank_i_ = this_rank;
 323
 324   for (int i=0; i < col->minimal_dists_arr_drul_[LEFT].size (); i++)
 325     {
 326       Column_rod &cr = col->minimal_dists_arr_drul_[LEFT][i];
 327       int left_idx = cr.other_l_->rank_i () - cols_[0].pcol_l_->rank_i ();
 328       if (left_idx < 0)
 329         continue;
 330
 331       if (cols_[left_idx].pcol_l_ != cr.other_l_)
 332         continue;
 333
 334       Spacer_rod l_rod;
 335       l_rod.distance_f_ = cr.distance_f_;
 336       l_rod.other_idx_ = left_idx;
 337       c.rods_[LEFT].push (l_rod);
 338
 339       Spacer_rod r_rod;
 340       r_rod.distance_f_ = cr.distance_f_;
 341       r_rod.other_idx_ = this_rank;
 342       cols_[left_idx].rods_[RIGHT].push (r_rod);
 343     }
 344
 345   for (int i=0; i < col->spring_arr_drul_[LEFT].size (); i++)
 346     {
 347       Column_spring &cr = col->spring_arr_drul_[LEFT][i];
 348       int idx = cr.other_l_->rank_i () - cols_[0].pcol_l_->rank_i ();
 349       if (idx < 0)
 350         continue;
 351
 352       if (cols_[idx].pcol_l_ != cr.other_l_)
 353         continue;
 354       connect (idx, this_rank, cr.distance_f_, cr.strength_f_);
 355     }
 356
 357   cols_.push (c);
 358 }
 359
 360
 361 void
 362 Spring_spacer::add_columns (Link_array<Paper_column> cols)
 363 {
 364   energy_normalisation_f_  = sqr (line_len_f_);
 365   add_column (cols[0], true, 0.0);
 366   for (int i=1; i< cols.size ()-1; i++)
 367     add_column (cols[i],false,0.0);
 368
 369   if (line_len_f_ > 0)
 370     add_column (cols.top (), true, line_len_f_);
 371   else
 372     add_column (cols.top (), false, 0);
 373 }
 374
 375
 376
 377 void
 378 Spring_spacer::print() const
 379 {
 380 #ifndef NPRINT
 381   for (int i=0; i < cols_.size(); i++)
 382     {
 383       DOUT << "col " << i << " ";
 384       cols_[i].print();
 385     }
 386
 387   for (Cons<Idealspacing> *p =ideal_p_list_; p; p = p->next_)
 388     {
 389       p->car_->print();
 390     }
 391 #endif
 392 }
 393
 394
 395 void
 396 Spring_spacer::connect (int i, int j, Real d, Real h)
 397 {
 398   if (d > 100 CM)
 399     {
 400       programming_error( _f ("Improbable distance: %f point, setting to 10 mm", d));
 401       d = 1 CM;
 402     }
 403   if(d < 0)
 404     {
 405       programming_error (_ ("Negative distance, setting to 10 mm"));
 406       d = 10 MM;
 407     }
 408
 409   assert(h >=0);
 410
 411   Idealspacing * s = new Idealspacing;
 412
 413   s->cols_drul_[LEFT] = i ;
 414   s->cols_drul_[RIGHT] = j;
 415   s->space_f_ = d;
 416   s->hooke_f_ = h;
 417
 418   ideal_p_list_ = new Killing_cons<Idealspacing> (s, ideal_p_list_);
 419 }
 420
 421 void
 422 Spring_spacer::prepare()
 423 {
 424   handle_loose_cols();
 425   print();
 426 }
 427
 428
 429 Spring_spacer::~Spring_spacer()
 430 {
 431   delete ideal_p_list_;
 432 }