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);
401 Spring_spacer::error_pcol_l_arr() const
403 Link_array<Paper_column> retval;
404 for (int i=0; i< cols_.size(); i++)
406 retval.push (cols_[i].pcol_l_);
407 for (int i=0; i < loose_col_arr_.size(); i++)
409 retval.push (loose_col_arr_[i].pcol_l_);
414 Ugh. Should junk this.
417 Spring_spacer::loosen_column (int idx)
419 Column_info c=cols_.get (idx);
421 Cons<Idealspacing> **pp = &ideal_p_list_;
425 Idealspacing *j = (*pp)->car_;
426 if (j->cols_drul_[LEFT] == idx|| j->cols_drul_[RIGHT] == idx)
428 delete remove_cons (pp);
438 for (; j < loose_col_arr_.size(); j++)
440 if (loose_col_arr_[j].rank_i_ > c.rank_i_)
443 loose_col_arr_.insert (c,j);
448 Spring_spacer::print() const
451 for (int i=0; i < cols_.size(); i++)
453 DOUT << "col " << i << " ";
457 for (Cons<Idealspacing> *p =ideal_p_list_; p; p = p->next_)
466 Spring_spacer::connect (int i, int j, Real d, Real h)
468 assert(d >= 0 && d <= 100 CM);
471 Idealspacing * s = new Idealspacing;
473 s->cols_drul_[LEFT] = i ;
474 s->cols_drul_[RIGHT] = j;
478 ideal_p_list_ = new Killing_cons<Idealspacing> (s, ideal_p_list_);
482 Spring_spacer::prepare()
484 DOUT << "Preparing..";
488 DOUT << "finished preparing.\n";
492 Spring_spacer::constructor()
494 return new Spring_spacer;
500 get the shortest_playing running note at a time. */
502 Spring_spacer::get_ruling_durations(Array<Moment> &context_shortest_arr)
504 for (int i=0; i < cols_.size(); i++)
506 scol_l (i)->preprocess();
507 scol_l (i)->print ();
509 int start_context_i=0;
510 Moment context_shortest;
511 context_shortest.set_infinite (1);
512 context_shortest_arr.set_size(cols_.size());
514 for (int i=0; i < cols_.size(); i++)
516 Score_column * sc = scol_l(i);
518 if (sc->breakable_b () || sc->break_status_dir ())
520 for (int ji=i; ji >= start_context_i; ji--)
521 context_shortest_arr[ji] = context_shortest;
523 context_shortest.set_infinite (1);
525 else if (sc->musical_b ())
526 context_shortest = context_shortest <? sc->shortest_starter_mom_;
530 DOUT << "context shortest :[ ";
531 for (int i=0; i < context_shortest_arr.size(); i++)
533 DOUT << context_shortest_arr[i] << ", ";
540 TODO: take out the refs to width
544 generate springs between columns.
546 TODO: This needs rethinking.......
548 * Spacing should take optical effects into account
550 * Should be decentralised
552 The algorithm is taken from :
554 John S. Gourlay. ``Spacing a Line of Music,'' Technical Report
555 OSU-CISRC-10/87-TR35, Department of Computer and Information
556 Science, The Ohio State University, 1987.
560 Spring_spacer::calc_idealspacing()
562 Array<Moment> context_shortest_arr;
563 get_ruling_durations(context_shortest_arr);
565 Real interline_f = paper_l ()->get_realvar (interline_scm_sym);
567 Array<Real> ideal_arr;
568 Array<Real> hooke_arr;
569 for (int i=0; i < cols_.size() - 1; i++){
570 ideal_arr.push (-1.0);
571 hooke_arr.push (1.0);
575 First do all non-musical columns
577 for (int i=0; i < cols_.size(); i++)
579 if (!scol_l (i)->musical_b() && i+1 < cols_.size())
581 Real symbol_distance =cols_[i].width_[RIGHT] + 2 PT;
582 Real durational_distance = 0;
583 Moment delta_t = scol_l (i+1)->when_mom () - scol_l (i)->when_mom () ;
586 ugh should use shortest_playing distance
590 Real k= paper_l()->arithmetic_constant (context_shortest_arr[i]);
591 durational_distance = paper_l()->length_mom_to_dist (delta_t,k);
593 symbol_distance += -cols_[i+1].width_[LEFT];
596 ideal_arr[i] = symbol_distance >? durational_distance;
597 hooke_arr[i] = 1; //2.0;
604 for (int i=0; i < cols_.size(); i++)
606 if (scol_l (i)->musical_b())
608 Moment shortest_playing_len = scol_l(i)->shortest_playing_mom_;
609 Moment context_shortest = context_shortest_arr[i];
610 if (! shortest_playing_len)
612 warning (_f ("can't find a ruling note at %s",
613 scol_l (i)->when_mom ().str ()));
614 shortest_playing_len = 1;
616 if (! context_shortest)
618 warning (_f ("no minimum in measure at %s",
619 scol_l (i)->when_mom ().str ()));
620 context_shortest = 1;
622 Moment delta_t = scol_l (i+1)->when_mom () - scol_l (i)->when_mom ();
623 Real k= paper_l()->arithmetic_constant(context_shortest);
624 Real dist = paper_l()->length_mom_to_dist (shortest_playing_len, k);
625 dist *= (double)(delta_t / shortest_playing_len);
628 According to [Ross] and [Wanske], and from what i've seen:
630 * whitespace at the begin of the bar should be fixed at
631 (about) one interline.
634 when spacing gets real tight, a smaller fixed value may be
635 used, so that there are two discrete amounts of whitespace
636 possible at the begin of a bar; but this is not implemented
639 * whitespace at the end of the bar is the normal amount of
640 "hinterfleish" that would have been used, had there been
641 yet another note in the bar.
644 some editors argue that the bar line should not take any
645 space, not to hinder the flow of music spaced around a bar
648 [Ross] and [Wanske] do not suggest this, however. Further,
649 it introduces some spacing problems and I think that it is ugly
656 first musical column of bar
658 if (i && !scol_l (i - 1)->musical_b ())
660 // one interline minimum at start of bar
662 // cols_[i].width_[RIGHT] += interline_f;
663 cols_[i].width_[RIGHT] = cols_[i].width_[RIGHT] >? interline_f;
665 // should adjust dist too?
666 ideal_arr[i-1] = ideal_arr[i-1] >? (2 * interline_f);
670 last musical column of bar
672 if (i + 1 < cols_.size () && !scol_l(i+1)->musical_b ())
674 // two interline minimum ok for last column?
675 dist = dist >? 2 * interline_f;
679 urg: simply *adding* an interline leaves big gaps at
680 end of measure in star-spangled-banner (after lyrics
683 cols_[i].width_[RIGHT] += interline_f; // before
685 having a minimum of one interline solves this problem
686 in most (but not all??) cases.
688 for music without lyrics (esp. when set very tightly),
689 adding an interline looks good: probably because this
690 hides a bug that allows the last note's "hinterfleish"
691 to be removed (e.g., see wtk1-fugue2: that's ugly now).
695 cols_[i].width_[RIGHT] = cols_[i].width_[RIGHT] >? 2 * interline_f;
698 // ugh, do we need this?
699 if (i < cols_.size () - 1 && !scol_l (i + 1)->musical_b ())
701 Real minimum = -cols_[i + 1].width_[LEFT] + cols_[i].width_[RIGHT]
703 dist = dist >? minimum;
710 shorter distances should stretch less.
714 hooke[i] = 2 * max_ideal_space - ideal[i]
718 for (int i=0; i < ideal_arr.size(); i++)
719 hooke_arr[i] = 1/ideal_arr[i];
721 for (int i=0; i < ideal_arr.size(); i++)
723 assert (ideal_arr[i] >=0 && hooke_arr[i] >=0);
724 connect (i, i+1, ideal_arr[i], hooke_arr[i]);