2 spring-spacer.cc -- implement Spring_spacer
4 source file of the GNU LilyPond music typesetter
6 (c) 1996, 1997, 1998 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"
23 #include "main.hh" // experimental_fietsers
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++)
74 if (cols[i].fixed_b())
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++)
155 if (cols[i].fixed_b() &&
156 abs (cols[i].fixed_position() - v (i)) > COLFUDGE)
159 Array<Column_rod> &rods (cols[i].pcol_l_->minimal_dists_arr_drul_[RIGHT]);
160 for (int j =0; j < rods.size (); j++)
162 int delta_idx= rods[j].other_l_->rank_i () - cols[i].rank_i ();
163 if (i + delta_idx >= dim )
165 if (rods[j].other_l_ != cols[i + delta_idx].pcol_l_)
167 if (v (i + delta_idx) - v (i) < rods[j].distance_f_)
175 /** try to generate a solution which obeys the min distances and fixed positions
178 Spring_spacer::try_initial_solution() const
181 if (try_initial_solution_and_tell (v))
182 warning ("I'm too fat; call Oprah");
188 Spring_spacer::try_initial_solution_and_tell (Vector &v) const
191 bool succeeded = true;
192 Vector initsol (dim);
193 for (int i=0; i < dim; i++)
195 int first_rank = cols[0].rank_i ();
196 int last_rank = cols.top ().rank_i ();
198 Real min_x = i ? initsol (i-1) : 0.0;
199 for (int j=0; j < cols[i].pcol_l_->minimal_dists_arr_drul_[LEFT].size (); j++)
201 Column_rod cr (cols[i].pcol_l_->minimal_dists_arr_drul_[LEFT] [j]);
202 if (cr.other_l_->rank_i () < first_rank)
205 int idx = cr.other_l_->rank_i () - first_rank;
206 assert (i > idx && idx >= 0);
207 if (cr.other_l_->break_status_i_ != cols[idx].pcol_l_->break_status_i_ )
210 min_x = min_x >? (initsol (idx) + cr.distance_f_);
213 if (cols[i].fixed_b())
215 initsol (i)=cols[i].fixed_position();
216 if (initsol (i) < min_x )
230 // generate the matrices
232 Spring_spacer::make_matrices (Matrix &quad, Vector &lin, Real &c) const
238 for (PCursor<Idealspacing*> i (ideal_p_list_.top()); i.ok (); i++)
243 quad (r,r) += i->hooke_f_;
244 quad (r,l) -= i->hooke_f_;
245 quad (l,r) -= i->hooke_f_;
246 quad (l,l) += i->hooke_f_;
248 lin (r) -= i->space_f_*i->hooke_f_;
249 lin (l) += i->space_f_*i->hooke_f_;
251 c += sqr (i->space_f_);
256 Spring_spacer::set_fixed_cols (Mixed_qp &qp) const
258 for (int j=0; j < cols.size(); j++)
259 if (cols[j].fixed_b())
260 qp.add_fixed_var (j,cols[j].fixed_position());
263 // put the constraints into the LP problem
265 Spring_spacer::make_constraints (Mixed_qp& lp) const
268 int last_rank = cols.top ().pcol_l_->rank_i ();
270 for (int j=0; j < dim -1; j++)
272 Paper_column* lc = cols[j].pcol_l_;
273 int my_rank = lc->rank_i();
274 for (int i = 0; i < lc->minimal_dists_arr_drul_[RIGHT].size (); i++)
277 Column_rod & cr = lc->minimal_dists_arr_drul_[RIGHT][i];
278 int right_rank = cr.other_l_->rank_i ();
280 cout << "lr, rr, last = " << my_rank << ", " <<right_rank << ", " << last_rank << endl;
282 if (right_rank > last_rank)
285 int right_idx = right_rank - my_rank + j;
286 cout << "li, ri = " << j << "," << right_idx;
287 cout << "lr, rr = " << my_rank << ", " <<right_rank << endl;
291 lp.add_inequality_cons (c1, cr.distance_f_);
298 Spring_spacer::calculate_energy_f (Vector solution) const
301 for (PCursor<Idealspacing*> i (ideal_p_list_.top()); i.ok(); i++)
303 e += i->energy_f(solution(i->right_i_) - solution(i->left_i_));
309 Spring_spacer::lower_bound_solution (Col_hpositions*positions) const
311 Mixed_qp lp (cols.size());
312 make_matrices (lp.quad,lp.lin, lp.const_term);
315 Vector start (cols.size());
317 Vector solution_vec (lp.solve (start));
319 DOUT << "Lower bound sol: " << solution_vec;
320 positions->energy_f_ = calculate_energy_f (solution_vec);
321 positions->config = solution_vec;
322 positions->satisfies_constraints_b_ = check_constraints (solution_vec);
326 Spring_spacer::solve (Col_hpositions*positions) const
328 Vector solution_try (try_initial_solution());
330 if (check_constraints (solution_try))
332 Mixed_qp lp (cols.size());
333 make_matrices (lp.quad,lp.lin, lp.const_term);
334 make_constraints (lp);
337 Vector solution_vec (lp.solve (solution_try));
340 positions->satisfies_constraints_b_ = check_constraints (solution_vec);
341 if (!positions->satisfies_constraints_b_)
343 WARN << _("solution doesn't satisfy constraints.\n") ;
345 position_loose_cols (solution_vec);
346 positions->energy_f_ = calculate_energy_f (solution_vec);
347 positions->config = solution_vec;
348 positions->error_col_l_arr_ = error_pcol_l_arr();
352 positions->set_stupid_solution (solution_try);
357 add one column to the problem.
360 Spring_spacer::add_column (Paper_column *col, bool fixed, Real fixpos)
362 Colinfo c (col,(fixed)? &fixpos : 0);
364 c.rank_i_ = cols.top().rank_i_+1;
373 Spring_spacer::error_pcol_l_arr() const
375 Array<Paper_column*> retval;
376 for (int i=0; i< cols.size(); i++)
378 retval.push (cols[i].pcol_l_);
379 for (int i=0; i < loose_col_arr_.size(); i++)
381 retval.push (loose_col_arr_[i].pcol_l_);
387 Spring_spacer::loosen_column (int i)
389 Colinfo c=cols.get (i);
390 for (PCursor<Idealspacing*> j (ideal_p_list_.top()); j.ok (); j++)
392 if (j->left_i_ == i|| j->right_i_ == i)
400 for (; j < loose_col_arr_.size(); j++)
402 if (loose_col_arr_[j].rank_i_ > c.rank_i_)
405 loose_col_arr_.insert (c,j);
410 Spring_spacer::print() const
413 for (int i=0; i < cols.size(); i++)
415 DOUT << "col " << i<<' ';
418 for (PCursor<Idealspacing*> i (ideal_p_list_.top()); i.ok (); i++)
427 Spring_spacer::connect (int i, int j, Real d, Real h)
429 assert(d >= 0 && d <= 100 CM);
432 Idealspacing * s = new Idealspacing;
439 ideal_p_list_.bottom().add (s);
446 Spring_spacer::prepare()
454 Spring_spacer::constructor()
456 return new Spring_spacer;
462 get the shortest_playing running note at a time. */
464 Spring_spacer::get_ruling_durations(Array<Moment> &shortest_playing_arr,
465 Array<Moment> &context_shortest_arr)
467 for (int i=0; i < cols.size(); i++)
469 scol_l (i)->preprocess();
470 scol_l (i)->print ();
472 int start_context_i=0;
473 Moment context_shortest;
474 context_shortest.set_infinite (1);
475 context_shortest_arr.set_size(cols.size());
477 for (int i=0; i < cols.size(); i++)
479 Moment now = scol_l (i)->when();
480 Moment shortest_playing;
481 shortest_playing.set_infinite (1);
483 if (scol_l (i)->breakable_b_)
485 for (int ji=i; ji >= start_context_i; ji--)
486 context_shortest_arr[ji] = context_shortest;
488 context_shortest.set_infinite (1);
490 if (scol_l (i)->durations.size())
492 context_shortest = context_shortest <? scol_l(i)->durations[0];
495 // ji was j, but triggered ICE
496 for (int ji=i+1; ji --;)
498 if (scol_l(ji)->durations.size() &&
499 now - scol_l(ji)->when() >= shortest_playing)
502 for (int k = scol_l (ji)->durations.size();
503 k-- && scol_l(ji)->durations[k] + scol_l(ji)->when() > now;
506 shortest_playing = shortest_playing <? scol_l(ji)->durations[k];
509 shortest_playing_arr.push(shortest_playing);
513 DOUT << "shortest_playing/:[ ";
514 for (int i=0; i < shortest_playing_arr.size(); i++)
516 DOUT << shortest_playing_arr[i] << " ";
517 DOUT << context_shortest_arr[i] << ", ";
524 generate springs between columns.
528 TODO: This needs rethinking. Spacing should take optical
529 effects into account, and should be local (measure wide)
531 The algorithm is taken from :
533 John S. Gourlay. ``Spacing a Line of Music,'' Technical Report
534 OSU-CISRC-10/87-TR35, Department of Computer and Information
535 Science, The Ohio State University, 1987.
539 Spring_spacer::calc_idealspacing()
541 Array<Moment> shortest_playing_arr;
542 Array<Moment> context_shortest_arr;
543 get_ruling_durations(shortest_playing_arr, context_shortest_arr);
545 Real interline_f = paper_l ()->interline_f ();
546 Real nw_f = paper_l ()->note_width ();
548 Array<Real> ideal_arr_;
549 Array<Real> hooke_arr_;
550 for (int i=0; i < cols.size() - 1; i++){
551 ideal_arr_.push (-1.0);
552 hooke_arr_.push (1.0);
556 First do all non-musical columns
558 for (int i=0; i < cols.size(); i++)
560 if (!scol_l (i)->musical_b() && i+1 < cols.size())
562 Real symbol_distance =cols[i].width_[RIGHT] + 2 PT;
563 Real durational_distance = 0;
566 Moment delta_t = scol_l (i+1)->when() - scol_l (i)->when () ;
568 Real k= paper_l()->arithmetic_constant(context_shortest_arr[i]);
570 ugh should use shortest_playing distance
573 durational_distance = paper_l()->duration_to_dist (delta_t,k);
574 symbol_distance += -cols[i+1].width_[LEFT];
577 ideal_arr_[i] = symbol_distance >? durational_distance;
578 hooke_arr_[i] = 1; //2.0;
585 for (int i=0; i < cols.size(); i++)
587 if (scol_l (i)->musical_b())
589 Moment shortest_playing_len = shortest_playing_arr[i];
590 Moment context_shortest = context_shortest_arr[i];
591 if (! shortest_playing_len)
593 warning (_("Can't find a ruling note at ")
594 +scol_l (i)->when().str ());
595 shortest_playing_len = 1;
597 if (! context_shortest)
599 warning(_("No minimum in measure at ")
600 + scol_l (i)->when().str ());
601 context_shortest = 1;
603 Moment delta_t = scol_l (i+1)->when() - scol_l (i)->when ();
604 Real k= paper_l()->arithmetic_constant(context_shortest);
605 Real dist = paper_l()->duration_to_dist (shortest_playing_len, k);
606 dist *= delta_t / shortest_playing_len;
609 According to [Ross] and [Wanske], and from what i've seen:
611 * whitespace at the begin of the bar should be fixed at
612 (about) one interline.
614 when spacing gets real tight, a smaller fixed value may be
615 used, so that there are two discrete amounts of whitespace
616 possible at the begin of a bar; but this is not implemented
619 * whitespace at the end of the bar is the normal amount of
620 "hinterfleish" that would have been used, had there been
621 yet another note in the bar.
623 some editors argue that the bar line should not take any
624 space, not to hinder the flow of music spaced around a bar
626 [Ross] and [Wanske] do not suggest this, however. Further,
627 it introduces some spacing problems and think that it is ugly
633 first musical column of bar
635 if (i && scol_l (i - 1)->breakable_b_)
637 // fixed: probably should set minimum (rod/spring)?
638 cols[i-1].width_[RIGHT] += interline_f;
639 // should adjust dist too?
640 ideal_arr_[i-1] = ideal_arr_[i-1] >? interline_f;
644 last musical column of bar
646 if (i + 1 < cols.size () && scol_l(i+1)->breakable_b_)
649 dist = dist >? interline_f;
652 uhuh, this code looks fine, already?
653 someone was junking this last "hinterfleisch" whitespace?!
655 but this seems to be fixed now :-)
658 cols[i].width_[RIGHT] += interline_f;
661 // ugh, do we need this?
662 if (i < cols.size () - 1 && !scol_l (i + 1)->musical_b ())
664 Real minimum = -cols[i + 1].width_[LEFT] + cols[i].width_[RIGHT]
666 dist = dist >? minimum;
669 // ugh: never let columns touch... try to set over here...
670 // ugh: use j iso i triggers ice in gcc-2.7.2.3
671 cols[i].width_[LEFT] -= nw_f / 4;
672 ideal_arr_[i] = dist;
676 for (int i=0; i < ideal_arr_.size(); i++)
678 assert (ideal_arr_[i] >=0 && hooke_arr_[i] >=0);
679 connect (i, i+1, ideal_arr_[i], hooke_arr_[i]);