2 spring-spacer.cc -- implement Spring_spacer
4 source file of the GNU LilyPond music typesetter
6 (c) 1996,1997 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 (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++)
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());
153 for (int i=0; i < dim; i++)
156 if (cols[i].fixed()&&
157 abs (cols[i].fixed_position() - v (i)) > COLFUDGE)
163 Real mindist=cols[i-1].width_[RIGHT]
164 -cols[i].width_[LEFT];
167 Real dif =v (i) - v (i-1)- mindist;
168 bool b = (dif > - COLFUDGE);
178 /// try to generate a solution which obeys the min distances and fixed
181 Spring_spacer::try_initial_solution() const
184 Vector initsol (dim);
185 for (int i=0; i < dim; i++)
189 initsol (i)=cols[i].fixed_position();
193 Real r =initsol (i-1) + cols[i-1].width_[RIGHT];
201 Real mindist=cols[i-1].width_[RIGHT]
202 - cols[i].width_[LEFT];
204 warning (_("Excentric column"));
205 initsol (i)=initsol (i-1)+mindist;
214 // generate the matrices
216 Spring_spacer::make_matrices (Matrix &quad, Vector &lin, Real &c) const
222 for (PCursor<Idealspacing*> i (ideal_p_list_.top()); i.ok (); i++)
227 quad (r,r) += i->hooke_f_;
228 quad (r,l) -= i->hooke_f_;
229 quad (l,r) -= i->hooke_f_;
230 quad (l,l) += i->hooke_f_;
232 lin (r) -= i->space_f_*i->hooke_f_;
233 lin (l) += i->space_f_*i->hooke_f_;
235 c += sqr (i->space_f_);
240 Spring_spacer::set_fixed_cols (Mixed_qp &qp) const
242 for (int j=0; j < cols.size(); j++)
244 qp.add_fixed_var (j,cols[j].fixed_position());
247 // put the constraints into the LP problem
249 Spring_spacer::make_constraints (Mixed_qp& lp) const
252 for (int j=0; j < dim; j++)
262 lp.add_inequality_cons (c1, cols[j-1].width_[RIGHT]
263 - cols[j].width_[LEFT]);
270 Spring_spacer::calculate_energy_f (Vector solution) const
273 for (PCursor<Idealspacing*> i (ideal_p_list_.top()); i.ok(); i++)
275 e += i->energy_f(solution(i->right_i_) - solution(i->left_i_));
281 Spring_spacer::lower_bound_solution (Col_hpositions*positions) const
283 Mixed_qp lp (cols.size());
284 make_matrices (lp.quad,lp.lin, lp.const_term);
287 Vector start (cols.size());
289 Vector solution_vec (lp.solve (start));
291 DOUT << "Lower bound sol: " << solution_vec;
292 positions->energy_f_ = calculate_energy_f (solution_vec);
293 positions->config = solution_vec;
294 positions->satisfies_constraints_b_ = check_constraints (solution_vec);
298 Spring_spacer::solve (Col_hpositions*positions) const
300 Vector solution_try (try_initial_solution());
302 if (check_constraints (solution_try))
304 Mixed_qp lp (cols.size());
305 make_matrices (lp.quad,lp.lin, lp.const_term);
306 make_constraints (lp);
309 Vector solution_vec (lp.solve (solution_try));
312 positions->satisfies_constraints_b_ = check_constraints (solution_vec);
313 if (!positions->satisfies_constraints_b_)
315 WARN << _("solution doesn't satisfy constraints.\n") ;
317 position_loose_cols (solution_vec);
318 positions->energy_f_ = calculate_energy_f (solution_vec);
319 positions->config = solution_vec;
320 positions->error_col_l_arr_ = error_pcol_l_arr();
324 positions->set_stupid_solution (solution_try);
329 add one column to the problem.
332 Spring_spacer::add_column (Paper_column *col, bool fixed, Real fixpos)
334 Colinfo c (col,(fixed)? &fixpos : 0);
336 c.rank_i_ = cols.top().rank_i_+1;
343 Spring_spacer::error_pcol_l_arr() const
345 Array<Paper_column*> retval;
346 for (int i=0; i< cols.size(); i++)
348 retval.push (cols[i].pcol_l_);
349 for (int i=0; i < loose_col_arr_.size(); i++)
351 retval.push (loose_col_arr_[i].pcol_l_);
357 Spring_spacer::loosen_column (int i)
359 Colinfo c=cols.get (i);
360 for (PCursor<Idealspacing*> j (ideal_p_list_.top()); j.ok (); j++)
362 if (j->left_i_ == i|| j->right_i_ == i)
370 for (; j < loose_col_arr_.size(); j++)
372 if (loose_col_arr_[j].rank_i_ > c.rank_i_)
375 loose_col_arr_.insert (c,j);
380 Spring_spacer::print() const
383 for (int i=0; i < cols.size(); i++)
385 DOUT << "col " << i<<' ';
388 for (PCursor<Idealspacing*> i (ideal_p_list_.top()); i.ok (); i++)
397 Spring_spacer::connect (int i, int j, Real d, Real h)
399 assert(d >= 0 && d <= 100 CM);
402 Idealspacing * s = new Idealspacing;
409 ideal_p_list_.bottom().add (s);
416 Spring_spacer::prepare()
424 Spring_spacer::constructor()
426 return new Spring_spacer;
432 get the shortest_playing running note at a time. */
434 Spring_spacer::get_ruling_durations(Array<Moment> &shortest_playing_arr,
435 Array<Moment> &context_shortest_arr)
437 for (int i=0; i < cols.size(); i++)
439 scol_l (i)->preprocess();
440 scol_l (i)->print ();
442 int start_context_i=0;
443 Moment context_shortest;
444 context_shortest.set_infinite (1);
445 context_shortest_arr.set_size(cols.size());
447 for (int i=0; i < cols.size(); i++)
449 Moment now = scol_l (i)->when();
450 Moment shortest_playing;
451 shortest_playing.set_infinite (1);
453 if (scol_l (i)->breakable_b_)
455 for (int ji=i; ji >= start_context_i; ji--)
456 context_shortest_arr[ji] = context_shortest;
458 context_shortest.set_infinite (1);
460 if (scol_l (i)->durations.size())
462 context_shortest = context_shortest <? scol_l(i)->durations[0];
465 // ji was j, but triggered ICE
466 for (int ji=i+1; ji --;)
468 if (scol_l(ji)->durations.size() &&
469 now - scol_l(ji)->when() >= shortest_playing)
472 for (int k = scol_l (ji)->durations.size();
473 k-- && scol_l(ji)->durations[k] + scol_l(ji)->when() > now;
476 shortest_playing = shortest_playing <? scol_l(ji)->durations[k];
479 shortest_playing_arr.push(shortest_playing);
483 DOUT << "shortest_playing/:[ ";
484 for (int i=0; i < shortest_playing_arr.size(); i++)
486 DOUT << shortest_playing_arr[i] << " ";
487 DOUT << context_shortest_arr[i] << ", ";
494 generate springs between columns.
498 TODO: This needs rethinking. Spacing should take optical
499 effects into account, and should be local (measure wide)
501 The algorithm is taken from :
503 John S. Gourlay. ``Spacing a Line of Music,'' Technical Report
504 OSU-CISRC-10/87-TR35, Department of Computer and Information
505 Science, The Ohio State University, 1987.
509 Spring_spacer::calc_idealspacing()
511 Array<Moment> shortest_playing_arr;
512 Array<Moment> context_shortest_arr;
513 get_ruling_durations(shortest_playing_arr, context_shortest_arr);
515 Real interline_f = paper_l ()->interline_f ();
516 Real nw_f = paper_l ()->note_width ();
518 Array<Real> ideal_arr_;
519 Array<Real> hooke_arr_;
520 for (int i=0; i < cols.size() - 1; i++){
521 ideal_arr_.push (-1.0);
522 hooke_arr_.push (1.0);
526 First do all non-musical columns
528 for (int i=0; i < cols.size(); i++)
530 if (!scol_l (i)->musical_b() && i+1 < cols.size())
532 Real symbol_distance =cols[i].width_[RIGHT] + 2 PT;
533 Real durational_distance = 0;
536 Moment delta_t = scol_l (i+1)->when() - scol_l (i)->when () ;
538 Real k= paper_l()->arithmetic_constant(context_shortest_arr[i]);
540 ugh should use shortest_playing distance
543 durational_distance = paper_l()->duration_to_dist (delta_t,k);
544 symbol_distance += -cols[i+1].width_[LEFT];
547 ideal_arr_[i] = symbol_distance >? durational_distance;
548 hooke_arr_[i] = 1; //2.0;
555 for (int i=0; i < cols.size(); i++)
557 if (scol_l (i)->musical_b())
559 Moment shortest_playing_len = shortest_playing_arr[i];
560 Moment context_shortest = context_shortest_arr[i];
561 if (! shortest_playing_len)
563 warning (_("Can't find a ruling note at ")
564 +scol_l (i)->when().str ());
565 shortest_playing_len = 1;
567 if (! context_shortest)
569 warning(_("No minimum in measure at ")
570 + scol_l (i)->when().str ());
571 context_shortest = 1;
573 Moment delta_t = scol_l (i+1)->when() - scol_l (i)->when ();
574 Real k= paper_l()->arithmetic_constant(context_shortest);
575 Real dist = paper_l()->duration_to_dist (shortest_playing_len, k);
576 dist *= delta_t / shortest_playing_len;
579 According to [Ross] and [Wanske], and from what i've seen:
581 * whitespace at the begin of the bar should be fixed at
582 (about) one interline.
584 when spacing gets real tight, a smaller fixed value may be
585 used, so that there are two discrete amounts of whitespace
586 possible at the begin of a bar; but this is not implemented
589 * whitespace at the end of the bar is the normal amount of
590 "hinterfleish" that would have been used, had there been
591 yet another note in the bar.
593 some editors argue that the bar line should not take any
594 space, not to hinder the flow of music spaced around a bar
596 [Ross] and [Wanske] do not suggest this, however. Further,
597 it introduces some spacing problems and think that it is ugly
603 first musical column of bar
605 if (i && scol_l (i - 1)->breakable_b_)
607 // fixed: probably should set minimum (rod/spring)?
608 cols[i-1].width_[RIGHT] += interline_f;
609 // should adjust dist too?
610 ideal_arr_[i-1] = ideal_arr_[i-1] >? interline_f;
614 last musical column of bar
616 if (i + 1 < cols.size () && scol_l(i+1)->breakable_b_)
619 dist = dist >? interline_f;
622 uhuh, this code looks fine, already?
623 someone was junking this last "hinterfleisch" whitespace?!
625 but this seems to be fixed now :-)
628 cols[i].width_[RIGHT] += interline_f;
631 // ugh, do we need this?
632 if (i < cols.size () - 1 && !scol_l (i + 1)->musical_b ())
634 Real minimum = -cols[i + 1].width_[LEFT] + cols[i].width_[RIGHT]
636 dist = dist >? minimum;
639 // ugh: never let columns touch... try to set over here...
640 // ugh: use j iso i triggers ice in gcc-2.7.2.3
641 cols[i].width_[LEFT] -= nw_f / 4;
642 ideal_arr_[i] = dist;
646 for (int i=0; i < ideal_arr_.size(); i++)
648 assert (ideal_arr_[i] >=0 && hooke_arr_[i] >=0);
649 connect (i, i+1, ideal_arr_[i], hooke_arr_[i]);