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"
55 get_detail (SCM alist, SCM sym, Real def)
57 SCM entry = scm_assq (sym, alist);
59 if (scm_is_pair (entry))
60 return robust_scm2double (scm_cdr (entry), def);
65 Beam_quant_parameters::fill (Grob *him)
67 SCM details = him->get_property ("details");
70 BEAM_EPS = get_detail (details, ly_symbol2scm ("beam-eps"), 1e-3);
71 REGION_SIZE = get_detail (details, ly_symbol2scm ("region-size"), 2);
74 SECONDARY_BEAM_DEMERIT = get_detail (details, ly_symbol2scm ("secondary-beam-demerit"), 10.0)
75 // For stems that are non-standard, the forbidden beam quanting
76 // doesn't really work, so decrease their importance.
77 * exp(- 8*fabs (1.0 - robust_scm2double(him->get_property ("length-fraction"), 1.0)));
78 STEM_LENGTH_DEMERIT_FACTOR = get_detail (details, ly_symbol2scm ("stem-length-demerit-factor"), 5);
79 HORIZONTAL_INTER_QUANT_PENALTY = get_detail (details, ly_symbol2scm ("horizontal-inter-quant"), 500);
81 STEM_LENGTH_LIMIT_PENALTY = get_detail (details, ly_symbol2scm ("stem-length-limit-penalty"), 5000);
82 DAMPING_DIRECTION_PENALTY = get_detail (details, ly_symbol2scm ("damping-direction-penalty"), 800);
83 HINT_DIRECTION_PENALTY = get_detail (details, ly_symbol2scm ("hint-direction-penalty"), 20);
84 MUSICAL_DIRECTION_FACTOR = get_detail (details, ly_symbol2scm ("musical-direction-factor"), 400);
85 IDEAL_SLOPE_FACTOR = get_detail (details, ly_symbol2scm ("ideal-slope-factor"), 10);
86 ROUND_TO_ZERO_SLOPE = get_detail (details, ly_symbol2scm ("round-to-zero-slope"), 0.02);
89 COLLISION_PENALTY = get_detail (details, ly_symbol2scm ("collision-penalty"), 500);
91 /* For grace notes, beams get scaled down to 80%, but glyphs go down
92 to 63% (magstep -4 for accidentals). To make the padding
93 commensurate with glyph size for grace notes, we take the square
94 of the length fraction, yielding a 64% decrease.
96 COLLISION_PADDING = get_detail (details, ly_symbol2scm ("collision-padding"), 0.5)
97 * sqr (robust_scm2double(him->get_property ("length-fraction"), 1.0));
98 STEM_COLLISION_FACTOR = get_detail (details, ly_symbol2scm ("stem-collision-factor"), 0.1);
101 // Add x if x is positive, add |x|*fac if x is negative.
103 shrink_extra_weight (Real x, Real fac)
105 return fabs (x) * ((x < 0) ? fac : 1.0);
108 /****************************************************************/
110 Beam_configuration::Beam_configuration ()
112 y = Interval (0.0, 0.0);
114 next_scorer_todo = ORIGINAL_DISTANCE;
117 bool Beam_configuration::done () const
119 return next_scorer_todo >= NUM_SCORERS;
122 void Beam_configuration::add (Real demerit, const string &reason)
126 #if DEBUG_BEAM_SCORING
128 score_card_ += to_string (" %s %.2f", reason.c_str (), demerit);
132 Beam_configuration *Beam_configuration::new_config (Interval start,
135 Beam_configuration *qs = new Beam_configuration;
136 qs->y = Interval (int (start[LEFT]) + offset[LEFT],
137 int (start[RIGHT]) + offset[RIGHT]);
139 // This orders the sequence so we try combinations closest to the
140 // the ideal offset first.
141 Real start_score = abs (offset[RIGHT]) + abs (offset[LEFT]);
142 qs->demerits = start_score / 1000.0;
143 qs->next_scorer_todo = ORIGINAL_DISTANCE + 1;
149 Beam_scoring_problem::y_at (Real x, Beam_configuration const *p) const
151 return p->y[LEFT] + x * p->y.delta () / x_span_;
154 /****************************************************************/
159 - Make all demerits customisable
161 - Add demerits for quants per se, as to forbid a specific quant
165 // This is a temporary hack to see how much we can gain by using a
166 // priority queue on the beams to score.
167 static int score_count = 0;
168 LY_DEFINE (ly_beam_score_count, "ly:beam-score-count", 0, 0, 0,
170 "count number of beam scores.")
172 return scm_from_int (score_count);
175 void Beam_scoring_problem::add_collision (Real x, Interval y,
178 // We used to screen for quant range, but no more.
181 c.beam_y_.set_empty ();
183 for (vsize j = 0; j < segments_.size (); j++)
185 if (segments_[j].horizontal_.contains (x))
186 c.beam_y_.add_point (segments_[j].vertical_count_ * beam_translation_);
187 if (segments_[j].horizontal_[LEFT] > x)
190 c.beam_y_.widen (0.5 * beam_thickness_);
194 y *= 1 / staff_space_;
196 c.base_penalty_ = score_factor;
197 collisions_.push_back (c);
200 void Beam_scoring_problem::init_instance_variables (Grob *me, Drul_array<Real> ys, bool align_broken_intos)
202 beam_ = dynamic_cast<Spanner *> (me);
206 If 'ys' are finite, use them as starting points for y-positions of the
207 ends of the beam, instead of the best-fit through the natural ends of
208 the stems. Otherwise, we want to do initial slope calculations.
210 do_initial_slope_calculations_ = false;
211 for (LEFT_and_RIGHT (d))
212 do_initial_slope_calculations_ |= isinf (unquanted_y_[d]) || isnan (unquanted_y_[d]);
215 Calculations are relative to a unit-scaled staff, i.e. the quants are
216 divided by the current staff_space_.
218 staff_space_ = Staff_symbol_referencer::staff_space (beam_);
219 beam_thickness_ = Beam::get_beam_thickness (beam_) / staff_space_;
220 line_thickness_ = Staff_symbol_referencer::line_thickness (beam_) / staff_space_;
222 // This is the least-squares DY, corrected for concave beams.
223 musical_dy_ = robust_scm2double (beam_->get_property ("least-squares-dy"), 0);
225 vector<Spanner *> beams;
226 align_broken_intos_ = align_broken_intos;
227 if (align_broken_intos_)
229 Spanner *orig = dynamic_cast<Spanner *> (beam_->original ());
231 align_broken_intos_ = false;
232 else if (!orig->broken_intos_.size ())
233 align_broken_intos_ = false;
235 beams.insert (beams.end (), orig->broken_intos_.begin (), orig->broken_intos_.end ());
237 if (!align_broken_intos_)
238 beams.push_back (beam_);
241 x_span_ is a single scalar, cumulatively summing the length of all the
242 segments the parent beam was broken-into.
246 normal_stem_count_ = 0;
247 for (vsize i = 0; i < beams.size (); i++)
249 extract_grob_set (beams[i], "stems", stems);
250 extract_grob_set (beams[i], "covered-grobs", fake_collisions);
251 vector<Grob *> collisions;
253 for (vsize j = 0; j < fake_collisions.size (); j++)
254 if (fake_collisions[j]->get_system () == beams[i]->get_system ())
255 collisions.push_back (fake_collisions[j]);
258 for (int a = 2; a--;)
259 common[a] = common_refpoint_of_array (stems, beams[i], Axis (a));
261 for (LEFT_and_RIGHT (d))
262 common[X_AXIS] = beams[i]->get_bound (d)->common_refpoint (common[X_AXIS], X_AXIS);
264 // positions of the endpoints of this beam segment, including any overhangs
265 const Interval x_pos = robust_scm2interval (beams[i]->get_property ("X-positions"),
266 Interval (0.0, 0.0));
268 Drul_array<Grob *> edge_stems (Beam::first_normal_stem (beams[i]),
269 Beam::last_normal_stem (beams[i]));
271 Drul_array<bool> dirs_found (0, 0);
273 Real my_y = beams[i]->relative_coordinate (common[Y_AXIS], Y_AXIS);
275 Interval beam_width (-1.0, -1.0);
276 for (vsize j = 0; j < stems.size (); j++)
279 beam_multiplicity_.push_back (Stem::beam_multiplicity (stems[j]));
280 head_positions_.push_back (Stem::head_positions (stems[j]));
281 is_normal_.push_back (Stem::is_normal_stem (stems[j]));
283 Stem_info si (Stem::get_stem_info (s));
284 si.scale (1 / staff_space_);
285 stem_infos_.push_back (si);
286 chord_start_y_.push_back (Stem::chord_start_y (s));
287 dirs_found[si.dir_] = true;
289 bool f = to_boolean (s->get_property ("french-beaming"))
290 && s != edge_stems[LEFT] && s != edge_stems[RIGHT];
292 Real y = Beam::calc_stem_y (beams[i], s, common, x_pos[LEFT], x_pos[RIGHT], CENTER,
294 base_lengths_.push_back (y / staff_space_);
295 stem_xpositions_.push_back (s->relative_coordinate (common[X_AXIS], X_AXIS) - x_pos[LEFT] + x_span_);
296 stem_ypositions_.push_back (s->relative_coordinate (common[Y_AXIS], Y_AXIS) - my_y);
298 if (is_normal_.back ())
300 if (beam_width[LEFT] == -1.0)
301 beam_width[LEFT] = stem_xpositions_.back ();
302 beam_width[RIGHT] = stem_xpositions_.back ();
306 edge_dirs_ = Drul_array<Direction> (CENTER, CENTER);
307 normal_stem_count_ += Beam::normal_stem_count (beams[i]);
308 if (normal_stem_count_)
309 edge_dirs_ = Drul_array<Direction> (stem_infos_[0].dir_,
310 stem_infos_.back ().dir_);
312 is_xstaff_ = has_interface<Align_interface> (common[Y_AXIS]);
313 is_knee_ |= dirs_found[DOWN] && dirs_found[UP];
315 staff_radius_ = Staff_symbol_referencer::staff_radius (beams[i]);
316 edge_beam_counts_ = Drul_array<int>
317 (Stem::beam_multiplicity (stems[0]).length () + 1,
318 Stem::beam_multiplicity (stems.back ()).length () + 1);
320 // TODO - why are we dividing by staff_space_?
321 beam_translation_ = Beam::get_beam_translation (beams[i]) / staff_space_;
323 for (LEFT_and_RIGHT (d))
325 quant_range_[d].set_full ();
329 Real stem_offset = edge_stems[d]->relative_coordinate (common[Y_AXIS], Y_AXIS)
330 - beams[i]->relative_coordinate (common[Y_AXIS], Y_AXIS);
331 Interval heads = Stem::head_positions (edge_stems[d]) * 0.5 * staff_space_;
333 Direction ed = edge_dirs_[d];
334 heads.widen (0.5 * staff_space_
335 + (edge_beam_counts_[d] - 1) * beam_translation_ + beam_thickness_ * .5);
336 quant_range_[d][-ed] = heads[ed] + stem_offset;
339 segments_ = Beam::get_beam_segments (beams[i]);
340 vector_sort (segments_, beam_segment_less);
341 for (vsize j = 0; j < segments_.size (); j++)
342 segments_[j].horizontal_ += (x_span_ - x_pos[LEFT]);
344 set<Grob *> colliding_stems;
345 for (vsize j = 0; j < collisions.size (); j++)
347 if (!collisions[j]->is_live ())
350 if (has_interface<Beam> (collisions[j]) && Beam::is_cross_staff (collisions[j]))
354 for (Axis a = X_AXIS; a < NO_AXES; incr (a))
355 b[a] = collisions[j]->extent (common[a], a);
357 if (b[X_AXIS][RIGHT] < x_pos[LEFT] || b[X_AXIS][LEFT] > x_pos[RIGHT])
359 if (b[X_AXIS].is_empty () || b[Y_AXIS].is_empty ())
362 b[X_AXIS] += (x_span_ - x_pos[LEFT]);
364 Real width = b[X_AXIS].length ();
365 Real width_factor = sqrt (width / staff_space_);
367 for (LEFT_and_RIGHT (d))
368 add_collision (b[X_AXIS][d], b[Y_AXIS], width_factor);
370 Grob *stem = unsmob<Grob> (collisions[j]->get_object ("stem"));
371 if (has_interface<Stem> (stem) && Stem::is_normal_stem (stem))
373 colliding_stems.insert (stem);
377 for (set<Grob *>::const_iterator it (colliding_stems.begin ()); it != colliding_stems.end (); it++)
380 Real x = (robust_relative_extent (s, common[X_AXIS], X_AXIS) - x_pos[LEFT] + x_span_).center ();
382 Direction stem_dir = get_grob_direction (*it);
385 y[-stem_dir] = Stem::chord_start_y (*it) + (*it)->relative_coordinate (common[Y_AXIS], Y_AXIS)
388 Real factor = parameters_.STEM_COLLISION_FACTOR;
389 if (!unsmob<Grob> (s->get_object ("beam")))
391 add_collision (x, y, factor);
393 x_span_ += beams[i]->spanner_length ();
397 Beam_scoring_problem::Beam_scoring_problem (Grob *me, Drul_array<Real> ys, bool align_broken_intos)
399 beam_ = dynamic_cast<Spanner *> (me);
401 align_broken_intos_ = align_broken_intos;
403 parameters_.fill (me);
404 init_instance_variables (me, ys, align_broken_intos);
405 if (do_initial_slope_calculations_)
407 least_squares_positions ();
409 shift_region_to_valid ();
413 // Assuming V is not empty, pick a 'reasonable' point inside V.
415 point_in_interval (Interval v, Real dist)
419 else if (isinf (v[UP]))
420 return v[DOWN] + dist;
425 /* Set stem's shorten property if unset.
428 take some y-position (chord/beam/nearest?) into account
429 scmify forced-fraction
431 This is done in beam because the shorten has to be uniform over the
436 set_minimum_dy (Grob *me, Real *dy)
441 If dy is smaller than the smallest quant, we
442 get absurd direction-sign penalties.
445 Real ss = Staff_symbol_referencer::staff_space (me);
446 Real beam_thickness = Beam::get_beam_thickness (me) / ss;
447 Real slt = Staff_symbol_referencer::line_thickness (me) / ss;
448 Real sit = (beam_thickness - slt) / 2;
450 Real hang = 1.0 - (beam_thickness - slt) / 2;
452 *dy = sign (*dy) * max (fabs (*dy),
453 min (min (sit, inter), hang));
458 Beam_scoring_problem::no_visible_stem_positions ()
460 if (!head_positions_.size ())
462 unquanted_y_ = Interval (0, 0);
466 Interval head_positions;
468 for (vsize i = 0; i < head_positions_.size (); i++)
470 head_positions.unite (head_positions_[i]);
471 multiplicity.unite (beam_multiplicity_[i]);
474 Direction dir = get_grob_direction (beam_);
477 programming_error ("The beam should have a direction by now.");
479 Real y = head_positions.linear_combination (dir)
481 + dir * beam_translation_ * (multiplicity.length () + 1);
483 unquanted_y_ = Interval (y, y);
487 Beam_scoring_problem::first_normal_index ()
489 for (vsize i = 0; i < is_normal_.size (); i++)
493 beam_->programming_error ("No normal stems, but asking for first normal stem index.");
498 Beam_scoring_problem::last_normal_index ()
500 for (vsize i = is_normal_.size (); i--;)
504 beam_->programming_error ("No normal stems, but asking for first normal stem index.");
509 Beam_scoring_problem::least_squares_positions ()
511 if (!normal_stem_count_)
513 no_visible_stem_positions ();
517 if (stem_infos_.size () < 1)
520 vsize fnx = first_normal_index ();
521 vsize lnx = last_normal_index ();
523 Interval ideal (stem_infos_[fnx].ideal_y_ + stem_ypositions_[fnx],
524 stem_infos_[lnx].ideal_y_ + stem_ypositions_[lnx]);
532 Interval chord (chord_start_y_[0],
533 chord_start_y_.back ());
535 /* Simple beams (2 stems) on middle line should be allowed to be
538 However, if both stems reach middle line,
539 ideal[LEFT] == ideal[RIGHT] and ideal.delta () == 0.
541 For that case, we apply artificial slope */
542 if (!ideal[LEFT] && chord.delta () && stem_infos_.size () == 2)
545 Direction d = (Direction) (sign (chord.delta ()) * UP);
546 unquanted_y_[d] = Beam::get_beam_thickness (beam_) / 2;
547 unquanted_y_[-d] = -unquanted_y_[d];
550 unquanted_y_ = ideal;
552 ldy = unquanted_y_[RIGHT] - unquanted_y_[LEFT];
556 vector<Offset> ideals;
557 for (vsize i = 0; i < stem_infos_.size (); i++)
559 ideals.push_back (Offset (stem_xpositions_[i],
560 stem_infos_[i].ideal_y_
561 + stem_ypositions_[i]));
563 minimise_least_squares (&slope, &y, ideals);
565 dy = slope * x_span_;
567 set_minimum_dy (beam_, &dy);
570 unquanted_y_ = Interval (y, (y + dy));
574 beam_->set_property ("least-squares-dy", scm_from_double (musical_dy_));
578 Determine whether a beam is concave.
580 A beam is concave when the middle notes get closer to the
581 beam than the left and right edge notes.
583 This is determined in two ways: by looking at the positions of the
584 middle notes, or by looking at the deviation of the inside notes
585 compared to the line connecting first and last.
587 The tricky thing is what to do with beams with chords. There are no
588 real guidelines in this case.
592 is_concave_single_notes (vector<int> const &positions, Direction beam_dir)
595 covering.add_point (positions[0]);
596 covering.add_point (positions.back ());
600 bool concave = false;
603 notes above and below the interval covered by 1st and last note.
605 for (vsize i = 1; i + 1 < positions.size (); i++)
607 above = above || (positions[i] > covering[UP]);
608 below = below || (positions[i] < covering[DOWN]);
611 concave = concave || (above && below);
613 A note as close or closer to the beam than begin and end, but the
614 note is reached in the opposite direction as the last-first dy
616 int dy = positions.back () - positions[0];
617 int closest = max (beam_dir * positions.back (), beam_dir * positions[0]);
618 for (vsize i = 2; !concave && i + 1 < positions.size (); i++)
620 int inner_dy = positions[i] - positions[i - 1];
621 if (sign (inner_dy) != sign (dy)
622 && (beam_dir * positions[i] >= closest
623 || beam_dir * positions[i - 1] >= closest))
627 bool all_closer = true;
628 for (vsize i = 1; all_closer && i + 1 < positions.size (); i++)
630 all_closer = all_closer
631 && (beam_dir * positions[i] > closest);
634 concave = concave || all_closer;
639 calc_positions_concaveness (vector<int> const &positions, Direction beam_dir)
641 Real dy = positions.back () - positions[0];
642 Real slope = dy / Real (positions.size () - 1);
643 Real concaveness = 0.0;
644 for (vsize i = 1; i + 1 < positions.size (); i++)
646 Real line_y = slope * i + positions[0];
648 concaveness += max (beam_dir * (positions[i] - line_y), 0.0);
651 concaveness /= positions.size ();
654 Normalize. For dy = 0, the slope ends up as 0 anyway, so the
655 scaling of concaveness doesn't matter much.
658 concaveness /= fabs (dy);
663 Beam_scoring_problem::calc_concaveness ()
665 SCM conc = beam_->get_property ("concaveness");
666 if (scm_is_number (conc))
667 return scm_to_double (conc);
669 if (is_knee_ || is_xstaff_)
672 Direction beam_dir = CENTER;
673 for (vsize i = is_normal_.size (); i--;)
674 if (is_normal_[i] && stem_infos_[i].dir_)
675 beam_dir = stem_infos_[i].dir_;
677 if (normal_stem_count_ <= 2)
680 vector<int> close_positions;
681 vector<int> far_positions;
682 for (vsize i = 0; i < is_normal_.size (); i++)
686 For chords, we take the note head that is closest to the beam.
688 Hmmm.. wait, for the beams in the last measure of morgenlied,
689 this doesn't look so good. Let's try the heads farthest from
693 close_positions.push_back ((int) rint (head_positions_[i][beam_dir]));
694 far_positions.push_back ((int) rint (head_positions_[i][-beam_dir]));
697 Real concaveness = 0.0;
699 if (is_concave_single_notes (beam_dir == UP ? close_positions : far_positions, beam_dir))
705 concaveness = (calc_positions_concaveness (far_positions, beam_dir)
706 + calc_positions_concaveness (close_positions, beam_dir)) / 2;
713 Beam_scoring_problem::slope_damping ()
715 if (normal_stem_count_ <= 1)
718 SCM s = beam_->get_property ("damping");
719 Real damping = scm_to_double (s);
720 Real concaveness = calc_concaveness ();
721 if (concaveness >= 10000)
723 unquanted_y_[LEFT] = unquanted_y_[RIGHT];
730 Real dy = unquanted_y_[RIGHT] - unquanted_y_[LEFT];
732 Real slope = dy && x_span_ ? dy / x_span_ : 0;
734 slope = 0.6 * tanh (slope) / (damping + concaveness);
736 Real damped_dy = slope * x_span_;
738 set_minimum_dy (beam_, &damped_dy);
740 unquanted_y_[LEFT] += (dy - damped_dy) / 2;
741 unquanted_y_[RIGHT] -= (dy - damped_dy) / 2;
746 Beam_scoring_problem::shift_region_to_valid ()
748 if (!normal_stem_count_)
751 Real beam_dy = unquanted_y_[RIGHT] - unquanted_y_[LEFT];
752 Real slope = x_span_ ? beam_dy / x_span_ : 0.0;
755 Shift the positions so that we have a chance of finding good
756 quants (i.e. no short stem failures.)
758 Interval feasible_left_point;
759 feasible_left_point.set_full ();
761 for (vsize i = 0; i < stem_infos_.size (); i++)
763 // TODO - check for invisible here...
765 = stem_infos_[i].shortest_y_
766 - slope * stem_xpositions_ [i];
769 left_y is now relative to the stem S. We want relative to
770 ourselves, so translate:
772 left_y += stem_ypositions_[i];
775 flp[-stem_infos_[i].dir_] = left_y;
777 feasible_left_point.intersect (flp);
780 vector<Grob *> filtered;
782 We only update these for objects that are too large for quanting
783 to find a workaround. Typically, these are notes with
784 stems, and timesig/keysig/clef, which take out the entire area
785 inside the staff as feasible.
787 The code below disregards the thickness and multiplicity of the
788 beam. This should not be a problem, as the beam quanting will
789 take care of computing the impact those exactly.
791 Real min_y_size = 2.0;
793 // A list of intervals into which beams may not fall
794 vector<Interval> forbidden_intervals;
796 for (vsize i = 0; i < collisions_.size (); i++)
798 if (collisions_[i].x_ < 0 || collisions_[i].x_ > x_span_)
801 if (collisions_[i].y_.length () < min_y_size)
804 for (LEFT_and_RIGHT (d))
806 Real dy = slope * collisions_[i].x_;
809 for (DOWN_and_UP (yd))
811 Real left_y = collisions_[i].y_[yd] - dy;
812 disallowed[yd] = left_y;
815 forbidden_intervals.push_back (disallowed);
819 vector_sort (forbidden_intervals, Interval::left_less);
820 Real beam_left_y = unquanted_y_[LEFT];
821 Interval feasible_beam_placements (beam_left_y, beam_left_y);
823 Interval_minefield minefield (feasible_beam_placements, 0.0);
824 for (vsize i = 0; i < forbidden_intervals.size (); i++)
825 minefield.add_forbidden_interval (forbidden_intervals[i]);
827 feasible_beam_placements = minefield.feasible_placements ();
829 // if the beam placement falls out of the feasible region, we push it
830 // to infinity so that it can never be a feasible candidate below
831 for (DOWN_and_UP (d))
833 if (!feasible_left_point.contains (feasible_beam_placements[d]))
834 feasible_beam_placements[d] = d * infinity_f;
837 if ((feasible_beam_placements[UP] == infinity_f && feasible_beam_placements[DOWN] == -infinity_f) && !feasible_left_point.is_empty ())
839 // We are somewhat screwed: we have a collision, but at least
840 // there is a way to satisfy stem length constraints.
841 beam_left_y = point_in_interval (feasible_left_point, 2.0);
843 else if (!feasible_left_point.is_empty ())
845 // Only one of them offers is feasible solution. Pick that one.
846 if (abs (beam_left_y - feasible_beam_placements[DOWN]) > abs (beam_left_y - feasible_beam_placements[UP]))
847 beam_left_y = feasible_beam_placements[UP];
849 beam_left_y = feasible_beam_placements[DOWN];
853 // We are completely screwed.
854 beam_->warning (_ ("no viable initial configuration found: may not find good beam slope"));
857 unquanted_y_ = Drul_array<Real> (beam_left_y, (beam_left_y + beam_dy));
861 Beam_scoring_problem::generate_quants (vector<Beam_configuration *> *scores) const
863 int region_size = (int) parameters_.REGION_SIZE;
865 // Knees and collisions are harder, lets try some more possibilities
868 if (collisions_.size ())
872 Real sit = (beam_thickness_ - line_thickness_) / 2;
874 Real hang = 1.0 - (beam_thickness_ - line_thickness_) / 2;
875 Real base_quants [] = {straddle, sit, inter, hang};
876 int num_base_quants = int (sizeof (base_quants) / sizeof (Real));
879 Asymetry ? should run to <= region_size ?
881 vector<Real> unshifted_quants;
882 for (int i = -region_size; i < region_size; i++)
883 for (int j = 0; j < num_base_quants; j++)
885 unshifted_quants.push_back (i + base_quants[j]);
888 for (vsize i = 0; i < unshifted_quants.size (); i++)
889 for (vsize j = 0; j < unshifted_quants.size (); j++)
891 Beam_configuration *c
892 = Beam_configuration::new_config (unquanted_y_,
893 Interval (unshifted_quants[i],
894 unshifted_quants[j]));
896 for (LEFT_and_RIGHT (d))
898 if (!quant_range_[d].contains (c->y[d]))
906 scores->push_back (c);
911 void Beam_scoring_problem::one_scorer (Beam_configuration *config) const
914 switch (config->next_scorer_todo)
917 score_slope_ideal (config);
919 case SLOPE_DIRECTION:
920 score_slope_direction (config);
923 score_slope_musical (config);
926 score_forbidden_quants (config);
929 score_stem_lengths (config);
932 score_collisions (config);
934 case HORIZONTAL_INTER:
935 score_horizontal_inter_quants (config);
939 case ORIGINAL_DISTANCE:
943 config->next_scorer_todo++;
947 Beam_scoring_problem::force_score (SCM inspect_quants, const vector<Beam_configuration *> &configs) const
949 Drul_array<Real> ins = ly_scm2interval (inspect_quants);
951 Beam_configuration *best = NULL;
952 for (vsize i = 0; i < configs.size (); i++)
954 Real d = fabs (configs[i]->y[LEFT] - ins[LEFT]) + fabs (configs[i]->y[RIGHT] - ins[RIGHT]);
962 programming_error ("cannot find quant");
964 while (!best->done ())
971 Beam_scoring_problem::solve () const
973 vector<Beam_configuration *> configs;
974 generate_quants (&configs);
976 if (configs.empty ())
978 programming_error ("No viable beam quanting found. Using unquanted y value.");
982 if (to_boolean (beam_->get_property ("skip-quanting")))
985 Beam_configuration *best = NULL;
988 = to_boolean (beam_->layout ()->lookup_variable (ly_symbol2scm ("debug-beam-scoring")));
989 SCM inspect_quants = beam_->get_property ("inspect-quants");
990 if (scm_is_pair (inspect_quants))
993 best = force_score (inspect_quants, configs);
997 std::priority_queue < Beam_configuration *, std::vector<Beam_configuration *>,
998 Beam_configuration_less > queue;
999 for (vsize i = 0; i < configs.size (); i++)
1000 queue.push (configs[i]);
1005 It would be neat if we generated new configurations on the
1006 fly, depending on the best complete score so far, eg.
1009 if (best->demerits < sqrt(queue.size())
1011 while (best->demerits > sqrt(queue.size()) {
1012 generate and insert new configuration
1016 that would allow us to do away with region_size altogether.
1020 best = queue.top ();
1030 Interval final_positions = best->y;
1032 #if DEBUG_BEAM_SCORING
1037 for (vsize i = 0; i < configs.size (); i++)
1039 if (configs[i]->done ())
1043 string card = best->score_card_ + to_string (" c%d/%d", completed, configs.size ());
1044 beam_->set_property ("annotation", ly_string2scm (card));
1048 junk_pointers (configs);
1049 if (align_broken_intos_)
1051 Interval normalized_endpoints = robust_scm2interval (beam_->get_property ("normalized-endpoints"), Interval (0, 1));
1052 Real y_length = final_positions[RIGHT] - final_positions[LEFT];
1054 final_positions[LEFT] += normalized_endpoints[LEFT] * y_length;
1055 final_positions[RIGHT] -= (1 - normalized_endpoints[RIGHT]) * y_length;
1058 return final_positions;
1062 Beam_scoring_problem::score_stem_lengths (Beam_configuration *config) const
1064 Real limit_penalty = parameters_.STEM_LENGTH_LIMIT_PENALTY;
1065 Drul_array<Real> score (0, 0);
1066 Drul_array<int> count (0, 0);
1068 for (vsize i = 0; i < stem_xpositions_.size (); i++)
1073 Real x = stem_xpositions_[i];
1076 ? config->y[RIGHT] * x / dx + config->y[LEFT] * (x_span_ - x) / dx
1077 : (config->y[RIGHT] + config->y[LEFT]) / 2;
1078 Real current_y = beam_y + base_lengths_[i];
1079 Real length_pen = parameters_.STEM_LENGTH_DEMERIT_FACTOR;
1081 Stem_info info = stem_infos_[i];
1082 Direction d = info.dir_;
1084 score[d] += limit_penalty * max (0.0, (d * (info.shortest_y_ - current_y)));
1086 Real ideal_diff = d * (current_y - info.ideal_y_);
1087 Real ideal_score = shrink_extra_weight (ideal_diff, 1.5);
1089 /* We introduce a power, to make the scoring strictly
1090 convex. Otherwise a symmetric knee beam (up/down/up/down)
1091 does not have an optimum in the middle. */
1093 ideal_score = pow (ideal_score, 1.1);
1095 score[d] += length_pen * ideal_score;
1099 /* Divide by number of stems, to make the measure scale-free. */
1100 for (DOWN_and_UP (d))
1101 score[d] /= max (count[d], 1);
1104 sometimes, two perfectly symmetric kneed beams will have the same score
1105 and can either be quanted up or down.
1107 we choose the quanting in the direction of the slope so that the first stem
1108 always seems longer, reaching to the second, rather than squashed.
1110 if (is_knee_ && count[LEFT] == count[RIGHT] && count[LEFT] == 1 && unquanted_y_.delta ())
1111 score[Direction (sign (unquanted_y_.delta ()))] += score[Direction (sign (unquanted_y_.delta ()))] < 1.0 ? 0.01 : 0.0;
1113 config->add (score[LEFT] + score[RIGHT], "L");
1117 Beam_scoring_problem::score_slope_direction (Beam_configuration *config) const
1119 Real dy = config->y.delta ();
1120 Real damped_dy = unquanted_y_.delta ();
1123 DAMPING_DIRECTION_PENALTY is a very harsh measure, while for
1124 complex beaming patterns, horizontal is often a good choice.
1126 TODO: find a way to incorporate the complexity of the beam in this
1129 if (sign (damped_dy) != sign (dy))
1133 if (fabs (damped_dy / x_span_) > parameters_.ROUND_TO_ZERO_SLOPE)
1134 dem += parameters_.DAMPING_DIRECTION_PENALTY;
1136 dem += parameters_.HINT_DIRECTION_PENALTY;
1139 dem += parameters_.DAMPING_DIRECTION_PENALTY;
1142 config->add (dem, "Sd");
1145 // Score for going against the direction of the musical pattern
1147 Beam_scoring_problem::score_slope_musical (Beam_configuration *config) const
1149 Real dy = config->y.delta ();
1150 Real dem = parameters_.MUSICAL_DIRECTION_FACTOR
1151 * max (0.0, (fabs (dy) - fabs (musical_dy_)));
1152 config->add (dem, "Sm");
1155 // Score deviation from calculated ideal slope.
1157 Beam_scoring_problem::score_slope_ideal (Beam_configuration *config) const
1159 Real dy = config->y.delta ();
1160 Real damped_dy = unquanted_y_.delta ();
1163 Real slope_penalty = parameters_.IDEAL_SLOPE_FACTOR;
1165 /* Xstaff beams tend to use extreme slopes to get short stems. We
1166 put in a penalty here. */
1168 slope_penalty *= 10;
1170 /* Huh, why would a too steep beam be better than a too flat one ? */
1171 dem += shrink_extra_weight (fabs (damped_dy) - fabs (dy), 1.5)
1174 config->add (dem, "Si");
1180 return x - floor (x);
1183 // TODO - there is some overlap with forbidden quants, but for
1184 // horizontal beams, it is much more serious to have stafflines
1185 // appearing in the wrong place, so we have a separate scorer.
1187 Beam_scoring_problem::score_horizontal_inter_quants (Beam_configuration *config) const
1189 if (config->y.delta () == 0.0
1190 && abs (config->y[LEFT]) < staff_radius_ * staff_space_)
1192 Real yshift = config->y[LEFT] - 0.5 * staff_space_;
1193 if (fabs (my_round (yshift) - yshift) < 0.01 * staff_space_)
1194 config->add (parameters_.HORIZONTAL_INTER_QUANT_PENALTY, "H");
1199 TODO: The fixed value SECONDARY_BEAM_DEMERIT is probably flawed:
1200 because for 32nd and 64th beams the forbidden quants are relatively
1201 more important than stem lengths.
1204 Beam_scoring_problem::score_forbidden_quants (Beam_configuration *config) const
1206 Real dy = config->y.delta ();
1208 Real extra_demerit =
1209 parameters_.SECONDARY_BEAM_DEMERIT
1210 / max (edge_beam_counts_[LEFT], edge_beam_counts_[RIGHT]);
1213 Real eps = parameters_.BEAM_EPS;
1215 for (LEFT_and_RIGHT (d))
1217 for (int j = 1; j <= edge_beam_counts_[d]; j++)
1219 Direction stem_dir = edge_dirs_[d];
1222 The fudge_factor is to provide a little leniency for
1223 borderline cases. If we do 2.0, then the upper outer line
1224 will be in the gap of the (2, sit) quant, leading to a
1225 false demerit. By increasing the fudge factor to 2.2, we
1228 Real fudge_factor = 2.2;
1229 Real gap1 = config->y[d] - stem_dir * ((j - 1) * beam_translation_ + beam_thickness_ / 2 - line_thickness_ / fudge_factor);
1230 Real gap2 = config->y[d] - stem_dir * (j * beam_translation_ - beam_thickness_ / 2 + line_thickness_ / fudge_factor);
1233 gap.add_point (gap1);
1234 gap.add_point (gap2);
1236 for (Real k = -staff_radius_;
1237 k <= staff_radius_ + eps; k += 1.0)
1238 if (gap.contains (k))
1240 Real dist = min (fabs (gap[UP] - k), fabs (gap[DOWN] - k));
1243 this parameter is tuned to grace-stem-length.ly
1244 retuned from 0.40 to 0.39 by MS because of slight increases
1245 in gap.length () resulting from measuring beams at real ends
1246 instead of from the middle of stems.
1249 This function needs better comments so we know what is forbidden
1252 Real fixed_demerit = 0.39;
1254 dem += extra_demerit
1256 + (1 - fixed_demerit) * (dist / gap.length ()) * 2);
1261 config->add (dem, "Fl");
1263 if (max (edge_beam_counts_[LEFT], edge_beam_counts_[RIGHT]) >= 2)
1265 Real straddle = 0.0;
1266 Real sit = (beam_thickness_ - line_thickness_) / 2;
1268 Real hang = 1.0 - (beam_thickness_ - line_thickness_) / 2;
1270 for (LEFT_and_RIGHT (d))
1272 if (edge_beam_counts_[d] >= 2
1273 && fabs (config->y[d] - edge_dirs_[d] * beam_translation_) < staff_radius_ + inter)
1275 // TODO up/down symmetry.
1276 if (edge_dirs_[d] == UP && dy <= eps
1277 && fabs (my_modf (config->y[d]) - sit) < eps)
1278 dem += extra_demerit;
1280 if (edge_dirs_[d] == DOWN && dy >= eps
1281 && fabs (my_modf (config->y[d]) - hang) < eps)
1282 dem += extra_demerit;
1285 if (edge_beam_counts_[d] >= 3
1286 && fabs (config->y[d] - 2 * edge_dirs_[d] * beam_translation_) < staff_radius_ + inter)
1288 // TODO up/down symmetry.
1289 if (edge_dirs_[d] == UP && dy <= eps
1290 && fabs (my_modf (config->y[d]) - straddle) < eps)
1291 dem += extra_demerit;
1293 if (edge_dirs_[d] == DOWN && dy >= eps
1294 && fabs (my_modf (config->y[d]) - straddle) < eps)
1295 dem += extra_demerit;
1300 config->add (dem, "Fs");
1304 Beam_scoring_problem::score_collisions (Beam_configuration *config) const
1306 Real demerits = 0.0;
1307 for (vsize i = 0; i < collisions_.size (); i++)
1309 Interval collision_y = collisions_[i].y_;
1310 Real x = collisions_[i].x_;
1312 Real center_beam_y = y_at (x, config);
1313 Interval beam_y = center_beam_y + collisions_[i].beam_y_;
1315 Real dist = infinity_f;
1316 if (!intersection (beam_y, collision_y).is_empty ())
1319 dist = min (beam_y.distance (collision_y[DOWN]),
1320 beam_y.distance (collision_y[UP]));
1324 = max (parameters_.COLLISION_PADDING - dist, 0.0)
1325 / parameters_.COLLISION_PADDING;
1326 Real collision_demerit = collisions_[i].base_penalty_ *
1327 pow (scale_free, 3) * parameters_.COLLISION_PENALTY;
1329 if (collision_demerit > 0) {
1330 demerits += collision_demerit;
1334 config->add (demerits, "C");