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"
50 get_detail (SCM alist, SCM sym, Real def)
52 SCM entry = scm_assq (sym, alist);
54 if (scm_is_pair (entry))
55 return robust_scm2double (scm_cdr (entry), def);
60 Beam_quant_parameters::fill (Grob *him)
62 SCM details = him->get_property ("details");
65 BEAM_EPS = get_detail (details, ly_symbol2scm ("beam-eps"), 1e-3);
66 REGION_SIZE = get_detail (details, ly_symbol2scm ("region-size"), 2);
69 SECONDARY_BEAM_DEMERIT = get_detail (details, ly_symbol2scm ("secondary-beam-demerit"), 10.0);
70 STEM_LENGTH_DEMERIT_FACTOR = get_detail (details, ly_symbol2scm ("stem-length-demerit-factor"), 5);
71 HORIZONTAL_INTER_QUANT_PENALTY = get_detail (details, ly_symbol2scm ("horizontal-inter-quant"), 500);
73 STEM_LENGTH_LIMIT_PENALTY = get_detail (details, ly_symbol2scm ("stem-length-limit-penalty"), 5000);
74 DAMPING_DIRECTION_PENALTY = get_detail (details, ly_symbol2scm ("damping-direction-penalty"), 800);
75 HINT_DIRECTION_PENALTY = get_detail (details, ly_symbol2scm ("hint-direction-penalty"), 20);
76 MUSICAL_DIRECTION_FACTOR = get_detail (details, ly_symbol2scm ("musical-direction-factor"), 400);
77 IDEAL_SLOPE_FACTOR = get_detail (details, ly_symbol2scm ("ideal-slope-factor"), 10);
78 ROUND_TO_ZERO_SLOPE = get_detail (details, ly_symbol2scm ("round-to-zero-slope"), 0.02);
81 COLLISION_PENALTY = get_detail (details, ly_symbol2scm ("collision-penalty"), 500);
82 COLLISION_PADDING = get_detail (details, ly_symbol2scm ("collision-padding"), 0.5);
83 STEM_COLLISION_FACTOR = get_detail (details, ly_symbol2scm ("stem-collision-factor"), 0.1);
86 // Add x if x is positive, add |x|*fac if x is negative.
88 shrink_extra_weight (Real x, Real fac)
90 return fabs (x) * ((x < 0) ? fac : 1.0);
93 /****************************************************************/
95 Beam_configuration::Beam_configuration ()
97 y = Interval (0.0, 0.0);
99 next_scorer_todo = ORIGINAL_DISTANCE;
102 bool Beam_configuration::done () const
104 return next_scorer_todo >= NUM_SCORERS;
107 void Beam_configuration::add (Real demerit, const string &reason)
111 #if DEBUG_BEAM_SCORING
113 score_card_ += to_string (" %s %.2f", reason.c_str (), demerit);
117 Beam_configuration *Beam_configuration::new_config (Interval start,
120 Beam_configuration *qs = new Beam_configuration;
121 qs->y = Interval (int (start[LEFT]) + offset[LEFT],
122 int (start[RIGHT]) + offset[RIGHT]);
124 // This orders the sequence so we try combinations closest to the
125 // the ideal offset first.
126 Real start_score = abs (offset[RIGHT]) + abs (offset[LEFT]);
127 qs->demerits = start_score / 1000.0;
128 qs->next_scorer_todo = ORIGINAL_DISTANCE + 1;
134 Beam_scoring_problem::y_at (Real x, Beam_configuration const *p) const
136 return p->y[LEFT] + x * p->y.delta () / x_span_;
139 /****************************************************************/
144 - Make all demerits customisable
146 - Add demerits for quants per se, as to forbid a specific quant
150 // This is a temporary hack to see how much we can gain by using a
151 // priority queue on the beams to score.
152 static int score_count = 0;
153 LY_DEFINE (ly_beam_score_count, "ly:beam-score-count", 0, 0, 0,
155 "count number of beam scores.")
157 return scm_from_int (score_count);
160 void Beam_scoring_problem::add_collision (Real x, Interval y,
163 // We used to screen for quant range, but no more.
166 c.beam_y_.set_empty ();
168 for (vsize j = 0; j < segments_.size (); j++)
170 if (segments_[j].horizontal_.contains (x))
171 c.beam_y_.add_point (segments_[j].vertical_count_ * beam_translation_);
172 if (segments_[j].horizontal_[LEFT] > x)
175 c.beam_y_.widen (0.5 * beam_thickness_);
179 y *= 1 / staff_space_;
181 c.base_penalty_ = score_factor;
182 collisions_.push_back (c);
185 void Beam_scoring_problem::init_instance_variables (Grob *me, Drul_array<Real> ys, bool align_broken_intos)
187 beam_ = dynamic_cast<Spanner *> (me);
191 If 'ys' are finite, use them as starting points for y-positions of the
192 ends of the beam, instead of the best-fit through the natural ends of
193 the stems. Otherwise, we want to do initial slope calculations.
195 do_initial_slope_calculations_ = false;
196 for (LEFT_and_RIGHT (d))
197 do_initial_slope_calculations_ |= isinf (unquanted_y_[d]) || isnan (unquanted_y_[d]);
200 Calculations are relative to a unit-scaled staff, i.e. the quants are
201 divided by the current staff_space_.
203 staff_space_ = Staff_symbol_referencer::staff_space (beam_);
204 beam_thickness_ = Beam::get_beam_thickness (beam_) / staff_space_;
205 line_thickness_ = Staff_symbol_referencer::line_thickness (beam_) / staff_space_;
207 // This is the least-squares DY, corrected for concave beams.
208 musical_dy_ = robust_scm2double (beam_->get_property ("least-squares-dy"), 0);
210 vector<Spanner *> beams;
211 align_broken_intos_ = align_broken_intos;
212 if (align_broken_intos_)
214 Spanner *orig = dynamic_cast<Spanner *> (beam_->original ());
216 align_broken_intos_ = false;
217 else if (!orig->broken_intos_.size ())
218 align_broken_intos_ = false;
220 beams.insert (beams.end (), orig->broken_intos_.begin (), orig->broken_intos_.end ());
222 if (!align_broken_intos_)
223 beams.push_back (beam_);
226 x_span_ is a single scalar, cumulatively summing the length of all the
227 segments the parent beam was broken-into.
231 normal_stem_count_ = 0;
232 for (vsize i = 0; i < beams.size (); i++)
234 extract_grob_set (beams[i], "stems", stems);
235 extract_grob_set (beams[i], "covered-grobs", fake_collisions);
236 vector<Grob *> collisions;
238 for (vsize j = 0; j < fake_collisions.size (); j++)
239 if (fake_collisions[j]->get_system () == beams[i]->get_system ())
240 collisions.push_back (fake_collisions[j]);
243 for (int a = 2; a--;)
244 common[a] = common_refpoint_of_array (stems, beams[i], Axis (a));
246 for (LEFT_and_RIGHT (d))
247 common[X_AXIS] = beams[i]->get_bound (d)->common_refpoint (common[X_AXIS], X_AXIS);
249 // positions of the endpoints of this beam segment, including any overhangs
250 const Interval x_pos = robust_scm2interval (beams[i]->get_property ("X-positions"),
251 Interval (0.0, 0.0));
253 Drul_array<Grob *> edge_stems (Beam::first_normal_stem (beams[i]),
254 Beam::last_normal_stem (beams[i]));
256 Drul_array<bool> dirs_found (0, 0);
258 Real my_y = beams[i]->relative_coordinate (common[Y_AXIS], Y_AXIS);
260 Interval beam_width (-1.0, -1.0);
261 for (vsize j = 0; j < stems.size (); j++)
264 beam_multiplicity_.push_back (Stem::beam_multiplicity (stems[j]));
265 head_positions_.push_back (Stem::head_positions (stems[j]));
266 is_normal_.push_back (Stem::is_normal_stem (stems[j]));
268 Stem_info si (Stem::get_stem_info (s));
269 si.scale (1 / staff_space_);
270 stem_infos_.push_back (si);
271 chord_start_y_.push_back (Stem::chord_start_y (s));
272 dirs_found[si.dir_] = true;
274 bool f = to_boolean (s->get_property ("french-beaming"))
275 && s != edge_stems[LEFT] && s != edge_stems[RIGHT];
277 Real y = Beam::calc_stem_y (beams[i], s, common, x_pos[LEFT], x_pos[RIGHT], CENTER,
279 base_lengths_.push_back (y / staff_space_);
280 stem_xpositions_.push_back (s->relative_coordinate (common[X_AXIS], X_AXIS) - x_pos[LEFT] + x_span_);
281 stem_ypositions_.push_back (s->relative_coordinate (common[Y_AXIS], Y_AXIS) - my_y);
283 if (is_normal_.back ())
285 if (beam_width[LEFT] == -1.0)
286 beam_width[LEFT] = stem_xpositions_.back ();
287 beam_width[RIGHT] = stem_xpositions_.back ();
291 edge_dirs_ = Drul_array<Direction> (CENTER, CENTER);
292 normal_stem_count_ += Beam::normal_stem_count (beams[i]);
293 if (normal_stem_count_)
294 edge_dirs_ = Drul_array<Direction> (stem_infos_[0].dir_,
295 stem_infos_.back ().dir_);
297 is_xstaff_ = Align_interface::has_interface (common[Y_AXIS]);
298 is_knee_ |= dirs_found[DOWN] && dirs_found[UP];
300 staff_radius_ = Staff_symbol_referencer::staff_radius (beams[i]);
301 edge_beam_counts_ = Drul_array<int>
302 (Stem::beam_multiplicity (stems[0]).length () + 1,
303 Stem::beam_multiplicity (stems.back ()).length () + 1);
305 // TODO - why are we dividing by staff_space_?
306 beam_translation_ = Beam::get_beam_translation (beams[i]) / staff_space_;
308 for (LEFT_and_RIGHT (d))
310 quant_range_[d].set_full ();
314 Real stem_offset = edge_stems[d]->relative_coordinate (common[Y_AXIS], Y_AXIS)
315 - beams[i]->relative_coordinate (common[Y_AXIS], Y_AXIS);
316 Interval heads = Stem::head_positions (edge_stems[d]) * 0.5 * staff_space_;
318 Direction ed = edge_dirs_[d];
319 heads.widen (0.5 * staff_space_
320 + (edge_beam_counts_[d] - 1) * beam_translation_ + beam_thickness_ * .5);
321 quant_range_[d][-ed] = heads[ed] + stem_offset;
324 segments_ = Beam::get_beam_segments (beams[i]);
325 vector_sort (segments_, beam_segment_less);
326 for (vsize j = 0; j < segments_.size (); j++)
327 segments_[j].horizontal_ += (x_span_ - x_pos[LEFT]);
329 set<Grob *> colliding_stems;
330 for (vsize j = 0; j < collisions.size (); j++)
332 if (!collisions[j]->is_live ())
335 if (Beam::has_interface (collisions[j]) && Beam::is_cross_staff (collisions[j]))
339 for (Axis a = X_AXIS; a < NO_AXES; incr (a))
340 b[a] = collisions[j]->extent (common[a], a);
342 if (b[X_AXIS][RIGHT] < x_pos[LEFT] || b[X_AXIS][LEFT] > x_pos[RIGHT])
344 if (b[X_AXIS].is_empty () || b[Y_AXIS].is_empty ())
347 b[X_AXIS] += (x_span_ - x_pos[LEFT]);
349 Real width = b[X_AXIS].length ();
350 Real width_factor = sqrt (width / staff_space_);
352 for (LEFT_and_RIGHT (d))
353 add_collision (b[X_AXIS][d], b[Y_AXIS], width_factor);
355 Grob *stem = Grob::unsmob (collisions[j]->get_object ("stem"));
356 if (stem && Stem::has_interface (stem) && Stem::is_normal_stem (stem))
358 colliding_stems.insert (stem);
362 for (set<Grob *>::const_iterator it (colliding_stems.begin ()); it != colliding_stems.end (); it++)
365 Real x = (s->extent (common[X_AXIS], X_AXIS) - x_pos[LEFT] + x_span_).center ();
367 Direction stem_dir = get_grob_direction (*it);
370 y[-stem_dir] = Stem::chord_start_y (*it) + (*it)->relative_coordinate (common[Y_AXIS], Y_AXIS)
373 Real factor = parameters_.STEM_COLLISION_FACTOR;
374 if (!Grob::is_smob (s->get_object ("beam")))
376 add_collision (x, y, factor);
378 x_span_ += beams[i]->spanner_length ();
382 Beam_scoring_problem::Beam_scoring_problem (Grob *me, Drul_array<Real> ys, bool align_broken_intos)
384 beam_ = dynamic_cast<Spanner *> (me);
386 align_broken_intos_ = align_broken_intos;
388 parameters_.fill (me);
389 init_instance_variables (me, ys, align_broken_intos);
390 if (do_initial_slope_calculations_)
392 least_squares_positions ();
394 shift_region_to_valid ();
398 // Assuming V is not empty, pick a 'reasonable' point inside V.
400 point_in_interval (Interval v, Real dist)
404 else if (isinf (v[UP]))
405 return v[DOWN] + dist;
410 /* Set stem's shorten property if unset.
413 take some y-position (chord/beam/nearest?) into account
414 scmify forced-fraction
416 This is done in beam because the shorten has to be uniform over the
421 set_minimum_dy (Grob *me, Real *dy)
426 If dy is smaller than the smallest quant, we
427 get absurd direction-sign penalties.
430 Real ss = Staff_symbol_referencer::staff_space (me);
431 Real beam_thickness = Beam::get_beam_thickness (me) / ss;
432 Real slt = Staff_symbol_referencer::line_thickness (me) / ss;
433 Real sit = (beam_thickness - slt) / 2;
435 Real hang = 1.0 - (beam_thickness - slt) / 2;
437 *dy = sign (*dy) * max (fabs (*dy),
438 min (min (sit, inter), hang));
443 Beam_scoring_problem::no_visible_stem_positions ()
445 if (!head_positions_.size ())
447 unquanted_y_ = Interval (0, 0);
451 Interval head_positions;
453 for (vsize i = 0; i < head_positions_.size (); i++)
455 head_positions.unite (head_positions_[i]);
456 multiplicity.unite (beam_multiplicity_[i]);
459 Direction dir = get_grob_direction (beam_);
462 programming_error ("The beam should have a direction by now.");
464 Real y = head_positions.linear_combination (dir)
466 + dir * beam_translation_ * (multiplicity.length () + 1);
468 unquanted_y_ = Interval (y, y);
472 Beam_scoring_problem::first_normal_index ()
474 for (vsize i = 0; i < is_normal_.size (); i++)
478 beam_->programming_error ("No normal stems, but asking for first normal stem index.");
483 Beam_scoring_problem::last_normal_index ()
485 for (vsize i = is_normal_.size (); i--;)
489 beam_->programming_error ("No normal stems, but asking for first normal stem index.");
494 Beam_scoring_problem::least_squares_positions ()
496 if (!normal_stem_count_)
498 no_visible_stem_positions ();
502 if (stem_infos_.size () < 1)
505 vsize fnx = first_normal_index ();
506 vsize lnx = last_normal_index ();
508 Interval ideal (stem_infos_[fnx].ideal_y_ + stem_ypositions_[fnx],
509 stem_infos_[lnx].ideal_y_ + stem_ypositions_[lnx]);
517 Interval chord (chord_start_y_[0],
518 chord_start_y_.back ());
520 /* Simple beams (2 stems) on middle line should be allowed to be
523 However, if both stems reach middle line,
524 ideal[LEFT] == ideal[RIGHT] and ideal.delta () == 0.
526 For that case, we apply artificial slope */
527 if (!ideal[LEFT] && chord.delta () && stem_infos_.size () == 2)
530 Direction d = (Direction) (sign (chord.delta ()) * UP);
531 unquanted_y_[d] = Beam::get_beam_thickness (beam_) / 2;
532 unquanted_y_[-d] = -unquanted_y_[d];
535 unquanted_y_ = ideal;
537 ldy = unquanted_y_[RIGHT] - unquanted_y_[LEFT];
541 vector<Offset> ideals;
542 for (vsize i = 0; i < stem_infos_.size (); i++)
544 ideals.push_back (Offset (stem_xpositions_[i],
545 stem_infos_[i].ideal_y_
546 + stem_ypositions_[i]));
548 minimise_least_squares (&slope, &y, ideals);
550 dy = slope * x_span_;
552 set_minimum_dy (beam_, &dy);
555 unquanted_y_ = Interval (y, (y + dy));
559 beam_->set_property ("least-squares-dy", scm_from_double (musical_dy_));
563 Determine whether a beam is concave.
565 A beam is concave when the middle notes get closer to the
566 beam than the left and right edge notes.
568 This is determined in two ways: by looking at the positions of the
569 middle notes, or by looking at the deviation of the inside notes
570 compared to the line connecting first and last.
572 The tricky thing is what to do with beams with chords. There are no
573 real guidelines in this case.
577 is_concave_single_notes (vector<int> const &positions, Direction beam_dir)
580 covering.add_point (positions[0]);
581 covering.add_point (positions.back ());
585 bool concave = false;
588 notes above and below the interval covered by 1st and last note.
590 for (vsize i = 1; i + 1 < positions.size (); i++)
592 above = above || (positions[i] > covering[UP]);
593 below = below || (positions[i] < covering[DOWN]);
596 concave = concave || (above && below);
598 A note as close or closer to the beam than begin and end, but the
599 note is reached in the opposite direction as the last-first dy
601 int dy = positions.back () - positions[0];
602 int closest = max (beam_dir * positions.back (), beam_dir * positions[0]);
603 for (vsize i = 2; !concave && i + 1 < positions.size (); i++)
605 int inner_dy = positions[i] - positions[i - 1];
606 if (sign (inner_dy) != sign (dy)
607 && (beam_dir * positions[i] >= closest
608 || beam_dir * positions[i - 1] >= closest))
612 bool all_closer = true;
613 for (vsize i = 1; all_closer && i + 1 < positions.size (); i++)
615 all_closer = all_closer
616 && (beam_dir * positions[i] > closest);
619 concave = concave || all_closer;
624 calc_positions_concaveness (vector<int> const &positions, Direction beam_dir)
626 Real dy = positions.back () - positions[0];
627 Real slope = dy / Real (positions.size () - 1);
628 Real concaveness = 0.0;
629 for (vsize i = 1; i + 1 < positions.size (); i++)
631 Real line_y = slope * i + positions[0];
633 concaveness += max (beam_dir * (positions[i] - line_y), 0.0);
636 concaveness /= positions.size ();
639 Normalize. For dy = 0, the slope ends up as 0 anyway, so the
640 scaling of concaveness doesn't matter much.
643 concaveness /= fabs (dy);
648 Beam_scoring_problem::calc_concaveness ()
650 SCM conc = beam_->get_property ("concaveness");
651 if (scm_is_number (conc))
652 return scm_to_double (conc);
654 if (is_knee_ || is_xstaff_)
657 Direction beam_dir = CENTER;
658 for (vsize i = is_normal_.size (); i--;)
659 if (is_normal_[i] && stem_infos_[i].dir_)
660 beam_dir = stem_infos_[i].dir_;
662 if (normal_stem_count_ <= 2)
665 vector<int> close_positions;
666 vector<int> far_positions;
667 for (vsize i = 0; i < is_normal_.size (); i++)
671 For chords, we take the note head that is closest to the beam.
673 Hmmm.. wait, for the beams in the last measure of morgenlied,
674 this doesn't look so good. Let's try the heads farthest from
678 close_positions.push_back ((int) rint (head_positions_[i][beam_dir]));
679 far_positions.push_back ((int) rint (head_positions_[i][-beam_dir]));
682 Real concaveness = 0.0;
684 if (is_concave_single_notes (beam_dir == UP ? close_positions : far_positions, beam_dir))
690 concaveness = (calc_positions_concaveness (far_positions, beam_dir)
691 + calc_positions_concaveness (close_positions, beam_dir)) / 2;
698 Beam_scoring_problem::slope_damping ()
700 if (normal_stem_count_ <= 1)
703 SCM s = beam_->get_property ("damping");
704 Real damping = scm_to_double (s);
705 Real concaveness = calc_concaveness ();
706 if (concaveness >= 10000)
708 unquanted_y_[LEFT] = unquanted_y_[RIGHT];
715 Real dy = unquanted_y_[RIGHT] - unquanted_y_[LEFT];
717 Real slope = dy && x_span_ ? dy / x_span_ : 0;
719 slope = 0.6 * tanh (slope) / (damping + concaveness);
721 Real damped_dy = slope * x_span_;
723 set_minimum_dy (beam_, &damped_dy);
725 unquanted_y_[LEFT] += (dy - damped_dy) / 2;
726 unquanted_y_[RIGHT] -= (dy - damped_dy) / 2;
731 Beam_scoring_problem::shift_region_to_valid ()
733 if (!normal_stem_count_)
736 Real beam_dy = unquanted_y_[RIGHT] - unquanted_y_[LEFT];
737 Real slope = x_span_ ? beam_dy / x_span_ : 0.0;
740 Shift the positions so that we have a chance of finding good
741 quants (i.e. no short stem failures.)
743 Interval feasible_left_point;
744 feasible_left_point.set_full ();
746 for (vsize i = 0; i < stem_infos_.size (); i++)
748 // TODO - check for invisible here...
750 = stem_infos_[i].shortest_y_
751 - slope * stem_xpositions_ [i];
754 left_y is now relative to the stem S. We want relative to
755 ourselves, so translate:
757 left_y += stem_ypositions_[i];
760 flp[-stem_infos_[i].dir_] = left_y;
762 feasible_left_point.intersect (flp);
765 vector<Grob *> filtered;
767 We only update these for objects that are too large for quanting
768 to find a workaround. Typically, these are notes with
769 stems, and timesig/keysig/clef, which take out the entire area
770 inside the staff as feasible.
772 The code below disregards the thickness and multiplicity of the
773 beam. This should not be a problem, as the beam quanting will
774 take care of computing the impact those exactly.
776 Real min_y_size = 2.0;
778 // A list of intervals into which beams may not fall
779 vector<Interval> forbidden_intervals;
781 for (vsize i = 0; i < collisions_.size (); i++)
783 if (collisions_[i].x_ < 0 || collisions_[i].x_ > x_span_)
786 if (collisions_[i].y_.length () < min_y_size)
789 for (LEFT_and_RIGHT (d))
791 Real dy = slope * collisions_[i].x_;
794 for (DOWN_and_UP (yd))
796 Real left_y = collisions_[i].y_[yd] - dy;
797 disallowed[yd] = left_y;
800 forbidden_intervals.push_back (disallowed);
804 vector_sort (forbidden_intervals, Interval::left_less);
805 Real beam_left_y = unquanted_y_[LEFT];
806 Interval feasible_beam_placements (beam_left_y, beam_left_y);
808 Interval_minefield minefield (feasible_beam_placements, 0.0);
809 for (vsize i = 0; i < forbidden_intervals.size (); i++)
810 minefield.add_forbidden_interval (forbidden_intervals[i]);
812 feasible_beam_placements = minefield.feasible_placements ();
814 // if the beam placement falls out of the feasible region, we push it
815 // to infinity so that it can never be a feasible candidate below
816 for (DOWN_and_UP (d))
818 if (!feasible_left_point.contains (feasible_beam_placements[d]))
819 feasible_beam_placements[d] = d * infinity_f;
822 if ((feasible_beam_placements[UP] == infinity_f && feasible_beam_placements[DOWN] == -infinity_f) && !feasible_left_point.is_empty ())
824 // We are somewhat screwed: we have a collision, but at least
825 // there is a way to satisfy stem length constraints.
826 beam_left_y = point_in_interval (feasible_left_point, 2.0);
828 else if (!feasible_left_point.is_empty ())
830 // Only one of them offers is feasible solution. Pick that one.
831 if (abs (beam_left_y - feasible_beam_placements[DOWN]) > abs (beam_left_y - feasible_beam_placements[UP]))
832 beam_left_y = feasible_beam_placements[UP];
834 beam_left_y = feasible_beam_placements[DOWN];
838 // We are completely screwed.
839 beam_->warning (_ ("no viable initial configuration found: may not find good beam slope"));
842 unquanted_y_ = Drul_array<Real> (beam_left_y, (beam_left_y + beam_dy));
846 Beam_scoring_problem::generate_quants (vector<Beam_configuration *> *scores) const
848 int region_size = (int) parameters_.REGION_SIZE;
850 // Knees and collisions are harder, lets try some more possibilities
853 if (collisions_.size ())
857 Real sit = (beam_thickness_ - line_thickness_) / 2;
859 Real hang = 1.0 - (beam_thickness_ - line_thickness_) / 2;
860 Real base_quants [] = {straddle, sit, inter, hang};
861 int num_base_quants = int (sizeof (base_quants) / sizeof (Real));
864 Asymetry ? should run to <= region_size ?
866 vector<Real> unshifted_quants;
867 for (int i = -region_size; i < region_size; i++)
868 for (int j = 0; j < num_base_quants; j++)
870 unshifted_quants.push_back (i + base_quants[j]);
873 for (vsize i = 0; i < unshifted_quants.size (); i++)
874 for (vsize j = 0; j < unshifted_quants.size (); j++)
876 Beam_configuration *c
877 = Beam_configuration::new_config (unquanted_y_,
878 Interval (unshifted_quants[i],
879 unshifted_quants[j]));
881 for (LEFT_and_RIGHT (d))
883 if (!quant_range_[d].contains (c->y[d]))
891 scores->push_back (c);
896 void Beam_scoring_problem::one_scorer (Beam_configuration *config) const
899 switch (config->next_scorer_todo)
902 score_slope_ideal (config);
904 case SLOPE_DIRECTION:
905 score_slope_direction (config);
908 score_slope_musical (config);
911 score_forbidden_quants (config);
914 score_stem_lengths (config);
917 score_collisions (config);
919 case HORIZONTAL_INTER:
920 score_horizontal_inter_quants (config);
924 case ORIGINAL_DISTANCE:
928 config->next_scorer_todo++;
932 Beam_scoring_problem::force_score (SCM inspect_quants, const vector<Beam_configuration *> &configs) const
934 Drul_array<Real> ins = ly_scm2interval (inspect_quants);
936 Beam_configuration *best = NULL;
937 for (vsize i = 0; i < configs.size (); i++)
939 Real d = fabs (configs[i]->y[LEFT] - ins[LEFT]) + fabs (configs[i]->y[RIGHT] - ins[RIGHT]);
947 programming_error ("cannot find quant");
949 while (!best->done ())
956 Beam_scoring_problem::solve () const
958 vector<Beam_configuration *> configs;
959 generate_quants (&configs);
961 if (configs.empty ())
963 programming_error ("No viable beam quanting found. Using unquanted y value.");
967 if (to_boolean (beam_->get_property ("skip-quanting")))
970 Beam_configuration *best = NULL;
973 = to_boolean (beam_->layout ()->lookup_variable (ly_symbol2scm ("debug-beam-scoring")));
974 SCM inspect_quants = beam_->get_property ("inspect-quants");
975 if (scm_is_pair (inspect_quants))
978 best = force_score (inspect_quants, configs);
982 std::priority_queue < Beam_configuration *, std::vector<Beam_configuration *>,
983 Beam_configuration_less > queue;
984 for (vsize i = 0; i < configs.size (); i++)
985 queue.push (configs[i]);
990 It would be neat if we generated new configurations on the
991 fly, depending on the best complete score so far, eg.
994 if (best->demerits < sqrt(queue.size())
996 while (best->demerits > sqrt(queue.size()) {
997 generate and insert new configuration
1001 that would allow us to do away with region_size altogether.
1005 best = queue.top ();
1015 Interval final_positions = best->y;
1017 #if DEBUG_BEAM_SCORING
1022 for (vsize i = 0; i < configs.size (); i++)
1024 if (configs[i]->done ())
1028 string card = best->score_card_ + to_string (" c%d/%d", completed, configs.size ());
1029 beam_->set_property ("annotation", ly_string2scm (card));
1033 junk_pointers (configs);
1034 if (align_broken_intos_)
1036 Interval normalized_endpoints = robust_scm2interval (beam_->get_property ("normalized-endpoints"), Interval (0, 1));
1037 Real y_length = final_positions[RIGHT] - final_positions[LEFT];
1039 final_positions[LEFT] += normalized_endpoints[LEFT] * y_length;
1040 final_positions[RIGHT] -= (1 - normalized_endpoints[RIGHT]) * y_length;
1043 return final_positions;
1047 Beam_scoring_problem::score_stem_lengths (Beam_configuration *config) const
1049 Real limit_penalty = parameters_.STEM_LENGTH_LIMIT_PENALTY;
1050 Drul_array<Real> score (0, 0);
1051 Drul_array<int> count (0, 0);
1053 for (vsize i = 0; i < stem_xpositions_.size (); i++)
1058 Real x = stem_xpositions_[i];
1061 ? config->y[RIGHT] * x / dx + config->y[LEFT] * (x_span_ - x) / dx
1062 : (config->y[RIGHT] + config->y[LEFT]) / 2;
1063 Real current_y = beam_y + base_lengths_[i];
1064 Real length_pen = parameters_.STEM_LENGTH_DEMERIT_FACTOR;
1066 Stem_info info = stem_infos_[i];
1067 Direction d = info.dir_;
1069 score[d] += limit_penalty * max (0.0, (d * (info.shortest_y_ - current_y)));
1071 Real ideal_diff = d * (current_y - info.ideal_y_);
1072 Real ideal_score = shrink_extra_weight (ideal_diff, 1.5);
1074 /* We introduce a power, to make the scoring strictly
1075 convex. Otherwise a symmetric knee beam (up/down/up/down)
1076 does not have an optimum in the middle. */
1078 ideal_score = pow (ideal_score, 1.1);
1080 score[d] += length_pen * ideal_score;
1084 /* Divide by number of stems, to make the measure scale-free. */
1085 for (DOWN_and_UP (d))
1086 score[d] /= max (count[d], 1);
1089 sometimes, two perfectly symmetric kneed beams will have the same score
1090 and can either be quanted up or down.
1092 we choose the quanting in the direction of the slope so that the first stem
1093 always seems longer, reaching to the second, rather than squashed.
1095 if (is_knee_ && count[LEFT] == count[RIGHT] && count[LEFT] == 1 && unquanted_y_.delta ())
1096 score[Direction (sign (unquanted_y_.delta ()))] += score[Direction (sign (unquanted_y_.delta ()))] < 1.0 ? 0.01 : 0.0;
1098 config->add (score[LEFT] + score[RIGHT], "L");
1102 Beam_scoring_problem::score_slope_direction (Beam_configuration *config) const
1104 Real dy = config->y.delta ();
1105 Real damped_dy = unquanted_y_.delta ();
1108 DAMPING_DIRECTION_PENALTY is a very harsh measure, while for
1109 complex beaming patterns, horizontal is often a good choice.
1111 TODO: find a way to incorporate the complexity of the beam in this
1114 if (sign (damped_dy) != sign (dy))
1118 if (fabs (damped_dy / x_span_) > parameters_.ROUND_TO_ZERO_SLOPE)
1119 dem += parameters_.DAMPING_DIRECTION_PENALTY;
1121 dem += parameters_.HINT_DIRECTION_PENALTY;
1124 dem += parameters_.DAMPING_DIRECTION_PENALTY;
1127 config->add (dem, "Sd");
1130 // Score for going against the direction of the musical pattern
1132 Beam_scoring_problem::score_slope_musical (Beam_configuration *config) const
1134 Real dy = config->y.delta ();
1135 Real dem = parameters_.MUSICAL_DIRECTION_FACTOR
1136 * max (0.0, (fabs (dy) - fabs (musical_dy_)));
1137 config->add (dem, "Sm");
1140 // Score deviation from calculated ideal slope.
1142 Beam_scoring_problem::score_slope_ideal (Beam_configuration *config) const
1144 Real dy = config->y.delta ();
1145 Real damped_dy = unquanted_y_.delta ();
1148 Real slope_penalty = parameters_.IDEAL_SLOPE_FACTOR;
1150 /* Xstaff beams tend to use extreme slopes to get short stems. We
1151 put in a penalty here. */
1153 slope_penalty *= 10;
1155 /* Huh, why would a too steep beam be better than a too flat one ? */
1156 dem += shrink_extra_weight (fabs (damped_dy) - fabs (dy), 1.5)
1159 config->add (dem, "Si");
1165 return x - floor (x);
1168 // TODO - there is some overlap with forbidden quants, but for
1169 // horizontal beams, it is much more serious to have stafflines
1170 // appearing in the wrong place, so we have a separate scorer.
1172 Beam_scoring_problem::score_horizontal_inter_quants (Beam_configuration *config) const
1174 if (config->y.delta () == 0.0
1175 && abs (config->y[LEFT]) < staff_radius_ * staff_space_)
1177 Real yshift = config->y[LEFT] - 0.5 * staff_space_;
1178 if (fabs (my_round (yshift) - yshift) < 0.01 * staff_space_)
1179 config->add (parameters_.HORIZONTAL_INTER_QUANT_PENALTY, "H");
1184 TODO: The fixed value SECONDARY_BEAM_DEMERIT is probably flawed:
1185 because for 32nd and 64th beams the forbidden quants are relatively
1186 more important than stem lengths.
1189 Beam_scoring_problem::score_forbidden_quants (Beam_configuration *config) const
1191 Real dy = config->y.delta ();
1193 Real extra_demerit = parameters_.SECONDARY_BEAM_DEMERIT
1194 / max (edge_beam_counts_[LEFT], edge_beam_counts_[RIGHT]);
1197 Real eps = parameters_.BEAM_EPS;
1199 for (LEFT_and_RIGHT (d))
1201 for (int j = 1; j <= edge_beam_counts_[d]; j++)
1203 Direction stem_dir = edge_dirs_[d];
1206 The 2.2 factor is to provide a little leniency for
1207 borderline cases. If we do 2.0, then the upper outer line
1208 will be in the gap of the (2, sit) quant, leading to a
1211 Real gap1 = config->y[d] - stem_dir * ((j - 1) * beam_translation_ + beam_thickness_ / 2 - line_thickness_ / 2.2);
1212 Real gap2 = config->y[d] - stem_dir * (j * beam_translation_ - beam_thickness_ / 2 + line_thickness_ / 2.2);
1215 gap.add_point (gap1);
1216 gap.add_point (gap2);
1218 for (Real k = -staff_radius_;
1219 k <= staff_radius_ + eps; k += 1.0)
1220 if (gap.contains (k))
1222 Real dist = min (fabs (gap[UP] - k), fabs (gap[DOWN] - k));
1225 this parameter is tuned to grace-stem-length.ly
1226 retuned from 0.40 to 0.39 by MS because of slight increases
1227 in gap.length () resulting from measuring beams at real ends
1228 instead of from the middle of stems.
1231 This function needs better comments so we know what is forbidden
1234 Real fixed_demerit = 0.39;
1236 dem += extra_demerit
1238 + (1 - fixed_demerit) * (dist / gap.length ()) * 2);
1243 if (max (edge_beam_counts_[LEFT], edge_beam_counts_[RIGHT]) >= 2)
1245 Real straddle = 0.0;
1246 Real sit = (beam_thickness_ - line_thickness_) / 2;
1248 Real hang = 1.0 - (beam_thickness_ - line_thickness_) / 2;
1250 for (LEFT_and_RIGHT (d))
1252 if (edge_beam_counts_[d] >= 2
1253 && fabs (config->y[d] - edge_dirs_[d] * beam_translation_) < staff_radius_ + inter)
1255 // TODO up/down symmetry.
1256 if (edge_dirs_[d] == UP && dy <= eps
1257 && fabs (my_modf (config->y[d]) - sit) < eps)
1258 dem += extra_demerit;
1260 if (edge_dirs_[d] == DOWN && dy >= eps
1261 && fabs (my_modf (config->y[d]) - hang) < eps)
1262 dem += extra_demerit;
1265 if (edge_beam_counts_[d] >= 3
1266 && fabs (config->y[d] - 2 * edge_dirs_[d] * beam_translation_) < staff_radius_ + inter)
1268 // TODO up/down symmetry.
1269 if (edge_dirs_[d] == UP && dy <= eps
1270 && fabs (my_modf (config->y[d]) - straddle) < eps)
1271 dem += extra_demerit;
1273 if (edge_dirs_[d] == DOWN && dy >= eps
1274 && fabs (my_modf (config->y[d]) - straddle) < eps)
1275 dem += extra_demerit;
1280 config->add (dem, "F");
1284 Beam_scoring_problem::score_collisions (Beam_configuration *config) const
1286 Real demerits = 0.0;
1287 for (vsize i = 0; i < collisions_.size (); i++)
1289 Interval collision_y = collisions_[i].y_;
1290 Real x = collisions_[i].x_;
1292 Real center_beam_y = y_at (x, config);
1293 Interval beam_y = center_beam_y + collisions_[i].beam_y_;
1295 Real dist = infinity_f;
1296 if (!intersection (beam_y, collision_y).is_empty ())
1299 dist = min (beam_y.distance (collision_y[DOWN]),
1300 beam_y.distance (collision_y[UP]));
1303 = max (parameters_.COLLISION_PADDING - dist, 0.0)
1304 / parameters_.COLLISION_PADDING;
1306 += collisions_[i].base_penalty_ *
1307 pow (scale_free, 3) * parameters_.COLLISION_PENALTY;
1310 config->add (demerits, "C");