2 This file is part of LilyPond, the GNU music typesetter.
4 Copyright (C) 1997--2011 Han-Wen Nienhuys <hanwen@xs4all.nl>
5 Jan Nieuwenhuizen <janneke@gnu.org>
7 LilyPond is free software: you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation, either version 3 of the License, or
10 (at your option) any later version.
12 LilyPond is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with LilyPond. If not, see <http://www.gnu.org/licenses/>.
21 #include "beam-scoring-problem.hh"
27 #include "align-interface.hh"
30 #include "international.hh"
32 #include "output-def.hh"
33 #include "pointer-group-interface.hh"
34 #include "staff-symbol-referencer.hh"
39 get_detail (SCM alist, SCM sym, Real def)
41 SCM entry = scm_assq (sym, alist);
43 if (scm_is_pair (entry))
44 return robust_scm2double (scm_cdr (entry), def);
49 Beam_quant_parameters::fill (Grob *him)
51 SCM details = him->get_property ("details");
53 SECONDARY_BEAM_DEMERIT = get_detail (details, ly_symbol2scm ("secondary-beam-demerit"), 10.0);
54 STEM_LENGTH_DEMERIT_FACTOR = get_detail (details, ly_symbol2scm ("stem-length-demerit-factor"), 5);
55 REGION_SIZE = get_detail (details, ly_symbol2scm ("region-size"), 2);
56 BEAM_EPS = get_detail (details, ly_symbol2scm ("beam-eps"), 1e-3);
57 STEM_LENGTH_LIMIT_PENALTY = get_detail (details, ly_symbol2scm ("stem-length-limit-penalty"), 5000);
58 DAMPING_DIRECTION_PENALTY = get_detail (details, ly_symbol2scm ("damping-direction-penalty"), 800);
59 HINT_DIRECTION_PENALTY = get_detail (details, ly_symbol2scm ("hint-direction-penalty"), 20);
60 MUSICAL_DIRECTION_FACTOR = get_detail (details, ly_symbol2scm ("musical-direction-factor"), 400);
61 IDEAL_SLOPE_FACTOR = get_detail (details, ly_symbol2scm ("ideal-slope-factor"), 10);
62 ROUND_TO_ZERO_SLOPE = get_detail (details, ly_symbol2scm ("round-to-zero-slope"), 0.02);
66 shrink_extra_weight (Real x, Real fac)
68 return fabs (x) * ((x < 0) ? fac : 1.0);
71 /****************************************************************/
73 Beam_configuration::Beam_configuration ()
75 y = Interval (0.0, 0.0);
77 next_scorer_todo = ORIGINAL_DISTANCE;
80 bool Beam_configuration::done () const
82 return next_scorer_todo >= NUM_SCORERS;
85 void Beam_configuration::add (Real demerit, const string &reason)
89 #if DEBUG_BEAM_SCORING
91 score_card_ += to_string (" %s %.2f", reason.c_str (), demerit);
95 Beam_configuration* Beam_configuration::new_config (Interval start,
98 Beam_configuration* qs = new Beam_configuration;
99 qs->y = Interval (int (start[LEFT]) + offset[LEFT],
100 int (start[RIGHT]) + offset[RIGHT]);
102 // This orders the sequence so we try combinations closest to the
103 // the ideal offset first.
104 Real start_score = abs (offset[RIGHT]) + abs (offset[LEFT]);
105 qs->demerits = start_score / 1000.0;
106 qs->next_scorer_todo = ORIGINAL_DISTANCE + 1;
111 /****************************************************************/
116 - Make all demerits customisable
118 - One sensible check per demerit (what's this --hwn)
120 - Add demerits for quants per se, as to forbid a specific quant
124 best_quant_score_idx (vector<Beam_configuration*> const &configs)
128 for (vsize i = configs.size (); i--;)
130 if (configs[i]->demerits < best)
132 best = configs [i]->demerits;
140 // This is a temporary hack to see how much we can gain by using a
141 // priority queue on the beams to score.
142 static int score_count = 0;
143 LY_DEFINE (ly_beam_score_count, "ly:beam-score-count", 0, 0, 0,
145 "count number of beam scores.") {
146 return scm_from_int (score_count);
149 void Beam_scoring_problem::init_stems ()
151 extract_grob_set (beam, "stems", stems);
152 for (int a = 2; a--;)
153 common[a] = common_refpoint_of_array (stems, beam, Axis (a));
155 Grob *fvs = Beam::first_normal_stem (beam);
156 Grob *lvs = Beam::last_normal_stem (beam);
158 x_span = Interval (fvs ? fvs->relative_coordinate (common[X_AXIS], X_AXIS) : 0.0,
159 lvs ? lvs->relative_coordinate (common[X_AXIS], X_AXIS) : 0.0);
161 Drul_array<bool> dirs_found (0, 0);
162 for (vsize i = 0; i < stems.size (); i++)
165 if (!Stem::is_normal_stem (s))
168 Stem_info si (Stem::get_stem_info (s));
169 si.scale (1 / staff_space);
170 stem_infos.push_back (si);
171 dirs_found[si.dir_] = true;
173 bool f = to_boolean (s->get_property ("french-beaming"))
174 && s != lvs && s != fvs;
176 Real y = Beam::calc_stem_y (beam, s, common, x_span[LEFT], x_span[RIGHT], CENTER,
178 base_lengths.push_back (y / staff_space);
179 stem_xpositions.push_back (s->relative_coordinate (common[X_AXIS], X_AXIS));
182 edge_dirs = Drul_array<Direction> (CENTER, CENTER);
183 if (stem_infos.size ())
185 edge_dirs = Drul_array<Direction> (stem_infos[0].dir_,
186 stem_infos.back().dir_);
189 is_xstaff = Align_interface::has_interface (common[Y_AXIS]);
190 is_knee = dirs_found[LEFT] && dirs_found[RIGHT];
192 staff_radius = Staff_symbol_referencer::staff_radius (beam);
193 edge_beam_counts = Drul_array<int>
194 (Stem::beam_multiplicity (stems[0]).length () + 1,
195 Stem::beam_multiplicity (stems.back ()).length () + 1);
197 beam_translation = Beam::get_beam_translation (beam) / staff_space;
200 Beam_scoring_problem::Beam_scoring_problem (Grob *me, Drul_array<Real> ys)
206 Calculations are relative to a unit-scaled staff, i.e. the quants are
207 divided by the current staff_space.
209 staff_space = Staff_symbol_referencer::staff_space (me);
210 beam_thickness = Beam::get_beam_thickness (me) / staff_space;
211 line_thickness = Staff_symbol_referencer::line_thickness (me) / staff_space;
213 // This is the least-squares DY, corrected for concave beams.
214 musical_dy = robust_scm2double (me->get_property ("least-squares-dy"), 0);
216 parameters.fill (me);
221 Beam_scoring_problem::generate_quants (vector<Beam_configuration*> *scores) const
223 int region_size = (int) parameters.REGION_SIZE;
226 Knees are harder, lets try some more possibilities for knees.
232 Real sit = (beam_thickness - line_thickness) / 2;
234 Real hang = 1.0 - (beam_thickness - line_thickness) / 2;
235 Real base_quants [] = {straddle, sit, inter, hang};
236 int num_base_quants = int (sizeof (base_quants) / sizeof (Real));
239 Asymetry ? should run to <= region_size ?
241 vector<Real> unshifted_quants;
242 for (int i = -region_size; i < region_size; i++)
243 for (int j = 0; j < num_base_quants; j++)
245 unshifted_quants.push_back (i + base_quants[j]);
248 for (vsize i = 0; i < unshifted_quants.size (); i++)
249 for (vsize j = 0; j < unshifted_quants.size (); j++)
250 scores->push_back (Beam_configuration::new_config (unquanted_y,
251 Interval (unshifted_quants[i],
252 unshifted_quants[j])));
256 void Beam_scoring_problem::one_scorer (Beam_configuration* config) const
259 switch (config->next_scorer_todo) {
261 score_slopes_dy (config);
264 score_forbidden_quants (config);
267 score_stem_lengths (config);
271 case ORIGINAL_DISTANCE:
275 config->next_scorer_todo++;
280 Beam_scoring_problem::force_score (SCM inspect_quants, const vector<Beam_configuration*> &configs) const
282 Drul_array<Real> ins = ly_scm2interval (inspect_quants);
284 Beam_configuration *best = NULL;
285 for (vsize i = 0; i < configs.size (); i++)
287 Real d = fabs (configs[i]->y[LEFT]- ins[LEFT]) + fabs (configs[i]->y[RIGHT] - ins[RIGHT]);
295 programming_error ("cannot find quant");
301 Beam_scoring_problem::solve () const {
302 vector<Beam_configuration*> configs;
303 generate_quants (&configs);
305 Beam_configuration *best = NULL;
307 SCM inspect_quants = beam->get_property ("inspect-quants");
308 if (to_boolean (beam->layout ()->lookup_variable (ly_symbol2scm ("debug-beam-scoring")))
309 && scm_is_pair (inspect_quants))
311 best = force_score (inspect_quants, configs);
315 std::priority_queue<Beam_configuration*, std::vector<Beam_configuration*>,
316 Beam_configuration_less> queue;
317 for (vsize i = 0; i < configs.size(); i++)
318 queue.push(configs[i]);
324 It would be neat if we generated new configurations on the
325 fly, depending on the best complete score so far, eg.
328 if (best->demerits < sqrt(queue.size())
330 while (best->demerits > sqrt(queue.size()) {
331 generate and insert new configuration
335 that would allow us to do away with region_size altogether.
348 Interval final_positions = best->y;
350 #if DEBUG_BEAM_SCORING
351 if (to_boolean (beam->layout ()->lookup_variable (ly_symbol2scm ("debug-beam-scoring"))))
355 for (vsize i = 0; i < configs.size (); i++)
357 if (configs[i]->done ())
361 string card = best->score_card_ + to_string (" c%d/%d", completed, configs.size());
362 beam->set_property ("quant-score", ly_string2scm (card));
366 junk_pointers (configs);
367 return final_positions;
371 Beam_scoring_problem::score_stem_lengths (Beam_configuration* config) const
373 Real limit_penalty = parameters.STEM_LENGTH_LIMIT_PENALTY;
374 Drul_array<Real> score (0, 0);
375 Drul_array<int> count (0, 0);
377 for (vsize i = 0; i < stem_xpositions.size (); i++)
379 Real x = stem_xpositions[i];
380 Real dx = x_span.delta ();
382 ? config->y[RIGHT] * (x - x_span[LEFT]) / dx + config->y[LEFT] * (x_span[RIGHT] - x) / dx
383 : (config->y[RIGHT] + config->y[LEFT]) / 2;
384 Real current_y = beam_y + base_lengths[i];
385 Real length_pen = parameters.STEM_LENGTH_DEMERIT_FACTOR;
387 Stem_info info = stem_infos[i];
388 Direction d = info.dir_;
390 score[d] += limit_penalty * max (0.0, (d * (info.shortest_y_ - current_y)));
392 Real ideal_diff = d * (current_y - info.ideal_y_);
393 Real ideal_score = shrink_extra_weight (ideal_diff, 1.5);
395 /* We introduce a power, to make the scoring strictly
396 convex. Otherwise a symmetric knee beam (up/down/up/down)
397 does not have an optimum in the middle. */
399 ideal_score = pow (ideal_score, 1.1);
401 score[d] += length_pen * ideal_score;
405 /* Divide by number of stems, to make the measure scale-free. */
408 score[d] /= max (count[d], 1);
409 while (flip (&d) != DOWN);
411 config->add (score[LEFT] + score[RIGHT], "L");
415 Beam_scoring_problem::score_slopes_dy (Beam_configuration *config) const
417 Real dy = config->y.delta ();
418 Real damped_dy = unquanted_y.delta();
422 DAMPING_DIRECTION_PENALTY is a very harsh measure, while for
423 complex beaming patterns, horizontal is often a good choice.
425 TODO: find a way to incorporate the complexity of the beam in this
428 if (sign (damped_dy) != sign (dy))
432 if (fabs (damped_dy / x_span.delta ()) > parameters.ROUND_TO_ZERO_SLOPE)
433 dem += parameters.DAMPING_DIRECTION_PENALTY;
435 dem += parameters.HINT_DIRECTION_PENALTY;
438 dem += parameters.DAMPING_DIRECTION_PENALTY;
441 dem += parameters.MUSICAL_DIRECTION_FACTOR
442 * max (0.0, (fabs (dy) - fabs (musical_dy)));
444 Real slope_penalty = parameters.IDEAL_SLOPE_FACTOR;
446 /* Xstaff beams tend to use extreme slopes to get short stems. We
447 put in a penalty here. */
451 /* Huh, why would a too steep beam be better than a too flat one ? */
452 dem += shrink_extra_weight (fabs (damped_dy) - fabs (dy), 1.5)
455 config->add (dem, "S");
461 return x - floor (x);
465 TODO: The fixed value SECONDARY_BEAM_DEMERIT is probably flawed:
466 because for 32nd and 64th beams the forbidden quants are relatively
467 more important than stem lengths.
470 Beam_scoring_problem::score_forbidden_quants (Beam_configuration *config) const
472 Real dy = config->y.delta ();
474 Real extra_demerit = parameters.SECONDARY_BEAM_DEMERIT /
475 max (edge_beam_counts[LEFT], edge_beam_counts[RIGHT]);
479 Real eps = parameters.BEAM_EPS;
483 for (int j = 1; j <= edge_beam_counts[d]; j++)
485 Direction stem_dir = edge_dirs[d];
488 The 2.2 factor is to provide a little leniency for
489 borderline cases. If we do 2.0, then the upper outer line
490 will be in the gap of the (2, sit) quant, leading to a
493 Real gap1 = config->y[d] - stem_dir * ((j - 1) * beam_translation + beam_thickness / 2 - line_thickness / 2.2);
494 Real gap2 = config->y[d] - stem_dir * (j * beam_translation - beam_thickness / 2 + line_thickness / 2.2);
497 gap.add_point (gap1);
498 gap.add_point (gap2);
500 for (Real k = -staff_radius;
501 k <= staff_radius + eps; k += 1.0)
502 if (gap.contains (k))
504 Real dist = min (fabs (gap[UP] - k), fabs (gap[DOWN] - k));
507 this parameter is tuned to grace-stem-length.ly
509 Real fixed_demerit = 0.4;
513 + (1 - fixed_demerit) * (dist / gap.length ()) * 2);
517 while ((flip (&d)) != LEFT);
519 if (max (edge_beam_counts[LEFT], edge_beam_counts[RIGHT]) >= 2)
522 Real sit = (beam_thickness - line_thickness) / 2;
524 Real hang = 1.0 - (beam_thickness - line_thickness) / 2;
529 if (edge_beam_counts[d] >= 2
530 && fabs (config->y[d] - edge_dirs[d] * beam_translation) < staff_radius + inter)
532 // TODO up/down symmetry.
533 if (edge_dirs[d] == UP && dy <= eps
534 && fabs (my_modf (config->y[d]) - sit) < eps)
535 dem += extra_demerit;
537 if (edge_dirs[d] == DOWN && dy >= eps
538 && fabs (my_modf (config->y[d]) - hang) < eps)
539 dem += extra_demerit;
542 if (edge_beam_counts[d] >= 3
543 && fabs (config->y[d] - 2 * edge_dirs[d] * beam_translation) < staff_radius + inter)
545 // TODO up/down symmetry.
546 if (edge_dirs[d] == UP && dy <= eps
547 && fabs (my_modf (config->y[d]) - straddle) < eps)
548 dem += extra_demerit;
550 if (edge_dirs[d] == DOWN && dy >= eps
551 && fabs (my_modf (config->y[d]) - straddle) < eps)
552 dem += extra_demerit;
555 while (flip (&d) != LEFT);
558 config->add (dem, "F");