2 spring-spacer.cc -- implement Spring_spacer
4 source file of the GNU LilyPond music typesetter
6 (c) 1996--1999 Han-Wen Nienhuys <hanwen@cs.uu.nl>
12 #include "killing-cons.tcc"
13 #include "spring-spacer.hh"
16 #include "dimensions.hh"
18 #include "unionfind.hh"
19 #include "idealspacing.hh"
20 #include "pointer.tcc"
21 #include "score-column.hh"
22 #include "paper-def.hh"
27 Spring_spacer::default_solution() const
29 return try_initial_solution();
33 Spring_spacer::scol_l (int i)
35 return dynamic_cast<Score_column*>(cols_[i].pcol_l_);
38 const Real COLFUDGE=1e-3;
39 template class P<Real>; // ugh.
42 Spring_spacer::contains_b (Paper_column const *w)
44 for (int i=0; i< cols_.size(); i++)
45 if (cols_[i].pcol_l_ == w)
52 Spring_spacer::OK() const
55 for (int i = 1; i < cols_.size(); i++)
56 assert (cols_[i].rank_i_ > cols_[i-1].rank_i_);
57 for (int i = 1; i < loose_col_arr_.size(); i++)
58 assert (loose_col_arr_[i].rank_i_ > loose_col_arr_[i-1].rank_i_);
63 Make sure no unconnected columns happen.
66 Spring_spacer::handle_loose_cols()
68 Union_find connected (cols_.size());
71 for (Cons<Idealspacing> *i = ideal_p_list_; i; i = i->next_)
73 connected.connect (i->car_->cols_drul_[LEFT],i->car_->cols_drul_[RIGHT]);
75 for (int i = 0; i < cols_.size(); i++)
76 if (cols_[i].fixed_b())
78 for (int i=1; i < fixed.size(); i++)
79 connected.connect (fixed[i-1], fixed[i]);
81 for (int i = cols_.size(); i--;)
83 if (! connected.equiv (fixed[0], i))
85 warning (_f ("unconnected column: %d", i));
94 Guess a stupid position for loose columns. Put loose columns at
95 regular distances from enclosing calced columns
98 Spring_spacer::position_loose_cols (Vector &sol_vec) const
100 if (!loose_col_arr_.size())
102 assert (sol_vec.dim());
103 Array<bool> fix_b_arr;
104 fix_b_arr.set_size (cols_.size() + loose_col_arr_.size ());
105 Real utter_right_f=-infinity_f;
106 Real utter_left_f =infinity_f;
107 for (int i=0; i < loose_col_arr_.size(); i++)
109 fix_b_arr[loose_col_arr_[i].rank_i_] = false;
111 for (int i=0; i < cols_.size(); i++)
113 int r= cols_[i].rank_i_;
115 utter_right_f = utter_right_f >? sol_vec (i);
116 utter_left_f = utter_left_f <? sol_vec (i);
118 Vector v (fix_b_arr.size());
121 for (int i=0; i < v.dim(); i++)
125 assert (cols_[j].rank_i_ == i);
126 v (i) = sol_vec (j++);
131 (j>0) ?sol_vec (j-1) : utter_left_f;
133 (j < sol_vec.dim()) ? sol_vec (j) : utter_right_f;
134 int left_rank = (j>0) ? cols_[j-1].rank_i_ : 0;
135 int right_rank = (j<sol_vec.dim()) ? cols_[j].rank_i_ : sol_vec.dim ();
137 int d_r = right_rank - left_rank;
138 Column_info loose=loose_col_arr_[k++];
139 int r = loose.rank_i_ ;
140 assert (r > left_rank && r < right_rank);
142 v (i) = (r - left_rank)*left_pos_f/ d_r +
143 (right_rank - r) *right_pos_f /d_r;
150 Spring_spacer::check_constraints (Vector v) const
153 assert (dim == cols_.size());
154 DOUT << "checking " << v;
155 for (int i=0; i < dim; i++)
157 if (cols_[i].fixed_b() &&
158 abs (cols_[i].fixed_position() - v (i)) > COLFUDGE)
160 DOUT << "Fixpos broken\n";
163 Array<Spacer_rod> const &rods (cols_[i].rods_[RIGHT]);
164 for (int j =0; j < rods.size (); j++)
166 int other =rods[j].other_idx_;
167 Real diff =v (other) - v (i) ;
168 if (COLFUDGE +diff < rods[j].distance_f_)
170 DOUT << "i, other_i: " << i << " " << other << '\n';
171 DOUT << "dist, minimal = " << diff << " "
172 << rods[j].distance_f_ << '\n';
181 /** try to generate a solution which obeys the min
182 distances and fixed positions
185 Spring_spacer::try_initial_solution() const
188 if (!try_initial_solution_and_tell (v))
190 warning (_ ("I'm too fat; call Oprah"));
197 Spring_spacer::try_initial_solution_and_tell (Vector &v) const
199 int dim=cols_.size();
200 bool succeeded = true;
201 Vector initsol (dim);
203 assert (cols_[0].fixed_b ());
204 DOUT << "fixpos 0 " << cols_[0].fixed_position ();
205 for (int i=0; i < dim; i++)
207 Real min_x = i ? initsol (i-1) : cols_[0].fixed_position ();
208 Array<Spacer_rod> const &sr_arr(cols_[i].rods_[LEFT]);
209 for (int j=0; j < sr_arr.size (); j++)
211 min_x = min_x >? (initsol (sr_arr[j].other_idx_) + sr_arr[j].distance_f_);
215 if (cols_[i].fixed_b())
217 initsol (i)=cols_[i].fixed_position();
218 if (initsol (i) < min_x )
220 DOUT << "failing: init, min : " << initsol (i) << " " << min_x << '\n';
228 DOUT << "tried and told solution: " << v;
230 DOUT << "(failed)\n";
236 // generate the matrices
238 Spring_spacer::make_matrices (Matrix &quad, Vector &lin, Real &c) const
244 for (Cons<Idealspacing> *p =ideal_p_list_; p; p = p->next_)
246 Idealspacing *i = p->car_;
247 int l = i->cols_drul_[LEFT];
248 int r = i->cols_drul_[RIGHT];
250 quad (r,r) += i->hooke_f_;
251 quad (r,l) -= i->hooke_f_;
252 quad (l,r) -= i->hooke_f_;
253 quad (l,l) += i->hooke_f_;
255 lin (r) -= i->space_f_*i->hooke_f_;
256 lin (l) += i->space_f_*i->hooke_f_;
258 c += sqr (i->space_f_);
268 Spring_spacer::set_fixed_cols (Mixed_qp &qp) const
270 for (int j=0; j < cols_.size(); j++)
271 if (cols_[j].fixed_b())
272 qp.add_fixed_var (j,cols_[j].fixed_position());
275 // put the constraints into the LP problem
277 Spring_spacer::make_constraints (Mixed_qp& lp) const
279 int dim=cols_.size();
281 for (int j=0; j < dim -1; j++)
283 Array<Spacer_rod> const&rod_arr (cols_[j].rods_[RIGHT]);
284 for (int i = 0; i < rod_arr.size (); i++)
287 c1(rod_arr[i].other_idx_)=1.0 ;
290 lp.add_inequality_cons (c1, rod_arr[i].distance_f_);
297 Spring_spacer::calculate_energy_f (Vector solution) const
300 for (Cons<Idealspacing>*p =ideal_p_list_; p; p = p->next_)
302 Idealspacing * i = p->car_;
303 e += i->energy_f(solution(i->cols_drul_[RIGHT]) - solution(i->cols_drul_[LEFT]));
309 Spring_spacer::lower_bound_solution (Column_x_positions*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);
325 Spring_spacer::Spring_spacer ()
328 energy_normalisation_f_ = 1.0;
332 Spring_spacer::solve (Column_x_positions*positions) const
334 DOUT << "Spring_spacer::solve ()...";
338 bool constraint_satisfaction = try_initial_solution_and_tell (solution_try);
339 if (constraint_satisfaction)
341 Mixed_qp lp (cols_.size());
342 make_matrices (lp.quad_,lp.lin_, lp.const_term_);
343 make_constraints (lp);
346 Vector solution_vec (lp.solve (solution_try));
348 positions->satisfies_constraints_b_ = check_constraints (solution_vec);
349 if (!positions->satisfies_constraints_b_)
351 WARN << _ ("solution doesn't satisfy constraints") << '\n' ;
353 position_loose_cols (solution_vec);
354 positions->energy_f_ = calculate_energy_f (solution_vec);
355 positions->config = solution_vec;
356 positions->error_col_l_arr_ = error_pcol_l_arr();
360 positions->set_stupid_solution (solution_try);
363 DOUT << "Finished Spring_spacer::solve ()...";
367 add one column to the problem.
370 Spring_spacer::add_column (Paper_column *col, bool fixed, Real fixpos)
372 Column_info c (col,(fixed)? &fixpos : 0);
373 int this_rank = cols_.size();
374 c.rank_i_ = this_rank;
376 for (int i=0; i < col->minimal_dists_arr_drul_[LEFT].size (); i++)
378 Column_rod &cr = col->minimal_dists_arr_drul_[LEFT][i];
379 int left_idx = cr.other_l_->rank_i () - cols_[0].pcol_l_->rank_i ();
383 if (cols_[left_idx].pcol_l_ != cr.other_l_)
387 l_rod.distance_f_ = cr.distance_f_;
388 l_rod.other_idx_ = left_idx;
389 c.rods_[LEFT].push (l_rod);
392 r_rod.distance_f_ = cr.distance_f_;
393 r_rod.other_idx_ = this_rank;
394 cols_[left_idx].rods_[RIGHT].push (r_rod);
397 if (experimental_features_global_b)
399 for (int i=0; i < col->spring_arr_drul_[LEFT].size (); i++)
401 Column_spring &cr = col->spring_arr_drul_[LEFT][i];
402 int idx = cr.other_l_->rank_i () - cols_[0].pcol_l_->rank_i ();
406 if (cols_[idx].pcol_l_ != cr.other_l_)
410 connect (idx, this_rank, cr.distance_f_,
411 cr.strength_f_ / cr.distance_f_);
420 Spring_spacer::error_pcol_l_arr() const
422 Link_array<Paper_column> retval;
423 for (int i=0; i< cols_.size(); i++)
425 retval.push (cols_[i].pcol_l_);
426 for (int i=0; i < loose_col_arr_.size(); i++)
428 retval.push (loose_col_arr_[i].pcol_l_);
433 Ugh. Should junk this.
436 Spring_spacer::loosen_column (int idx)
438 Column_info c=cols_.get (idx);
440 Cons<Idealspacing> **pp = &ideal_p_list_;
444 Idealspacing *j = (*pp)->car_;
445 if (j->cols_drul_[LEFT] == idx|| j->cols_drul_[RIGHT] == idx)
447 delete remove_cons (pp);
457 for (; j < loose_col_arr_.size(); j++)
459 if (loose_col_arr_[j].rank_i_ > c.rank_i_)
462 loose_col_arr_.insert (c,j);
467 Spring_spacer::print() const
470 for (int i=0; i < cols_.size(); i++)
472 DOUT << "col " << i << " ";
476 for (Cons<Idealspacing> *p =ideal_p_list_; p; p = p->next_)
485 Spring_spacer::connect (int i, int j, Real d, Real h)
487 assert(d >= 0 && d <= 100 CM);
490 Idealspacing * s = new Idealspacing;
492 s->cols_drul_[LEFT] = i ;
493 s->cols_drul_[RIGHT] = j;
497 ideal_p_list_ = new Killing_cons<Idealspacing> (s, ideal_p_list_);
501 Spring_spacer::prepare()
503 if (!experimental_features_global_b)
510 Spring_spacer::constructor()
512 return new Spring_spacer;
518 get the shortest_playing running note at a time. */
520 Spring_spacer::get_ruling_durations(Array<Moment> &context_shortest_arr)
522 for (int i=0; i < cols_.size(); i++)
524 scol_l (i)->preprocess();
525 scol_l (i)->print ();
527 int start_context_i=0;
528 Moment context_shortest;
529 context_shortest.set_infinite (1);
530 context_shortest_arr.set_size(cols_.size());
532 for (int i=0; i < cols_.size(); i++)
534 Score_column * sc = scol_l(i);
536 if (sc->breakable_b () || sc->break_status_dir ())
538 for (int ji=i; ji >= start_context_i; ji--)
539 context_shortest_arr[ji] = context_shortest;
541 context_shortest.set_infinite (1);
543 else if (sc->musical_b ())
544 context_shortest = context_shortest <? sc->shortest_starter_mom_;
548 DOUT << "context shortest :[ ";
549 for (int i=0; i < context_shortest_arr.size(); i++)
551 DOUT << context_shortest_arr[i] << ", ";
558 TODO: take out the refs to width
562 generate springs between columns.
564 TODO: This needs rethinking.......
566 * Spacing should take optical effects into account
568 * Should be decentralised
570 The algorithm is taken from :
572 John S. Gourlay. ``Spacing a Line of Music,'' Technical Report
573 OSU-CISRC-10/87-TR35, Department of Computer and Information
574 Science, The Ohio State University, 1987.
578 Spring_spacer::calc_idealspacing()
580 Array<Moment> context_shortest_arr;
581 get_ruling_durations(context_shortest_arr);
583 Real interline_f = paper_l ()->get_realvar (interline_scm_sym);
585 Array<Real> ideal_arr;
586 Array<Real> hooke_arr;
587 for (int i=0; i < cols_.size() - 1; i++){
588 ideal_arr.push (-1.0);
589 hooke_arr.push (1.0);
593 First do all non-musical columns
595 for (int i=0; i < cols_.size(); i++)
597 if (!scol_l (i)->musical_b() && i+1 < cols_.size())
599 Real symbol_distance =cols_[i].width_[RIGHT] + 2 PT;
600 Real durational_distance = 0;
601 Moment delta_t = scol_l (i+1)->when_mom () - scol_l (i)->when_mom () ;
604 ugh should use shortest_playing distance
608 Real k= paper_l()->arithmetic_constant (context_shortest_arr[i]);
609 durational_distance = paper_l()->length_mom_to_dist (delta_t,k);
611 symbol_distance += -cols_[i+1].width_[LEFT];
614 ideal_arr[i] = symbol_distance >? durational_distance;
615 hooke_arr[i] = 1; //2.0;
622 for (int i=0; i < cols_.size(); i++)
624 if (scol_l (i)->musical_b())
626 Moment shortest_playing_len = scol_l(i)->shortest_playing_mom_;
627 Moment context_shortest = context_shortest_arr[i];
628 if (! shortest_playing_len)
630 warning (_f ("can't find a ruling note at %s",
631 scol_l (i)->when_mom ().str ()));
632 shortest_playing_len = 1;
634 if (! context_shortest)
636 warning (_f ("no minimum in measure at %s",
637 scol_l (i)->when_mom ().str ()));
638 context_shortest = 1;
640 Moment delta_t = scol_l (i+1)->when_mom () - scol_l (i)->when_mom ();
641 Real k= paper_l()->arithmetic_constant(context_shortest);
642 Real dist = paper_l()->length_mom_to_dist (shortest_playing_len, k);
643 dist *= (double)(delta_t / shortest_playing_len);
646 According to [Ross] and [Wanske], and from what i've seen:
648 * whitespace at the begin of the bar should be fixed at
649 (about) one interline.
652 when spacing gets real tight, a smaller fixed value may be
653 used, so that there are two discrete amounts of whitespace
654 possible at the begin of a bar; but this is not implemented
657 * whitespace at the end of the bar is the normal amount of
658 "hinterfleish" that would have been used, had there been
659 yet another note in the bar.
662 some editors argue that the bar line should not take any
663 space, not to hinder the flow of music spaced around a bar
666 [Ross] and [Wanske] do not suggest this, however. Further,
667 it introduces some spacing problems and I think that it is ugly
674 first musical column of bar
676 if (i && !scol_l (i - 1)->musical_b ())
678 // one interline minimum at start of bar
680 // cols_[i].width_[RIGHT] += interline_f;
681 cols_[i].width_[RIGHT] = cols_[i].width_[RIGHT] >? interline_f;
683 // should adjust dist too?
684 ideal_arr[i-1] = ideal_arr[i-1] >? (2 * interline_f);
688 last musical column of bar
690 if (i + 1 < cols_.size () && !scol_l(i+1)->musical_b ())
692 // two interline minimum ok for last column?
693 dist = dist >? 2 * interline_f;
697 urg: simply *adding* an interline leaves big gaps at
698 end of measure in star-spangled-banner (after lyrics
701 cols_[i].width_[RIGHT] += interline_f; // before
703 having a minimum of one interline solves this problem
704 in most (but not all??) cases.
706 for music without lyrics (esp. when set very tightly),
707 adding an interline looks good: probably because this
708 hides a bug that allows the last note's "hinterfleish"
709 to be removed (e.g., see wtk1-fugue2: that's ugly now).
713 cols_[i].width_[RIGHT] = cols_[i].width_[RIGHT] >? 2 * interline_f;
716 // ugh, do we need this?
717 if (i < cols_.size () - 1 && !scol_l (i + 1)->musical_b ())
719 Real minimum = -cols_[i + 1].width_[LEFT] + cols_[i].width_[RIGHT]
721 dist = dist >? minimum;
728 shorter distances should stretch less.
732 hooke[i] = 2 * max_ideal_space - ideal[i]
736 for (int i=0; i < ideal_arr.size(); i++)
737 hooke_arr[i] = 1/ideal_arr[i];
739 for (int i=0; i < ideal_arr.size(); i++)
741 assert (ideal_arr[i] >=0 && hooke_arr[i] >=0);
742 connect (i, i+1, ideal_arr[i], hooke_arr[i]);