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 = infinity_mom;
444 context_shortest_arr.set_size(cols.size());
446 for (int i=0; i < cols.size(); i++)
448 Moment now = scol_l (i)->when();
449 Moment shortest_playing = infinity_mom;
451 if (scol_l (i)->breakable_b_)
453 for (int ji=i; ji >= start_context_i; ji--)
454 context_shortest_arr[ji] = context_shortest;
456 context_shortest = infinity_mom;
458 if (scol_l (i)->durations.size())
460 context_shortest = context_shortest <? scol_l(i)->durations[0];
463 // ji was j, but triggered ICE
464 for (int ji=i+1; ji --;)
466 if (scol_l(ji)->durations.size() &&
467 now - scol_l(ji)->when() >= shortest_playing)
470 for (int k = scol_l (ji)->durations.size();
471 k-- && scol_l(ji)->durations[k] + scol_l(ji)->when() > now;
474 shortest_playing = shortest_playing <? scol_l(ji)->durations[k];
477 shortest_playing_arr.push(shortest_playing);
481 DOUT << "shortest_playing/:[ ";
482 for (int i=0; i < shortest_playing_arr.size(); i++)
484 DOUT << shortest_playing_arr[i] << " ";
485 DOUT << context_shortest_arr[i] << ", ";
492 generate springs between columns.
496 TODO: This needs rethinking. Spacing should take optical
497 effects into account, and should be local (measure wide)
499 The algorithm is taken from :
501 John S. Gourlay. ``Spacing a Line of Music,'' Technical Report
502 OSU-CISRC-10/87-TR35, Department of Computer and Information
503 Science, The Ohio State University, 1987.
507 Spring_spacer::calc_idealspacing()
509 Array<Moment> shortest_playing_arr;
510 Array<Moment> context_shortest_arr;
511 get_ruling_durations(shortest_playing_arr, context_shortest_arr);
513 Real interline_f = paper_l ()->interline_f ();
514 Real nw_f = paper_l ()->note_width ();
516 Array<Real> ideal_arr_;
517 Array<Real> hooke_arr_;
518 for (int i=0; i < cols.size() - 1; i++){
519 ideal_arr_.push (-1.0);
520 hooke_arr_.push (1.0);
524 First do all non-musical columns
526 for (int i=0; i < cols.size(); i++)
528 if (!scol_l (i)->musical_b() && i+1 < cols.size())
530 Real symbol_distance =cols[i].width_[RIGHT] + 2 PT;
531 Real durational_distance = 0;
534 Moment delta_t = scol_l (i+1)->when() - scol_l (i)->when () ;
536 Real k= paper_l()->arithmetic_constant(context_shortest_arr[i]);
538 ugh should use shortest_playing distance
541 durational_distance = paper_l()->duration_to_dist (delta_t,k);
542 symbol_distance += -cols[i+1].width_[LEFT];
545 ideal_arr_[i] = symbol_distance >? durational_distance;
546 hooke_arr_[i] = 1; //2.0;
553 for (int i=0; i < cols.size(); i++)
555 if (scol_l (i)->musical_b())
557 Moment shortest_playing_len = shortest_playing_arr[i];
558 Moment context_shortest = context_shortest_arr[i];
559 if (! shortest_playing_len)
561 warning (_("Can't find a ruling note at ")
562 +String (scol_l (i)->when()));
563 shortest_playing_len = 1;
565 if (! context_shortest)
567 warning(_("No minimum in measure at ")
568 + String (scol_l (i)->when()));
569 context_shortest = 1;
571 Moment delta_t = scol_l (i+1)->when() - scol_l (i)->when ();
572 Real k= paper_l()->arithmetic_constant(context_shortest);
573 Real dist = paper_l()->duration_to_dist (shortest_playing_len, k);
574 dist *= delta_t / shortest_playing_len;
577 According to [Ross] and [Wanske], and from what i've seen:
579 * whitespace at the begin of the bar should be fixed at
580 (about) one interline.
582 when spacing gets real tight, a smaller fixed value may be
583 used, so that there are two discrete amounts of whitespace
584 possible at the begin of a bar; but this is not implemented
587 * whitespace at the end of the bar is the normal amount of
588 "hinterfleish" that would have been used, had there been
589 yet another note in the bar.
591 some editors argue that the bar line should not take any
592 space, not to hinder the flow of music spaced around a bar
594 [Ross] and [Wanske] do not suggest this, however. Further,
595 it introduces some spacing problems and think that it is ugly
601 first musical column of bar
603 if (i && scol_l (i - 1)->breakable_b_)
605 // fixed: probably should set minimum (rod/spring)?
606 cols[i-1].width_[RIGHT] += interline_f;
607 // should adjust dist too?
608 ideal_arr_[i-1] = ideal_arr_[i-1] >? interline_f;
612 last musical column of bar
614 if (i + 1 < cols.size () && scol_l(i+1)->breakable_b_)
617 dist = dist >? interline_f;
620 uhuh, this code looks fine, already?
621 someone was junking this last "hinterfleisch" whitespace?!
623 but this seems to be fixed now :-)
626 cols[i].width_[RIGHT] += interline_f;
629 // ugh, do we need this?
630 if (i < cols.size () - 1 && !scol_l (i + 1)->musical_b ())
632 Real minimum = -cols[i + 1].width_[LEFT] + cols[i].width_[RIGHT]
634 dist = dist >? minimum;
637 // ugh: never let columns touch... try to set over here...
638 // ugh: use j iso i triggers ice in gcc-2.7.2.3
639 cols[i].width_[LEFT] -= nw_f / 4;
640 ideal_arr_[i] = dist;
644 for (int i=0; i < ideal_arr_.size(); i++)
646 assert (ideal_arr_[i] >=0 && hooke_arr_[i] >=0);
647 connect (i, i+1, ideal_arr_[i], hooke_arr_[i]);