2 spring-spacer.cc -- implement Spring_spacer
4 source file of the GNU LilyPond music typesetter
6 (c) 1996,1997 Han-Wen Nienhuys <hanwen@stack.nl>
12 #include "spring-spacer.hh"
16 #include "unionfind.hh"
17 #include "idealspacing.hh"
18 #include "pointer.tcc"
19 #include "score-column.hh"
20 #include "paper-def.hh"
26 Spring_spacer::default_solution() const
28 return try_initial_solution() ;
32 Spring_spacer::scol_l (int i)
34 return (Score_column*)cols[i].pcol_l_;
37 const Real COLFUDGE=1e-3;
38 template class P<Real>; // ugh.
41 Spring_spacer::contains (Paper_column const *w)
43 for (int i=0; i< cols.size(); i++)
44 if (cols[i].pcol_l_ == w)
51 Spring_spacer::OK() const
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_);
62 Make sure no unconnected columns happen.
65 Spring_spacer::handle_loose_cols()
67 Union_find connected (cols.size());
69 for (PCursor<Idealspacing*> i (ideal_p_list_.top()); i.ok (); i++)
71 connected.connect (i->left_i_,i->right_i_);
73 for (int i = 0; i < cols.size(); i++)
76 for (int i=1; i < fixed.size(); i++)
77 connected.connect (fixed[i-1], fixed[i]);
79 for (int i = cols.size(); i--;)
81 if (! connected.equiv (fixed[0], i))
83 warning ("unconnected column: " + String (i));
92 Guess a stupid position for loose columns. Put loose columns at
93 regular distances from enclosing calced columns
96 Spring_spacer::position_loose_cols (Vector &sol_vec) const
98 if (!loose_col_arr_.size())
100 assert (sol_vec.dim());
101 Array<bool> fix_b_arr;
102 fix_b_arr.set_size (cols.size() + loose_col_arr_.size ());
103 Real utter_right_f=-infinity_f;
104 Real utter_left_f =infinity_f;
105 for (int i=0; i < loose_col_arr_.size(); i++)
107 fix_b_arr[loose_col_arr_[i].rank_i_] = false;
109 for (int i=0; i < cols.size(); i++)
111 int r= cols[i].rank_i_;
113 utter_right_f = utter_right_f >? sol_vec (i);
114 utter_left_f = utter_left_f <? sol_vec (i);
116 Vector v (fix_b_arr.size());
119 for (int i=0; i < v.dim(); i++)
123 assert (cols[j].rank_i_ == i);
124 v (i) = sol_vec (j++);
129 (j>0) ?sol_vec (j-1) : utter_left_f;
131 (j < sol_vec.dim()) ? sol_vec (j) : utter_right_f;
132 int left_rank = (j>0) ? cols[j-1].rank_i_ : 0;
133 int right_rank = (j<sol_vec.dim()) ? cols[j].rank_i_ : sol_vec.dim ();
135 int d_r = right_rank - left_rank;
136 Colinfo loose=loose_col_arr_[k++];
137 int r = loose.rank_i_ ;
138 assert (r > left_rank && r < right_rank);
140 v (i) = (r - left_rank)*left_pos_f/ d_r +
141 (right_rank - r) *right_pos_f /d_r;
148 Spring_spacer::check_constraints (Vector v) const
151 assert (dim == cols.size());
153 for (int i=0; i < dim; i++)
156 if (cols[i].fixed()&&
157 abs (cols[i].fixed_position() - v (i)) > COLFUDGE)
163 Real mindist=cols[i-1].minright()
167 Real dif =v (i) - v (i-1)- mindist;
168 bool b = (dif > - COLFUDGE);
179 Spring_spacer::check_feasible() const
181 Vector sol (try_initial_solution());
182 return check_constraints (sol);
185 /// generate a solution which obeys the min distances and fixed positions
187 Spring_spacer::try_initial_solution() const
190 Vector initsol (dim);
191 for (int i=0; i < dim; i++)
195 initsol (i)=cols[i].fixed_position();
199 Real r =initsol (i-1) + cols[i-1].minright();
202 warning ("overriding fixed position");
210 Real mindist=cols[i-1].minright()
213 warning ("Excentric column");
214 initsol (i)=initsol (i-1)+mindist;
224 Spring_spacer::find_initial_solution() const
226 Vector v (try_initial_solution());
227 assert (check_constraints (v));
231 // generate the matrices
233 Spring_spacer::make_matrices (Matrix &quad, Vector &lin, Real &c) const
239 for (PCursor<Idealspacing*> i (ideal_p_list_.top()); i.ok (); i++)
244 quad (r,r) += i->hooke_f_;
245 quad (r,l) -= i->hooke_f_;
246 quad (l,r) -= i->hooke_f_;
247 quad (l,l) += i->hooke_f_;
249 lin (r) -= i->space_f_*i->hooke_f_;
250 lin (l) += i->space_f_*i->hooke_f_;
252 c += sqr (i->space_f_);
257 Spring_spacer::set_fixed_cols (Mixed_qp &qp) const
259 for (int j=0; j < cols.size(); j++)
261 qp.add_fixed_var (j,cols[j].fixed_position());
266 // put the constraints into the LP problem
268 Spring_spacer::make_constraints (Mixed_qp& lp) const
271 for (int j=0; j < dim; j++)
280 lp.add_inequality_cons (c1, cols[j-1].minright() +
287 Spring_spacer::lower_bound_solution (Col_hpositions*positions) const
289 Mixed_qp lp (cols.size());
290 make_matrices (lp.quad,lp.lin, lp.const_term);
293 Vector start (cols.size());
295 Vector solution_vec (lp.solve (start));
297 positions->energy_f_ = lp.eval (solution_vec);
298 positions->config = solution_vec;
299 positions->satisfies_constraints_b_ = check_constraints (solution_vec);
303 Spring_spacer::solve (Col_hpositions*positions) const
305 assert (check_feasible());
307 Mixed_qp lp (cols.size());
308 make_matrices (lp.quad,lp.lin, lp.const_term);
309 make_constraints (lp);
311 Vector start=find_initial_solution();
312 Vector solution_vec (lp.solve (start));
315 positions->satisfies_constraints_b_ = check_constraints (solution_vec);
316 if (!positions->satisfies_constraints_b_)
318 WARN << "solution doesn't satisfy constraints.\n" ;
320 position_loose_cols (solution_vec);
321 positions->energy_f_ = lp.eval (solution_vec);
322 positions->config = solution_vec;
323 positions->error_col_l_arr_ = error_pcol_l_arr();
328 add one column to the problem.
331 Spring_spacer::add_column (Paper_column *col, bool fixed, Real fixpos)
333 Colinfo c (col,(fixed)? &fixpos : 0);
335 c.rank_i_ = cols.top().rank_i_+1;
342 Spring_spacer::error_pcol_l_arr() const
344 Array<Paper_column*> retval;
345 for (int i=0; i< cols.size(); i++)
347 retval.push (cols[i].pcol_l_);
348 for (int i=0; i < loose_col_arr_.size(); i++)
350 retval.push (loose_col_arr_[i].pcol_l_);
356 Spring_spacer::loosen_column (int i)
358 Colinfo c=cols.get (i);
359 for (PCursor<Idealspacing*> j (ideal_p_list_.top()); j.ok (); j++)
361 if (j->left_i_ == i|| j->right_i_ == i)
369 for (; j < loose_col_arr_.size(); j++)
371 if (loose_col_arr_[j].rank_i_ > c.rank_i_)
374 loose_col_arr_.insert (c,j);
379 Spring_spacer::print() const
382 for (int i=0; i < cols.size(); i++)
384 DOUT << "col " << i<<' ';
387 for (PCursor<Idealspacing*> i (ideal_p_list_.top()); i.ok (); i++)
396 Spring_spacer::connect (int i, int j, Real d, Real h)
398 assert(d >= 0 && d <= 100 CM);
401 Idealspacing * s = new Idealspacing;
407 ideal_p_list_.bottom().add (s);
414 Spring_spacer::prepare()
422 Spring_spacer::constructor()
424 return new Spring_spacer;
430 get the shortest_playing running note at a time. */
432 Spring_spacer::get_ruling_durations(Array<Moment> &shortest_playing_arr,
433 Array<Moment> &context_shortest_arr)
435 for (int i=0; i < cols.size(); i++)
436 scol_l (i)->preprocess();
438 int start_context_i=0;
439 Moment context_shortest = infinity_mom;
440 context_shortest_arr.set_size(cols.size());
442 for (int i=0; i < cols.size(); i++)
444 Moment now = scol_l (i)->when();
445 Moment shortest_playing = infinity_mom;
447 if (scol_l (i)->breakable_b_)
449 for (int ji=i; ji >= start_context_i; ji--)
450 context_shortest_arr[ji] = context_shortest;
452 context_shortest = infinity_mom;
454 if (scol_l (i)->durations.size())
456 context_shortest = context_shortest <? scol_l(i)->durations[0];
458 // ji was j, but triggered ICE
459 for (int ji=i+1; ji --;)
461 if (scol_l(ji)->durations.size() &&
462 now - scol_l(ji)->when() >= shortest_playing)
465 for (int k = scol_l (ji)->durations.size();
466 k-- && scol_l(ji)->durations[k] + scol_l(ji)->when() > now;
469 shortest_playing = shortest_playing <? scol_l(ji)->durations[k];
472 shortest_playing_arr.push(shortest_playing);
476 DOUT << "shortest_playing/:[ ";
477 for (int i=0; i < shortest_playing_arr.size(); i++)
479 DOUT << shortest_playing_arr[i] << " ";
480 DOUT << context_shortest_arr[i] << ", ";
487 generate springs between columns.
491 TODO: This needs rethinking. Spacing should take optical
492 effects into account, and should be local (measure wide)
494 The algorithm is taken from :
496 John S. Gourlay. ``Spacing a Line of Music,'' Technical Report
497 OSU-CISRC-10/87-TR35, Department of Computer and Information
498 Science, The Ohio State University, 1987.
502 Spring_spacer::calc_idealspacing()
504 Array<Moment> shortest_playing_arr;
505 Array<Moment> context_shortest_arr;
506 get_ruling_durations(shortest_playing_arr, context_shortest_arr);
509 Array<Real> ideal_arr_;
510 Array<Real> hooke_arr_;
511 for (int i=0; i < cols.size(); i++){
512 ideal_arr_.push (-1.0);
513 hooke_arr_.push (1.0);
516 for (int i=0; i < cols.size(); i++)
518 if (!scol_l (i)->musical_b())
520 Real symbol_distance =cols[i].minright() + 2 PT;
521 Real durational_distance = 0;
523 if (i+1 < cols.size())
525 Moment delta_t = scol_l (i+1)->when() - scol_l (i)->when () ;
527 Real k= paper_l()->arithmetic_constant(context_shortest_arr[i]);
529 ugh should use shortest_playing distance
532 durational_distance = paper_l()->duration_to_dist (delta_t,k);
533 symbol_distance += cols[i+1].minleft();
536 ideal_arr_[i] = symbol_distance >? durational_distance;
540 for (int i=0; i < cols.size(); i++)
542 if (scol_l (i)->musical_b())
544 Moment shortest_playing_len = shortest_playing_arr[i];
545 Moment context_shortest = context_shortest_arr[i];
546 if (! shortest_playing_len)
548 warning ("Can't find a ruling note at "
549 +String (scol_l (i)->when()));
550 shortest_playing_len = 1;
552 if (! context_shortest)
554 warning("No minimum in measure at "
555 + String (scol_l (i)->when()));
556 context_shortest = 1;
558 Moment delta_t = scol_l (i+1)->when() - scol_l (i)->when ();
559 Real k= paper_l()->arithmetic_constant(context_shortest);
560 Real dist = paper_l()->duration_to_dist (shortest_playing_len, k);
561 dist *= delta_t / shortest_playing_len;
563 /* all sorts of ugliness to avoid running into bars/clefs, but not taking
564 extra space if this is not needed */
565 if (!scol_l (i+1)->musical_b())
567 Real minimum_dist = cols[i+1].minleft() + 2 PT + cols[i].minright () ;
568 if (ideal_arr_[i+1] + minimum_dist < dist)
570 ideal_arr_[i] = dist - ideal_arr_[i+1];
571 // hooke_arr_[i+1] =1.0;
573 ideal_arr_[i] = minimum_dist;
577 ideal_arr_[i] = dist;
581 for (int i=0; i < ideal_arr_.size()-1; i++)
583 assert (ideal_arr_[i] >=0 && hooke_arr_[i] >=0);
584 connect (i, i+1, ideal_arr_[i], hooke_arr_[i]);