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@cs.uu.nl>
12 #include "spring-spacer.hh"
15 #include "dimensions.hh"
17 #include "unionfind.hh"
18 #include "idealspacing.hh"
19 #include "pointer.tcc"
20 #include "score-column.hh"
21 #include "paper-def.hh"
25 Spring_spacer::default_solution () const
27 return try_initial_solution () ;
31 Spring_spacer::scol_l (int i)
33 return (Score_column*)cols_[i].pcol_l_;
36 const Real COLFUDGE=1e-3;
37 template class P<Real>; // ugh.
40 Spring_spacer::contains_b (Paper_column const *w)
42 for (int i=0; i< cols_.size (); i++)
43 if (cols_[i].pcol_l_ == w)
50 Spring_spacer::OK () const
53 for (int i = 1; i < cols_.size (); i++)
54 assert (cols_[i].rank_i_ > cols_[i-1].rank_i_);
55 for (int i = 1; i < loose_col_arr_.size (); i++)
56 assert (loose_col_arr_[i].rank_i_ > loose_col_arr_[i-1].rank_i_);
61 Make sure no unconnected columns happen.
64 Spring_spacer::handle_loose_cols ()
66 Union_find connected (cols_.size ());
68 for (PCursor<Idealspacing*> i (ideal_p_list_.top ()); i.ok (); i++)
70 connected.connect (i->left_i_,i->right_i_);
72 for (int i = 0; i < cols_.size (); i++)
73 if (cols_[i].fixed_b ())
75 for (int i=1; i < fixed.size (); i++)
76 connected.connect (fixed[i-1], fixed[i]);
78 for (int i = cols_.size (); i--;)
80 if (! connected.equiv (fixed[0], i))
82 warning (_f ("unconnected column: %d", i));
91 Guess a stupid position for loose columns. Put loose columns at
92 regular distances from enclosing calced columns
95 Spring_spacer::position_loose_cols (Vector &sol_vec) const
97 if (!loose_col_arr_.size ())
99 assert (sol_vec.dim ());
100 Array<bool> fix_b_arr;
101 fix_b_arr.set_size (cols_.size () + loose_col_arr_.size ());
102 Real utter_right_f=-infinity_f;
103 Real utter_left_f =infinity_f;
104 for (int i=0; i < loose_col_arr_.size (); i++)
106 fix_b_arr[loose_col_arr_[i].rank_i_] = false;
108 for (int i=0; i < cols_.size (); i++)
110 int r= cols_[i].rank_i_;
112 utter_right_f = utter_right_f >? sol_vec (i);
113 utter_left_f = utter_left_f <? sol_vec (i);
115 Vector v (fix_b_arr.size ());
118 for (int i=0; i < v.dim (); i++)
122 assert (cols_[j].rank_i_ == i);
123 v (i) = sol_vec (j++);
128 (j>0) ?sol_vec (j-1) : utter_left_f;
130 (j < sol_vec.dim ()) ? sol_vec (j) : utter_right_f;
131 int left_rank = (j>0) ? cols_[j-1].rank_i_ : 0;
132 int right_rank = (j<sol_vec.dim ()) ? cols_[j].rank_i_ : sol_vec.dim ();
134 int d_r = right_rank - left_rank;
135 Column_info loose=loose_col_arr_[k++];
136 int r = loose.rank_i_ ;
137 assert (r > left_rank && r < right_rank);
139 v (i) = (r - left_rank)*left_pos_f/ d_r +
140 (right_rank - r) *right_pos_f /d_r;
147 Spring_spacer::check_constraints (Vector v) const
150 assert (dim == cols_.size ());
151 DOUT << "checking " << v;
152 for (int i=0; i < dim; i++)
154 if (cols_[i].fixed_b () &&
155 abs (cols_[i].fixed_position () - v (i)) > COLFUDGE)
157 DOUT << "Fixpos broken\n";
160 Array<Spacer_rod> const &rods (cols_[i].rods_[RIGHT]);
161 for (int j =0; j < rods.size (); j++)
163 int other =rods[j].other_idx_;
164 Real diff =v (other) - v (i) ;
165 if (COLFUDGE +diff < rods[j].distance_f_)
167 DOUT << "i, other_i: " << i << " " << other << '\n';
168 DOUT << "dist, minimal = " << diff << " "
169 << rods[j].distance_f_ << '\n';
178 /** try to generate a solution which obeys the min distances and fixed positions
181 Spring_spacer::try_initial_solution () const
184 if (!try_initial_solution_and_tell (v))
186 warning (_ ("I'm too fat; call Oprah"));
193 Spring_spacer::try_initial_solution_and_tell (Vector &v) const
195 int dim=cols_.size ();
196 bool succeeded = true;
197 Vector initsol (dim);
199 assert (cols_[0].fixed_b ());
200 DOUT << "fixpos 0 " << cols_[0].fixed_position ();
201 for (int i=0; i < dim; i++)
203 Real min_x = i ? initsol (i-1) : cols_[0].fixed_position ();
204 Array<Spacer_rod> const &sr_arr (cols_[i].rods_[LEFT]);
205 for (int j=0; j < sr_arr.size (); j++)
207 min_x = min_x >? (initsol (sr_arr[j].other_idx_) + sr_arr[j].distance_f_);
211 if (cols_[i].fixed_b ())
213 initsol (i)=cols_[i].fixed_position ();
214 if (initsol (i) < min_x )
216 DOUT << "failing: init, min : " << initsol (i) << " " << min_x << '\n';
224 DOUT << "tried and told solution: " << v;
226 DOUT << " (failed)\n";
232 // generate the matrices
234 Spring_spacer::make_matrices (Matrix &quad, Vector &lin, Real &c) const
240 for (PCursor<Idealspacing*> i (ideal_p_list_.top ()); i.ok (); i++)
245 quad (r,r) += i->hooke_f_;
246 quad (r,l) -= i->hooke_f_;
247 quad (l,r) -= i->hooke_f_;
248 quad (l,l) += i->hooke_f_;
250 lin (r) -= i->space_f_*i->hooke_f_;
251 lin (l) += i->space_f_*i->hooke_f_;
253 c += sqr (i->space_f_);
256 if (quad.dim () > 10)
263 Spring_spacer::set_fixed_cols (Mixed_qp &qp) const
265 for (int j=0; j < cols_.size (); j++)
266 if (cols_[j].fixed_b ())
267 qp.add_fixed_var (j,cols_[j].fixed_position ());
270 // put the constraints into the LP problem
272 Spring_spacer::make_constraints (Mixed_qp& lp) const
274 int dim=cols_.size ();
276 for (int j=0; j < dim -1; j++)
278 Array<Spacer_rod> const&rod_arr (cols_[j].rods_[RIGHT]);
279 for (int i = 0; i < rod_arr.size (); i++)
282 c1 (rod_arr[i].other_idx_)=1.0 ;
285 lp.add_inequality_cons (c1, rod_arr[i].distance_f_);
292 Spring_spacer::calculate_energy_f (Vector solution) const
295 for (PCursor<Idealspacing*> i (ideal_p_list_.top ()); i.ok (); i++)
297 e += i->energy_f (solution (i->right_i_) - solution (i->left_i_));
303 Spring_spacer::lower_bound_solution (Column_x_positions*positions) const
305 Mixed_qp lp (cols_.size ());
306 make_matrices (lp.quad_,lp.lin_, lp.const_term_);
309 Vector start (cols_.size ());
311 Vector solution_vec (lp.solve (start));
313 DOUT << "Lower bound sol: " << solution_vec;
314 positions->energy_f_ = calculate_energy_f (solution_vec);
315 positions->config = solution_vec;
316 positions->satisfies_constraints_b_ = check_constraints (solution_vec);
319 Spring_spacer::Spring_spacer ()
321 energy_normalisation_f_ = 1.0;
325 Spring_spacer::solve (Column_x_positions*positions) const
328 DOUT << "Spring_spacer::solve ()...";
331 bool constraint_satisfaction = try_initial_solution_and_tell (solution_try);
332 if (constraint_satisfaction)
334 Mixed_qp lp (cols_.size ());
335 make_matrices (lp.quad_,lp.lin_, lp.const_term_);
336 make_constraints (lp);
339 Vector solution_vec (lp.solve (solution_try));
341 positions->satisfies_constraints_b_ = check_constraints (solution_vec);
342 if (!positions->satisfies_constraints_b_)
344 WARN << _ ("solution doesn't satisfy constraints") << '\n' ;
346 position_loose_cols (solution_vec);
347 positions->energy_f_ = calculate_energy_f (solution_vec);
348 positions->config = solution_vec;
349 positions->error_col_l_arr_ = error_pcol_l_arr ();
353 positions->set_stupid_solution (solution_try);
355 DOUT << "Finished Spring_spacer::solve ()...";
359 add one column to the problem.
362 Spring_spacer::add_column (Paper_column *col, bool fixed, Real fixpos)
364 Column_info c (col, (fixed)? &fixpos : 0);
365 int this_rank = cols_.size ();
366 c.rank_i_ = this_rank;
368 for (int i=0; i < col->minimal_dists_arr_drul_[LEFT].size (); i++)
370 Column_rod &cr = col->minimal_dists_arr_drul_[LEFT][i];
371 int left_idx = cr.other_l_->rank_i () - cols_[0].pcol_l_->rank_i ();
375 if (cols_[left_idx].pcol_l_ != cr.other_l_)
379 l_rod.distance_f_ = cr.distance_f_;
380 l_rod.other_idx_ = left_idx;
381 c.rods_[LEFT].push (l_rod);
384 r_rod.distance_f_ = cr.distance_f_;
385 r_rod.other_idx_ = this_rank;
386 cols_[left_idx].rods_[RIGHT].push (r_rod);
393 Spring_spacer::error_pcol_l_arr () const
395 Array<Paper_column*> retval;
396 for (int i=0; i< cols_.size (); i++)
398 retval.push (cols_[i].pcol_l_);
399 for (int i=0; i < loose_col_arr_.size (); i++)
401 retval.push (loose_col_arr_[i].pcol_l_);
407 Spring_spacer::loosen_column (int i)
409 Column_info c=cols_.get (i);
410 for (PCursor<Idealspacing*> j (ideal_p_list_.top ()); j.ok (); j++)
412 if (j->left_i_ == i|| j->right_i_ == i)
420 for (; j < loose_col_arr_.size (); j++)
422 if (loose_col_arr_[j].rank_i_ > c.rank_i_)
425 loose_col_arr_.insert (c,j);
430 Spring_spacer::print () const
433 for (int i=0; i < cols_.size (); i++)
435 DOUT << "col " << i << " ";
438 for (PCursor<Idealspacing*> i (ideal_p_list_.top ()); i.ok (); i++)
447 Spring_spacer::connect (int i, int j, Real d, Real h)
449 assert (d >= 0 && d <= 100 CM);
452 Idealspacing * s = new Idealspacing;
459 ideal_p_list_.bottom ().add (s);
466 Spring_spacer::prepare ()
468 DOUT << "Preparing..";
469 calc_idealspacing ();
470 handle_loose_cols ();
472 DOUT << "finished preparing.\n";
476 Spring_spacer::constructor ()
478 return new Spring_spacer;
484 get the shortest_playing running note at a time. */
486 Spring_spacer::get_ruling_durations (Array<Moment> &shortest_playing_arr,
487 Array<Moment> &context_shortest_arr)
489 for (int i=0; i < cols_.size (); i++)
491 scol_l (i)->preprocess ();
492 scol_l (i)->print ();
494 int start_context_i=0;
495 Moment context_shortest;
496 context_shortest.set_infinite (1);
497 context_shortest_arr.set_size (cols_.size ());
499 for (int i=0; i < cols_.size (); i++)
501 Moment now = scol_l (i)->when ();
502 Moment shortest_playing;
503 shortest_playing.set_infinite (1);
505 if (scol_l (i)->breakable_b_)
507 for (int ji=i; ji >= start_context_i; ji--)
508 context_shortest_arr[ji] = context_shortest;
510 context_shortest.set_infinite (1);
512 if (scol_l (i)->durations.size ())
514 context_shortest = context_shortest <? scol_l (i)->durations[0];
517 // ji was j, but triggered ICE
518 for (int ji=i+1; ji --;)
520 if (scol_l (ji)->durations.size () &&
521 now - scol_l (ji)->when () >= shortest_playing)
524 for (int k = scol_l (ji)->durations.size ();
525 k-- && scol_l (ji)->durations[k] + scol_l (ji)->when () > now;
528 shortest_playing = shortest_playing <? scol_l (ji)->durations[k];
531 shortest_playing_arr.push (shortest_playing);
535 DOUT << "shortest_playing/:[ ";
536 for (int i=0; i < shortest_playing_arr.size (); i++)
538 DOUT << shortest_playing_arr[i] << " ";
539 DOUT << context_shortest_arr[i] << ", ";
546 TODO: take out the refs to width
549 generate springs between columns.
551 TODO: This needs rethinking.
553 * Spacing should take optical
556 * Should be decentralised
558 The algorithm is taken from :
560 John S. Gourlay. ``Spacing a Line of Music,'' Technical Report
561 OSU-CISRC-10/87-TR35, Department of Computer and Information
562 Science, The Ohio State University, 1987.
566 Spring_spacer::calc_idealspacing ()
568 Array<Moment> shortest_playing_arr;
569 Array<Moment> context_shortest_arr;
570 get_ruling_durations (shortest_playing_arr, context_shortest_arr);
572 Real interline_f = paper_l ()->interline_f ();
575 Array<Real> ideal_arr_;
576 Array<Real> hooke_arr_;
577 for (int i=0; i < cols_.size () - 1; i++){
578 ideal_arr_.push (-1.0);
579 hooke_arr_.push (1.0);
583 First do all non-musical columns
585 for (int i=0; i < cols_.size (); i++)
587 if (!scol_l (i)->musical_b () && i+1 < cols_.size ())
589 Real symbol_distance =cols_[i].width_[RIGHT] + 2 PT;
590 Real durational_distance = 0;
593 Moment delta_t = scol_l (i+1)->when () - scol_l (i)->when () ;
597 ugh should use shortest_playing distance
601 Real k= paper_l ()->arithmetic_constant (context_shortest_arr[i]);
602 durational_distance = paper_l ()->duration_to_dist (delta_t,k);
604 symbol_distance += -cols_[i+1].width_[LEFT];
607 ideal_arr_[i] = symbol_distance >? durational_distance;
608 hooke_arr_[i] = 1; //2.0;
615 for (int i=0; i < cols_.size (); i++)
617 if (scol_l (i)->musical_b ())
619 Moment shortest_playing_len = shortest_playing_arr[i];
620 Moment context_shortest = context_shortest_arr[i];
621 if (! shortest_playing_len)
623 warning (_f ("can't find a ruling note at %s",
624 scol_l (i)->when ().str ()));
625 shortest_playing_len = 1;
627 if (! context_shortest)
629 warning (_f ("no minimum in measure at %s",
630 scol_l (i)->when ().str ()));
631 context_shortest = 1;
633 Moment delta_t = scol_l (i+1)->when () - scol_l (i)->when ();
634 Real k= paper_l ()->arithmetic_constant (context_shortest);
635 Real dist = paper_l ()->duration_to_dist (shortest_playing_len, k);
636 dist *= (double) (delta_t / shortest_playing_len);
639 According to [Ross] and [Wanske], and from what i've seen:
641 * whitespace at the begin of the bar should be fixed at
642 (about) one interline.
644 when spacing gets real tight, a smaller fixed value may be
645 used, so that there are two discrete amounts of whitespace
646 possible at the begin of a bar; but this is not implemented
649 * whitespace at the end of the bar is the normal amount of
650 "hinterfleish" that would have been used, had there been
651 yet another note in the bar.
653 some editors argue that the bar line should not take any
654 space, not to hinder the flow of music spaced around a bar
656 [Ross] and [Wanske] do not suggest this, however. Further,
657 it introduces some spacing problems and think that it is ugly
663 first musical column of bar
665 if (i && scol_l (i - 1)->breakable_b_)
667 // fixed: probably should set minimum (rod/spring)?
668 cols_[i-1].width_[RIGHT] += interline_f;
669 // should adjust dist too?
670 ideal_arr_[i-1] = ideal_arr_[i-1] >? (2 * interline_f);
674 last musical column of bar
676 if (i + 1 < cols_.size () && scol_l (i+1)->breakable_b_)
679 dist = dist >? interline_f;
682 uhuh, this code looks fine, already?
683 someone was junking this last "hinterfleisch" whitespace?!
685 but this seems to be fixed now :-)
688 cols_[i].width_[RIGHT] += interline_f;
691 // ugh, do we need this?
692 if (i < cols_.size () - 1 && !scol_l (i + 1)->musical_b ())
694 Real minimum = -cols_[i + 1].width_[LEFT] + cols_[i].width_[RIGHT]
696 dist = dist >? minimum;
698 ideal_arr_[i] = dist;
702 for (int i=0; i < ideal_arr_.size (); i++)
704 assert (ideal_arr_[i] >=0 && hooke_arr_[i] >=0);
705 connect (i, i+1, ideal_arr_[i], hooke_arr_[i]);