2 spring-spacer.cc -- implement Spring_spacer
4 source file of the GNU LilyPond music typesetter
6 (c) 1996, 1997--1998, 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_b (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());
152 DOUT << "checking " << v;
153 for (int i=0; i < dim; i++)
155 if (cols_[i].fixed_b() &&
156 abs (cols_[i].fixed_position() - v (i)) > COLFUDGE)
158 DOUT << "Fixpos broken\n";
161 Array<Spacer_rod> const &rods (cols_[i].rods_[RIGHT]);
162 for (int j =0; j < rods.size (); j++)
164 int other =rods[j].other_idx_;
165 Real diff =v (other) - v (i) ;
166 if (COLFUDGE +diff < rods[j].distance_f_)
168 DOUT << "i, other_i: " << i << " " << other << "\n";
169 DOUT << "dist, minimal = " << diff <<" "
170 << rods[j].distance_f_<<'\n';
179 /** try to generate a solution which obeys the min distances and fixed positions
182 Spring_spacer::try_initial_solution() const
185 if (!try_initial_solution_and_tell (v))
187 warning ("I'm too fat; call Oprah");
194 Spring_spacer::try_initial_solution_and_tell (Vector &v) const
196 int dim=cols_.size();
197 bool succeeded = true;
198 Vector initsol (dim);
200 assert (cols_[0].fixed_b ());
201 DOUT << "fixpos 0 " << cols_[0].fixed_position ();
202 for (int i=0; i < dim; i++)
204 Real min_x = i ? initsol (i-1) : cols_[0].fixed_position ();
205 Array<Spacer_rod> const &sr_arr(cols_[i].rods_[LEFT]);
206 for (int j=0; j < sr_arr.size (); j++)
208 min_x = min_x >? (initsol (sr_arr[j].other_idx_) + sr_arr[j].distance_f_);
212 if (cols_[i].fixed_b())
214 initsol (i)=cols_[i].fixed_position();
215 if (initsol (i) < min_x )
217 DOUT << "failing: init, min : " << initsol (i) << " " << min_x << "\n";
225 DOUT << "tried and told solution: " << v;
227 DOUT << "(failed)\n";
233 // generate the matrices
235 Spring_spacer::make_matrices (Matrix &quad, Vector &lin, Real &c) const
241 for (PCursor<Idealspacing*> i (ideal_p_list_.top()); i.ok (); i++)
246 quad (r,r) += i->hooke_f_;
247 quad (r,l) -= i->hooke_f_;
248 quad (l,r) -= i->hooke_f_;
249 quad (l,l) += i->hooke_f_;
251 lin (r) -= i->space_f_*i->hooke_f_;
252 lin (l) += i->space_f_*i->hooke_f_;
254 c += sqr (i->space_f_);
264 Spring_spacer::set_fixed_cols (Mixed_qp &qp) const
266 for (int j=0; j < cols_.size(); j++)
267 if (cols_[j].fixed_b())
268 qp.add_fixed_var (j,cols_[j].fixed_position());
271 // put the constraints into the LP problem
273 Spring_spacer::make_constraints (Mixed_qp& lp) const
275 int dim=cols_.size();
277 for (int j=0; j < dim -1; j++)
279 Array<Spacer_rod> const&rod_arr (cols_[j].rods_[RIGHT]);
280 for (int i = 0; i < rod_arr.size (); i++)
283 c1(rod_arr[i].other_idx_)=1.0 ;
286 lp.add_inequality_cons (c1, rod_arr[i].distance_f_);
293 Spring_spacer::calculate_energy_f (Vector solution) const
296 for (PCursor<Idealspacing*> i (ideal_p_list_.top()); i.ok(); i++)
298 e += i->energy_f(solution(i->right_i_) - solution(i->left_i_));
304 Spring_spacer::lower_bound_solution (Col_hpositions*positions) const
306 Mixed_qp lp (cols_.size());
307 make_matrices (lp.quad_,lp.lin_, lp.const_term_);
310 Vector start (cols_.size());
312 Vector solution_vec (lp.solve (start));
314 DOUT << "Lower bound sol: " << solution_vec;
315 positions->energy_f_ = calculate_energy_f (solution_vec);
316 positions->config = solution_vec;
317 positions->satisfies_constraints_b_ = check_constraints (solution_vec);
320 Spring_spacer::Spring_spacer ()
322 energy_normalisation_f_ = 1.0;
326 Spring_spacer::solve (Col_hpositions*positions) const
329 DOUT << "Spring_spacer::solve ()...";
332 bool constraint_satisfaction = try_initial_solution_and_tell (solution_try);
333 if (constraint_satisfaction)
335 Mixed_qp lp (cols_.size());
336 make_matrices (lp.quad_,lp.lin_, lp.const_term_);
337 make_constraints (lp);
340 Vector solution_vec (lp.solve (solution_try));
342 positions->satisfies_constraints_b_ = check_constraints (solution_vec);
343 if (!positions->satisfies_constraints_b_)
345 WARN << _("solution doesn't satisfy constraints.\n") ;
347 position_loose_cols (solution_vec);
348 positions->energy_f_ = calculate_energy_f (solution_vec);
349 positions->config = solution_vec;
350 positions->error_col_l_arr_ = error_pcol_l_arr();
354 positions->set_stupid_solution (solution_try);
356 DOUT << "Finished Spring_spacer::solve ()...";
360 add one column to the problem.
363 Spring_spacer::add_column (Paper_column *col, bool fixed, Real fixpos)
365 Colinfo c (col,(fixed)? &fixpos : 0);
366 int this_rank = cols_.size();
367 c.rank_i_ = this_rank;
369 for (int i=0; i < col->minimal_dists_arr_drul_[LEFT].size (); i++)
371 Column_rod &cr = col->minimal_dists_arr_drul_[LEFT][i];
372 int left_idx = cr.other_l_->rank_i () - cols_[0].pcol_l_->rank_i ();
376 if (cols_[left_idx].pcol_l_ != cr.other_l_)
380 l_rod.distance_f_ = cr.distance_f_;
381 l_rod.other_idx_ = left_idx;
382 c.rods_[LEFT].push (l_rod);
385 r_rod.distance_f_ = cr.distance_f_;
386 r_rod.other_idx_ = this_rank;
387 cols_[left_idx].rods_[RIGHT].push (r_rod);
394 Spring_spacer::error_pcol_l_arr() const
396 Array<Paper_column*> retval;
397 for (int i=0; i< cols_.size(); i++)
399 retval.push (cols_[i].pcol_l_);
400 for (int i=0; i < loose_col_arr_.size(); i++)
402 retval.push (loose_col_arr_[i].pcol_l_);
408 Spring_spacer::loosen_column (int i)
410 Colinfo c=cols_.get (i);
411 for (PCursor<Idealspacing*> j (ideal_p_list_.top()); j.ok (); j++)
413 if (j->left_i_ == i|| j->right_i_ == i)
421 for (; j < loose_col_arr_.size(); j++)
423 if (loose_col_arr_[j].rank_i_ > c.rank_i_)
426 loose_col_arr_.insert (c,j);
431 Spring_spacer::print() const
434 for (int i=0; i < cols_.size(); i++)
436 DOUT << "col " << i<<' ';
439 for (PCursor<Idealspacing*> i (ideal_p_list_.top()); i.ok (); i++)
448 Spring_spacer::connect (int i, int j, Real d, Real h)
450 assert(d >= 0 && d <= 100 CM);
453 Idealspacing * s = new Idealspacing;
460 ideal_p_list_.bottom().add (s);
467 Spring_spacer::prepare()
469 DOUT << "Preparing..";
473 DOUT << "finished preparing.\n";
477 Spring_spacer::constructor()
479 return new Spring_spacer;
485 get the shortest_playing running note at a time. */
487 Spring_spacer::get_ruling_durations(Array<Moment> &shortest_playing_arr,
488 Array<Moment> &context_shortest_arr)
490 for (int i=0; i < cols_.size(); i++)
492 scol_l (i)->preprocess();
493 scol_l (i)->print ();
495 int start_context_i=0;
496 Moment context_shortest;
497 context_shortest.set_infinite (1);
498 context_shortest_arr.set_size(cols_.size());
500 for (int i=0; i < cols_.size(); i++)
502 Moment now = scol_l (i)->when();
503 Moment shortest_playing;
504 shortest_playing.set_infinite (1);
506 if (scol_l (i)->breakable_b_)
508 for (int ji=i; ji >= start_context_i; ji--)
509 context_shortest_arr[ji] = context_shortest;
511 context_shortest.set_infinite (1);
513 if (scol_l (i)->durations.size())
515 context_shortest = context_shortest <? scol_l(i)->durations[0];
518 // ji was j, but triggered ICE
519 for (int ji=i+1; ji --;)
521 if (scol_l(ji)->durations.size() &&
522 now - scol_l(ji)->when() >= shortest_playing)
525 for (int k = scol_l (ji)->durations.size();
526 k-- && scol_l(ji)->durations[k] + scol_l(ji)->when() > now;
529 shortest_playing = shortest_playing <? scol_l(ji)->durations[k];
532 shortest_playing_arr.push(shortest_playing);
536 DOUT << "shortest_playing/:[ ";
537 for (int i=0; i < shortest_playing_arr.size(); i++)
539 DOUT << shortest_playing_arr[i] << " ";
540 DOUT << context_shortest_arr[i] << ", ";
547 TODO: take out the refs to width
550 generate springs between columns.
552 TODO: This needs rethinking. Spacing should take optical
555 The algorithm is taken from :
557 John S. Gourlay. ``Spacing a Line of Music,'' Technical Report
558 OSU-CISRC-10/87-TR35, Department of Computer and Information
559 Science, The Ohio State University, 1987.
563 Spring_spacer::calc_idealspacing()
565 Array<Moment> shortest_playing_arr;
566 Array<Moment> context_shortest_arr;
567 get_ruling_durations(shortest_playing_arr, context_shortest_arr);
569 Real interline_f = paper_l ()->interline_f ();
572 Array<Real> ideal_arr_;
573 Array<Real> hooke_arr_;
574 for (int i=0; i < cols_.size() - 1; i++){
575 ideal_arr_.push (-1.0);
576 hooke_arr_.push (1.0);
580 First do all non-musical columns
582 for (int i=0; i < cols_.size(); i++)
584 if (!scol_l (i)->musical_b() && i+1 < cols_.size())
586 Real symbol_distance =cols_[i].width_[RIGHT] + 2 PT;
587 Real durational_distance = 0;
590 Moment delta_t = scol_l (i+1)->when() - scol_l (i)->when () ;
592 Real k= paper_l()->arithmetic_constant (context_shortest_arr[i]);
594 ugh should use shortest_playing distance
597 durational_distance = paper_l()->duration_to_dist (delta_t,k);
598 symbol_distance += -cols_[i+1].width_[LEFT];
601 ideal_arr_[i] = symbol_distance >? durational_distance;
602 hooke_arr_[i] = 1; //2.0;
609 for (int i=0; i < cols_.size(); i++)
611 if (scol_l (i)->musical_b())
613 Moment shortest_playing_len = shortest_playing_arr[i];
614 Moment context_shortest = context_shortest_arr[i];
615 if (! shortest_playing_len)
617 warning (_("Can't find a ruling note at ")
618 +scol_l (i)->when().str ());
619 shortest_playing_len = 1;
621 if (! context_shortest)
623 warning(_("No minimum in measure at ")
624 + scol_l (i)->when().str ());
625 context_shortest = 1;
627 Moment delta_t = scol_l (i+1)->when() - scol_l (i)->when ();
628 Real k= paper_l()->arithmetic_constant(context_shortest);
629 Real dist = paper_l()->duration_to_dist (shortest_playing_len, k);
630 dist *= (double)(delta_t / shortest_playing_len);
633 According to [Ross] and [Wanske], and from what i've seen:
635 * whitespace at the begin of the bar should be fixed at
636 (about) one interline.
638 when spacing gets real tight, a smaller fixed value may be
639 used, so that there are two discrete amounts of whitespace
640 possible at the begin of a bar; but this is not implemented
643 * whitespace at the end of the bar is the normal amount of
644 "hinterfleish" that would have been used, had there been
645 yet another note in the bar.
647 some editors argue that the bar line should not take any
648 space, not to hinder the flow of music spaced around a bar
650 [Ross] and [Wanske] do not suggest this, however. Further,
651 it introduces some spacing problems and think that it is ugly
657 first musical column of bar
659 if (i && scol_l (i - 1)->breakable_b_)
661 // fixed: probably should set minimum (rod/spring)?
662 cols_[i-1].width_[RIGHT] += interline_f;
663 // should adjust dist too?
664 ideal_arr_[i-1] = ideal_arr_[i-1] >? interline_f;
668 last musical column of bar
670 if (i + 1 < cols_.size () && scol_l(i+1)->breakable_b_)
673 dist = dist >? interline_f;
676 uhuh, this code looks fine, already?
677 someone was junking this last "hinterfleisch" whitespace?!
679 but this seems to be fixed now :-)
682 cols_[i].width_[RIGHT] += interline_f;
685 // ugh, do we need this?
686 if (i < cols_.size () - 1 && !scol_l (i + 1)->musical_b ())
688 Real minimum = -cols_[i + 1].width_[LEFT] + cols_[i].width_[RIGHT]
690 dist = dist >? minimum;
692 ideal_arr_[i] = dist;
696 for (int i=0; i < ideal_arr_.size(); i++)
698 assert (ideal_arr_[i] >=0 && hooke_arr_[i] >=0);
699 connect (i, i+1, ideal_arr_[i], hooke_arr_[i]);