2 This file is part of LilyPond, the GNU music typesetter.
4 Copyright (C) 1997--2015 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 "grob-array.hh"
35 #include "international.hh"
36 #include "interval-minefield.hh"
37 #include "least-squares.hh"
38 #include "libc-extension.hh"
40 #include "note-head.hh"
41 #include "output-def.hh"
42 #include "pointer-group-interface.hh"
44 #include "staff-symbol-referencer.hh"
48 #include "string-convert.hh"
51 get_detail (SCM alist, SCM sym, Real def)
53 SCM entry = scm_assq (sym, alist);
55 if (scm_is_pair (entry))
56 return robust_scm2double (scm_cdr (entry), def);
61 Beam_quant_parameters::fill (Grob *him)
63 SCM details = him->get_property ("details");
66 BEAM_EPS = get_detail (details, ly_symbol2scm ("beam-eps"), 1e-3);
67 REGION_SIZE = get_detail (details, ly_symbol2scm ("region-size"), 2);
70 SECONDARY_BEAM_DEMERIT = get_detail (details, ly_symbol2scm ("secondary-beam-demerit"), 10.0)
71 // For stems that are non-standard, the forbidden beam quanting
72 // doesn't really work, so decrease their importance.
73 * exp(- 8*fabs (1.0 - robust_scm2double(him->get_property ("length-fraction"), 1.0)));
74 STEM_LENGTH_DEMERIT_FACTOR = get_detail (details, ly_symbol2scm ("stem-length-demerit-factor"), 5);
75 HORIZONTAL_INTER_QUANT_PENALTY = get_detail (details, ly_symbol2scm ("horizontal-inter-quant"), 500);
77 STEM_LENGTH_LIMIT_PENALTY = get_detail (details, ly_symbol2scm ("stem-length-limit-penalty"), 5000);
78 DAMPING_DIRECTION_PENALTY = get_detail (details, ly_symbol2scm ("damping-direction-penalty"), 800);
79 HINT_DIRECTION_PENALTY = get_detail (details, ly_symbol2scm ("hint-direction-penalty"), 20);
80 MUSICAL_DIRECTION_FACTOR = get_detail (details, ly_symbol2scm ("musical-direction-factor"), 400);
81 IDEAL_SLOPE_FACTOR = get_detail (details, ly_symbol2scm ("ideal-slope-factor"), 10);
82 ROUND_TO_ZERO_SLOPE = get_detail (details, ly_symbol2scm ("round-to-zero-slope"), 0.02);
85 COLLISION_PENALTY = get_detail (details, ly_symbol2scm ("collision-penalty"), 500);
87 /* For grace notes, beams get scaled down to 80%, but glyphs go down
88 to 63% (magstep -4 for accidentals). To make the padding
89 commensurate with glyph size for grace notes, we take the square
90 of the length fraction, yielding a 64% decrease.
92 COLLISION_PADDING = get_detail (details, ly_symbol2scm ("collision-padding"), 0.5)
93 * sqr (robust_scm2double(him->get_property ("length-fraction"), 1.0));
94 STEM_COLLISION_FACTOR = get_detail (details, ly_symbol2scm ("stem-collision-factor"), 0.1);
97 // Add x if x is positive, add |x|*fac if x is negative.
99 shrink_extra_weight (Real x, Real fac)
101 return fabs (x) * ((x < 0) ? fac : 1.0);
104 /****************************************************************/
106 Beam_configuration::Beam_configuration ()
108 y = Interval (0.0, 0.0);
110 next_scorer_todo = ORIGINAL_DISTANCE;
113 bool Beam_configuration::done () const
115 return next_scorer_todo >= NUM_SCORERS;
118 void Beam_configuration::add (Real demerit, const string &reason)
122 #if DEBUG_BEAM_SCORING
124 score_card_ += to_string (" %s %.2f", reason.c_str (), demerit);
128 Beam_configuration *Beam_configuration::new_config (Interval start,
131 Beam_configuration *qs = new Beam_configuration;
132 qs->y = Interval (int (start[LEFT]) + offset[LEFT],
133 int (start[RIGHT]) + offset[RIGHT]);
135 // This orders the sequence so we try combinations closest to the
136 // the ideal offset first.
137 Real start_score = abs (offset[RIGHT]) + abs (offset[LEFT]);
138 qs->demerits = start_score / 1000.0;
139 qs->next_scorer_todo = ORIGINAL_DISTANCE + 1;
145 Beam_scoring_problem::y_at (Real x, Beam_configuration const *p) const
147 return p->y[LEFT] + x * p->y.delta () / x_span_;
150 /****************************************************************/
155 - Make all demerits customisable
157 - Add demerits for quants per se, as to forbid a specific quant
161 // This is a temporary hack to see how much we can gain by using a
162 // priority queue on the beams to score.
163 static int score_count = 0;
164 LY_DEFINE (ly_beam_score_count, "ly:beam-score-count", 0, 0, 0,
166 "count number of beam scores.")
168 return scm_from_int (score_count);
171 void Beam_scoring_problem::add_collision (Real x, Interval y,
174 // We used to screen for quant range, but no more.
177 c.beam_y_.set_empty ();
179 for (vsize j = 0; j < segments_.size (); j++)
181 if (segments_[j].horizontal_.contains (x))
182 c.beam_y_.add_point (segments_[j].vertical_count_ * beam_translation_);
183 if (segments_[j].horizontal_[LEFT] > x)
186 c.beam_y_.widen (0.5 * beam_thickness_);
190 y *= 1 / staff_space_;
192 c.base_penalty_ = score_factor;
193 collisions_.push_back (c);
196 void Beam_scoring_problem::init_instance_variables (Grob *me, Drul_array<Real> ys, bool align_broken_intos)
198 beam_ = dynamic_cast<Spanner *> (me);
202 If 'ys' are finite, use them as starting points for y-positions of the
203 ends of the beam, instead of the best-fit through the natural ends of
204 the stems. Otherwise, we want to do initial slope calculations.
206 do_initial_slope_calculations_ = false;
207 for (LEFT_and_RIGHT (d))
208 do_initial_slope_calculations_ |= isinf (unquanted_y_[d]) || isnan (unquanted_y_[d]);
211 Calculations are relative to a unit-scaled staff, i.e. the quants are
212 divided by the current staff_space_.
214 staff_space_ = Staff_symbol_referencer::staff_space (beam_);
215 beam_thickness_ = Beam::get_beam_thickness (beam_) / staff_space_;
216 line_thickness_ = Staff_symbol_referencer::line_thickness (beam_) / staff_space_;
218 // This is the least-squares DY, corrected for concave beams.
219 musical_dy_ = robust_scm2double (beam_->get_property ("least-squares-dy"), 0);
221 vector<Spanner *> beams;
222 align_broken_intos_ = align_broken_intos;
223 if (align_broken_intos_)
225 Spanner *orig = dynamic_cast<Spanner *> (beam_->original ());
227 align_broken_intos_ = false;
228 else if (!orig->broken_intos_.size ())
229 align_broken_intos_ = false;
231 beams.insert (beams.end (), orig->broken_intos_.begin (), orig->broken_intos_.end ());
233 if (!align_broken_intos_)
234 beams.push_back (beam_);
237 x_span_ is a single scalar, cumulatively summing the length of all the
238 segments the parent beam was broken-into.
242 normal_stem_count_ = 0;
243 for (vsize i = 0; i < beams.size (); i++)
245 extract_grob_set (beams[i], "stems", stems);
246 extract_grob_set (beams[i], "covered-grobs", fake_collisions);
247 vector<Grob *> collisions;
249 for (vsize j = 0; j < fake_collisions.size (); j++)
250 if (fake_collisions[j]->get_system () == beams[i]->get_system ())
251 collisions.push_back (fake_collisions[j]);
254 for (int a = 2; a--;)
255 common[a] = common_refpoint_of_array (stems, beams[i], Axis (a));
257 for (LEFT_and_RIGHT (d))
258 common[X_AXIS] = beams[i]->get_bound (d)->common_refpoint (common[X_AXIS], X_AXIS);
260 // positions of the endpoints of this beam segment, including any overhangs
261 const Interval x_pos = robust_scm2interval (beams[i]->get_property ("X-positions"),
262 Interval (0.0, 0.0));
264 Drul_array<Grob *> edge_stems (Beam::first_normal_stem (beams[i]),
265 Beam::last_normal_stem (beams[i]));
267 Drul_array<bool> dirs_found (0, 0);
269 Real my_y = beams[i]->relative_coordinate (common[Y_AXIS], Y_AXIS);
271 Interval beam_width (-1.0, -1.0);
272 for (vsize j = 0; j < stems.size (); j++)
275 beam_multiplicity_.push_back (Stem::beam_multiplicity (stems[j]));
276 head_positions_.push_back (Stem::head_positions (stems[j]));
277 is_normal_.push_back (Stem::is_normal_stem (stems[j]));
279 Stem_info si (Stem::get_stem_info (s));
280 si.scale (1 / staff_space_);
281 stem_infos_.push_back (si);
282 chord_start_y_.push_back (Stem::chord_start_y (s));
283 dirs_found[si.dir_] = true;
285 bool f = to_boolean (s->get_property ("french-beaming"))
286 && s != edge_stems[LEFT] && s != edge_stems[RIGHT];
288 Real y = Beam::calc_stem_y (beams[i], s, common, x_pos[LEFT], x_pos[RIGHT], CENTER,
290 base_lengths_.push_back (y / staff_space_);
291 stem_xpositions_.push_back (s->relative_coordinate (common[X_AXIS], X_AXIS) - x_pos[LEFT] + x_span_);
292 stem_ypositions_.push_back (s->relative_coordinate (common[Y_AXIS], Y_AXIS) - my_y);
294 if (is_normal_.back ())
296 if (beam_width[LEFT] == -1.0)
297 beam_width[LEFT] = stem_xpositions_.back ();
298 beam_width[RIGHT] = stem_xpositions_.back ();
302 edge_dirs_ = Drul_array<Direction> (CENTER, CENTER);
303 normal_stem_count_ += Beam::normal_stem_count (beams[i]);
304 if (normal_stem_count_)
305 edge_dirs_ = Drul_array<Direction> (stem_infos_[0].dir_,
306 stem_infos_.back ().dir_);
308 is_xstaff_ = Align_interface::has_interface (common[Y_AXIS]);
309 is_knee_ |= dirs_found[DOWN] && dirs_found[UP];
311 staff_radius_ = Staff_symbol_referencer::staff_radius (beams[i]);
312 edge_beam_counts_ = Drul_array<int>
313 (Stem::beam_multiplicity (stems[0]).length () + 1,
314 Stem::beam_multiplicity (stems.back ()).length () + 1);
316 // TODO - why are we dividing by staff_space_?
317 beam_translation_ = Beam::get_beam_translation (beams[i]) / staff_space_;
319 for (LEFT_and_RIGHT (d))
321 quant_range_[d].set_full ();
325 Real stem_offset = edge_stems[d]->relative_coordinate (common[Y_AXIS], Y_AXIS)
326 - beams[i]->relative_coordinate (common[Y_AXIS], Y_AXIS);
327 Interval heads = Stem::head_positions (edge_stems[d]) * 0.5 * staff_space_;
329 Direction ed = edge_dirs_[d];
330 heads.widen (0.5 * staff_space_
331 + (edge_beam_counts_[d] - 1) * beam_translation_ + beam_thickness_ * .5);
332 quant_range_[d][-ed] = heads[ed] + stem_offset;
335 segments_ = Beam::get_beam_segments (beams[i]);
336 vector_sort (segments_, beam_segment_less);
337 for (vsize j = 0; j < segments_.size (); j++)
338 segments_[j].horizontal_ += (x_span_ - x_pos[LEFT]);
340 set<Grob *> colliding_stems;
341 for (vsize j = 0; j < collisions.size (); j++)
343 if (!collisions[j]->is_live ())
346 if (Beam::has_interface (collisions[j]) && Beam::is_cross_staff (collisions[j]))
350 for (Axis a = X_AXIS; a < NO_AXES; incr (a))
351 b[a] = collisions[j]->extent (common[a], a);
353 if (b[X_AXIS][RIGHT] < x_pos[LEFT] || b[X_AXIS][LEFT] > x_pos[RIGHT])
355 if (b[X_AXIS].is_empty () || b[Y_AXIS].is_empty ())
358 b[X_AXIS] += (x_span_ - x_pos[LEFT]);
360 Real width = b[X_AXIS].length ();
361 Real width_factor = sqrt (width / staff_space_);
363 for (LEFT_and_RIGHT (d))
364 add_collision (b[X_AXIS][d], b[Y_AXIS], width_factor);
366 Grob *stem = unsmob<Grob> (collisions[j]->get_object ("stem"));
367 if (stem && Stem::has_interface (stem) && Stem::is_normal_stem (stem))
369 colliding_stems.insert (stem);
373 for (set<Grob *>::const_iterator it (colliding_stems.begin ()); it != colliding_stems.end (); it++)
376 Real x = (s->extent (common[X_AXIS], X_AXIS) - x_pos[LEFT] + x_span_).center ();
378 Direction stem_dir = get_grob_direction (*it);
381 y[-stem_dir] = Stem::chord_start_y (*it) + (*it)->relative_coordinate (common[Y_AXIS], Y_AXIS)
384 Real factor = parameters_.STEM_COLLISION_FACTOR;
385 if (!unsmob<Grob> (s->get_object ("beam")))
387 add_collision (x, y, factor);
389 x_span_ += beams[i]->spanner_length ();
393 Beam_scoring_problem::Beam_scoring_problem (Grob *me, Drul_array<Real> ys, bool align_broken_intos)
395 beam_ = dynamic_cast<Spanner *> (me);
397 align_broken_intos_ = align_broken_intos;
399 parameters_.fill (me);
400 init_instance_variables (me, ys, align_broken_intos);
401 if (do_initial_slope_calculations_)
403 least_squares_positions ();
405 shift_region_to_valid ();
409 // Assuming V is not empty, pick a 'reasonable' point inside V.
411 point_in_interval (Interval v, Real dist)
415 else if (isinf (v[UP]))
416 return v[DOWN] + dist;
421 /* Set stem's shorten property if unset.
424 take some y-position (chord/beam/nearest?) into account
425 scmify forced-fraction
427 This is done in beam because the shorten has to be uniform over the
432 set_minimum_dy (Grob *me, Real *dy)
437 If dy is smaller than the smallest quant, we
438 get absurd direction-sign penalties.
441 Real ss = Staff_symbol_referencer::staff_space (me);
442 Real beam_thickness = Beam::get_beam_thickness (me) / ss;
443 Real slt = Staff_symbol_referencer::line_thickness (me) / ss;
444 Real sit = (beam_thickness - slt) / 2;
446 Real hang = 1.0 - (beam_thickness - slt) / 2;
448 *dy = sign (*dy) * max (fabs (*dy),
449 min (min (sit, inter), hang));
454 Beam_scoring_problem::no_visible_stem_positions ()
456 if (!head_positions_.size ())
458 unquanted_y_ = Interval (0, 0);
462 Interval head_positions;
464 for (vsize i = 0; i < head_positions_.size (); i++)
466 head_positions.unite (head_positions_[i]);
467 multiplicity.unite (beam_multiplicity_[i]);
470 Direction dir = get_grob_direction (beam_);
473 programming_error ("The beam should have a direction by now.");
475 Real y = head_positions.linear_combination (dir)
477 + dir * beam_translation_ * (multiplicity.length () + 1);
479 unquanted_y_ = Interval (y, y);
483 Beam_scoring_problem::first_normal_index ()
485 for (vsize i = 0; i < is_normal_.size (); i++)
489 beam_->programming_error ("No normal stems, but asking for first normal stem index.");
494 Beam_scoring_problem::last_normal_index ()
496 for (vsize i = is_normal_.size (); i--;)
500 beam_->programming_error ("No normal stems, but asking for first normal stem index.");
505 Beam_scoring_problem::least_squares_positions ()
507 if (!normal_stem_count_)
509 no_visible_stem_positions ();
513 if (stem_infos_.size () < 1)
516 vsize fnx = first_normal_index ();
517 vsize lnx = last_normal_index ();
519 Interval ideal (stem_infos_[fnx].ideal_y_ + stem_ypositions_[fnx],
520 stem_infos_[lnx].ideal_y_ + stem_ypositions_[lnx]);
528 Interval chord (chord_start_y_[0],
529 chord_start_y_.back ());
531 /* Simple beams (2 stems) on middle line should be allowed to be
534 However, if both stems reach middle line,
535 ideal[LEFT] == ideal[RIGHT] and ideal.delta () == 0.
537 For that case, we apply artificial slope */
538 if (!ideal[LEFT] && chord.delta () && stem_infos_.size () == 2)
541 Direction d = (Direction) (sign (chord.delta ()) * UP);
542 unquanted_y_[d] = Beam::get_beam_thickness (beam_) / 2;
543 unquanted_y_[-d] = -unquanted_y_[d];
546 unquanted_y_ = ideal;
548 ldy = unquanted_y_[RIGHT] - unquanted_y_[LEFT];
552 vector<Offset> ideals;
553 for (vsize i = 0; i < stem_infos_.size (); i++)
555 ideals.push_back (Offset (stem_xpositions_[i],
556 stem_infos_[i].ideal_y_
557 + stem_ypositions_[i]));
559 minimise_least_squares (&slope, &y, ideals);
561 dy = slope * x_span_;
563 set_minimum_dy (beam_, &dy);
566 unquanted_y_ = Interval (y, (y + dy));
570 beam_->set_property ("least-squares-dy", scm_from_double (musical_dy_));
574 Determine whether a beam is concave.
576 A beam is concave when the middle notes get closer to the
577 beam than the left and right edge notes.
579 This is determined in two ways: by looking at the positions of the
580 middle notes, or by looking at the deviation of the inside notes
581 compared to the line connecting first and last.
583 The tricky thing is what to do with beams with chords. There are no
584 real guidelines in this case.
588 is_concave_single_notes (vector<int> const &positions, Direction beam_dir)
591 covering.add_point (positions[0]);
592 covering.add_point (positions.back ());
596 bool concave = false;
599 notes above and below the interval covered by 1st and last note.
601 for (vsize i = 1; i + 1 < positions.size (); i++)
603 above = above || (positions[i] > covering[UP]);
604 below = below || (positions[i] < covering[DOWN]);
607 concave = concave || (above && below);
609 A note as close or closer to the beam than begin and end, but the
610 note is reached in the opposite direction as the last-first dy
612 int dy = positions.back () - positions[0];
613 int closest = max (beam_dir * positions.back (), beam_dir * positions[0]);
614 for (vsize i = 2; !concave && i + 1 < positions.size (); i++)
616 int inner_dy = positions[i] - positions[i - 1];
617 if (sign (inner_dy) != sign (dy)
618 && (beam_dir * positions[i] >= closest
619 || beam_dir * positions[i - 1] >= closest))
623 bool all_closer = true;
624 for (vsize i = 1; all_closer && i + 1 < positions.size (); i++)
626 all_closer = all_closer
627 && (beam_dir * positions[i] > closest);
630 concave = concave || all_closer;
635 calc_positions_concaveness (vector<int> const &positions, Direction beam_dir)
637 Real dy = positions.back () - positions[0];
638 Real slope = dy / Real (positions.size () - 1);
639 Real concaveness = 0.0;
640 for (vsize i = 1; i + 1 < positions.size (); i++)
642 Real line_y = slope * i + positions[0];
644 concaveness += max (beam_dir * (positions[i] - line_y), 0.0);
647 concaveness /= positions.size ();
650 Normalize. For dy = 0, the slope ends up as 0 anyway, so the
651 scaling of concaveness doesn't matter much.
654 concaveness /= fabs (dy);
659 Beam_scoring_problem::calc_concaveness ()
661 SCM conc = beam_->get_property ("concaveness");
662 if (scm_is_number (conc))
663 return scm_to_double (conc);
665 if (is_knee_ || is_xstaff_)
668 Direction beam_dir = CENTER;
669 for (vsize i = is_normal_.size (); i--;)
670 if (is_normal_[i] && stem_infos_[i].dir_)
671 beam_dir = stem_infos_[i].dir_;
673 if (normal_stem_count_ <= 2)
676 vector<int> close_positions;
677 vector<int> far_positions;
678 for (vsize i = 0; i < is_normal_.size (); i++)
682 For chords, we take the note head that is closest to the beam.
684 Hmmm.. wait, for the beams in the last measure of morgenlied,
685 this doesn't look so good. Let's try the heads farthest from
689 close_positions.push_back ((int) rint (head_positions_[i][beam_dir]));
690 far_positions.push_back ((int) rint (head_positions_[i][-beam_dir]));
693 Real concaveness = 0.0;
695 if (is_concave_single_notes (beam_dir == UP ? close_positions : far_positions, beam_dir))
701 concaveness = (calc_positions_concaveness (far_positions, beam_dir)
702 + calc_positions_concaveness (close_positions, beam_dir)) / 2;
709 Beam_scoring_problem::slope_damping ()
711 if (normal_stem_count_ <= 1)
714 SCM s = beam_->get_property ("damping");
715 Real damping = scm_to_double (s);
716 Real concaveness = calc_concaveness ();
717 if (concaveness >= 10000)
719 unquanted_y_[LEFT] = unquanted_y_[RIGHT];
726 Real dy = unquanted_y_[RIGHT] - unquanted_y_[LEFT];
728 Real slope = dy && x_span_ ? dy / x_span_ : 0;
730 slope = 0.6 * tanh (slope) / (damping + concaveness);
732 Real damped_dy = slope * x_span_;
734 set_minimum_dy (beam_, &damped_dy);
736 unquanted_y_[LEFT] += (dy - damped_dy) / 2;
737 unquanted_y_[RIGHT] -= (dy - damped_dy) / 2;
742 Beam_scoring_problem::shift_region_to_valid ()
744 if (!normal_stem_count_)
747 Real beam_dy = unquanted_y_[RIGHT] - unquanted_y_[LEFT];
748 Real slope = x_span_ ? beam_dy / x_span_ : 0.0;
751 Shift the positions so that we have a chance of finding good
752 quants (i.e. no short stem failures.)
754 Interval feasible_left_point;
755 feasible_left_point.set_full ();
757 for (vsize i = 0; i < stem_infos_.size (); i++)
759 // TODO - check for invisible here...
761 = stem_infos_[i].shortest_y_
762 - slope * stem_xpositions_ [i];
765 left_y is now relative to the stem S. We want relative to
766 ourselves, so translate:
768 left_y += stem_ypositions_[i];
771 flp[-stem_infos_[i].dir_] = left_y;
773 feasible_left_point.intersect (flp);
776 vector<Grob *> filtered;
778 We only update these for objects that are too large for quanting
779 to find a workaround. Typically, these are notes with
780 stems, and timesig/keysig/clef, which take out the entire area
781 inside the staff as feasible.
783 The code below disregards the thickness and multiplicity of the
784 beam. This should not be a problem, as the beam quanting will
785 take care of computing the impact those exactly.
787 Real min_y_size = 2.0;
789 // A list of intervals into which beams may not fall
790 vector<Interval> forbidden_intervals;
792 for (vsize i = 0; i < collisions_.size (); i++)
794 if (collisions_[i].x_ < 0 || collisions_[i].x_ > x_span_)
797 if (collisions_[i].y_.length () < min_y_size)
800 for (LEFT_and_RIGHT (d))
802 Real dy = slope * collisions_[i].x_;
805 for (DOWN_and_UP (yd))
807 Real left_y = collisions_[i].y_[yd] - dy;
808 disallowed[yd] = left_y;
811 forbidden_intervals.push_back (disallowed);
815 vector_sort (forbidden_intervals, Interval::left_less);
816 Real beam_left_y = unquanted_y_[LEFT];
817 Interval feasible_beam_placements (beam_left_y, beam_left_y);
819 Interval_minefield minefield (feasible_beam_placements, 0.0);
820 for (vsize i = 0; i < forbidden_intervals.size (); i++)
821 minefield.add_forbidden_interval (forbidden_intervals[i]);
823 feasible_beam_placements = minefield.feasible_placements ();
825 // if the beam placement falls out of the feasible region, we push it
826 // to infinity so that it can never be a feasible candidate below
827 for (DOWN_and_UP (d))
829 if (!feasible_left_point.contains (feasible_beam_placements[d]))
830 feasible_beam_placements[d] = d * infinity_f;
833 if ((feasible_beam_placements[UP] == infinity_f && feasible_beam_placements[DOWN] == -infinity_f) && !feasible_left_point.is_empty ())
835 // We are somewhat screwed: we have a collision, but at least
836 // there is a way to satisfy stem length constraints.
837 beam_left_y = point_in_interval (feasible_left_point, 2.0);
839 else if (!feasible_left_point.is_empty ())
841 // Only one of them offers is feasible solution. Pick that one.
842 if (abs (beam_left_y - feasible_beam_placements[DOWN]) > abs (beam_left_y - feasible_beam_placements[UP]))
843 beam_left_y = feasible_beam_placements[UP];
845 beam_left_y = feasible_beam_placements[DOWN];
849 // We are completely screwed.
850 beam_->warning (_ ("no viable initial configuration found: may not find good beam slope"));
853 unquanted_y_ = Drul_array<Real> (beam_left_y, (beam_left_y + beam_dy));
857 Beam_scoring_problem::generate_quants (vector<Beam_configuration *> *scores) const
859 int region_size = (int) parameters_.REGION_SIZE;
861 // Knees and collisions are harder, lets try some more possibilities
864 if (collisions_.size ())
868 Real sit = (beam_thickness_ - line_thickness_) / 2;
870 Real hang = 1.0 - (beam_thickness_ - line_thickness_) / 2;
871 Real base_quants [] = {straddle, sit, inter, hang};
872 int num_base_quants = int (sizeof (base_quants) / sizeof (Real));
875 Asymetry ? should run to <= region_size ?
877 vector<Real> unshifted_quants;
878 for (int i = -region_size; i < region_size; i++)
879 for (int j = 0; j < num_base_quants; j++)
881 unshifted_quants.push_back (i + base_quants[j]);
884 for (vsize i = 0; i < unshifted_quants.size (); i++)
885 for (vsize j = 0; j < unshifted_quants.size (); j++)
887 Beam_configuration *c
888 = Beam_configuration::new_config (unquanted_y_,
889 Interval (unshifted_quants[i],
890 unshifted_quants[j]));
892 for (LEFT_and_RIGHT (d))
894 if (!quant_range_[d].contains (c->y[d]))
902 scores->push_back (c);
907 void Beam_scoring_problem::one_scorer (Beam_configuration *config) const
910 switch (config->next_scorer_todo)
913 score_slope_ideal (config);
915 case SLOPE_DIRECTION:
916 score_slope_direction (config);
919 score_slope_musical (config);
922 score_forbidden_quants (config);
925 score_stem_lengths (config);
928 score_collisions (config);
930 case HORIZONTAL_INTER:
931 score_horizontal_inter_quants (config);
935 case ORIGINAL_DISTANCE:
939 config->next_scorer_todo++;
943 Beam_scoring_problem::force_score (SCM inspect_quants, const vector<Beam_configuration *> &configs) const
945 Drul_array<Real> ins = ly_scm2interval (inspect_quants);
947 Beam_configuration *best = NULL;
948 for (vsize i = 0; i < configs.size (); i++)
950 Real d = fabs (configs[i]->y[LEFT] - ins[LEFT]) + fabs (configs[i]->y[RIGHT] - ins[RIGHT]);
958 programming_error ("cannot find quant");
960 while (!best->done ())
967 Beam_scoring_problem::solve () const
969 vector<Beam_configuration *> configs;
970 generate_quants (&configs);
972 if (configs.empty ())
974 programming_error ("No viable beam quanting found. Using unquanted y value.");
978 if (to_boolean (beam_->get_property ("skip-quanting")))
981 Beam_configuration *best = NULL;
984 = to_boolean (beam_->layout ()->lookup_variable (ly_symbol2scm ("debug-beam-scoring")));
985 SCM inspect_quants = beam_->get_property ("inspect-quants");
986 if (scm_is_pair (inspect_quants))
989 best = force_score (inspect_quants, configs);
993 std::priority_queue < Beam_configuration *, std::vector<Beam_configuration *>,
994 Beam_configuration_less > queue;
995 for (vsize i = 0; i < configs.size (); i++)
996 queue.push (configs[i]);
1001 It would be neat if we generated new configurations on the
1002 fly, depending on the best complete score so far, eg.
1005 if (best->demerits < sqrt(queue.size())
1007 while (best->demerits > sqrt(queue.size()) {
1008 generate and insert new configuration
1012 that would allow us to do away with region_size altogether.
1016 best = queue.top ();
1026 Interval final_positions = best->y;
1028 #if DEBUG_BEAM_SCORING
1033 for (vsize i = 0; i < configs.size (); i++)
1035 if (configs[i]->done ())
1039 string card = best->score_card_ + to_string (" c%d/%d", completed, configs.size ());
1040 beam_->set_property ("annotation", ly_string2scm (card));
1044 junk_pointers (configs);
1045 if (align_broken_intos_)
1047 Interval normalized_endpoints = robust_scm2interval (beam_->get_property ("normalized-endpoints"), Interval (0, 1));
1048 Real y_length = final_positions[RIGHT] - final_positions[LEFT];
1050 final_positions[LEFT] += normalized_endpoints[LEFT] * y_length;
1051 final_positions[RIGHT] -= (1 - normalized_endpoints[RIGHT]) * y_length;
1054 return final_positions;
1058 Beam_scoring_problem::score_stem_lengths (Beam_configuration *config) const
1060 Real limit_penalty = parameters_.STEM_LENGTH_LIMIT_PENALTY;
1061 Drul_array<Real> score (0, 0);
1062 Drul_array<int> count (0, 0);
1064 for (vsize i = 0; i < stem_xpositions_.size (); i++)
1069 Real x = stem_xpositions_[i];
1072 ? config->y[RIGHT] * x / dx + config->y[LEFT] * (x_span_ - x) / dx
1073 : (config->y[RIGHT] + config->y[LEFT]) / 2;
1074 Real current_y = beam_y + base_lengths_[i];
1075 Real length_pen = parameters_.STEM_LENGTH_DEMERIT_FACTOR;
1077 Stem_info info = stem_infos_[i];
1078 Direction d = info.dir_;
1080 score[d] += limit_penalty * max (0.0, (d * (info.shortest_y_ - current_y)));
1082 Real ideal_diff = d * (current_y - info.ideal_y_);
1083 Real ideal_score = shrink_extra_weight (ideal_diff, 1.5);
1085 /* We introduce a power, to make the scoring strictly
1086 convex. Otherwise a symmetric knee beam (up/down/up/down)
1087 does not have an optimum in the middle. */
1089 ideal_score = pow (ideal_score, 1.1);
1091 score[d] += length_pen * ideal_score;
1095 /* Divide by number of stems, to make the measure scale-free. */
1096 for (DOWN_and_UP (d))
1097 score[d] /= max (count[d], 1);
1100 sometimes, two perfectly symmetric kneed beams will have the same score
1101 and can either be quanted up or down.
1103 we choose the quanting in the direction of the slope so that the first stem
1104 always seems longer, reaching to the second, rather than squashed.
1106 if (is_knee_ && count[LEFT] == count[RIGHT] && count[LEFT] == 1 && unquanted_y_.delta ())
1107 score[Direction (sign (unquanted_y_.delta ()))] += score[Direction (sign (unquanted_y_.delta ()))] < 1.0 ? 0.01 : 0.0;
1109 config->add (score[LEFT] + score[RIGHT], "L");
1113 Beam_scoring_problem::score_slope_direction (Beam_configuration *config) const
1115 Real dy = config->y.delta ();
1116 Real damped_dy = unquanted_y_.delta ();
1119 DAMPING_DIRECTION_PENALTY is a very harsh measure, while for
1120 complex beaming patterns, horizontal is often a good choice.
1122 TODO: find a way to incorporate the complexity of the beam in this
1125 if (sign (damped_dy) != sign (dy))
1129 if (fabs (damped_dy / x_span_) > parameters_.ROUND_TO_ZERO_SLOPE)
1130 dem += parameters_.DAMPING_DIRECTION_PENALTY;
1132 dem += parameters_.HINT_DIRECTION_PENALTY;
1135 dem += parameters_.DAMPING_DIRECTION_PENALTY;
1138 config->add (dem, "Sd");
1141 // Score for going against the direction of the musical pattern
1143 Beam_scoring_problem::score_slope_musical (Beam_configuration *config) const
1145 Real dy = config->y.delta ();
1146 Real dem = parameters_.MUSICAL_DIRECTION_FACTOR
1147 * max (0.0, (fabs (dy) - fabs (musical_dy_)));
1148 config->add (dem, "Sm");
1151 // Score deviation from calculated ideal slope.
1153 Beam_scoring_problem::score_slope_ideal (Beam_configuration *config) const
1155 Real dy = config->y.delta ();
1156 Real damped_dy = unquanted_y_.delta ();
1159 Real slope_penalty = parameters_.IDEAL_SLOPE_FACTOR;
1161 /* Xstaff beams tend to use extreme slopes to get short stems. We
1162 put in a penalty here. */
1164 slope_penalty *= 10;
1166 /* Huh, why would a too steep beam be better than a too flat one ? */
1167 dem += shrink_extra_weight (fabs (damped_dy) - fabs (dy), 1.5)
1170 config->add (dem, "Si");
1176 return x - floor (x);
1179 // TODO - there is some overlap with forbidden quants, but for
1180 // horizontal beams, it is much more serious to have stafflines
1181 // appearing in the wrong place, so we have a separate scorer.
1183 Beam_scoring_problem::score_horizontal_inter_quants (Beam_configuration *config) const
1185 if (config->y.delta () == 0.0
1186 && abs (config->y[LEFT]) < staff_radius_ * staff_space_)
1188 Real yshift = config->y[LEFT] - 0.5 * staff_space_;
1189 if (fabs (my_round (yshift) - yshift) < 0.01 * staff_space_)
1190 config->add (parameters_.HORIZONTAL_INTER_QUANT_PENALTY, "H");
1195 TODO: The fixed value SECONDARY_BEAM_DEMERIT is probably flawed:
1196 because for 32nd and 64th beams the forbidden quants are relatively
1197 more important than stem lengths.
1200 Beam_scoring_problem::score_forbidden_quants (Beam_configuration *config) const
1202 Real dy = config->y.delta ();
1204 Real extra_demerit =
1205 parameters_.SECONDARY_BEAM_DEMERIT
1206 / max (edge_beam_counts_[LEFT], edge_beam_counts_[RIGHT]);
1209 Real eps = parameters_.BEAM_EPS;
1211 for (LEFT_and_RIGHT (d))
1213 for (int j = 1; j <= edge_beam_counts_[d]; j++)
1215 Direction stem_dir = edge_dirs_[d];
1218 The fudge_factor is to provide a little leniency for
1219 borderline cases. If we do 2.0, then the upper outer line
1220 will be in the gap of the (2, sit) quant, leading to a
1221 false demerit. By increasing the fudge factor to 2.2, we
1224 Real fudge_factor = 2.2;
1225 Real gap1 = config->y[d] - stem_dir * ((j - 1) * beam_translation_ + beam_thickness_ / 2 - line_thickness_ / fudge_factor);
1226 Real gap2 = config->y[d] - stem_dir * (j * beam_translation_ - beam_thickness_ / 2 + line_thickness_ / fudge_factor);
1229 gap.add_point (gap1);
1230 gap.add_point (gap2);
1232 for (Real k = -staff_radius_;
1233 k <= staff_radius_ + eps; k += 1.0)
1234 if (gap.contains (k))
1236 Real dist = min (fabs (gap[UP] - k), fabs (gap[DOWN] - k));
1239 this parameter is tuned to grace-stem-length.ly
1240 retuned from 0.40 to 0.39 by MS because of slight increases
1241 in gap.length () resulting from measuring beams at real ends
1242 instead of from the middle of stems.
1245 This function needs better comments so we know what is forbidden
1248 Real fixed_demerit = 0.39;
1250 dem += extra_demerit
1252 + (1 - fixed_demerit) * (dist / gap.length ()) * 2);
1257 config->add (dem, "Fl");
1259 if (max (edge_beam_counts_[LEFT], edge_beam_counts_[RIGHT]) >= 2)
1261 Real straddle = 0.0;
1262 Real sit = (beam_thickness_ - line_thickness_) / 2;
1264 Real hang = 1.0 - (beam_thickness_ - line_thickness_) / 2;
1266 for (LEFT_and_RIGHT (d))
1268 if (edge_beam_counts_[d] >= 2
1269 && fabs (config->y[d] - edge_dirs_[d] * beam_translation_) < staff_radius_ + inter)
1271 // TODO up/down symmetry.
1272 if (edge_dirs_[d] == UP && dy <= eps
1273 && fabs (my_modf (config->y[d]) - sit) < eps)
1274 dem += extra_demerit;
1276 if (edge_dirs_[d] == DOWN && dy >= eps
1277 && fabs (my_modf (config->y[d]) - hang) < eps)
1278 dem += extra_demerit;
1281 if (edge_beam_counts_[d] >= 3
1282 && fabs (config->y[d] - 2 * edge_dirs_[d] * beam_translation_) < staff_radius_ + inter)
1284 // TODO up/down symmetry.
1285 if (edge_dirs_[d] == UP && dy <= eps
1286 && fabs (my_modf (config->y[d]) - straddle) < eps)
1287 dem += extra_demerit;
1289 if (edge_dirs_[d] == DOWN && dy >= eps
1290 && fabs (my_modf (config->y[d]) - straddle) < eps)
1291 dem += extra_demerit;
1296 config->add (dem, "Fs");
1300 Beam_scoring_problem::score_collisions (Beam_configuration *config) const
1302 Real demerits = 0.0;
1303 for (vsize i = 0; i < collisions_.size (); i++)
1305 Interval collision_y = collisions_[i].y_;
1306 Real x = collisions_[i].x_;
1308 Real center_beam_y = y_at (x, config);
1309 Interval beam_y = center_beam_y + collisions_[i].beam_y_;
1311 Real dist = infinity_f;
1312 if (!intersection (beam_y, collision_y).is_empty ())
1315 dist = min (beam_y.distance (collision_y[DOWN]),
1316 beam_y.distance (collision_y[UP]));
1320 = max (parameters_.COLLISION_PADDING - dist, 0.0)
1321 / parameters_.COLLISION_PADDING;
1322 Real collision_demerit = collisions_[i].base_penalty_ *
1323 pow (scale_free, 3) * parameters_.COLLISION_PENALTY;
1325 if (collision_demerit > 0) {
1326 demerits += collision_demerit;
1330 config->add (demerits, "C");