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 = paper_l ()->get_var ("loose_column_distance");
  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
 263   DOUT << "Lower bound sol: " << solution_vec;
 264   positions->energy_f_ = calculate_energy_f (solution_vec);
 265   positions->config_ = solution_vec;
 266   positions->satisfies_constraints_b_ = check_constraints (solution_vec);
 267 }
 268
 269 Spring_spacer::Spring_spacer ()
 270 {
 271   ideal_p_list_ =0;
 272   energy_normalisation_f_ = 1.0;
 273 }
 274
 275 void
 276 Spring_spacer::solve (Column_x_positions*positions) const
 277 {
 278   DOUT << "Spring_spacer::solve ()...";
 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       Vector solution_vec (lp.solve (solution_try));
 291
 292       positions->satisfies_constraints_b_ = check_constraints (solution_vec);
 293       if (!positions->satisfies_constraints_b_)
 294         {
 295           WARN << _ ("solution doesn't satisfy constraints") << '\n' ;
 296         }
 297       positions->energy_f_ = calculate_energy_f (solution_vec);
 298       positions->config_ = solution_vec;
 299     }
 300   else
 301     {
 302       positions->set_stupid_solution (solution_try);
 303     }
 304
 305   DOUT << "Finished Spring_spacer::solve ()...";
 306 }
 307
 308 /**
 309   add one column to the problem.
 310 */
 311 void
 312 Spring_spacer::add_column (Paper_column  *col, bool fixed, Real fixpos)
 313 {
 314   Column_info c (col,(fixed)? &fixpos :  0);
 315   int this_rank =  cols_.size();
 316   c.rank_i_ = this_rank;
 317
 318   for (int i=0; i < col->minimal_dists_arr_drul_[LEFT].size (); i++)
 319     {
 320       Column_rod &cr = col->minimal_dists_arr_drul_[LEFT][i];
 321       int left_idx = cr.other_l_->rank_i () - cols_[0].pcol_l_->rank_i ();
 322       if (left_idx < 0)
 323         continue;
 324
 325       if (cols_[left_idx].pcol_l_ != cr.other_l_)
 326         continue;
 327
 328       Spacer_rod l_rod;
 329       l_rod.distance_f_ = cr.distance_f_;
 330       l_rod.other_idx_ = left_idx;
 331       c.rods_[LEFT].push (l_rod);
 332
 333       Spacer_rod r_rod;
 334       r_rod.distance_f_ = cr.distance_f_;
 335       r_rod.other_idx_ = this_rank;
 336       cols_[left_idx].rods_[RIGHT].push (r_rod);
 337     }
 338
 339   for (int i=0; i < col->spring_arr_drul_[LEFT].size (); i++)
 340     {
 341       Column_spring &cr = col->spring_arr_drul_[LEFT][i];
 342       int idx = cr.other_l_->rank_i () - cols_[0].pcol_l_->rank_i ();
 343       if (idx < 0)
 344         continue;
 345
 346       if (cols_[idx].pcol_l_ != cr.other_l_)
 347         continue;
 348       connect (idx, this_rank, cr.distance_f_, cr.strength_f_);
 349     }
 350
 351   cols_.push (c);
 352 }
 353
 354
 355 void
 356 Spring_spacer::print() const
 357 {
 358 #ifndef NPRINT
 359   for (int i=0; i < cols_.size(); i++)
 360     {
 361       DOUT << "col " << i << " ";
 362       cols_[i].print();
 363     }
 364
 365   for (Cons<Idealspacing> *p =ideal_p_list_; p; p = p->next_)
 366     {
 367       p->car_->print();
 368     }
 369 #endif
 370 }
 371
 372
 373 void
 374 Spring_spacer::connect (int i, int j, Real d, Real h)
 375 {
 376   if (d > 100 CM)
 377     {
 378       programming_error( _f("Improbable distance: %f point, setting to 10 mm", d));
 379       d = 1 CM;
 380     }
 381   if(d < 0)
 382     {
 383       programming_error (_("Negative distance. Setting to 10 mm"));
 384       d = 10 MM;
 385     }
 386
 387   assert(h >=0);
 388
 389   Idealspacing * s = new Idealspacing;
 390
 391   s->cols_drul_[LEFT] = i ;
 392   s->cols_drul_[RIGHT] = j;
 393   s->space_f_ = d;
 394   s->hooke_f_ = h;
 395
 396   ideal_p_list_ = new Killing_cons<Idealspacing> (s, ideal_p_list_);
 397 }
 398
 399 void
 400 Spring_spacer::prepare()
 401 {
 402   handle_loose_cols();
 403   print();
 404 }
 405
 406 Line_spacer*
 407 Spring_spacer::constructor()
 408 {
 409   return new Spring_spacer;
 410 }
 411
 412
 413
 414
 415 Spring_spacer::~Spring_spacer()
 416 {
 417   delete ideal_p_list_;
 418 }