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"
28 #include "align-interface.hh"
30 #include "direction.hh"
31 #include "directional-element-interface.hh"
33 #include "international.hh"
34 #include "libc-extension.hh"
36 #include "output-def.hh"
37 #include "pointer-group-interface.hh"
38 #include "staff-symbol-referencer.hh"
44 get_detail (SCM alist, SCM sym, Real def)
46 SCM entry = scm_assq (sym, alist);
48 if (scm_is_pair (entry))
49 return robust_scm2double (scm_cdr (entry), def);
54 Beam_quant_parameters::fill (Grob *him)
56 SCM details = him->get_property ("details");
59 BEAM_EPS = get_detail (details, ly_symbol2scm ("beam-eps"), 1e-3);
60 REGION_SIZE = get_detail (details, ly_symbol2scm ("region-size"), 2);
63 SECONDARY_BEAM_DEMERIT = get_detail (details, ly_symbol2scm ("secondary-beam-demerit"), 10.0);
64 STEM_LENGTH_DEMERIT_FACTOR = get_detail (details, ly_symbol2scm ("stem-length-demerit-factor"), 5);
65 HORIZONTAL_INTER_QUANT_PENALTY = get_detail (details, ly_symbol2scm ("horizontal-inter-quant"), 500);
67 STEM_LENGTH_LIMIT_PENALTY = get_detail (details, ly_symbol2scm ("stem-length-limit-penalty"), 5000);
68 DAMPING_DIRECTION_PENALTY = get_detail (details, ly_symbol2scm ("damping-direction-penalty"), 800);
69 HINT_DIRECTION_PENALTY = get_detail (details, ly_symbol2scm ("hint-direction-penalty"), 20);
70 MUSICAL_DIRECTION_FACTOR = get_detail (details, ly_symbol2scm ("musical-direction-factor"), 400);
71 IDEAL_SLOPE_FACTOR = get_detail (details, ly_symbol2scm ("ideal-slope-factor"), 10);
72 ROUND_TO_ZERO_SLOPE = get_detail (details, ly_symbol2scm ("round-to-zero-slope"), 0.02);
75 COLLISION_PENALTY = get_detail (details, ly_symbol2scm ("collision-penalty"), 500);
76 COLLISION_PADDING = get_detail (details, ly_symbol2scm ("collision-padding"), 0.5);
77 STEM_COLLISION_FACTOR = get_detail (details, ly_symbol2scm ("stem-collision-factor"), 0.1);
80 // Add x if x is positive, add |x|*fac if x is negative.
82 shrink_extra_weight (Real x, Real fac)
84 return fabs (x) * ((x < 0) ? fac : 1.0);
87 /****************************************************************/
89 Beam_configuration::Beam_configuration ()
91 y = Interval (0.0, 0.0);
93 next_scorer_todo = ORIGINAL_DISTANCE;
96 bool Beam_configuration::done () const
98 return next_scorer_todo >= NUM_SCORERS;
101 void Beam_configuration::add (Real demerit, const string &reason)
105 #if DEBUG_BEAM_SCORING
107 score_card_ += to_string (" %s %.2f", reason.c_str (), demerit);
111 Beam_configuration *Beam_configuration::new_config (Interval start,
114 Beam_configuration *qs = new Beam_configuration;
115 qs->y = Interval (int (start[LEFT]) + offset[LEFT],
116 int (start[RIGHT]) + offset[RIGHT]);
118 // This orders the sequence so we try combinations closest to the
119 // the ideal offset first.
120 Real start_score = abs (offset[RIGHT]) + abs (offset[LEFT]);
121 qs->demerits = start_score / 1000.0;
122 qs->next_scorer_todo = ORIGINAL_DISTANCE + 1;
128 Beam_scoring_problem::y_at (Real x, Beam_configuration const *p) const
130 return p->y[LEFT] + (x - x_span[LEFT]) * p->y.delta () / x_span.delta ();
133 /****************************************************************/
138 - Make all demerits customisable
140 - Add demerits for quants per se, as to forbid a specific quant
144 // This is a temporary hack to see how much we can gain by using a
145 // priority queue on the beams to score.
146 static int score_count = 0;
147 LY_DEFINE (ly_beam_score_count, "ly:beam-score-count", 0, 0, 0,
149 "count number of beam scores.")
151 return scm_from_int (score_count);
154 void Beam_scoring_problem::add_collision (Real x, Interval y,
157 if (edge_dirs[LEFT] == edge_dirs[RIGHT])
159 Direction d = edge_dirs[LEFT];
161 Real quant_range_y = quant_range[LEFT][-d]
162 + (x - x_span[LEFT]) * (quant_range[RIGHT][-d] - quant_range[LEFT][-d]) / x_span.delta ();
164 if (d * (quant_range_y - minmax (d, y[UP], y[DOWN])) > 0)
171 c.beam_y_.set_empty ();
173 for (vsize j = 0; j < segments_.size (); j++)
175 if (segments_[j].horizontal_.contains (x))
176 c.beam_y_.add_point (segments_[j].vertical_count_ * beam_translation);
177 if (segments_[j].horizontal_[LEFT] > x)
180 c.beam_y_.widen (0.5 * beam_thickness);
184 y *= 1 / staff_space;
186 c.base_penalty_ = score_factor;
187 collisions_.push_back (c);
190 void Beam_scoring_problem::init_collisions (vector<Grob *> grobs)
192 Grob *common_x = NULL;
193 segments_ = Beam::get_beam_segments (beam, &common_x);
194 vector_sort (segments_, beam_segment_less);
195 if (common[X_AXIS] != common_x)
197 programming_error ("Disagree on common x. Skipping collisions in beam scoring.");
202 for (vsize i = 0; i < grobs.size (); i++)
205 for (Axis a = X_AXIS; a < NO_AXES; incr (a))
206 b[a] = grobs[i]->extent (common[a], a);
208 Real width = b[X_AXIS].length ();
209 Real width_factor = sqrt (width / staff_space);
213 add_collision (b[X_AXIS][d], b[Y_AXIS], width_factor);
214 while (flip (&d) != LEFT);
216 Grob *stem = unsmob_grob (grobs[i]->get_object ("stem"));
217 if (stem && Stem::has_interface (stem) && Stem::is_normal_stem (stem))
223 for (set<Grob *>::const_iterator it (stems.begin ()); it != stems.end (); it++)
226 Real x = s->extent (common[X_AXIS], X_AXIS).center ();
228 Direction stem_dir = get_grob_direction (*it);
231 y[-stem_dir] = Stem::chord_start_y (*it) + (*it)->relative_coordinate (common[Y_AXIS], Y_AXIS)
232 - beam->relative_coordinate (common[Y_AXIS], Y_AXIS);
234 Real factor = parameters.STEM_COLLISION_FACTOR;
235 if (!unsmob_grob (s->get_object ("beam"))
236 && !Stem::flag (s).is_empty ())
238 add_collision (x, y, factor);
242 void Beam_scoring_problem::init_stems ()
244 extract_grob_set (beam, "covered-grobs", collisions);
245 extract_grob_set (beam, "stems", stems);
246 for (int a = 2; a--;)
248 common[a] = common_refpoint_of_array (stems, beam, Axis (a));
249 common[a] = common_refpoint_of_array (collisions, common[a], Axis (a));
252 Drul_array<Grob *> edge_stems (Beam::first_normal_stem (beam),
253 Beam::last_normal_stem (beam));
256 x_span[d] = edge_stems[d] ? edge_stems[d]->relative_coordinate (common[X_AXIS], X_AXIS) : 0.0;
257 while (flip (&d) != LEFT);
259 Drul_array<bool> dirs_found (0, 0);
260 for (vsize i = 0; i < stems.size (); i++)
263 if (!Stem::is_normal_stem (s))
266 Stem_info si (Stem::get_stem_info (s));
267 si.scale (1 / staff_space);
268 stem_infos.push_back (si);
269 dirs_found[si.dir_] = true;
271 bool f = to_boolean (s->get_property ("french-beaming"))
272 && s != edge_stems[LEFT] && s != edge_stems[RIGHT];
274 Real y = Beam::calc_stem_y (beam, s, common, x_span[LEFT], x_span[RIGHT], CENTER,
276 base_lengths.push_back (y / staff_space);
277 stem_xpositions.push_back (s->relative_coordinate (common[X_AXIS], X_AXIS));
280 edge_dirs = Drul_array<Direction> (CENTER, CENTER);
281 if (stem_infos.size ())
283 edge_dirs = Drul_array<Direction> (stem_infos[0].dir_,
284 stem_infos.back ().dir_);
287 is_xstaff = Align_interface::has_interface (common[Y_AXIS]);
288 is_knee = dirs_found[LEFT] && dirs_found[RIGHT];
290 staff_radius = Staff_symbol_referencer::staff_radius (beam);
291 edge_beam_counts = Drul_array<int>
292 (Stem::beam_multiplicity (stems[0]).length () + 1,
293 Stem::beam_multiplicity (stems.back ()).length () + 1);
295 // TODO - why are we dividing by staff_space?
296 beam_translation = Beam::get_beam_translation (beam) / staff_space;
301 quant_range[d].set_full ();
305 Real stem_offset = edge_stems[d]->relative_coordinate (common[Y_AXIS], Y_AXIS)
306 - beam->relative_coordinate (common[Y_AXIS], Y_AXIS);
307 Interval heads = Stem::head_positions (edge_stems[d]) * 0.5 * staff_space;
309 Direction ed = edge_dirs[d];
310 heads.widen (0.5 * staff_space
311 + (edge_beam_counts[d] - 1) * beam_translation + beam_thickness * .5);
312 quant_range[d][-ed] = heads[ed] + stem_offset;
314 while (flip (&d) != LEFT);
316 init_collisions (collisions);
319 Beam_scoring_problem::Beam_scoring_problem (Grob *me, Drul_array<Real> ys)
325 Calculations are relative to a unit-scaled staff, i.e. the quants are
326 divided by the current staff_space.
328 staff_space = Staff_symbol_referencer::staff_space (me);
329 beam_thickness = Beam::get_beam_thickness (me) / staff_space;
330 line_thickness = Staff_symbol_referencer::line_thickness (me) / staff_space;
332 // This is the least-squares DY, corrected for concave beams.
333 musical_dy = robust_scm2double (me->get_property ("least-squares-dy"), 0);
335 parameters.fill (me);
340 Beam_scoring_problem::generate_quants (vector<Beam_configuration *> *scores) const
342 int region_size = (int) parameters.REGION_SIZE;
344 // Knees and collisions are harder, lets try some more possibilities
347 if (collisions_.size ())
351 Real sit = (beam_thickness - line_thickness) / 2;
353 Real hang = 1.0 - (beam_thickness - line_thickness) / 2;
354 Real base_quants [] = {straddle, sit, inter, hang};
355 int num_base_quants = int (sizeof (base_quants) / sizeof (Real));
358 Asymetry ? should run to <= region_size ?
360 vector<Real> unshifted_quants;
361 for (int i = -region_size; i < region_size; i++)
362 for (int j = 0; j < num_base_quants; j++)
364 unshifted_quants.push_back (i + base_quants[j]);
367 for (vsize i = 0; i < unshifted_quants.size (); i++)
368 for (vsize j = 0; j < unshifted_quants.size (); j++)
370 Beam_configuration *c
371 = Beam_configuration::new_config (unquanted_y,
372 Interval (unshifted_quants[i],
373 unshifted_quants[j]));
378 if (!quant_range[d].contains (c->y[d]))
385 while (flip (&d) != LEFT);
387 scores->push_back (c);
392 void Beam_scoring_problem::one_scorer (Beam_configuration *config) const
395 switch (config->next_scorer_todo)
398 score_slope_ideal (config);
400 case SLOPE_DIRECTION:
401 score_slope_direction (config);
404 score_slope_musical (config);
407 score_forbidden_quants (config);
410 score_stem_lengths (config);
413 score_collisions (config);
415 case HORIZONTAL_INTER:
416 score_horizontal_inter_quants (config);
420 case ORIGINAL_DISTANCE:
424 config->next_scorer_todo++;
428 Beam_scoring_problem::force_score (SCM inspect_quants, const vector<Beam_configuration *> &configs) const
430 Drul_array<Real> ins = ly_scm2interval (inspect_quants);
432 Beam_configuration *best = NULL;
433 for (vsize i = 0; i < configs.size (); i++)
435 Real d = fabs (configs[i]->y[LEFT] - ins[LEFT]) + fabs (configs[i]->y[RIGHT] - ins[RIGHT]);
443 programming_error ("cannot find quant");
445 while (!best->done ())
452 Beam_scoring_problem::solve () const
454 vector<Beam_configuration *> configs;
455 generate_quants (&configs);
457 if (configs.empty ())
459 programming_error ("No viable beam quanting found. Using unquanted y value.");
463 Beam_configuration *best = NULL;
466 = to_boolean (beam->layout ()->lookup_variable (ly_symbol2scm ("debug-beam-scoring")));
467 SCM inspect_quants = beam->get_property ("inspect-quants");
468 if (scm_is_pair (inspect_quants))
471 best = force_score (inspect_quants, configs);
475 std::priority_queue < Beam_configuration *, std::vector<Beam_configuration *>,
476 Beam_configuration_less > queue;
477 for (vsize i = 0; i < configs.size (); i++)
478 queue.push (configs[i]);
483 It would be neat if we generated new configurations on the
484 fly, depending on the best complete score so far, eg.
487 if (best->demerits < sqrt(queue.size())
489 while (best->demerits > sqrt(queue.size()) {
490 generate and insert new configuration
494 that would allow us to do away with region_size altogether.
508 Interval final_positions = best->y;
510 #if DEBUG_BEAM_SCORING
515 for (vsize i = 0; i < configs.size (); i++)
517 if (configs[i]->done ())
521 string card = best->score_card_ + to_string (" c%d/%d", completed, configs.size ());
522 beam->set_property ("annotation", ly_string2scm (card));
526 junk_pointers (configs);
527 return final_positions;
531 Beam_scoring_problem::score_stem_lengths (Beam_configuration *config) const
533 Real limit_penalty = parameters.STEM_LENGTH_LIMIT_PENALTY;
534 Drul_array<Real> score (0, 0);
535 Drul_array<int> count (0, 0);
537 for (vsize i = 0; i < stem_xpositions.size (); i++)
539 Real x = stem_xpositions[i];
540 Real dx = x_span.delta ();
542 ? config->y[RIGHT] * (x - x_span[LEFT]) / dx + config->y[LEFT] * (x_span[RIGHT] - x) / dx
543 : (config->y[RIGHT] + config->y[LEFT]) / 2;
544 Real current_y = beam_y + base_lengths[i];
545 Real length_pen = parameters.STEM_LENGTH_DEMERIT_FACTOR;
547 Stem_info info = stem_infos[i];
548 Direction d = info.dir_;
550 score[d] += limit_penalty * max (0.0, (d * (info.shortest_y_ - current_y)));
552 Real ideal_diff = d * (current_y - info.ideal_y_);
553 Real ideal_score = shrink_extra_weight (ideal_diff, 1.5);
555 /* We introduce a power, to make the scoring strictly
556 convex. Otherwise a symmetric knee beam (up/down/up/down)
557 does not have an optimum in the middle. */
559 ideal_score = pow (ideal_score, 1.1);
561 score[d] += length_pen * ideal_score;
565 /* Divide by number of stems, to make the measure scale-free. */
568 score[d] /= max (count[d], 1);
569 while (flip (&d) != DOWN);
571 config->add (score[LEFT] + score[RIGHT], "L");
575 Beam_scoring_problem::score_slope_direction (Beam_configuration *config) const
577 Real dy = config->y.delta ();
578 Real damped_dy = unquanted_y.delta ();
581 DAMPING_DIRECTION_PENALTY is a very harsh measure, while for
582 complex beaming patterns, horizontal is often a good choice.
584 TODO: find a way to incorporate the complexity of the beam in this
587 if (sign (damped_dy) != sign (dy))
591 if (fabs (damped_dy / x_span.delta ()) > parameters.ROUND_TO_ZERO_SLOPE)
592 dem += parameters.DAMPING_DIRECTION_PENALTY;
594 dem += parameters.HINT_DIRECTION_PENALTY;
597 dem += parameters.DAMPING_DIRECTION_PENALTY;
600 config->add (dem, "Sd");
603 // Score for going against the direction of the musical pattern
605 Beam_scoring_problem::score_slope_musical (Beam_configuration *config) const
607 Real dy = config->y.delta ();
608 Real dem = parameters.MUSICAL_DIRECTION_FACTOR
609 * max (0.0, (fabs (dy) - fabs (musical_dy)));
610 config->add (dem, "Sm");
613 // Score deviation from calculated ideal slope.
615 Beam_scoring_problem::score_slope_ideal (Beam_configuration *config) const
617 Real dy = config->y.delta ();
618 Real damped_dy = unquanted_y.delta ();
621 Real slope_penalty = parameters.IDEAL_SLOPE_FACTOR;
623 /* Xstaff beams tend to use extreme slopes to get short stems. We
624 put in a penalty here. */
628 /* Huh, why would a too steep beam be better than a too flat one ? */
629 dem += shrink_extra_weight (fabs (damped_dy) - fabs (dy), 1.5)
632 config->add (dem, "Si");
638 return x - floor (x);
641 // TODO - there is some overlap with forbidden quants, but for
642 // horizontal beams, it is much more serious to have stafflines
643 // appearing in the wrong place, so we have a separate scorer.
645 Beam_scoring_problem::score_horizontal_inter_quants (Beam_configuration *config) const
647 if (config->y.delta () == 0.0
648 && abs (config->y[LEFT]) < staff_radius * staff_space)
650 Real yshift = config->y[LEFT] - 0.5 * staff_space;
651 if (fabs (my_round (yshift) - yshift) < 0.01 * staff_space)
652 config->add (parameters.HORIZONTAL_INTER_QUANT_PENALTY, "H");
657 TODO: The fixed value SECONDARY_BEAM_DEMERIT is probably flawed:
658 because for 32nd and 64th beams the forbidden quants are relatively
659 more important than stem lengths.
662 Beam_scoring_problem::score_forbidden_quants (Beam_configuration *config) const
664 Real dy = config->y.delta ();
666 Real extra_demerit = parameters.SECONDARY_BEAM_DEMERIT
667 / max (edge_beam_counts[LEFT], edge_beam_counts[RIGHT]);
671 Real eps = parameters.BEAM_EPS;
675 for (int j = 1; j <= edge_beam_counts[d]; j++)
677 Direction stem_dir = edge_dirs[d];
680 The 2.2 factor is to provide a little leniency for
681 borderline cases. If we do 2.0, then the upper outer line
682 will be in the gap of the (2, sit) quant, leading to a
685 Real gap1 = config->y[d] - stem_dir * ((j - 1) * beam_translation + beam_thickness / 2 - line_thickness / 2.2);
686 Real gap2 = config->y[d] - stem_dir * (j * beam_translation - beam_thickness / 2 + line_thickness / 2.2);
689 gap.add_point (gap1);
690 gap.add_point (gap2);
692 for (Real k = -staff_radius;
693 k <= staff_radius + eps; k += 1.0)
694 if (gap.contains (k))
696 Real dist = min (fabs (gap[UP] - k), fabs (gap[DOWN] - k));
699 this parameter is tuned to grace-stem-length.ly
701 Real fixed_demerit = 0.4;
705 + (1 - fixed_demerit) * (dist / gap.length ()) * 2);
709 while ((flip (&d)) != LEFT);
711 if (max (edge_beam_counts[LEFT], edge_beam_counts[RIGHT]) >= 2)
714 Real sit = (beam_thickness - line_thickness) / 2;
716 Real hang = 1.0 - (beam_thickness - line_thickness) / 2;
721 if (edge_beam_counts[d] >= 2
722 && fabs (config->y[d] - edge_dirs[d] * beam_translation) < staff_radius + inter)
724 // TODO up/down symmetry.
725 if (edge_dirs[d] == UP && dy <= eps
726 && fabs (my_modf (config->y[d]) - sit) < eps)
727 dem += extra_demerit;
729 if (edge_dirs[d] == DOWN && dy >= eps
730 && fabs (my_modf (config->y[d]) - hang) < eps)
731 dem += extra_demerit;
734 if (edge_beam_counts[d] >= 3
735 && fabs (config->y[d] - 2 * edge_dirs[d] * beam_translation) < staff_radius + inter)
737 // TODO up/down symmetry.
738 if (edge_dirs[d] == UP && dy <= eps
739 && fabs (my_modf (config->y[d]) - straddle) < eps)
740 dem += extra_demerit;
742 if (edge_dirs[d] == DOWN && dy >= eps
743 && fabs (my_modf (config->y[d]) - straddle) < eps)
744 dem += extra_demerit;
747 while (flip (&d) != LEFT);
750 config->add (dem, "F");
754 Beam_scoring_problem::score_collisions (Beam_configuration *config) const
757 for (vsize i = 0; i < collisions_.size (); i++)
759 Interval collision_y = collisions_[i].y_;
760 Real x = collisions_[i].x_;
762 Real center_beam_y = y_at (x, config);
763 Interval beam_y = center_beam_y + collisions_[i].beam_y_;
765 Real dist = infinity_f;
766 if (!intersection (beam_y, collision_y).is_empty ())
769 dist = min (beam_y.distance (collision_y[DOWN]),
770 beam_y.distance (collision_y[UP]));
773 = max (parameters.COLLISION_PADDING - dist, 0.0) /
774 parameters.COLLISION_PADDING;
776 += collisions_[i].base_penalty_ *
777 pow (scale_free, 3) * parameters.COLLISION_PENALTY;
780 config->add (demerits, "C");