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"
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);
179 Spring_spacer::check_feasible() const
181 Vector sol (try_initial_solution());
182 return check_constraints (sol);
185 /// generate a solution which obeys the min distances and fixed positions
187 Spring_spacer::try_initial_solution() const
190 Vector initsol (dim);
191 for (int i=0; i < dim; i++)
195 initsol (i)=cols[i].fixed_position();
199 Real r =initsol (i-1) + cols[i-1].width_[RIGHT];
202 warning ("overriding fixed position");
210 Real mindist=cols[i-1].width_[RIGHT]
211 - cols[i].width_[LEFT];
213 warning ("Excentric column");
214 initsol (i)=initsol (i-1)+mindist;
224 Spring_spacer::find_initial_solution() const
226 Vector v (try_initial_solution());
227 assert (check_constraints (v));
231 // generate the matrices
233 Spring_spacer::make_matrices (Matrix &quad, Vector &lin, Real &c) const
239 for (PCursor<Idealspacing*> i (ideal_p_list_.top()); i.ok (); i++)
244 quad (r,r) += i->hooke_f_;
245 quad (r,l) -= i->hooke_f_;
246 quad (l,r) -= i->hooke_f_;
247 quad (l,l) += i->hooke_f_;
249 lin (r) -= i->space_f_*i->hooke_f_;
250 lin (l) += i->space_f_*i->hooke_f_;
252 c += sqr (i->space_f_);
257 Spring_spacer::set_fixed_cols (Mixed_qp &qp) const
259 for (int j=0; j < cols.size(); j++)
261 qp.add_fixed_var (j,cols[j].fixed_position());
266 // put the constraints into the LP problem
268 Spring_spacer::make_constraints (Mixed_qp& lp) const
271 for (int j=0; j < dim; j++)
280 lp.add_inequality_cons (c1,
281 cols[j-1].width_[RIGHT] - cols[j].width_[LEFT]);
288 Spring_spacer::calculate_energy_f (Vector solution) const
291 for (PCursor<Idealspacing*> i (ideal_p_list_.top()); i.ok(); i++)
293 e += i->energy_f(solution(i->right_i_) - solution(i->left_i_));
299 Spring_spacer::lower_bound_solution (Col_hpositions*positions) const
301 Mixed_qp lp (cols.size());
302 make_matrices (lp.quad,lp.lin, lp.const_term);
305 Vector start (cols.size());
307 Vector solution_vec (lp.solve (start));
309 positions->energy_f_ = calculate_energy_f (solution_vec);
310 positions->config = solution_vec;
311 positions->satisfies_constraints_b_ = check_constraints (solution_vec);
315 Spring_spacer::solve (Col_hpositions*positions) const
317 assert (check_feasible());
319 Mixed_qp lp (cols.size());
320 make_matrices (lp.quad,lp.lin, lp.const_term);
321 make_constraints (lp);
323 Vector start=find_initial_solution();
324 Vector solution_vec (lp.solve (start));
327 positions->satisfies_constraints_b_ = check_constraints (solution_vec);
328 if (!positions->satisfies_constraints_b_)
330 WARN << "solution doesn't satisfy constraints.\n" ;
332 position_loose_cols (solution_vec);
333 positions->energy_f_ = calculate_energy_f (solution_vec);
334 positions->config = solution_vec;
335 positions->error_col_l_arr_ = error_pcol_l_arr();
340 add one column to the problem.
343 Spring_spacer::add_column (Paper_column *col, bool fixed, Real fixpos)
345 Colinfo c (col,(fixed)? &fixpos : 0);
347 c.rank_i_ = cols.top().rank_i_+1;
354 Spring_spacer::error_pcol_l_arr() const
356 Array<Paper_column*> retval;
357 for (int i=0; i< cols.size(); i++)
359 retval.push (cols[i].pcol_l_);
360 for (int i=0; i < loose_col_arr_.size(); i++)
362 retval.push (loose_col_arr_[i].pcol_l_);
368 Spring_spacer::loosen_column (int i)
370 Colinfo c=cols.get (i);
371 for (PCursor<Idealspacing*> j (ideal_p_list_.top()); j.ok (); j++)
373 if (j->left_i_ == i|| j->right_i_ == i)
381 for (; j < loose_col_arr_.size(); j++)
383 if (loose_col_arr_[j].rank_i_ > c.rank_i_)
386 loose_col_arr_.insert (c,j);
391 Spring_spacer::print() const
394 for (int i=0; i < cols.size(); i++)
396 DOUT << "col " << i<<' ';
399 for (PCursor<Idealspacing*> i (ideal_p_list_.top()); i.ok (); i++)
408 Spring_spacer::connect (int i, int j, Real d, Real h)
410 assert(d >= 0 && d <= 100 CM);
413 Idealspacing * s = new Idealspacing;
419 ideal_p_list_.bottom().add (s);
426 Spring_spacer::prepare()
434 Spring_spacer::constructor()
436 return new Spring_spacer;
442 get the shortest_playing running note at a time. */
444 Spring_spacer::get_ruling_durations(Array<Moment> &shortest_playing_arr,
445 Array<Moment> &context_shortest_arr)
447 for (int i=0; i < cols.size(); i++)
448 scol_l (i)->preprocess();
450 int start_context_i=0;
451 Moment context_shortest = infinity_mom;
452 context_shortest_arr.set_size(cols.size());
454 for (int i=0; i < cols.size(); i++)
456 Moment now = scol_l (i)->when();
457 Moment shortest_playing = infinity_mom;
459 if (scol_l (i)->breakable_b_)
461 for (int ji=i; ji >= start_context_i; ji--)
462 context_shortest_arr[ji] = context_shortest;
464 context_shortest = infinity_mom;
466 if (scol_l (i)->durations.size())
468 context_shortest = context_shortest <? scol_l(i)->durations[0];
470 // ji was j, but triggered ICE
471 for (int ji=i+1; ji --;)
473 if (scol_l(ji)->durations.size() &&
474 now - scol_l(ji)->when() >= shortest_playing)
477 for (int k = scol_l (ji)->durations.size();
478 k-- && scol_l(ji)->durations[k] + scol_l(ji)->when() > now;
481 shortest_playing = shortest_playing <? scol_l(ji)->durations[k];
484 shortest_playing_arr.push(shortest_playing);
488 DOUT << "shortest_playing/:[ ";
489 for (int i=0; i < shortest_playing_arr.size(); i++)
491 DOUT << shortest_playing_arr[i] << " ";
492 DOUT << context_shortest_arr[i] << ", ";
499 generate springs between columns.
503 TODO: This needs rethinking. Spacing should take optical
504 effects into account, and should be local (measure wide)
506 The algorithm is taken from :
508 John S. Gourlay. ``Spacing a Line of Music,'' Technical Report
509 OSU-CISRC-10/87-TR35, Department of Computer and Information
510 Science, The Ohio State University, 1987.
514 Spring_spacer::calc_idealspacing()
516 Array<Moment> shortest_playing_arr;
517 Array<Moment> context_shortest_arr;
518 get_ruling_durations(shortest_playing_arr, context_shortest_arr);
521 Array<Real> ideal_arr_;
522 Array<Real> hooke_arr_;
523 for (int i=0; i < cols.size(); i++){
524 ideal_arr_.push (-1.0);
525 hooke_arr_.push (1.0);
528 for (int i=0; i < cols.size(); i++)
530 if (!scol_l (i)->musical_b())
532 Real symbol_distance =cols[i].width_[RIGHT] + 2 PT;
533 Real durational_distance = 0;
535 if (i+1 < cols.size())
537 Moment delta_t = scol_l (i+1)->when() - scol_l (i)->when () ;
539 Real k= paper_l()->arithmetic_constant(context_shortest_arr[i]);
541 ugh should use shortest_playing distance
544 durational_distance = paper_l()->duration_to_dist (delta_t,k);
545 symbol_distance += -cols[i+1].width_[LEFT];
548 ideal_arr_[i] = symbol_distance >? durational_distance;
552 for (int i=0; i < cols.size(); i++)
554 if (scol_l (i)->musical_b())
556 Moment shortest_playing_len = shortest_playing_arr[i];
557 Moment context_shortest = context_shortest_arr[i];
558 if (! shortest_playing_len)
560 warning ("Can't find a ruling note at "
561 +String (scol_l (i)->when()));
562 shortest_playing_len = 1;
564 if (! context_shortest)
566 warning("No minimum in measure at "
567 + String (scol_l (i)->when()));
568 context_shortest = 1;
570 Moment delta_t = scol_l (i+1)->when() - scol_l (i)->when ();
571 Real k= paper_l()->arithmetic_constant(context_shortest);
572 Real dist = paper_l()->duration_to_dist (shortest_playing_len, k);
573 dist *= delta_t / shortest_playing_len;
575 /* all sorts of ugliness to avoid running into bars/clefs, but not taking
576 extra space if this is not needed */
577 if (!scol_l (i+1)->musical_b())
579 Real minimum_dist = - cols[i+1].width_[LEFT] + 2 PT + cols[i].width_[RIGHT];
580 if (ideal_arr_[i+1] + minimum_dist < dist)
582 ideal_arr_[i] = dist - ideal_arr_[i+1];
583 // hooke_arr_[i+1] =1.0;
585 ideal_arr_[i] = minimum_dist;
589 ideal_arr_[i] = dist;
593 for (int i=0; i < ideal_arr_.size()-1; i++)
595 assert (ideal_arr_[i] >=0 && hooke_arr_[i] >=0);
596 connect (i, i+1, ideal_arr_[i], hooke_arr_[i]);