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 distances and fixed positions
184 Spring_spacer::try_initial_solution() const
187 if (!try_initial_solution_and_tell (v))
189 warning (_ ("I'm too fat; call Oprah"));
196 Spring_spacer::try_initial_solution_and_tell (Vector &v) const
198 int dim=cols_.size();
199 bool succeeded = true;
200 Vector initsol (dim);
202 assert (cols_[0].fixed_b ());
203 DOUT << "fixpos 0 " << cols_[0].fixed_position ();
204 for (int i=0; i < dim; i++)
206 Real min_x = i ? initsol (i-1) : cols_[0].fixed_position ();
207 Array<Spacer_rod> const &sr_arr(cols_[i].rods_[LEFT]);
208 for (int j=0; j < sr_arr.size (); j++)
210 min_x = min_x >? (initsol (sr_arr[j].other_idx_) + sr_arr[j].distance_f_);
214 if (cols_[i].fixed_b())
216 initsol (i)=cols_[i].fixed_position();
217 if (initsol (i) < min_x )
219 DOUT << "failing: init, min : " << initsol (i) << " " << min_x << '\n';
227 DOUT << "tried and told solution: " << v;
229 DOUT << "(failed)\n";
235 // generate the matrices
237 Spring_spacer::make_matrices (Matrix &quad, Vector &lin, Real &c) const
243 for (Cons<Idealspacing> *p =ideal_p_list_; p; p = p->next_)
245 Idealspacing *i = p->car_;
246 int l = i->cols_drul_[LEFT];
247 int r = i->cols_drul_[RIGHT];
249 quad (r,r) += i->hooke_f_;
250 quad (r,l) -= i->hooke_f_;
251 quad (l,r) -= i->hooke_f_;
252 quad (l,l) += i->hooke_f_;
254 lin (r) -= i->space_f_*i->hooke_f_;
255 lin (l) += i->space_f_*i->hooke_f_;
257 c += sqr (i->space_f_);
267 Spring_spacer::set_fixed_cols (Mixed_qp &qp) const
269 for (int j=0; j < cols_.size(); j++)
270 if (cols_[j].fixed_b())
271 qp.add_fixed_var (j,cols_[j].fixed_position());
274 // put the constraints into the LP problem
276 Spring_spacer::make_constraints (Mixed_qp& lp) const
278 int dim=cols_.size();
280 for (int j=0; j < dim -1; j++)
282 Array<Spacer_rod> const&rod_arr (cols_[j].rods_[RIGHT]);
283 for (int i = 0; i < rod_arr.size (); i++)
286 c1(rod_arr[i].other_idx_)=1.0 ;
289 lp.add_inequality_cons (c1, rod_arr[i].distance_f_);
296 Spring_spacer::calculate_energy_f (Vector solution) const
299 for (Cons<Idealspacing>*p =ideal_p_list_; p; p = p->next_)
301 Idealspacing * i = p->car_;
302 e += i->energy_f(solution(i->cols_drul_[RIGHT]) - solution(i->cols_drul_[LEFT]));
308 Spring_spacer::lower_bound_solution (Column_x_positions*positions) const
310 Mixed_qp lp (cols_.size());
311 make_matrices (lp.quad_,lp.lin_, lp.const_term_);
314 Vector start (cols_.size());
316 Vector solution_vec (lp.solve (start));
318 DOUT << "Lower bound sol: " << solution_vec;
319 positions->energy_f_ = calculate_energy_f (solution_vec);
320 positions->config = solution_vec;
321 positions->satisfies_constraints_b_ = check_constraints (solution_vec);
324 Spring_spacer::Spring_spacer ()
327 energy_normalisation_f_ = 1.0;
331 Spring_spacer::solve (Column_x_positions*positions) const
333 DOUT << "Spring_spacer::solve ()...";
337 bool constraint_satisfaction = try_initial_solution_and_tell (solution_try);
338 if (constraint_satisfaction)
340 Mixed_qp lp (cols_.size());
341 make_matrices (lp.quad_,lp.lin_, lp.const_term_);
342 make_constraints (lp);
345 Vector solution_vec (lp.solve (solution_try));
347 positions->satisfies_constraints_b_ = check_constraints (solution_vec);
348 if (!positions->satisfies_constraints_b_)
350 WARN << _ ("solution doesn't satisfy constraints") << '\n' ;
352 position_loose_cols (solution_vec);
353 positions->energy_f_ = calculate_energy_f (solution_vec);
354 positions->config = solution_vec;
355 positions->error_col_l_arr_ = error_pcol_l_arr();
359 positions->set_stupid_solution (solution_try);
362 DOUT << "Finished Spring_spacer::solve ()...";
366 add one column to the problem.
369 Spring_spacer::add_column (Paper_column *col, bool fixed, Real fixpos)
371 Column_info c (col,(fixed)? &fixpos : 0);
372 int this_rank = cols_.size();
373 c.rank_i_ = this_rank;
375 for (int i=0; i < col->minimal_dists_arr_drul_[LEFT].size (); i++)
377 Column_rod &cr = col->minimal_dists_arr_drul_[LEFT][i];
378 int left_idx = cr.other_l_->rank_i () - cols_[0].pcol_l_->rank_i ();
382 if (cols_[left_idx].pcol_l_ != cr.other_l_)
386 l_rod.distance_f_ = cr.distance_f_;
387 l_rod.other_idx_ = left_idx;
388 c.rods_[LEFT].push (l_rod);
391 r_rod.distance_f_ = cr.distance_f_;
392 r_rod.other_idx_ = this_rank;
393 cols_[left_idx].rods_[RIGHT].push (r_rod);
400 Spring_spacer::error_pcol_l_arr() const
402 Link_array<Paper_column> retval;
403 for (int i=0; i< cols_.size(); i++)
405 retval.push (cols_[i].pcol_l_);
406 for (int i=0; i < loose_col_arr_.size(); i++)
408 retval.push (loose_col_arr_[i].pcol_l_);
413 Ugh. Should junk this.
416 Spring_spacer::loosen_column (int idx)
418 Column_info c=cols_.get (idx);
420 Cons<Idealspacing> **pp = &ideal_p_list_;
424 Idealspacing *j = (*pp)->car_;
425 if (j->cols_drul_[LEFT] == idx|| j->cols_drul_[RIGHT] == idx)
427 delete remove_cons (pp);
437 for (; j < loose_col_arr_.size(); j++)
439 if (loose_col_arr_[j].rank_i_ > c.rank_i_)
442 loose_col_arr_.insert (c,j);
447 Spring_spacer::print() const
450 for (int i=0; i < cols_.size(); i++)
452 DOUT << "col " << i << " ";
456 for (Cons<Idealspacing> *p =ideal_p_list_; p; p = p->next_)
465 Spring_spacer::connect (int i, int j, Real d, Real h)
467 assert(d >= 0 && d <= 100 CM);
470 Idealspacing * s = new Idealspacing;
472 s->cols_drul_[LEFT] = i ;
473 s->cols_drul_[RIGHT] = j;
477 ideal_p_list_ = new Killing_cons<Idealspacing> (s, ideal_p_list_);
484 Spring_spacer::prepare()
486 DOUT << "Preparing..";
490 DOUT << "finished preparing.\n";
494 Spring_spacer::constructor()
496 return new Spring_spacer;
502 get the shortest_playing running note at a time. */
504 Spring_spacer::get_ruling_durations(Array<Moment> &shortest_playing_arr,
505 Array<Moment> &context_shortest_arr)
507 for (int i=0; i < cols_.size(); i++)
509 scol_l (i)->preprocess();
510 scol_l (i)->print ();
512 int start_context_i=0;
513 Moment context_shortest;
514 context_shortest.set_infinite (1);
515 context_shortest_arr.set_size(cols_.size());
517 for (int i=0; i < cols_.size(); i++)
519 Moment now = scol_l (i)->when();
520 Moment shortest_playing;
521 shortest_playing.set_infinite (1);
523 if (scol_l (i)->breakable_b_)
525 for (int ji=i; ji >= start_context_i; ji--)
526 context_shortest_arr[ji] = context_shortest;
528 context_shortest.set_infinite (1);
530 if (scol_l (i)->durations.size())
532 context_shortest = context_shortest <? scol_l(i)->durations[0];
535 // ji was j, but triggered ICE
536 for (int ji=i+1; ji --;)
538 if (scol_l(ji)->durations.size() &&
539 now - scol_l(ji)->when() >= shortest_playing)
542 for (int k = scol_l (ji)->durations.size();
543 k-- && scol_l(ji)->durations[k] + scol_l(ji)->when() > now;
546 shortest_playing = shortest_playing <? scol_l(ji)->durations[k];
549 shortest_playing_arr.push(shortest_playing);
553 DOUT << "shortest_playing/:[ ";
554 for (int i=0; i < shortest_playing_arr.size(); i++)
556 DOUT << shortest_playing_arr[i] << " ";
557 DOUT << context_shortest_arr[i] << ", ";
564 TODO: take out the refs to width
568 generate springs between columns.
570 TODO: This needs rethinking.......
572 * Spacing should take optical
575 * Should be decentralised
577 The algorithm is taken from :
579 John S. Gourlay. ``Spacing a Line of Music,'' Technical Report
580 OSU-CISRC-10/87-TR35, Department of Computer and Information
581 Science, The Ohio State University, 1987.
585 Spring_spacer::calc_idealspacing()
587 Array<Moment> shortest_playing_arr;
588 Array<Moment> context_shortest_arr;
589 get_ruling_durations(shortest_playing_arr, context_shortest_arr);
591 Real interline_f = paper_l ()->interline_f ();
594 Array<Real> ideal_arr;
595 Array<Real> hooke_arr;
596 for (int i=0; i < cols_.size() - 1; i++){
597 ideal_arr.push (-1.0);
598 hooke_arr.push (1.0);
602 First do all non-musical columns
604 for (int i=0; i < cols_.size(); i++)
606 if (!scol_l (i)->musical_b() && i+1 < cols_.size())
608 Real symbol_distance =cols_[i].width_[RIGHT] + 2 PT;
609 Real durational_distance = 0;
610 Moment delta_t = scol_l (i+1)->when() - scol_l (i)->when () ;
613 ugh should use shortest_playing distance
617 Real k= paper_l()->arithmetic_constant (context_shortest_arr[i]);
618 durational_distance = paper_l()->length_mom_to_dist (delta_t,k);
620 symbol_distance += -cols_[i+1].width_[LEFT];
623 ideal_arr[i] = symbol_distance >? durational_distance;
624 hooke_arr[i] = 1; //2.0;
631 for (int i=0; i < cols_.size(); i++)
633 if (scol_l (i)->musical_b())
635 Moment shortest_playing_len = shortest_playing_arr[i];
636 Moment context_shortest = context_shortest_arr[i];
637 if (! shortest_playing_len)
639 warning (_f ("can't find a ruling note at %s",
640 scol_l (i)->when().str ()));
641 shortest_playing_len = 1;
643 if (! context_shortest)
645 warning (_f ("no minimum in measure at %s",
646 scol_l (i)->when().str ()));
647 context_shortest = 1;
649 Moment delta_t = scol_l (i+1)->when() - scol_l (i)->when ();
650 Real k= paper_l()->arithmetic_constant(context_shortest);
651 Real dist = paper_l()->length_mom_to_dist (shortest_playing_len, k);
652 dist *= (double)(delta_t / shortest_playing_len);
655 According to [Ross] and [Wanske], and from what i've seen:
657 * whitespace at the begin of the bar should be fixed at
658 (about) one interline.
661 when spacing gets real tight, a smaller fixed value may be
662 used, so that there are two discrete amounts of whitespace
663 possible at the begin of a bar; but this is not implemented
666 * whitespace at the end of the bar is the normal amount of
667 "hinterfleish" that would have been used, had there been
668 yet another note in the bar.
671 some editors argue that the bar line should not take any
672 space, not to hinder the flow of music spaced around a bar
675 [Ross] and [Wanske] do not suggest this, however. Further,
676 it introduces some spacing problems and I think that it is ugly
683 first musical column of bar
685 if (i && scol_l (i - 1)->breakable_b_)
687 // one interline minimum at start of bar
689 // cols_[i].width_[RIGHT] += interline_f;
690 cols_[i].width_[RIGHT] = cols_[i].width_[RIGHT] >? interline_f;
692 // should adjust dist too?
693 ideal_arr[i-1] = ideal_arr[i-1] >? (2 * interline_f);
697 last musical column of bar
699 if (i + 1 < cols_.size () && scol_l(i+1)->breakable_b_)
701 // two interline minimum ok for last column?
702 dist = dist >? 2 * interline_f;
706 urg: simply *adding* an interline leaves big gaps at
707 end of measure in star-spangled-banner (after lyrics
710 cols_[i].width_[RIGHT] += interline_f; // before
712 having a minimum of one interline solves this problem
713 in most (but not all??) cases.
715 for music without lyrics (esp. when set very tightly),
716 adding an interline looks good: probably because this
717 hides a bug that allows the last note's "hinterfleish"
718 to be removed (e.g., see wtk1-fugue2: that's ugly now).
722 cols_[i].width_[RIGHT] = cols_[i].width_[RIGHT] >? 2 * interline_f;
725 // ugh, do we need this?
726 if (i < cols_.size () - 1 && !scol_l (i + 1)->musical_b ())
728 Real minimum = -cols_[i + 1].width_[LEFT] + cols_[i].width_[RIGHT]
730 dist = dist >? minimum;
737 shorter distances should stretch less.
741 hooke[i] = 2 * max_ideal_space - ideal[i]
745 for (int i=0; i < ideal_arr.size(); i++)
746 hooke_arr[i] = 1/ideal_arr[i];
748 for (int i=0; i < ideal_arr.size(); i++)
750 assert (ideal_arr[i] >=0 && hooke_arr[i] >=0);
751 connect (i, i+1, ideal_arr[i], hooke_arr[i]);