2 This file is part of LilyPond, the GNU music typesetter.
4 Copyright (C) 1997--2011 Han-Wen Nienhuys <hanwen@xs4all.nl>
5 Jan Nieuwenhuizen <janneke@gnu.org>
7 LilyPond is free software: you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation, either version 3 of the License, or
10 (at your option) any later version.
12 LilyPond is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with LilyPond. If not, see <http://www.gnu.org/licenses/>.
21 #include "beam-scoring-problem.hh"
28 #include "align-interface.hh"
30 #include "direction.hh"
31 #include "directional-element-interface.hh"
33 #include "grob-array.hh"
35 #include "international.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"
49 get_detail (SCM alist, SCM sym, Real def)
51 SCM entry = scm_assq (sym, alist);
53 if (scm_is_pair (entry))
54 return robust_scm2double (scm_cdr (entry), def);
59 Beam_quant_parameters::fill (Grob *him)
61 SCM details = him->get_property ("details");
64 BEAM_EPS = get_detail (details, ly_symbol2scm ("beam-eps"), 1e-3);
65 REGION_SIZE = get_detail (details, ly_symbol2scm ("region-size"), 2);
68 SECONDARY_BEAM_DEMERIT = get_detail (details, ly_symbol2scm ("secondary-beam-demerit"), 10.0);
69 STEM_LENGTH_DEMERIT_FACTOR = get_detail (details, ly_symbol2scm ("stem-length-demerit-factor"), 5);
70 HORIZONTAL_INTER_QUANT_PENALTY = get_detail (details, ly_symbol2scm ("horizontal-inter-quant"), 500);
72 STEM_LENGTH_LIMIT_PENALTY = get_detail (details, ly_symbol2scm ("stem-length-limit-penalty"), 5000);
73 DAMPING_DIRECTION_PENALTY = get_detail (details, ly_symbol2scm ("damping-direction-penalty"), 800);
74 HINT_DIRECTION_PENALTY = get_detail (details, ly_symbol2scm ("hint-direction-penalty"), 20);
75 MUSICAL_DIRECTION_FACTOR = get_detail (details, ly_symbol2scm ("musical-direction-factor"), 400);
76 IDEAL_SLOPE_FACTOR = get_detail (details, ly_symbol2scm ("ideal-slope-factor"), 10);
77 ROUND_TO_ZERO_SLOPE = get_detail (details, ly_symbol2scm ("round-to-zero-slope"), 0.02);
80 COLLISION_PENALTY = get_detail (details, ly_symbol2scm ("collision-penalty"), 500);
81 COLLISION_PADDING = get_detail (details, ly_symbol2scm ("collision-padding"), 0.5);
82 STEM_COLLISION_FACTOR = get_detail (details, ly_symbol2scm ("stem-collision-factor"), 0.1);
85 // Add x if x is positive, add |x|*fac if x is negative.
87 shrink_extra_weight (Real x, Real fac)
89 return fabs (x) * ((x < 0) ? fac : 1.0);
92 /****************************************************************/
94 Beam_configuration::Beam_configuration ()
96 y = Interval (0.0, 0.0);
98 next_scorer_todo = ORIGINAL_DISTANCE;
101 bool Beam_configuration::done () const
103 return next_scorer_todo >= NUM_SCORERS;
106 void Beam_configuration::add (Real demerit, const string &reason)
110 #if DEBUG_BEAM_SCORING
112 score_card_ += to_string (" %s %.2f", reason.c_str (), demerit);
116 Beam_configuration *Beam_configuration::new_config (Interval start,
119 Beam_configuration *qs = new Beam_configuration;
120 qs->y = Interval (int (start[LEFT]) + offset[LEFT],
121 int (start[RIGHT]) + offset[RIGHT]);
123 // This orders the sequence so we try combinations closest to the
124 // the ideal offset first.
125 Real start_score = abs (offset[RIGHT]) + abs (offset[LEFT]);
126 qs->demerits = start_score / 1000.0;
127 qs->next_scorer_todo = ORIGINAL_DISTANCE + 1;
133 Beam_scoring_problem::y_at (Real x, Beam_configuration const *p) const
135 return p->y[LEFT] + x * p->y.delta () / x_span_;
138 /****************************************************************/
143 - Make all demerits customisable
145 - Add demerits for quants per se, as to forbid a specific quant
149 // This is a temporary hack to see how much we can gain by using a
150 // priority queue on the beams to score.
151 static int score_count = 0;
152 LY_DEFINE (ly_beam_score_count, "ly:beam-score-count", 0, 0, 0,
154 "count number of beam scores.")
156 return scm_from_int (score_count);
159 void Beam_scoring_problem::add_collision (Real x, Interval y,
162 // We used to screen for quant range, but no more.
165 c.beam_y_.set_empty ();
167 for (vsize j = 0; j < segments_.size (); j++)
169 if (segments_[j].horizontal_.contains (x))
170 c.beam_y_.add_point (segments_[j].vertical_count_ * beam_translation_);
171 if (segments_[j].horizontal_[LEFT] > x)
174 c.beam_y_.widen (0.5 * beam_thickness_);
178 y *= 1 / staff_space_;
180 c.base_penalty_ = score_factor;
181 collisions_.push_back (c);
184 void Beam_scoring_problem::init_stems ()
186 vector<Spanner *> beams;
187 if (consistent_broken_slope_)
189 Spanner *orig = dynamic_cast<Spanner *> (beam_->original ());
191 consistent_broken_slope_ = false;
192 else if (!orig->broken_intos_.size ())
193 consistent_broken_slope_ = false;
195 beams.insert (beams.end (), orig->broken_intos_.begin (), orig->broken_intos_.end ());
197 if (!consistent_broken_slope_)
198 beams.push_back (beam_);
201 normal_stem_count_ = 0;
202 for (vsize i = 0; i < beams.size (); i++)
204 Interval local_x_span;
205 extract_grob_set (beams[i], "stems", stems);
206 extract_grob_set (beams[i], "covered-grobs", fake_collisions);
207 vector<Grob *> collisions;
209 for (vsize j = 0; j < fake_collisions.size (); j++)
210 if (fake_collisions[j]->get_system () == beams[i]->get_system ())
211 collisions.push_back (fake_collisions[j]);
214 for (int a = 2; a--;)
215 common[a] = common_refpoint_of_array (stems, beams[i], Axis (a));
217 Real x_left = beams[i]->relative_coordinate(common[X_AXIS], X_AXIS);
219 Drul_array<Grob *> edge_stems (Beam::first_normal_stem (beams[i]),
220 Beam::last_normal_stem (beams[i]));
223 local_x_span[d] = edge_stems[d] ? edge_stems[d]->relative_coordinate (common[X_AXIS], X_AXIS) : 0.0;
224 while (flip (&d) != LEFT);
226 Drul_array<bool> dirs_found (0, 0);
228 Real my_y = beams[i]->relative_coordinate (common[Y_AXIS], Y_AXIS);
230 Interval beam_width (-1.0,-1.0);
231 for (vsize j = 0; j < stems.size (); j++)
234 beam_multiplicity_.push_back (Stem::beam_multiplicity (stems[j]));
235 head_positions_.push_back (Stem::head_positions (stems[j]));
236 is_normal_.push_back (Stem::is_normal_stem (stems[j]));
238 Stem_info si (Stem::get_stem_info (s));
239 si.scale (1 / staff_space_);
240 stem_infos_.push_back (si);
241 chord_start_y_.push_back (Stem::chord_start_y (s));
242 dirs_found[si.dir_] = true;
244 bool f = to_boolean (s->get_property ("french-beaming"))
245 && s != edge_stems[LEFT] && s != edge_stems[RIGHT];
247 Real y = Beam::calc_stem_y (beams[i], s, common, local_x_span[LEFT], local_x_span[RIGHT], CENTER,
249 base_lengths_.push_back (y / staff_space_);
250 stem_xpositions_.push_back (s->relative_coordinate (common[X_AXIS], X_AXIS) - x_left + x_span_);
251 stem_ypositions_.push_back (s->relative_coordinate (common[Y_AXIS], Y_AXIS) - my_y);
252 if (is_normal_.back ())
254 if (beam_width[LEFT] == -1.0)
255 beam_width[LEFT] = stem_xpositions_.back ();
256 beam_width[RIGHT] = stem_xpositions_.back ();
260 edge_dirs_ = Drul_array<Direction> (CENTER, CENTER);
261 normal_stem_count_ += Beam::normal_stem_count (beams[i]);
262 if (normal_stem_count_)
263 edge_dirs_ = Drul_array<Direction> (stem_infos_[0].dir_,
264 stem_infos_.back ().dir_);
266 is_xstaff_ = Align_interface::has_interface (common[Y_AXIS]);
267 is_knee_ = dirs_found[LEFT] && dirs_found[RIGHT];
269 staff_radius_ = Staff_symbol_referencer::staff_radius (beams[i]);
270 edge_beam_counts_ = Drul_array<int>
271 (Stem::beam_multiplicity (stems[0]).length () + 1,
272 Stem::beam_multiplicity (stems.back ()).length () + 1);
274 // TODO - why are we dividing by staff_space_?
275 beam_translation_ = Beam::get_beam_translation (beams[i]) / staff_space_;
280 quant_range_[d].set_full ();
284 Real stem_offset = edge_stems[d]->relative_coordinate (common[Y_AXIS], Y_AXIS)
285 - beams[i]->relative_coordinate (common[Y_AXIS], Y_AXIS);
286 Interval heads = Stem::head_positions (edge_stems[d]) * 0.5 * staff_space_;
288 Direction ed = edge_dirs_[d];
289 heads.widen (0.5 * staff_space_
290 + (edge_beam_counts_[d] - 1) * beam_translation_ + beam_thickness_ * .5);
291 quant_range_[d][-ed] = heads[ed] + stem_offset;
293 while (flip (&d) != LEFT);
294 Grob *common_x = NULL;
295 segments_ = Beam::get_beam_segments (beams[i], &common_x);
296 vector_sort (segments_, beam_segment_less);
297 for (vsize j = 0; j < segments_.size (); j++)
298 segments_[j].horizontal_ += (x_span_ - x_left);
300 set<Grob *> colliding_stems;
301 for (vsize j = 0; j < collisions.size (); j++)
303 if (!collisions[j]->is_live ())
306 if (Beam::has_interface (collisions[j]) && Beam::is_cross_staff (collisions[j]))
310 for (Axis a = X_AXIS; a < NO_AXES; incr (a))
311 b[a] = collisions[j]->extent (common[a], a);
313 if (b[X_AXIS].is_empty () || b[Y_AXIS].is_empty ())
316 b[X_AXIS] += (x_span_ - x_left);
317 Real width = b[X_AXIS].length ();
318 Real width_factor = sqrt (width / staff_space_);
322 add_collision (b[X_AXIS][d], b[Y_AXIS], width_factor);
323 while (flip (&d) != LEFT);
325 Grob *stem = unsmob_grob (collisions[j]->get_object ("stem"));
326 if (stem && Stem::has_interface (stem) && Stem::is_normal_stem (stem))
328 colliding_stems.insert (stem);
332 for (set<Grob *>::const_iterator it (colliding_stems.begin ()); it != colliding_stems.end (); it++)
335 Real x = (s->extent (common[X_AXIS], X_AXIS) - x_left + x_span_).center ();
337 Direction stem_dir = get_grob_direction (*it);
340 y[-stem_dir] = Stem::chord_start_y (*it) + (*it)->relative_coordinate (common[Y_AXIS], Y_AXIS)
341 - beams[i]->relative_coordinate (common[Y_AXIS], Y_AXIS);
343 Real factor = parameters_.STEM_COLLISION_FACTOR;
344 if (!unsmob_grob (s->get_object ("beam")))
346 add_collision (x, y, factor);
348 x_span_ += beams[i]->spanner_length ();
352 Here, we eliminate all extremal hangover, be it from non-normal stems
353 (like stemlets) or broken beams (if we're not calculating consistent
356 if (normal_stem_count_)
358 Interval trimmings (0.0, 0.0);
363 vsize idx = d == LEFT ? first_normal_index () : last_normal_index ();
364 trimmings[d] = d * ((d == LEFT ? 0 : x_span_) - stem_xpositions_[idx]);
366 while (flip (&d) != LEFT);
369 x_span_ -= trimmings[d];
370 while (flip (&d) != LEFT);
372 for (vsize i = 0; i < stem_xpositions_.size (); i++)
373 stem_xpositions_[i] -= trimmings[LEFT];
377 Beam_scoring_problem::Beam_scoring_problem (Grob *me, Drul_array<Real> ys)
379 beam_ = dynamic_cast<Spanner *> (me);
381 consistent_broken_slope_ = to_boolean (me->get_property ("consistent-broken-slope"));
383 Calculations are relative to a unit-scaled staff, i.e. the quants are
384 divided by the current staff_space_.
386 staff_space_ = Staff_symbol_referencer::staff_space (me);
387 beam_thickness_ = Beam::get_beam_thickness (me) / staff_space_;
388 line_thickness_ = Staff_symbol_referencer::line_thickness (me) / staff_space_;
390 // This is the least-squares DY, corrected for concave beams.
391 musical_dy_ = robust_scm2double (me->get_property ("least-squares-dy"), 0);
393 parameters_.fill (me);
395 least_squares_positions ();
397 shift_region_to_valid ();
400 // Assuming V is not empty, pick a 'reasonable' point inside V.
402 point_in_interval (Interval v, Real dist)
406 else if (isinf (v[UP]))
407 return v[DOWN] + dist;
412 /* Set stem's shorten property if unset.
415 take some y-position (chord/beam/nearest?) into account
416 scmify forced-fraction
418 This is done in beam because the shorten has to be uniform over the
423 set_minimum_dy (Grob *me, Real *dy)
428 If dy is smaller than the smallest quant, we
429 get absurd direction-sign penalties.
432 Real ss = Staff_symbol_referencer::staff_space (me);
433 Real beam_thickness = Beam::get_beam_thickness (me) / ss;
434 Real slt = Staff_symbol_referencer::line_thickness (me) / ss;
435 Real sit = (beam_thickness - slt) / 2;
437 Real hang = 1.0 - (beam_thickness - slt) / 2;
439 *dy = sign (*dy) * max (fabs (*dy),
440 min (min (sit, inter), hang));
445 Beam_scoring_problem::no_visible_stem_positions ()
447 if (!head_positions_.size ())
449 unquanted_y_ = Interval (0, 0);
453 Interval head_positions;
455 for (vsize i = 0; i < head_positions_.size (); i++)
457 head_positions.unite (head_positions_[i]);
458 multiplicity.unite (beam_multiplicity_[i]);
461 Direction dir = get_grob_direction (beam_);
464 programming_error ("The beam should have a direction by now.");
466 Real y = head_positions.linear_combination (dir)
468 + dir * beam_translation_ * (multiplicity.length () + 1);
470 unquanted_y_ = Interval (y, y);
474 Beam_scoring_problem::first_normal_index ()
476 for (vsize i = 0; i < is_normal_.size (); i++)
480 beam_->programming_error ("No normal stems, but asking for first normal stem index.");
485 Beam_scoring_problem::last_normal_index ()
487 for (vsize i = is_normal_.size (); i--;)
491 beam_->programming_error ("No normal stems, but asking for first normal stem index.");
496 Beam_scoring_problem::least_squares_positions ()
498 if (!normal_stem_count_)
500 no_visible_stem_positions ();
504 if (stem_infos_.size () < 1)
507 vsize fnx = first_normal_index ();
508 vsize lnx = last_normal_index ();
510 Interval ideal (stem_infos_[fnx].ideal_y_ + stem_ypositions_[fnx],
511 stem_infos_[lnx].ideal_y_ + stem_ypositions_[lnx]);
519 Interval chord (chord_start_y_[0],
520 chord_start_y_.back ());
522 /* Simple beams (2 stems) on middle line should be allowed to be
525 However, if both stems reach middle line,
526 ideal[LEFT] == ideal[RIGHT] and ideal.delta () == 0.
528 For that case, we apply artificial slope */
529 if (!ideal[LEFT] && chord.delta () && stem_infos_.size () == 2)
532 Direction d = (Direction) (sign (chord.delta ()) * UP);
533 unquanted_y_[d] = Beam::get_beam_thickness (beam_) / 2;
534 unquanted_y_[-d] = -unquanted_y_[d];
537 unquanted_y_ = ideal;
540 For broken beams this doesn't work well. In this case, the
541 slope esp. of the first part of a broken beam should predict
542 where the second part goes.
544 ldy = unquanted_y_[RIGHT] - unquanted_y_[LEFT];
548 vector<Offset> ideals;
549 for (vsize i = 0; i < stem_infos_.size (); i++)
551 ideals.push_back (Offset (stem_xpositions_[i],
552 stem_infos_[i].ideal_y_
553 + stem_ypositions_[i]));
555 minimise_least_squares (&slope, &y, ideals);
557 dy = slope * x_span_;
559 set_minimum_dy (beam_, &dy);
562 unquanted_y_ = Interval (y, (y + dy));
569 Beam_scoring_problem::slope_damping ()
571 if (normal_stem_count_ <= 1)
574 SCM s = beam_->get_property ("damping");
575 Real damping = scm_to_double (s);
576 Real concaveness = robust_scm2double (beam_->get_property ("concaveness"), 0.0);
577 if (concaveness >= 10000)
579 unquanted_y_[LEFT] = unquanted_y_[RIGHT];
586 Real dy = unquanted_y_[RIGHT] - unquanted_y_[LEFT];
588 Real slope = dy && x_span_ ? dy / x_span_ : 0;
590 slope = 0.6 * tanh (slope) / (damping + concaveness);
592 Real damped_dy = slope * x_span_;
594 set_minimum_dy (beam_, &damped_dy);
596 unquanted_y_[LEFT] += (dy - damped_dy) / 2;
597 unquanted_y_[RIGHT] -= (dy - damped_dy) / 2;
602 Beam_scoring_problem::shift_region_to_valid ()
604 if (!normal_stem_count_)
607 Real beam_dy = unquanted_y_[RIGHT] - unquanted_y_[LEFT];
608 Real slope = x_span_ ? beam_dy / x_span_ : 0.0;
611 Shift the positions so that we have a chance of finding good
612 quants (i.e. no short stem failures.)
614 Interval feasible_left_point;
615 feasible_left_point.set_full ();
617 for (vsize i = 0; i < stem_infos_.size (); i++)
619 // TODO - check for invisible here...
621 = stem_infos_[i].shortest_y_
622 - slope * stem_xpositions_ [i];
625 left_y is now relative to the stem S. We want relative to
626 ourselves, so translate:
628 left_y += stem_ypositions_[i];
631 flp[-stem_infos_[i].dir_] = left_y;
633 feasible_left_point.intersect (flp);
636 vector<Grob *> filtered;
638 We only update these for objects that are too large for quanting
639 to find a workaround. Typically, these are notes with
640 stems, and timesig/keysig/clef, which take out the entire area
641 inside the staff as feasible.
643 The code below disregards the thickness and multiplicity of the
644 beam. This should not be a problem, as the beam quanting will
645 take care of computing the impact those exactly.
647 Real min_y_size = 2.0;
649 // A list of intervals into which beams may not fall
650 vector<Interval> forbidden_intervals;
652 for (vsize i = 0; i < collisions_.size (); i++)
654 if (collisions_[i].x_ < 0 || collisions_[i].x_ > x_span_)
657 if (collisions_[i].y_.length () < min_y_size)
663 Real dy = slope * collisions_[i].x_;
669 Real left_y = collisions_[i].y_[yd] - dy;
670 disallowed[yd] = left_y;
672 while (flip (&yd) != DOWN);
674 forbidden_intervals.push_back (disallowed);
676 while (flip (&d) != LEFT);
679 vector_sort (forbidden_intervals, Interval::left_less);
680 Real epsilon = 1.0e-10;
681 Real beam_left_y = unquanted_y_[LEFT];
682 Interval feasible_beam_placements (beam_left_y, beam_left_y);
685 forbidden_intervals contains a vector of intervals in which
686 the beam cannot start. it iterates through these intervals,
687 pushing feasible_beam_placements epsilon over or epsilon under a
688 collision. when this type of change happens, the loop is marked
689 as "dirty" and re-iterated.
691 TODO: figure out a faster ways that this loop can happen via
692 a better search algorithm and/or OOP.
699 for (vsize i = 0; i < forbidden_intervals.size (); i++)
704 if (forbidden_intervals[i][d] == d * infinity_f)
705 feasible_beam_placements[d] = d * infinity_f;
706 else if (forbidden_intervals[i].contains (feasible_beam_placements[d]))
708 feasible_beam_placements[d] = d * epsilon + forbidden_intervals[i][d];
712 while (flip (&d) != DOWN);
717 // if the beam placement falls out of the feasible region, we push it
718 // to infinity so that it can never be a feasible candidate below
722 if (!feasible_left_point.contains (feasible_beam_placements[d]))
723 feasible_beam_placements[d] = d * infinity_f;
725 while (flip (&d) != DOWN);
727 if ((feasible_beam_placements[UP] == infinity_f && feasible_beam_placements[DOWN] == -infinity_f) && !feasible_left_point.is_empty ())
729 // We are somewhat screwed: we have a collision, but at least
730 // there is a way to satisfy stem length constraints.
731 beam_left_y = point_in_interval (feasible_left_point, 2.0);
733 else if (!feasible_left_point.is_empty ())
735 // Only one of them offers is feasible solution. Pick that one.
736 if (abs (beam_left_y - feasible_beam_placements[DOWN]) > abs (beam_left_y - feasible_beam_placements[UP]))
737 beam_left_y = feasible_beam_placements[UP];
739 beam_left_y = feasible_beam_placements[DOWN];
743 // We are completely screwed.
744 beam_->warning (_ ("no viable initial configuration found: may not find good beam slope"));
747 unquanted_y_ = Drul_array<Real> (beam_left_y, (beam_left_y + beam_dy));
751 Beam_scoring_problem::generate_quants (vector<Beam_configuration *> *scores) const
753 int region_size = (int) parameters_.REGION_SIZE;
755 // Knees and collisions are harder, lets try some more possibilities
758 if (collisions_.size ())
762 Real sit = (beam_thickness_ - line_thickness_) / 2;
764 Real hang = 1.0 - (beam_thickness_ - line_thickness_) / 2;
765 Real base_quants [] = {straddle, sit, inter, hang};
766 int num_base_quants = int (sizeof (base_quants) / sizeof (Real));
769 Asymetry ? should run to <= region_size ?
771 vector<Real> unshifted_quants;
772 for (int i = -region_size; i < region_size; i++)
773 for (int j = 0; j < num_base_quants; j++)
775 unshifted_quants.push_back (i + base_quants[j]);
778 for (vsize i = 0; i < unshifted_quants.size (); i++)
779 for (vsize j = 0; j < unshifted_quants.size (); j++)
781 Beam_configuration *c
782 = Beam_configuration::new_config (unquanted_y_,
783 Interval (unshifted_quants[i],
784 unshifted_quants[j]));
789 if (!quant_range_[d].contains (c->y[d]))
796 while (flip (&d) != LEFT);
798 scores->push_back (c);
803 void Beam_scoring_problem::one_scorer (Beam_configuration *config) const
806 switch (config->next_scorer_todo)
809 score_slope_ideal (config);
811 case SLOPE_DIRECTION:
812 score_slope_direction (config);
815 score_slope_musical (config);
818 score_forbidden_quants (config);
821 score_stem_lengths (config);
824 score_collisions (config);
826 case HORIZONTAL_INTER:
827 score_horizontal_inter_quants (config);
831 case ORIGINAL_DISTANCE:
835 config->next_scorer_todo++;
839 Beam_scoring_problem::force_score (SCM inspect_quants, const vector<Beam_configuration *> &configs) const
841 Drul_array<Real> ins = ly_scm2interval (inspect_quants);
843 Beam_configuration *best = NULL;
844 for (vsize i = 0; i < configs.size (); i++)
846 Real d = fabs (configs[i]->y[LEFT] - ins[LEFT]) + fabs (configs[i]->y[RIGHT] - ins[RIGHT]);
854 programming_error ("cannot find quant");
856 while (!best->done ())
863 Beam_scoring_problem::solve () const
865 vector<Beam_configuration *> configs;
866 generate_quants (&configs);
868 if (configs.empty ())
870 programming_error ("No viable beam quanting found. Using unquanted y value.");
874 if (to_boolean (beam_->get_property ("skip-quanting")))
877 Beam_configuration *best = NULL;
880 = to_boolean (beam_->layout ()->lookup_variable (ly_symbol2scm ("debug-beam-scoring")));
881 SCM inspect_quants = beam_->get_property ("inspect-quants");
882 if (scm_is_pair (inspect_quants))
885 best = force_score (inspect_quants, configs);
889 std::priority_queue < Beam_configuration *, std::vector<Beam_configuration *>,
890 Beam_configuration_less > queue;
891 for (vsize i = 0; i < configs.size (); i++)
892 queue.push (configs[i]);
897 It would be neat if we generated new configurations on the
898 fly, depending on the best complete score so far, eg.
901 if (best->demerits < sqrt(queue.size())
903 while (best->demerits > sqrt(queue.size()) {
904 generate and insert new configuration
908 that would allow us to do away with region_size altogether.
922 Interval final_positions = best->y;
924 #if DEBUG_BEAM_SCORING
929 for (vsize i = 0; i < configs.size (); i++)
931 if (configs[i]->done ())
935 string card = best->score_card_ + to_string (" c%d/%d", completed, configs.size ());
936 beam_->set_property ("annotation", ly_string2scm (card));
940 junk_pointers (configs);
941 if (consistent_broken_slope_)
943 Interval normalized_endpoints = robust_scm2interval (beam_->get_property ("normalized-endpoints"), Interval (0, 1));
944 Real y_length = final_positions[RIGHT] - final_positions[LEFT];
946 final_positions[LEFT] += normalized_endpoints[LEFT] * y_length;
947 final_positions[RIGHT] -= (1 - normalized_endpoints[RIGHT]) * y_length;
950 return final_positions;
954 Beam_scoring_problem::score_stem_lengths (Beam_configuration *config) const
956 Real limit_penalty = parameters_.STEM_LENGTH_LIMIT_PENALTY;
957 Drul_array<Real> score (0, 0);
958 Drul_array<int> count (0, 0);
960 for (vsize i = 0; i < stem_xpositions_.size (); i++)
965 Real x = stem_xpositions_[i];
968 ? config->y[RIGHT] * x / dx + config->y[LEFT] * (x_span_ - x) / dx
969 : (config->y[RIGHT] + config->y[LEFT]) / 2;
970 Real current_y = beam_y + base_lengths_[i];
971 Real length_pen = parameters_.STEM_LENGTH_DEMERIT_FACTOR;
973 Stem_info info = stem_infos_[i];
974 Direction d = info.dir_;
976 score[d] += limit_penalty * max (0.0, (d * (info.shortest_y_ - current_y)));
978 Real ideal_diff = d * (current_y - info.ideal_y_);
979 Real ideal_score = shrink_extra_weight (ideal_diff, 1.5);
981 /* We introduce a power, to make the scoring strictly
982 convex. Otherwise a symmetric knee beam (up/down/up/down)
983 does not have an optimum in the middle. */
985 ideal_score = pow (ideal_score, 1.1);
987 score[d] += length_pen * ideal_score;
991 /* Divide by number of stems, to make the measure scale-free. */
994 score[d] /= max (count[d], 1);
995 while (flip (&d) != DOWN);
997 config->add (score[LEFT] + score[RIGHT], "L");
1001 Beam_scoring_problem::score_slope_direction (Beam_configuration *config) const
1003 Real dy = config->y.delta ();
1004 Real damped_dy = unquanted_y_.delta ();
1007 DAMPING_DIRECTION_PENALTY is a very harsh measure, while for
1008 complex beaming patterns, horizontal is often a good choice.
1010 TODO: find a way to incorporate the complexity of the beam in this
1013 if (sign (damped_dy) != sign (dy))
1017 if (fabs (damped_dy / x_span_) > parameters_.ROUND_TO_ZERO_SLOPE)
1018 dem += parameters_.DAMPING_DIRECTION_PENALTY;
1020 dem += parameters_.HINT_DIRECTION_PENALTY;
1023 dem += parameters_.DAMPING_DIRECTION_PENALTY;
1026 config->add (dem, "Sd");
1029 // Score for going against the direction of the musical pattern
1031 Beam_scoring_problem::score_slope_musical (Beam_configuration *config) const
1033 Real dy = config->y.delta ();
1034 Real dem = parameters_.MUSICAL_DIRECTION_FACTOR
1035 * max (0.0, (fabs (dy) - fabs (musical_dy_)));
1036 config->add (dem, "Sm");
1039 // Score deviation from calculated ideal slope.
1041 Beam_scoring_problem::score_slope_ideal (Beam_configuration *config) const
1043 Real dy = config->y.delta ();
1044 Real damped_dy = unquanted_y_.delta ();
1047 Real slope_penalty = parameters_.IDEAL_SLOPE_FACTOR;
1049 /* Xstaff beams tend to use extreme slopes to get short stems. We
1050 put in a penalty here. */
1052 slope_penalty *= 10;
1054 /* Huh, why would a too steep beam be better than a too flat one ? */
1055 dem += shrink_extra_weight (fabs (damped_dy) - fabs (dy), 1.5)
1058 config->add (dem, "Si");
1064 return x - floor (x);
1067 // TODO - there is some overlap with forbidden quants, but for
1068 // horizontal beams, it is much more serious to have stafflines
1069 // appearing in the wrong place, so we have a separate scorer.
1071 Beam_scoring_problem::score_horizontal_inter_quants (Beam_configuration *config) const
1073 if (config->y.delta () == 0.0
1074 && abs (config->y[LEFT]) < staff_radius_ * staff_space_)
1076 Real yshift = config->y[LEFT] - 0.5 * staff_space_;
1077 if (fabs (my_round (yshift) - yshift) < 0.01 * staff_space_)
1078 config->add (parameters_.HORIZONTAL_INTER_QUANT_PENALTY, "H");
1083 TODO: The fixed value SECONDARY_BEAM_DEMERIT is probably flawed:
1084 because for 32nd and 64th beams the forbidden quants are relatively
1085 more important than stem lengths.
1088 Beam_scoring_problem::score_forbidden_quants (Beam_configuration *config) const
1090 Real dy = config->y.delta ();
1092 Real extra_demerit = parameters_.SECONDARY_BEAM_DEMERIT
1093 / max (edge_beam_counts_[LEFT], edge_beam_counts_[RIGHT]);
1097 Real eps = parameters_.BEAM_EPS;
1101 for (int j = 1; j <= edge_beam_counts_[d]; j++)
1103 Direction stem_dir = edge_dirs_[d];
1106 The 2.2 factor is to provide a little leniency for
1107 borderline cases. If we do 2.0, then the upper outer line
1108 will be in the gap of the (2, sit) quant, leading to a
1111 Real gap1 = config->y[d] - stem_dir * ((j - 1) * beam_translation_ + beam_thickness_ / 2 - line_thickness_ / 2.2);
1112 Real gap2 = config->y[d] - stem_dir * (j * beam_translation_ - beam_thickness_ / 2 + line_thickness_ / 2.2);
1115 gap.add_point (gap1);
1116 gap.add_point (gap2);
1118 for (Real k = -staff_radius_;
1119 k <= staff_radius_ + eps; k += 1.0)
1120 if (gap.contains (k))
1122 Real dist = min (fabs (gap[UP] - k), fabs (gap[DOWN] - k));
1125 this parameter is tuned to grace-stem-length.ly
1127 Real fixed_demerit = 0.4;
1129 dem += extra_demerit
1131 + (1 - fixed_demerit) * (dist / gap.length ()) * 2);
1135 while ((flip (&d)) != LEFT);
1137 if (max (edge_beam_counts_[LEFT], edge_beam_counts_[RIGHT]) >= 2)
1139 Real straddle = 0.0;
1140 Real sit = (beam_thickness_ - line_thickness_) / 2;
1142 Real hang = 1.0 - (beam_thickness_ - line_thickness_) / 2;
1147 if (edge_beam_counts_[d] >= 2
1148 && fabs (config->y[d] - edge_dirs_[d] * beam_translation_) < staff_radius_ + inter)
1150 // TODO up/down symmetry.
1151 if (edge_dirs_[d] == UP && dy <= eps
1152 && fabs (my_modf (config->y[d]) - sit) < eps)
1153 dem += extra_demerit;
1155 if (edge_dirs_[d] == DOWN && dy >= eps
1156 && fabs (my_modf (config->y[d]) - hang) < eps)
1157 dem += extra_demerit;
1160 if (edge_beam_counts_[d] >= 3
1161 && fabs (config->y[d] - 2 * edge_dirs_[d] * beam_translation_) < staff_radius_ + inter)
1163 // TODO up/down symmetry.
1164 if (edge_dirs_[d] == UP && dy <= eps
1165 && fabs (my_modf (config->y[d]) - straddle) < eps)
1166 dem += extra_demerit;
1168 if (edge_dirs_[d] == DOWN && dy >= eps
1169 && fabs (my_modf (config->y[d]) - straddle) < eps)
1170 dem += extra_demerit;
1173 while (flip (&d) != LEFT);
1176 config->add (dem, "F");
1180 Beam_scoring_problem::score_collisions (Beam_configuration *config) const
1182 Real demerits = 0.0;
1183 for (vsize i = 0; i < collisions_.size (); i++)
1185 Interval collision_y = collisions_[i].y_;
1186 Real x = collisions_[i].x_;
1188 Real center_beam_y = y_at (x, config);
1189 Interval beam_y = center_beam_y + collisions_[i].beam_y_;
1191 Real dist = infinity_f;
1192 if (!intersection (beam_y, collision_y).is_empty ())
1195 dist = min (beam_y.distance (collision_y[DOWN]),
1196 beam_y.distance (collision_y[UP]));
1199 = max (parameters_.COLLISION_PADDING - dist, 0.0) /
1200 parameters_.COLLISION_PADDING;
1202 += collisions_[i].base_penalty_ *
1203 pow (scale_free, 3) * parameters_.COLLISION_PENALTY;
1206 config->add (demerits, "C");