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 Real nw_f
= paper_l ()->note_width ();
253 for (int j
=0; j
< dim
; j
++)
263 lp
.add_inequality_cons (c1
, cols
[j
-1].width_
[RIGHT
]
264 - cols
[j
].width_
[LEFT
]);
271 Spring_spacer::calculate_energy_f (Vector solution
) const
274 for (PCursor
<Idealspacing
*> i (ideal_p_list_
.top()); i
.ok(); i
++)
276 e
+= i
->energy_f(solution(i
->right_i_
) - solution(i
->left_i_
));
282 Spring_spacer::lower_bound_solution (Col_hpositions
*positions
) const
284 Mixed_qp
lp (cols
.size());
285 make_matrices (lp
.quad
,lp
.lin
, lp
.const_term
);
288 Vector
start (cols
.size());
290 Vector
solution_vec (lp
.solve (start
));
292 DOUT
<< "Lower bound sol: " << solution_vec
;
293 positions
->energy_f_
= calculate_energy_f (solution_vec
);
294 positions
->config
= solution_vec
;
295 positions
->satisfies_constraints_b_
= check_constraints (solution_vec
);
299 Spring_spacer::solve (Col_hpositions
*positions
) const
301 Vector
solution_try (try_initial_solution());
303 if (check_constraints (solution_try
))
305 Mixed_qp
lp (cols
.size());
306 make_matrices (lp
.quad
,lp
.lin
, lp
.const_term
);
307 make_constraints (lp
);
310 Vector
solution_vec (lp
.solve (solution_try
));
313 positions
->satisfies_constraints_b_
= check_constraints (solution_vec
);
314 if (!positions
->satisfies_constraints_b_
)
316 WARN
<< _("solution doesn't satisfy constraints.\n") ;
318 position_loose_cols (solution_vec
);
319 positions
->energy_f_
= calculate_energy_f (solution_vec
);
320 positions
->config
= solution_vec
;
321 positions
->error_col_l_arr_
= error_pcol_l_arr();
325 positions
->set_stupid_solution (solution_try
);
330 add one column to the problem.
333 Spring_spacer::add_column (Paper_column
*col
, bool fixed
, Real fixpos
)
335 Colinfo
c (col
,(fixed
)? &fixpos
: 0);
337 c
.rank_i_
= cols
.top().rank_i_
+1;
344 Spring_spacer::error_pcol_l_arr() const
346 Array
<Paper_column
*> retval
;
347 for (int i
=0; i
< cols
.size(); i
++)
349 retval
.push (cols
[i
].pcol_l_
);
350 for (int i
=0; i
< loose_col_arr_
.size(); i
++)
352 retval
.push (loose_col_arr_
[i
].pcol_l_
);
358 Spring_spacer::loosen_column (int i
)
360 Colinfo c
=cols
.get (i
);
361 for (PCursor
<Idealspacing
*> j (ideal_p_list_
.top()); j
.ok (); j
++)
363 if (j
->left_i_
== i
|| j
->right_i_
== i
)
371 for (; j
< loose_col_arr_
.size(); j
++)
373 if (loose_col_arr_
[j
].rank_i_
> c
.rank_i_
)
376 loose_col_arr_
.insert (c
,j
);
381 Spring_spacer::print() const
384 for (int i
=0; i
< cols
.size(); i
++)
386 DOUT
<< "col " << i
<<' ';
389 for (PCursor
<Idealspacing
*> i (ideal_p_list_
.top()); i
.ok (); i
++)
398 Spring_spacer::connect (int i
, int j
, Real d
, Real h
)
400 assert(d
>= 0 && d
<= 100 CM
);
403 Idealspacing
* s
= new Idealspacing
;
410 ideal_p_list_
.bottom().add (s
);
417 Spring_spacer::prepare()
425 Spring_spacer::constructor()
427 return new Spring_spacer
;
433 get the shortest_playing running note at a time. */
435 Spring_spacer::get_ruling_durations(Array
<Moment
> &shortest_playing_arr
,
436 Array
<Moment
> &context_shortest_arr
)
438 for (int i
=0; i
< cols
.size(); i
++)
440 scol_l (i
)->preprocess();
441 scol_l (i
)->print ();
443 int start_context_i
=0;
444 Moment context_shortest
= infinity_mom
;
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
= infinity_mom
;
452 if (scol_l (i
)->breakable_b_
)
454 for (int ji
=i
; ji
>= start_context_i
; ji
--)
455 context_shortest_arr
[ji
] = context_shortest
;
457 context_shortest
= infinity_mom
;
459 if (scol_l (i
)->durations
.size())
461 context_shortest
= context_shortest
<? scol_l(i
)->durations
[0];
464 // ji was j, but triggered ICE
465 for (int ji
=i
+1; ji
--;)
467 if (scol_l(ji
)->durations
.size() &&
468 now
- scol_l(ji
)->when() >= shortest_playing
)
471 for (int k
= scol_l (ji
)->durations
.size();
472 k
-- && scol_l(ji
)->durations
[k
] + scol_l(ji
)->when() > now
;
475 shortest_playing
= shortest_playing
<? scol_l(ji
)->durations
[k
];
478 shortest_playing_arr
.push(shortest_playing
);
482 DOUT
<< "shortest_playing/:[ ";
483 for (int i
=0; i
< shortest_playing_arr
.size(); i
++)
485 DOUT
<< shortest_playing_arr
[i
] << " ";
486 DOUT
<< context_shortest_arr
[i
] << ", ";
493 generate springs between columns.
497 TODO: This needs rethinking. Spacing should take optical
498 effects into account, and should be local (measure wide)
500 The algorithm is taken from :
502 John S. Gourlay. ``Spacing a Line of Music,'' Technical Report
503 OSU-CISRC-10/87-TR35, Department of Computer and Information
504 Science, The Ohio State University, 1987.
508 Spring_spacer::calc_idealspacing()
510 Array
<Moment
> shortest_playing_arr
;
511 Array
<Moment
> context_shortest_arr
;
512 get_ruling_durations(shortest_playing_arr
, context_shortest_arr
);
514 Real interline_f
= paper_l ()->interline_f ();
515 Real nw_f
= paper_l ()->note_width ();
517 Array
<Real
> ideal_arr_
;
518 Array
<Real
> hooke_arr_
;
519 for (int i
=0; i
< cols
.size() - 1; i
++){
520 ideal_arr_
.push (-1.0);
521 hooke_arr_
.push (1.0);
525 First do all non-musical columns
527 for (int i
=0; i
< cols
.size(); i
++)
529 if (!scol_l (i
)->musical_b() && i
+1 < cols
.size())
531 Real symbol_distance
=cols
[i
].width_
[RIGHT
] + 2 PT
;
532 Real durational_distance
= 0;
535 Moment delta_t
= scol_l (i
+1)->when() - scol_l (i
)->when () ;
537 Real k
= paper_l()->arithmetic_constant(context_shortest_arr
[i
]);
539 ugh should use shortest_playing distance
542 durational_distance
= paper_l()->duration_to_dist (delta_t
,k
);
543 symbol_distance
+= -cols
[i
+1].width_
[LEFT
];
546 ideal_arr_
[i
] = symbol_distance
>? durational_distance
;
547 hooke_arr_
[i
] = 1; //2.0;
554 for (int i
=0; i
< cols
.size(); i
++)
556 if (scol_l (i
)->musical_b())
558 Moment shortest_playing_len
= shortest_playing_arr
[i
];
559 Moment context_shortest
= context_shortest_arr
[i
];
560 if (! shortest_playing_len
)
562 warning (_("Can't find a ruling note at ")
563 +String (scol_l (i
)->when()));
564 shortest_playing_len
= 1;
566 if (! context_shortest
)
568 warning(_("No minimum in measure at ")
569 + String (scol_l (i
)->when()));
570 context_shortest
= 1;
572 Moment delta_t
= scol_l (i
+1)->when() - scol_l (i
)->when ();
573 Real k
= paper_l()->arithmetic_constant(context_shortest
);
574 Real dist
= paper_l()->duration_to_dist (shortest_playing_len
, k
);
575 dist
*= delta_t
/ shortest_playing_len
;
578 According to [Ross] and [Wanske], and from what i've seen:
580 * whitespace at the begin of the bar should be fixed at
581 (about) one interline.
583 when spacing gets real tight, a smaller fixed value may be
584 used, so that there are two discrete amounts of whitespace
585 possible at the begin of a bar; but this is not implemented
588 * whitespace at the end of the bar is the normal amount of
589 "hinterfleish" that would have been used, had there been
590 yet another note in the bar.
592 some editors argue that the bar line should not take any
593 space, not to hinder the flow of music spaced around a bar
595 [Ross] and [Wanske] do not suggest this, however. Further,
596 it introduces some spacing problems and think that it is ugly
602 first musical column of bar
604 if (i
&& scol_l (i
- 1)->breakable_b_
)
606 // fixed: probably should set minimum (rod/spring)?
607 cols
[i
-1].width_
[RIGHT
] += interline_f
;
608 // should adjust dist too?
609 ideal_arr_
[i
-1] = ideal_arr_
[i
-1] >? interline_f
;
613 last musical column of bar
615 if (i
+ 1 < cols
.size () && scol_l(i
+1)->breakable_b_
)
618 dist
= dist
>? interline_f
;
621 uhuh, this code looks fine, already?
622 someone was junking this last "hinterfleisch" whitespace?!
624 but this seems to be fixed now :-)
627 cols
[i
].width_
[RIGHT
] += interline_f
;
630 // ugh, do we need this?
631 if (i
< cols
.size () - 1 && !scol_l (i
+ 1)->musical_b ())
633 Real minimum
= -cols
[i
+ 1].width_
[LEFT
] + cols
[i
].width_
[RIGHT
]
635 dist
= dist
>? minimum
;
638 ideal_arr_
[i
] = dist
;
642 for (int i
=0; i
< ideal_arr_
.size(); i
++)
644 assert (ideal_arr_
[i
] >=0 && hooke_arr_
[i
] >=0);
645 connect (i
, i
+1, ideal_arr_
[i
], hooke_arr_
[i
]);