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"
27 #include "align-interface.hh"
29 #include "direction.hh"
30 #include "directional-element-interface.hh"
32 #include "grob-array.hh"
34 #include "international.hh"
35 #include "interval-minefield.hh"
36 #include "least-squares.hh"
37 #include "libc-extension.hh"
39 #include "note-head.hh"
40 #include "output-def.hh"
41 #include "pointer-group-interface.hh"
43 #include "staff-symbol-referencer.hh"
47 #include "string-convert.hh"
54 get_detail (SCM alist, SCM sym, Real def)
56 SCM entry = scm_assq (sym, alist);
58 if (scm_is_pair (entry))
59 return robust_scm2double (scm_cdr (entry), def);
64 Beam_quant_parameters::fill (Grob *him)
66 SCM details = him->get_property ("details");
69 BEAM_EPS = get_detail (details, ly_symbol2scm ("beam-eps"), 1e-3);
70 REGION_SIZE = get_detail (details, ly_symbol2scm ("region-size"), 2);
73 SECONDARY_BEAM_DEMERIT = get_detail (details, ly_symbol2scm ("secondary-beam-demerit"), 10.0)
74 // For stems that are non-standard, the forbidden beam quanting
75 // doesn't really work, so decrease their importance.
76 * exp(- 8*fabs (1.0 - robust_scm2double(him->get_property ("length-fraction"), 1.0)));
77 STEM_LENGTH_DEMERIT_FACTOR = get_detail (details, ly_symbol2scm ("stem-length-demerit-factor"), 5);
78 HORIZONTAL_INTER_QUANT_PENALTY = get_detail (details, ly_symbol2scm ("horizontal-inter-quant"), 500);
80 STEM_LENGTH_LIMIT_PENALTY = get_detail (details, ly_symbol2scm ("stem-length-limit-penalty"), 5000);
81 DAMPING_DIRECTION_PENALTY = get_detail (details, ly_symbol2scm ("damping-direction-penalty"), 800);
82 HINT_DIRECTION_PENALTY = get_detail (details, ly_symbol2scm ("hint-direction-penalty"), 20);
83 MUSICAL_DIRECTION_FACTOR = get_detail (details, ly_symbol2scm ("musical-direction-factor"), 400);
84 IDEAL_SLOPE_FACTOR = get_detail (details, ly_symbol2scm ("ideal-slope-factor"), 10);
85 ROUND_TO_ZERO_SLOPE = get_detail (details, ly_symbol2scm ("round-to-zero-slope"), 0.02);
88 COLLISION_PENALTY = get_detail (details, ly_symbol2scm ("collision-penalty"), 500);
90 /* For grace notes, beams get scaled down to 80%, but glyphs go down
91 to 63% (magstep -4 for accidentals). To make the padding
92 commensurate with glyph size for grace notes, we take the square
93 of the length fraction, yielding a 64% decrease.
95 COLLISION_PADDING = get_detail (details, ly_symbol2scm ("collision-padding"), 0.5)
96 * sqr (robust_scm2double(him->get_property ("length-fraction"), 1.0));
97 STEM_COLLISION_FACTOR = get_detail (details, ly_symbol2scm ("stem-collision-factor"), 0.1);
100 // Add x if x is positive, add |x|*fac if x is negative.
102 shrink_extra_weight (Real x, Real fac)
104 return fabs (x) * ((x < 0) ? fac : 1.0);
107 /****************************************************************/
109 Beam_configuration::Beam_configuration ()
111 y = Interval (0.0, 0.0);
113 next_scorer_todo = ORIGINAL_DISTANCE;
116 bool Beam_configuration::done () const
118 return next_scorer_todo >= NUM_SCORERS;
121 void Beam_configuration::add (Real demerit, const string &reason)
125 #if DEBUG_BEAM_SCORING
127 score_card_ += to_string (" %s %.2f", reason.c_str (), demerit);
131 Beam_configuration *Beam_configuration::new_config (Interval start,
134 Beam_configuration *qs = new Beam_configuration;
135 qs->y = Interval (int (start[LEFT]) + offset[LEFT],
136 int (start[RIGHT]) + offset[RIGHT]);
138 // This orders the sequence so we try combinations closest to the
139 // the ideal offset first.
140 Real start_score = abs (offset[RIGHT]) + abs (offset[LEFT]);
141 qs->demerits = start_score / 1000.0;
142 qs->next_scorer_todo = ORIGINAL_DISTANCE + 1;
148 Beam_scoring_problem::y_at (Real x, Beam_configuration const *p) const
150 return p->y[LEFT] + x * p->y.delta () / x_span_;
153 /****************************************************************/
158 - Make all demerits customisable
160 - Add demerits for quants per se, as to forbid a specific quant
164 // This is a temporary hack to see how much we can gain by using a
165 // priority queue on the beams to score.
166 static int score_count = 0;
167 LY_DEFINE (ly_beam_score_count, "ly:beam-score-count", 0, 0, 0,
169 "count number of beam scores.")
171 return scm_from_int (score_count);
174 void Beam_scoring_problem::add_collision (Real x, Interval y,
177 // We used to screen for quant range, but no more.
180 c.beam_y_.set_empty ();
182 for (vsize j = 0; j < segments_.size (); j++)
184 if (segments_[j].horizontal_.contains (x))
185 c.beam_y_.add_point (segments_[j].vertical_count_ * beam_translation_);
186 if (segments_[j].horizontal_[LEFT] > x)
189 c.beam_y_.widen (0.5 * beam_thickness_);
193 y *= 1 / staff_space_;
195 c.base_penalty_ = score_factor;
196 collisions_.push_back (c);
199 void Beam_scoring_problem::init_instance_variables (Grob *me, Drul_array<Real> ys, bool align_broken_intos)
201 beam_ = dynamic_cast<Spanner *> (me);
205 If 'ys' are finite, use them as starting points for y-positions of the
206 ends of the beam, instead of the best-fit through the natural ends of
207 the stems. Otherwise, we want to do initial slope calculations.
209 do_initial_slope_calculations_ = false;
210 for (LEFT_and_RIGHT (d))
211 do_initial_slope_calculations_ |= isinf (unquanted_y_[d]) || isnan (unquanted_y_[d]);
214 Calculations are relative to a unit-scaled staff, i.e. the quants are
215 divided by the current staff_space_.
217 staff_space_ = Staff_symbol_referencer::staff_space (beam_);
218 beam_thickness_ = Beam::get_beam_thickness (beam_) / staff_space_;
219 line_thickness_ = Staff_symbol_referencer::line_thickness (beam_) / staff_space_;
221 // This is the least-squares DY, corrected for concave beams.
222 musical_dy_ = robust_scm2double (beam_->get_property ("least-squares-dy"), 0);
224 vector<Spanner *> beams;
225 align_broken_intos_ = align_broken_intos;
226 if (align_broken_intos_)
228 Spanner *orig = dynamic_cast<Spanner *> (beam_->original ());
230 align_broken_intos_ = false;
231 else if (!orig->broken_intos_.size ())
232 align_broken_intos_ = false;
234 beams.insert (beams.end (), orig->broken_intos_.begin (), orig->broken_intos_.end ());
236 if (!align_broken_intos_)
237 beams.push_back (beam_);
240 x_span_ is a single scalar, cumulatively summing the length of all the
241 segments the parent beam was broken-into.
245 normal_stem_count_ = 0;
246 for (vsize i = 0; i < beams.size (); i++)
248 extract_grob_set (beams[i], "stems", stems);
249 extract_grob_set (beams[i], "covered-grobs", fake_collisions);
250 vector<Grob *> collisions;
252 for (vsize j = 0; j < fake_collisions.size (); j++)
253 if (fake_collisions[j]->get_system () == beams[i]->get_system ())
254 collisions.push_back (fake_collisions[j]);
257 for (int a = 2; a--;)
258 common[a] = common_refpoint_of_array (stems, beams[i], Axis (a));
260 for (LEFT_and_RIGHT (d))
261 common[X_AXIS] = beams[i]->get_bound (d)->common_refpoint (common[X_AXIS], X_AXIS);
263 // positions of the endpoints of this beam segment, including any overhangs
264 const Interval x_pos = robust_scm2interval (beams[i]->get_property ("X-positions"),
265 Interval (0.0, 0.0));
267 Drul_array<Grob *> edge_stems (Beam::first_normal_stem (beams[i]),
268 Beam::last_normal_stem (beams[i]));
270 Drul_array<bool> dirs_found (0, 0);
272 Real my_y = beams[i]->relative_coordinate (common[Y_AXIS], Y_AXIS);
274 Interval beam_width (-1.0, -1.0);
275 for (vsize j = 0; j < stems.size (); j++)
278 beam_multiplicity_.push_back (Stem::beam_multiplicity (stems[j]));
279 head_positions_.push_back (Stem::head_positions (stems[j]));
280 is_normal_.push_back (Stem::is_normal_stem (stems[j]));
282 Stem_info si (Stem::get_stem_info (s));
283 si.scale (1 / staff_space_);
284 stem_infos_.push_back (si);
285 chord_start_y_.push_back (Stem::chord_start_y (s));
286 dirs_found[si.dir_] = true;
288 bool f = to_boolean (s->get_property ("french-beaming"))
289 && s != edge_stems[LEFT] && s != edge_stems[RIGHT];
291 Real y = Beam::calc_stem_y (beams[i], s, common, x_pos[LEFT], x_pos[RIGHT], CENTER,
293 base_lengths_.push_back (y / staff_space_);
294 stem_xpositions_.push_back (s->relative_coordinate (common[X_AXIS], X_AXIS) - x_pos[LEFT] + x_span_);
295 stem_ypositions_.push_back (s->relative_coordinate (common[Y_AXIS], Y_AXIS) - my_y);
297 if (is_normal_.back ())
299 if (beam_width[LEFT] == -1.0)
300 beam_width[LEFT] = stem_xpositions_.back ();
301 beam_width[RIGHT] = stem_xpositions_.back ();
305 edge_dirs_ = Drul_array<Direction> (CENTER, CENTER);
306 normal_stem_count_ += Beam::normal_stem_count (beams[i]);
307 if (normal_stem_count_)
308 edge_dirs_ = Drul_array<Direction> (stem_infos_[0].dir_,
309 stem_infos_.back ().dir_);
311 is_xstaff_ = has_interface<Align_interface> (common[Y_AXIS]);
312 is_knee_ |= dirs_found[DOWN] && dirs_found[UP];
314 staff_radius_ = Staff_symbol_referencer::staff_radius (beams[i]);
315 edge_beam_counts_ = Drul_array<int>
316 (Stem::beam_multiplicity (stems[0]).length () + 1,
317 Stem::beam_multiplicity (stems.back ()).length () + 1);
319 // TODO - why are we dividing by staff_space_?
320 beam_translation_ = Beam::get_beam_translation (beams[i]) / staff_space_;
322 for (LEFT_and_RIGHT (d))
324 quant_range_[d].set_full ();
328 Real stem_offset = edge_stems[d]->relative_coordinate (common[Y_AXIS], Y_AXIS)
329 - beams[i]->relative_coordinate (common[Y_AXIS], Y_AXIS);
330 Interval heads = Stem::head_positions (edge_stems[d]) * 0.5 * staff_space_;
332 Direction ed = edge_dirs_[d];
333 heads.widen (0.5 * staff_space_
334 + (edge_beam_counts_[d] - 1) * beam_translation_ + beam_thickness_ * .5);
335 quant_range_[d][-ed] = heads[ed] + stem_offset;
338 segments_ = Beam::get_beam_segments (beams[i]);
339 vector_sort (segments_, beam_segment_less);
340 for (vsize j = 0; j < segments_.size (); j++)
341 segments_[j].horizontal_ += (x_span_ - x_pos[LEFT]);
343 set<Grob *> colliding_stems;
344 for (vsize j = 0; j < collisions.size (); j++)
346 if (!collisions[j]->is_live ())
349 if (has_interface<Beam> (collisions[j]) && Beam::is_cross_staff (collisions[j]))
353 for (Axis a = X_AXIS; a < NO_AXES; incr (a))
354 b[a] = collisions[j]->extent (common[a], a);
356 if (b[X_AXIS][RIGHT] < x_pos[LEFT] || b[X_AXIS][LEFT] > x_pos[RIGHT])
358 if (b[X_AXIS].is_empty () || b[Y_AXIS].is_empty ())
361 b[X_AXIS] += (x_span_ - x_pos[LEFT]);
363 Real width = b[X_AXIS].length ();
364 Real width_factor = sqrt (width / staff_space_);
366 for (LEFT_and_RIGHT (d))
367 add_collision (b[X_AXIS][d], b[Y_AXIS], width_factor);
369 Grob *stem = unsmob<Grob> (collisions[j]->get_object ("stem"));
370 if (has_interface<Stem> (stem) && Stem::is_normal_stem (stem))
372 colliding_stems.insert (stem);
376 for (set<Grob *>::const_iterator it (colliding_stems.begin ()); it != colliding_stems.end (); it++)
379 Real x = (robust_relative_extent (s, common[X_AXIS], X_AXIS) - x_pos[LEFT] + x_span_).center ();
381 Direction stem_dir = get_grob_direction (*it);
384 y[-stem_dir] = Stem::chord_start_y (*it) + (*it)->relative_coordinate (common[Y_AXIS], Y_AXIS)
387 Real factor = parameters_.STEM_COLLISION_FACTOR;
388 if (!unsmob<Grob> (s->get_object ("beam")))
390 add_collision (x, y, factor);
392 x_span_ += beams[i]->spanner_length ();
396 Beam_scoring_problem::Beam_scoring_problem (Grob *me, Drul_array<Real> ys, bool align_broken_intos)
398 beam_ = dynamic_cast<Spanner *> (me);
400 align_broken_intos_ = align_broken_intos;
402 parameters_.fill (me);
403 init_instance_variables (me, ys, align_broken_intos);
404 if (do_initial_slope_calculations_)
406 least_squares_positions ();
408 shift_region_to_valid ();
412 // Assuming V is not empty, pick a 'reasonable' point inside V.
414 point_in_interval (Interval v, Real dist)
418 else if (isinf (v[UP]))
419 return v[DOWN] + dist;
424 /* Set stem's shorten property if unset.
427 take some y-position (chord/beam/nearest?) into account
428 scmify forced-fraction
430 This is done in beam because the shorten has to be uniform over the
435 set_minimum_dy (Grob *me, Real *dy)
440 If dy is smaller than the smallest quant, we
441 get absurd direction-sign penalties.
444 Real ss = Staff_symbol_referencer::staff_space (me);
445 Real beam_thickness = Beam::get_beam_thickness (me) / ss;
446 Real slt = Staff_symbol_referencer::line_thickness (me) / ss;
447 Real sit = (beam_thickness - slt) / 2;
449 Real hang = 1.0 - (beam_thickness - slt) / 2;
451 *dy = sign (*dy) * std::max (fabs (*dy),
452 std::min (std::min (sit, inter), hang));
457 Beam_scoring_problem::no_visible_stem_positions ()
459 if (!head_positions_.size ())
461 unquanted_y_ = Interval (0, 0);
465 Interval head_positions;
467 for (vsize i = 0; i < head_positions_.size (); i++)
469 head_positions.unite (head_positions_[i]);
470 multiplicity.unite (beam_multiplicity_[i]);
473 Direction dir = get_grob_direction (beam_);
476 programming_error ("The beam should have a direction by now.");
478 Real y = head_positions.linear_combination (dir)
480 + dir * beam_translation_ * (multiplicity.length () + 1);
482 unquanted_y_ = Interval (y, y);
486 Beam_scoring_problem::first_normal_index ()
488 for (vsize i = 0; i < is_normal_.size (); i++)
492 beam_->programming_error ("No normal stems, but asking for first normal stem index.");
497 Beam_scoring_problem::last_normal_index ()
499 for (vsize i = is_normal_.size (); i--;)
503 beam_->programming_error ("No normal stems, but asking for first normal stem index.");
508 Beam_scoring_problem::least_squares_positions ()
510 if (!normal_stem_count_)
512 no_visible_stem_positions ();
516 if (stem_infos_.size () < 1)
519 vsize fnx = first_normal_index ();
520 vsize lnx = last_normal_index ();
522 Interval ideal (stem_infos_[fnx].ideal_y_ + stem_ypositions_[fnx],
523 stem_infos_[lnx].ideal_y_ + stem_ypositions_[lnx]);
531 Interval chord (chord_start_y_[0],
532 chord_start_y_.back ());
534 /* Simple beams (2 stems) on middle line should be allowed to be
537 However, if both stems reach middle line,
538 ideal[LEFT] == ideal[RIGHT] and ideal.delta () == 0.
540 For that case, we apply artificial slope */
541 if (!ideal[LEFT] && chord.delta () && stem_infos_.size () == 2)
544 Direction d = (Direction) (sign (chord.delta ()) * UP);
545 unquanted_y_[d] = Beam::get_beam_thickness (beam_) / 2;
546 unquanted_y_[-d] = -unquanted_y_[d];
549 unquanted_y_ = ideal;
551 ldy = unquanted_y_[RIGHT] - unquanted_y_[LEFT];
555 vector<Offset> ideals;
556 for (vsize i = 0; i < stem_infos_.size (); i++)
558 ideals.push_back (Offset (stem_xpositions_[i],
559 stem_infos_[i].ideal_y_
560 + stem_ypositions_[i]));
562 minimise_least_squares (&slope, &y, ideals);
564 dy = slope * x_span_;
566 set_minimum_dy (beam_, &dy);
569 unquanted_y_ = Interval (y, (y + dy));
573 beam_->set_property ("least-squares-dy", scm_from_double (musical_dy_));
577 Determine whether a beam is concave.
579 A beam is concave when the middle notes get closer to the
580 beam than the left and right edge notes.
582 This is determined in two ways: by looking at the positions of the
583 middle notes, or by looking at the deviation of the inside notes
584 compared to the line connecting first and last.
586 The tricky thing is what to do with beams with chords. There are no
587 real guidelines in this case.
591 is_concave_single_notes (vector<int> const &positions, Direction beam_dir)
594 covering.add_point (positions[0]);
595 covering.add_point (positions.back ());
599 bool concave = false;
602 notes above and below the interval covered by 1st and last note.
604 for (vsize i = 1; i + 1 < positions.size (); i++)
606 above = above || (positions[i] > covering[UP]);
607 below = below || (positions[i] < covering[DOWN]);
610 concave = concave || (above && below);
612 A note as close or closer to the beam than begin and end, but the
613 note is reached in the opposite direction as the last-first dy
615 int dy = positions.back () - positions[0];
616 int closest = std::max (beam_dir * positions.back (), beam_dir * positions[0]);
617 for (vsize i = 2; !concave && i + 1 < positions.size (); i++)
619 int inner_dy = positions[i] - positions[i - 1];
620 if (sign (inner_dy) != sign (dy)
621 && (beam_dir * positions[i] >= closest
622 || beam_dir * positions[i - 1] >= closest))
626 bool all_closer = true;
627 for (vsize i = 1; all_closer && i + 1 < positions.size (); i++)
629 all_closer = all_closer
630 && (beam_dir * positions[i] > closest);
633 concave = concave || all_closer;
638 calc_positions_concaveness (vector<int> const &positions, Direction beam_dir)
640 Real dy = positions.back () - positions[0];
641 Real slope = dy / Real (positions.size () - 1);
642 Real concaveness = 0.0;
643 for (vsize i = 1; i + 1 < positions.size (); i++)
645 Real line_y = slope * i + positions[0];
647 concaveness += std::max (beam_dir * (positions[i] - line_y), 0.0);
650 concaveness /= positions.size ();
653 Normalize. For dy = 0, the slope ends up as 0 anyway, so the
654 scaling of concaveness doesn't matter much.
657 concaveness /= fabs (dy);
662 Beam_scoring_problem::calc_concaveness ()
664 SCM conc = beam_->get_property ("concaveness");
665 if (scm_is_number (conc))
666 return scm_to_double (conc);
668 if (is_knee_ || is_xstaff_)
671 Direction beam_dir = CENTER;
672 for (vsize i = is_normal_.size (); i--;)
673 if (is_normal_[i] && stem_infos_[i].dir_)
674 beam_dir = stem_infos_[i].dir_;
676 if (normal_stem_count_ <= 2)
679 vector<int> close_positions;
680 vector<int> far_positions;
681 for (vsize i = 0; i < is_normal_.size (); i++)
685 For chords, we take the note head that is closest to the beam.
687 Hmmm.. wait, for the beams in the last measure of morgenlied,
688 this doesn't look so good. Let's try the heads farthest from
692 close_positions.push_back ((int) rint (head_positions_[i][beam_dir]));
693 far_positions.push_back ((int) rint (head_positions_[i][-beam_dir]));
696 Real concaveness = 0.0;
698 if (is_concave_single_notes (beam_dir == UP ? close_positions : far_positions, beam_dir))
704 concaveness = (calc_positions_concaveness (far_positions, beam_dir)
705 + calc_positions_concaveness (close_positions, beam_dir)) / 2;
712 Beam_scoring_problem::slope_damping ()
714 if (normal_stem_count_ <= 1)
717 SCM s = beam_->get_property ("damping");
718 Real damping = scm_to_double (s);
719 Real concaveness = calc_concaveness ();
720 if (concaveness >= 10000)
722 unquanted_y_[LEFT] = unquanted_y_[RIGHT];
729 Real dy = unquanted_y_[RIGHT] - unquanted_y_[LEFT];
731 Real slope = dy && x_span_ ? dy / x_span_ : 0;
733 slope = 0.6 * tanh (slope) / (damping + concaveness);
735 Real damped_dy = slope * x_span_;
737 set_minimum_dy (beam_, &damped_dy);
739 unquanted_y_[LEFT] += (dy - damped_dy) / 2;
740 unquanted_y_[RIGHT] -= (dy - damped_dy) / 2;
745 Beam_scoring_problem::shift_region_to_valid ()
747 if (!normal_stem_count_)
750 Real beam_dy = unquanted_y_[RIGHT] - unquanted_y_[LEFT];
751 Real slope = x_span_ ? beam_dy / x_span_ : 0.0;
754 Shift the positions so that we have a chance of finding good
755 quants (i.e. no short stem failures.)
757 Interval feasible_left_point;
758 feasible_left_point.set_full ();
760 for (vsize i = 0; i < stem_infos_.size (); i++)
762 // TODO - check for invisible here...
764 = stem_infos_[i].shortest_y_
765 - slope * stem_xpositions_ [i];
768 left_y is now relative to the stem S. We want relative to
769 ourselves, so translate:
771 left_y += stem_ypositions_[i];
774 flp[-stem_infos_[i].dir_] = left_y;
776 feasible_left_point.intersect (flp);
779 vector<Grob *> filtered;
781 We only update these for objects that are too large for quanting
782 to find a workaround. Typically, these are notes with
783 stems, and timesig/keysig/clef, which take out the entire area
784 inside the staff as feasible.
786 The code below disregards the thickness and multiplicity of the
787 beam. This should not be a problem, as the beam quanting will
788 take care of computing the impact those exactly.
790 Real min_y_size = 2.0;
792 // A list of intervals into which beams may not fall
793 vector<Interval> forbidden_intervals;
795 for (vsize i = 0; i < collisions_.size (); i++)
797 if (collisions_[i].x_ < 0 || collisions_[i].x_ > x_span_)
800 if (collisions_[i].y_.length () < min_y_size)
803 for (LEFT_and_RIGHT (d))
805 Real dy = slope * collisions_[i].x_;
808 for (DOWN_and_UP (yd))
810 Real left_y = collisions_[i].y_[yd] - dy;
811 disallowed[yd] = left_y;
814 forbidden_intervals.push_back (disallowed);
818 vector_sort (forbidden_intervals, Interval::left_less);
819 Real beam_left_y = unquanted_y_[LEFT];
820 Interval feasible_beam_placements (beam_left_y, beam_left_y);
822 Interval_minefield minefield (feasible_beam_placements, 0.0);
823 for (vsize i = 0; i < forbidden_intervals.size (); i++)
824 minefield.add_forbidden_interval (forbidden_intervals[i]);
826 feasible_beam_placements = minefield.feasible_placements ();
828 // if the beam placement falls out of the feasible region, we push it
829 // to infinity so that it can never be a feasible candidate below
830 for (DOWN_and_UP (d))
832 if (!feasible_left_point.contains (feasible_beam_placements[d]))
833 feasible_beam_placements[d] = d * infinity_f;
836 if ((feasible_beam_placements[UP] == infinity_f && feasible_beam_placements[DOWN] == -infinity_f) && !feasible_left_point.is_empty ())
838 // We are somewhat screwed: we have a collision, but at least
839 // there is a way to satisfy stem length constraints.
840 beam_left_y = point_in_interval (feasible_left_point, 2.0);
842 else if (!feasible_left_point.is_empty ())
844 // Only one of them offers is feasible solution. Pick that one.
845 if (abs (beam_left_y - feasible_beam_placements[DOWN]) > abs (beam_left_y - feasible_beam_placements[UP]))
846 beam_left_y = feasible_beam_placements[UP];
848 beam_left_y = feasible_beam_placements[DOWN];
852 // We are completely screwed.
853 beam_->warning (_ ("no viable initial configuration found: may not find good beam slope"));
856 unquanted_y_ = Drul_array<Real> (beam_left_y, (beam_left_y + beam_dy));
860 Beam_scoring_problem::generate_quants (vector<Beam_configuration *> *scores) const
862 int region_size = (int) parameters_.REGION_SIZE;
864 // Knees and collisions are harder, lets try some more possibilities
867 if (collisions_.size ())
871 Real sit = (beam_thickness_ - line_thickness_) / 2;
873 Real hang = 1.0 - (beam_thickness_ - line_thickness_) / 2;
874 Real base_quants [] = {straddle, sit, inter, hang};
875 int num_base_quants = int (sizeof (base_quants) / sizeof (Real));
878 Asymetry ? should run to <= region_size ?
880 vector<Real> unshifted_quants;
881 for (int i = -region_size; i < region_size; i++)
882 for (int j = 0; j < num_base_quants; j++)
884 unshifted_quants.push_back (i + base_quants[j]);
887 for (vsize i = 0; i < unshifted_quants.size (); i++)
888 for (vsize j = 0; j < unshifted_quants.size (); j++)
890 Beam_configuration *c
891 = Beam_configuration::new_config (unquanted_y_,
892 Interval (unshifted_quants[i],
893 unshifted_quants[j]));
895 for (LEFT_and_RIGHT (d))
897 if (!quant_range_[d].contains (c->y[d]))
905 scores->push_back (c);
910 void Beam_scoring_problem::one_scorer (Beam_configuration *config) const
913 switch (config->next_scorer_todo)
916 score_slope_ideal (config);
918 case SLOPE_DIRECTION:
919 score_slope_direction (config);
922 score_slope_musical (config);
925 score_forbidden_quants (config);
928 score_stem_lengths (config);
931 score_collisions (config);
933 case HORIZONTAL_INTER:
934 score_horizontal_inter_quants (config);
938 case ORIGINAL_DISTANCE:
942 config->next_scorer_todo++;
946 Beam_scoring_problem::force_score (SCM inspect_quants, const vector<Beam_configuration *> &configs) const
948 Drul_array<Real> ins = ly_scm2interval (inspect_quants);
950 Beam_configuration *best = NULL;
951 for (vsize i = 0; i < configs.size (); i++)
953 Real d = fabs (configs[i]->y[LEFT] - ins[LEFT]) + fabs (configs[i]->y[RIGHT] - ins[RIGHT]);
961 programming_error ("cannot find quant");
963 while (!best->done ())
970 Beam_scoring_problem::solve () const
972 vector<Beam_configuration *> configs;
973 generate_quants (&configs);
975 if (configs.empty ())
977 programming_error ("No viable beam quanting found. Using unquanted y value.");
981 if (to_boolean (beam_->get_property ("skip-quanting")))
984 Beam_configuration *best = NULL;
987 = to_boolean (beam_->layout ()->lookup_variable (ly_symbol2scm ("debug-beam-scoring")));
988 SCM inspect_quants = beam_->get_property ("inspect-quants");
989 if (scm_is_pair (inspect_quants))
992 best = force_score (inspect_quants, configs);
996 std::priority_queue < Beam_configuration *, std::vector<Beam_configuration *>,
997 Beam_configuration_less > queue;
998 for (vsize i = 0; i < configs.size (); i++)
999 queue.push (configs[i]);
1004 It would be neat if we generated new configurations on the
1005 fly, depending on the best complete score so far, eg.
1008 if (best->demerits < sqrt(queue.size())
1010 while (best->demerits > sqrt(queue.size()) {
1011 generate and insert new configuration
1015 that would allow us to do away with region_size altogether.
1019 best = queue.top ();
1029 Interval final_positions = best->y;
1031 #if DEBUG_BEAM_SCORING
1036 for (vsize i = 0; i < configs.size (); i++)
1038 if (configs[i]->done ())
1042 string card = best->score_card_ + to_string (" c%d/%d", completed, configs.size ());
1043 beam_->set_property ("annotation", ly_string2scm (card));
1047 junk_pointers (configs);
1048 if (align_broken_intos_)
1050 Interval normalized_endpoints = robust_scm2interval (beam_->get_property ("normalized-endpoints"), Interval (0, 1));
1051 Real y_length = final_positions[RIGHT] - final_positions[LEFT];
1053 final_positions[LEFT] += normalized_endpoints[LEFT] * y_length;
1054 final_positions[RIGHT] -= (1 - normalized_endpoints[RIGHT]) * y_length;
1057 return final_positions;
1061 Beam_scoring_problem::score_stem_lengths (Beam_configuration *config) const
1063 Real limit_penalty = parameters_.STEM_LENGTH_LIMIT_PENALTY;
1064 Drul_array<Real> score (0, 0);
1065 Drul_array<int> count (0, 0);
1067 for (vsize i = 0; i < stem_xpositions_.size (); i++)
1072 Real x = stem_xpositions_[i];
1075 ? config->y[RIGHT] * x / dx + config->y[LEFT] * (x_span_ - x) / dx
1076 : (config->y[RIGHT] + config->y[LEFT]) / 2;
1077 Real current_y = beam_y + base_lengths_[i];
1078 Real length_pen = parameters_.STEM_LENGTH_DEMERIT_FACTOR;
1080 Stem_info info = stem_infos_[i];
1081 Direction d = info.dir_;
1083 score[d] += limit_penalty * std::max (0.0, (d * (info.shortest_y_ - current_y)));
1085 Real ideal_diff = d * (current_y - info.ideal_y_);
1086 Real ideal_score = shrink_extra_weight (ideal_diff, 1.5);
1088 /* We introduce a power, to make the scoring strictly
1089 convex. Otherwise a symmetric knee beam (up/down/up/down)
1090 does not have an optimum in the middle. */
1092 ideal_score = pow (ideal_score, 1.1);
1094 score[d] += length_pen * ideal_score;
1098 /* Divide by number of stems, to make the measure scale-free. */
1099 for (DOWN_and_UP (d))
1100 score[d] /= std::max (count[d], 1);
1103 sometimes, two perfectly symmetric kneed beams will have the same score
1104 and can either be quanted up or down.
1106 we choose the quanting in the direction of the slope so that the first stem
1107 always seems longer, reaching to the second, rather than squashed.
1109 if (is_knee_ && count[LEFT] == count[RIGHT] && count[LEFT] == 1 && unquanted_y_.delta ())
1110 score[Direction (sign (unquanted_y_.delta ()))] += score[Direction (sign (unquanted_y_.delta ()))] < 1.0 ? 0.01 : 0.0;
1112 config->add (score[LEFT] + score[RIGHT], "L");
1116 Beam_scoring_problem::score_slope_direction (Beam_configuration *config) const
1118 Real dy = config->y.delta ();
1119 Real damped_dy = unquanted_y_.delta ();
1122 DAMPING_DIRECTION_PENALTY is a very harsh measure, while for
1123 complex beaming patterns, horizontal is often a good choice.
1125 TODO: find a way to incorporate the complexity of the beam in this
1128 if (sign (damped_dy) != sign (dy))
1132 if (fabs (damped_dy / x_span_) > parameters_.ROUND_TO_ZERO_SLOPE)
1133 dem += parameters_.DAMPING_DIRECTION_PENALTY;
1135 dem += parameters_.HINT_DIRECTION_PENALTY;
1138 dem += parameters_.DAMPING_DIRECTION_PENALTY;
1141 config->add (dem, "Sd");
1144 // Score for going against the direction of the musical pattern
1146 Beam_scoring_problem::score_slope_musical (Beam_configuration *config) const
1148 Real dy = config->y.delta ();
1149 Real dem = parameters_.MUSICAL_DIRECTION_FACTOR
1150 * std::max (0.0, (fabs (dy) - fabs (musical_dy_)));
1151 config->add (dem, "Sm");
1154 // Score deviation from calculated ideal slope.
1156 Beam_scoring_problem::score_slope_ideal (Beam_configuration *config) const
1158 Real dy = config->y.delta ();
1159 Real damped_dy = unquanted_y_.delta ();
1162 Real slope_penalty = parameters_.IDEAL_SLOPE_FACTOR;
1164 /* Xstaff beams tend to use extreme slopes to get short stems. We
1165 put in a penalty here. */
1167 slope_penalty *= 10;
1169 /* Huh, why would a too steep beam be better than a too flat one ? */
1170 dem += shrink_extra_weight (fabs (damped_dy) - fabs (dy), 1.5)
1173 config->add (dem, "Si");
1179 return x - floor (x);
1182 // TODO - there is some overlap with forbidden quants, but for
1183 // horizontal beams, it is much more serious to have stafflines
1184 // appearing in the wrong place, so we have a separate scorer.
1186 Beam_scoring_problem::score_horizontal_inter_quants (Beam_configuration *config) const
1188 if (config->y.delta () == 0.0
1189 && abs (config->y[LEFT]) < staff_radius_ * staff_space_)
1191 Real yshift = config->y[LEFT] - 0.5 * staff_space_;
1192 if (fabs (my_round (yshift) - yshift) < 0.01 * staff_space_)
1193 config->add (parameters_.HORIZONTAL_INTER_QUANT_PENALTY, "H");
1198 TODO: The fixed value SECONDARY_BEAM_DEMERIT is probably flawed:
1199 because for 32nd and 64th beams the forbidden quants are relatively
1200 more important than stem lengths.
1203 Beam_scoring_problem::score_forbidden_quants (Beam_configuration *config) const
1205 Real dy = config->y.delta ();
1207 Real extra_demerit =
1208 parameters_.SECONDARY_BEAM_DEMERIT
1209 / std::max (edge_beam_counts_[LEFT], edge_beam_counts_[RIGHT]);
1212 Real eps = parameters_.BEAM_EPS;
1214 for (LEFT_and_RIGHT (d))
1216 for (int j = 1; j <= edge_beam_counts_[d]; j++)
1218 Direction stem_dir = edge_dirs_[d];
1221 The fudge_factor is to provide a little leniency for
1222 borderline cases. If we do 2.0, then the upper outer line
1223 will be in the gap of the (2, sit) quant, leading to a
1224 false demerit. By increasing the fudge factor to 2.2, we
1227 Real fudge_factor = 2.2;
1228 Real gap1 = config->y[d] - stem_dir * ((j - 1) * beam_translation_ + beam_thickness_ / 2 - line_thickness_ / fudge_factor);
1229 Real gap2 = config->y[d] - stem_dir * (j * beam_translation_ - beam_thickness_ / 2 + line_thickness_ / fudge_factor);
1232 gap.add_point (gap1);
1233 gap.add_point (gap2);
1235 for (Real k = -staff_radius_;
1236 k <= staff_radius_ + eps; k += 1.0)
1237 if (gap.contains (k))
1239 Real dist = std::min (fabs (gap[UP] - k), fabs (gap[DOWN] - k));
1242 this parameter is tuned to grace-stem-length.ly
1243 retuned from 0.40 to 0.39 by MS because of slight increases
1244 in gap.length () resulting from measuring beams at real ends
1245 instead of from the middle of stems.
1248 This function needs better comments so we know what is forbidden
1251 Real fixed_demerit = 0.39;
1253 dem += extra_demerit
1255 + (1 - fixed_demerit) * (dist / gap.length ()) * 2);
1260 config->add (dem, "Fl");
1262 if (std::max (edge_beam_counts_[LEFT], edge_beam_counts_[RIGHT]) >= 2)
1264 Real straddle = 0.0;
1265 Real sit = (beam_thickness_ - line_thickness_) / 2;
1267 Real hang = 1.0 - (beam_thickness_ - line_thickness_) / 2;
1269 for (LEFT_and_RIGHT (d))
1271 if (edge_beam_counts_[d] >= 2
1272 && fabs (config->y[d] - edge_dirs_[d] * beam_translation_) < staff_radius_ + inter)
1274 // TODO up/down symmetry.
1275 if (edge_dirs_[d] == UP && dy <= eps
1276 && fabs (my_modf (config->y[d]) - sit) < eps)
1277 dem += extra_demerit;
1279 if (edge_dirs_[d] == DOWN && dy >= eps
1280 && fabs (my_modf (config->y[d]) - hang) < eps)
1281 dem += extra_demerit;
1284 if (edge_beam_counts_[d] >= 3
1285 && fabs (config->y[d] - 2 * edge_dirs_[d] * beam_translation_) < staff_radius_ + inter)
1287 // TODO up/down symmetry.
1288 if (edge_dirs_[d] == UP && dy <= eps
1289 && fabs (my_modf (config->y[d]) - straddle) < eps)
1290 dem += extra_demerit;
1292 if (edge_dirs_[d] == DOWN && dy >= eps
1293 && fabs (my_modf (config->y[d]) - straddle) < eps)
1294 dem += extra_demerit;
1299 config->add (dem, "Fs");
1303 Beam_scoring_problem::score_collisions (Beam_configuration *config) const
1305 Real demerits = 0.0;
1306 for (vsize i = 0; i < collisions_.size (); i++)
1308 Interval collision_y = collisions_[i].y_;
1309 Real x = collisions_[i].x_;
1311 Real center_beam_y = y_at (x, config);
1312 Interval beam_y = center_beam_y + collisions_[i].beam_y_;
1314 Real dist = infinity_f;
1315 if (!intersection (beam_y, collision_y).is_empty ())
1318 dist = std::min (beam_y.distance (collision_y[DOWN]),
1319 beam_y.distance (collision_y[UP]));
1323 = std::max (parameters_.COLLISION_PADDING - dist, 0.0)
1324 / parameters_.COLLISION_PADDING;
1325 Real collision_demerit = collisions_[i].base_penalty_ *
1326 pow (scale_free, 3) * parameters_.COLLISION_PENALTY;
1328 if (collision_demerit > 0) {
1329 demerits += collision_demerit;
1333 config->add (demerits, "C");