2 This file is part of LilyPond, the GNU music typesetter.
4 Copyright (C) 1997--2012 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;
198 do_initial_slope_calculations_ |= isinf (unquanted_y_[d]) || isnan (unquanted_y_[d]);
199 while (flip (&d) != LEFT);
202 Calculations are relative to a unit-scaled staff, i.e. the quants are
203 divided by the current staff_space_.
205 staff_space_ = Staff_symbol_referencer::staff_space (beam_);
206 beam_thickness_ = Beam::get_beam_thickness (beam_) / staff_space_;
207 line_thickness_ = Staff_symbol_referencer::line_thickness (beam_) / staff_space_;
209 // This is the least-squares DY, corrected for concave beams.
210 musical_dy_ = robust_scm2double (beam_->get_property ("least-squares-dy"), 0);
212 vector<Spanner *> beams;
213 align_broken_intos_ = align_broken_intos;
214 if (align_broken_intos_)
216 Spanner *orig = dynamic_cast<Spanner *> (beam_->original ());
218 align_broken_intos_ = false;
219 else if (!orig->broken_intos_.size ())
220 align_broken_intos_ = false;
222 beams.insert (beams.end (), orig->broken_intos_.begin (), orig->broken_intos_.end ());
224 if (!align_broken_intos_)
225 beams.push_back (beam_);
228 x_span_ is a single scalar, cumulatively summing the length of all the
229 segments the parent beam was broken-into.
233 normal_stem_count_ = 0;
234 for (vsize i = 0; i < beams.size (); i++)
236 extract_grob_set (beams[i], "stems", stems);
237 extract_grob_set (beams[i], "covered-grobs", fake_collisions);
238 vector<Grob *> collisions;
240 for (vsize j = 0; j < fake_collisions.size (); j++)
241 if (fake_collisions[j]->get_system () == beams[i]->get_system ())
242 collisions.push_back (fake_collisions[j]);
245 for (int a = 2; a--;)
246 common[a] = common_refpoint_of_array (stems, beams[i], Axis (a));
250 common[X_AXIS] = beams[i]->get_bound (d)->common_refpoint (common[X_AXIS], X_AXIS);
251 while (flip (&d) != LEFT);
253 // positions of the endpoints of this beam segment, including any overhangs
254 const Interval x_pos = robust_scm2interval (beams[i]->get_property ("X-positions"),
255 Interval (0.0, 0.0));
257 Drul_array<Grob *> edge_stems (Beam::first_normal_stem (beams[i]),
258 Beam::last_normal_stem (beams[i]));
260 Drul_array<bool> dirs_found (0, 0);
262 Real my_y = beams[i]->relative_coordinate (common[Y_AXIS], Y_AXIS);
264 Interval beam_width (-1.0, -1.0);
265 for (vsize j = 0; j < stems.size (); j++)
268 beam_multiplicity_.push_back (Stem::beam_multiplicity (stems[j]));
269 head_positions_.push_back (Stem::head_positions (stems[j]));
270 is_normal_.push_back (Stem::is_normal_stem (stems[j]));
272 Stem_info si (Stem::get_stem_info (s));
273 si.scale (1 / staff_space_);
274 stem_infos_.push_back (si);
275 chord_start_y_.push_back (Stem::chord_start_y (s));
276 dirs_found[si.dir_] = true;
278 bool f = to_boolean (s->get_property ("french-beaming"))
279 && s != edge_stems[LEFT] && s != edge_stems[RIGHT];
281 Real y = Beam::calc_stem_y (beams[i], s, common, x_pos[LEFT], x_pos[RIGHT], CENTER,
283 base_lengths_.push_back (y / staff_space_);
284 stem_xpositions_.push_back (s->relative_coordinate (common[X_AXIS], X_AXIS) - x_pos[LEFT] + x_span_);
285 stem_ypositions_.push_back (s->relative_coordinate (common[Y_AXIS], Y_AXIS) - my_y);
287 if (is_normal_.back ())
289 if (beam_width[LEFT] == -1.0)
290 beam_width[LEFT] = stem_xpositions_.back ();
291 beam_width[RIGHT] = stem_xpositions_.back ();
295 edge_dirs_ = Drul_array<Direction> (CENTER, CENTER);
296 normal_stem_count_ += Beam::normal_stem_count (beams[i]);
297 if (normal_stem_count_)
298 edge_dirs_ = Drul_array<Direction> (stem_infos_[0].dir_,
299 stem_infos_.back ().dir_);
301 is_xstaff_ = Align_interface::has_interface (common[Y_AXIS]);
302 is_knee_ |= dirs_found[DOWN] && dirs_found[UP];
304 staff_radius_ = Staff_symbol_referencer::staff_radius (beams[i]);
305 edge_beam_counts_ = Drul_array<int>
306 (Stem::beam_multiplicity (stems[0]).length () + 1,
307 Stem::beam_multiplicity (stems.back ()).length () + 1);
309 // TODO - why are we dividing by staff_space_?
310 beam_translation_ = Beam::get_beam_translation (beams[i]) / staff_space_;
315 quant_range_[d].set_full ();
319 Real stem_offset = edge_stems[d]->relative_coordinate (common[Y_AXIS], Y_AXIS)
320 - beams[i]->relative_coordinate (common[Y_AXIS], Y_AXIS);
321 Interval heads = Stem::head_positions (edge_stems[d]) * 0.5 * staff_space_;
323 Direction ed = edge_dirs_[d];
324 heads.widen (0.5 * staff_space_
325 + (edge_beam_counts_[d] - 1) * beam_translation_ + beam_thickness_ * .5);
326 quant_range_[d][-ed] = heads[ed] + stem_offset;
328 while (flip (&d) != LEFT);
330 segments_ = Beam::get_beam_segments (beams[i]);
331 vector_sort (segments_, beam_segment_less);
332 for (vsize j = 0; j < segments_.size (); j++)
333 segments_[j].horizontal_ += (x_span_ - x_pos[LEFT]);
335 set<Grob *> colliding_stems;
336 for (vsize j = 0; j < collisions.size (); j++)
338 if (!collisions[j]->is_live ())
341 if (Beam::has_interface (collisions[j]) && Beam::is_cross_staff (collisions[j]))
345 for (Axis a = X_AXIS; a < NO_AXES; incr (a))
346 b[a] = collisions[j]->extent (common[a], a);
348 if (b[X_AXIS][RIGHT] < x_pos[LEFT] || b[X_AXIS][LEFT] > x_pos[RIGHT])
350 if (b[X_AXIS].is_empty () || b[Y_AXIS].is_empty ())
353 b[X_AXIS] += (x_span_ - x_pos[LEFT]);
355 Real width = b[X_AXIS].length ();
356 Real width_factor = sqrt (width / staff_space_);
360 add_collision (b[X_AXIS][d], b[Y_AXIS], width_factor);
361 while (flip (&d) != LEFT);
363 Grob *stem = unsmob_grob (collisions[j]->get_object ("stem"));
364 if (stem && Stem::has_interface (stem) && Stem::is_normal_stem (stem))
366 colliding_stems.insert (stem);
370 for (set<Grob *>::const_iterator it (colliding_stems.begin ()); it != colliding_stems.end (); it++)
373 Real x = (s->extent (common[X_AXIS], X_AXIS) - x_pos[LEFT] + x_span_).center ();
375 Direction stem_dir = get_grob_direction (*it);
378 y[-stem_dir] = Stem::chord_start_y (*it) + (*it)->relative_coordinate (common[Y_AXIS], Y_AXIS)
381 Real factor = parameters_.STEM_COLLISION_FACTOR;
382 if (!unsmob_grob (s->get_object ("beam")))
384 add_collision (x, y, factor);
386 x_span_ += beams[i]->spanner_length ();
390 Beam_scoring_problem::Beam_scoring_problem (Grob *me, Drul_array<Real> ys, bool align_broken_intos)
392 beam_ = dynamic_cast<Spanner *> (me);
394 align_broken_intos_ = align_broken_intos;
396 parameters_.fill (me);
397 init_instance_variables (me, ys, align_broken_intos);
398 if (do_initial_slope_calculations_)
400 least_squares_positions ();
402 shift_region_to_valid ();
406 // Assuming V is not empty, pick a 'reasonable' point inside V.
408 point_in_interval (Interval v, Real dist)
412 else if (isinf (v[UP]))
413 return v[DOWN] + dist;
418 /* Set stem's shorten property if unset.
421 take some y-position (chord/beam/nearest?) into account
422 scmify forced-fraction
424 This is done in beam because the shorten has to be uniform over the
429 set_minimum_dy (Grob *me, Real *dy)
434 If dy is smaller than the smallest quant, we
435 get absurd direction-sign penalties.
438 Real ss = Staff_symbol_referencer::staff_space (me);
439 Real beam_thickness = Beam::get_beam_thickness (me) / ss;
440 Real slt = Staff_symbol_referencer::line_thickness (me) / ss;
441 Real sit = (beam_thickness - slt) / 2;
443 Real hang = 1.0 - (beam_thickness - slt) / 2;
445 *dy = sign (*dy) * max (fabs (*dy),
446 min (min (sit, inter), hang));
451 Beam_scoring_problem::no_visible_stem_positions ()
453 if (!head_positions_.size ())
455 unquanted_y_ = Interval (0, 0);
459 Interval head_positions;
461 for (vsize i = 0; i < head_positions_.size (); i++)
463 head_positions.unite (head_positions_[i]);
464 multiplicity.unite (beam_multiplicity_[i]);
467 Direction dir = get_grob_direction (beam_);
470 programming_error ("The beam should have a direction by now.");
472 Real y = head_positions.linear_combination (dir)
474 + dir * beam_translation_ * (multiplicity.length () + 1);
476 unquanted_y_ = Interval (y, y);
480 Beam_scoring_problem::first_normal_index ()
482 for (vsize i = 0; i < is_normal_.size (); i++)
486 beam_->programming_error ("No normal stems, but asking for first normal stem index.");
491 Beam_scoring_problem::last_normal_index ()
493 for (vsize i = is_normal_.size (); i--;)
497 beam_->programming_error ("No normal stems, but asking for first normal stem index.");
502 Beam_scoring_problem::least_squares_positions ()
504 if (!normal_stem_count_)
506 no_visible_stem_positions ();
510 if (stem_infos_.size () < 1)
513 vsize fnx = first_normal_index ();
514 vsize lnx = last_normal_index ();
516 Interval ideal (stem_infos_[fnx].ideal_y_ + stem_ypositions_[fnx],
517 stem_infos_[lnx].ideal_y_ + stem_ypositions_[lnx]);
525 Interval chord (chord_start_y_[0],
526 chord_start_y_.back ());
528 /* Simple beams (2 stems) on middle line should be allowed to be
531 However, if both stems reach middle line,
532 ideal[LEFT] == ideal[RIGHT] and ideal.delta () == 0.
534 For that case, we apply artificial slope */
535 if (!ideal[LEFT] && chord.delta () && stem_infos_.size () == 2)
538 Direction d = (Direction) (sign (chord.delta ()) * UP);
539 unquanted_y_[d] = Beam::get_beam_thickness (beam_) / 2;
540 unquanted_y_[-d] = -unquanted_y_[d];
543 unquanted_y_ = ideal;
545 ldy = unquanted_y_[RIGHT] - unquanted_y_[LEFT];
549 vector<Offset> ideals;
550 for (vsize i = 0; i < stem_infos_.size (); i++)
552 ideals.push_back (Offset (stem_xpositions_[i],
553 stem_infos_[i].ideal_y_
554 + stem_ypositions_[i]));
556 minimise_least_squares (&slope, &y, ideals);
558 dy = slope * x_span_;
560 set_minimum_dy (beam_, &dy);
563 unquanted_y_ = Interval (y, (y + dy));
567 beam_->set_property ("least-squares-dy", scm_from_double (musical_dy_));
571 Determine whether a beam is concave.
573 A beam is concave when the middle notes get closer to the
574 beam than the left and right edge notes.
576 This is determined in two ways: by looking at the positions of the
577 middle notes, or by looking at the deviation of the inside notes
578 compared to the line connecting first and last.
580 The tricky thing is what to do with beams with chords. There are no
581 real guidelines in this case.
585 is_concave_single_notes (vector<int> const &positions, Direction beam_dir)
588 covering.add_point (positions[0]);
589 covering.add_point (positions.back ());
593 bool concave = false;
596 notes above and below the interval covered by 1st and last note.
598 for (vsize i = 1; i + 1 < positions.size (); i++)
600 above = above || (positions[i] > covering[UP]);
601 below = below || (positions[i] < covering[DOWN]);
604 concave = concave || (above && below);
606 A note as close or closer to the beam than begin and end, but the
607 note is reached in the opposite direction as the last-first dy
609 int dy = positions.back () - positions[0];
610 int closest = max (beam_dir * positions.back (), beam_dir * positions[0]);
611 for (vsize i = 2; !concave && i + 1 < positions.size (); i++)
613 int inner_dy = positions[i] - positions[i - 1];
614 if (sign (inner_dy) != sign (dy)
615 && (beam_dir * positions[i] >= closest
616 || beam_dir * positions[i - 1] >= closest))
620 bool all_closer = true;
621 for (vsize i = 1; all_closer && i + 1 < positions.size (); i++)
623 all_closer = all_closer
624 && (beam_dir * positions[i] > closest);
627 concave = concave || all_closer;
632 calc_positions_concaveness (vector<int> const &positions, Direction beam_dir)
634 Real dy = positions.back () - positions[0];
635 Real slope = dy / Real (positions.size () - 1);
636 Real concaveness = 0.0;
637 for (vsize i = 1; i + 1 < positions.size (); i++)
639 Real line_y = slope * i + positions[0];
641 concaveness += max (beam_dir * (positions[i] - line_y), 0.0);
644 concaveness /= positions.size ();
647 Normalize. For dy = 0, the slope ends up as 0 anyway, so the
648 scaling of concaveness doesn't matter much.
651 concaveness /= fabs (dy);
656 Beam_scoring_problem::calc_concaveness ()
658 SCM conc = beam_->get_property ("concaveness");
659 if (scm_is_number (conc))
660 return scm_to_double (conc);
665 Direction beam_dir = CENTER;
666 for (vsize i = is_normal_.size (); i--;)
667 if (is_normal_[i] && stem_infos_[i].dir_)
668 beam_dir = stem_infos_[i].dir_;
670 if (normal_stem_count_ <= 2)
673 vector<int> close_positions;
674 vector<int> far_positions;
675 for (vsize i = 0; i < is_normal_.size (); i++)
679 For chords, we take the note head that is closest to the beam.
681 Hmmm.. wait, for the beams in the last measure of morgenlied,
682 this doesn't look so good. Let's try the heads farthest from
686 close_positions.push_back ((int) rint (head_positions_[i][beam_dir]));
687 far_positions.push_back ((int) rint (head_positions_[i][-beam_dir]));
690 Real concaveness = 0.0;
692 if (is_concave_single_notes (beam_dir == UP ? close_positions : far_positions, beam_dir))
698 concaveness = (calc_positions_concaveness (far_positions, beam_dir)
699 + calc_positions_concaveness (close_positions, beam_dir)) / 2;
706 Beam_scoring_problem::slope_damping ()
708 if (normal_stem_count_ <= 1)
711 SCM s = beam_->get_property ("damping");
712 Real damping = scm_to_double (s);
713 Real concaveness = calc_concaveness ();
714 if (concaveness >= 10000)
716 unquanted_y_[LEFT] = unquanted_y_[RIGHT];
723 Real dy = unquanted_y_[RIGHT] - unquanted_y_[LEFT];
725 Real slope = dy && x_span_ ? dy / x_span_ : 0;
727 slope = 0.6 * tanh (slope) / (damping + concaveness);
729 Real damped_dy = slope * x_span_;
731 set_minimum_dy (beam_, &damped_dy);
733 unquanted_y_[LEFT] += (dy - damped_dy) / 2;
734 unquanted_y_[RIGHT] -= (dy - damped_dy) / 2;
739 Beam_scoring_problem::shift_region_to_valid ()
741 if (!normal_stem_count_)
744 Real beam_dy = unquanted_y_[RIGHT] - unquanted_y_[LEFT];
745 Real slope = x_span_ ? beam_dy / x_span_ : 0.0;
748 Shift the positions so that we have a chance of finding good
749 quants (i.e. no short stem failures.)
751 Interval feasible_left_point;
752 feasible_left_point.set_full ();
754 for (vsize i = 0; i < stem_infos_.size (); i++)
756 // TODO - check for invisible here...
758 = stem_infos_[i].shortest_y_
759 - slope * stem_xpositions_ [i];
762 left_y is now relative to the stem S. We want relative to
763 ourselves, so translate:
765 left_y += stem_ypositions_[i];
768 flp[-stem_infos_[i].dir_] = left_y;
770 feasible_left_point.intersect (flp);
773 vector<Grob *> filtered;
775 We only update these for objects that are too large for quanting
776 to find a workaround. Typically, these are notes with
777 stems, and timesig/keysig/clef, which take out the entire area
778 inside the staff as feasible.
780 The code below disregards the thickness and multiplicity of the
781 beam. This should not be a problem, as the beam quanting will
782 take care of computing the impact those exactly.
784 Real min_y_size = 2.0;
786 // A list of intervals into which beams may not fall
787 vector<Interval> forbidden_intervals;
789 for (vsize i = 0; i < collisions_.size (); i++)
791 if (collisions_[i].x_ < 0 || collisions_[i].x_ > x_span_)
794 if (collisions_[i].y_.length () < min_y_size)
800 Real dy = slope * collisions_[i].x_;
806 Real left_y = collisions_[i].y_[yd] - dy;
807 disallowed[yd] = left_y;
809 while (flip (&yd) != DOWN);
811 forbidden_intervals.push_back (disallowed);
813 while (flip (&d) != LEFT);
816 vector_sort (forbidden_intervals, Interval::left_less);
817 Real beam_left_y = unquanted_y_[LEFT];
818 Interval feasible_beam_placements (beam_left_y, beam_left_y);
820 Interval_minefield minefield (feasible_beam_placements, 0.0);
821 for (vsize i = 0; i < forbidden_intervals.size (); i++)
822 minefield.add_forbidden_interval (forbidden_intervals[i]);
824 feasible_beam_placements = minefield.feasible_placements ();
826 // if the beam placement falls out of the feasible region, we push it
827 // to infinity so that it can never be a feasible candidate below
831 if (!feasible_left_point.contains (feasible_beam_placements[d]))
832 feasible_beam_placements[d] = d * infinity_f;
834 while (flip (&d) != DOWN);
836 if ((feasible_beam_placements[UP] == infinity_f && feasible_beam_placements[DOWN] == -infinity_f) && !feasible_left_point.is_empty ())
838 // We are somewhat screwed: we have a collision, but at least
839 // there is a way to satisfy stem length constraints.
840 beam_left_y = point_in_interval (feasible_left_point, 2.0);
842 else if (!feasible_left_point.is_empty ())
844 // Only one of them offers is feasible solution. Pick that one.
845 if (abs (beam_left_y - feasible_beam_placements[DOWN]) > abs (beam_left_y - feasible_beam_placements[UP]))
846 beam_left_y = feasible_beam_placements[UP];
848 beam_left_y = feasible_beam_placements[DOWN];
852 // We are completely screwed.
853 beam_->warning (_ ("no viable initial configuration found: may not find good beam slope"));
856 unquanted_y_ = Drul_array<Real> (beam_left_y, (beam_left_y + beam_dy));
860 Beam_scoring_problem::generate_quants (vector<Beam_configuration *> *scores) const
862 int region_size = (int) parameters_.REGION_SIZE;
864 // Knees and collisions are harder, lets try some more possibilities
867 if (collisions_.size ())
871 Real sit = (beam_thickness_ - line_thickness_) / 2;
873 Real hang = 1.0 - (beam_thickness_ - line_thickness_) / 2;
874 Real base_quants [] = {straddle, sit, inter, hang};
875 int num_base_quants = int (sizeof (base_quants) / sizeof (Real));
878 Asymetry ? should run to <= region_size ?
880 vector<Real> unshifted_quants;
881 for (int i = -region_size; i < region_size; i++)
882 for (int j = 0; j < num_base_quants; j++)
884 unshifted_quants.push_back (i + base_quants[j]);
887 for (vsize i = 0; i < unshifted_quants.size (); i++)
888 for (vsize j = 0; j < unshifted_quants.size (); j++)
890 Beam_configuration *c
891 = Beam_configuration::new_config (unquanted_y_,
892 Interval (unshifted_quants[i],
893 unshifted_quants[j]));
898 if (!quant_range_[d].contains (c->y[d]))
905 while (flip (&d) != LEFT);
907 scores->push_back (c);
912 void Beam_scoring_problem::one_scorer (Beam_configuration *config) const
915 switch (config->next_scorer_todo)
918 score_slope_ideal (config);
920 case SLOPE_DIRECTION:
921 score_slope_direction (config);
924 score_slope_musical (config);
927 score_forbidden_quants (config);
930 score_stem_lengths (config);
933 score_collisions (config);
935 case HORIZONTAL_INTER:
936 score_horizontal_inter_quants (config);
940 case ORIGINAL_DISTANCE:
944 config->next_scorer_todo++;
948 Beam_scoring_problem::force_score (SCM inspect_quants, const vector<Beam_configuration *> &configs) const
950 Drul_array<Real> ins = ly_scm2interval (inspect_quants);
952 Beam_configuration *best = NULL;
953 for (vsize i = 0; i < configs.size (); i++)
955 Real d = fabs (configs[i]->y[LEFT] - ins[LEFT]) + fabs (configs[i]->y[RIGHT] - ins[RIGHT]);
963 programming_error ("cannot find quant");
965 while (!best->done ())
972 Beam_scoring_problem::solve () const
974 vector<Beam_configuration *> configs;
975 generate_quants (&configs);
977 if (configs.empty ())
979 programming_error ("No viable beam quanting found. Using unquanted y value.");
983 if (to_boolean (beam_->get_property ("skip-quanting")))
986 Beam_configuration *best = NULL;
989 = to_boolean (beam_->layout ()->lookup_variable (ly_symbol2scm ("debug-beam-scoring")));
990 SCM inspect_quants = beam_->get_property ("inspect-quants");
991 if (scm_is_pair (inspect_quants))
994 best = force_score (inspect_quants, configs);
998 std::priority_queue < Beam_configuration *, std::vector<Beam_configuration *>,
999 Beam_configuration_less > queue;
1000 for (vsize i = 0; i < configs.size (); i++)
1001 queue.push (configs[i]);
1006 It would be neat if we generated new configurations on the
1007 fly, depending on the best complete score so far, eg.
1010 if (best->demerits < sqrt(queue.size())
1012 while (best->demerits > sqrt(queue.size()) {
1013 generate and insert new configuration
1017 that would allow us to do away with region_size altogether.
1021 best = queue.top ();
1031 Interval final_positions = best->y;
1033 #if DEBUG_BEAM_SCORING
1038 for (vsize i = 0; i < configs.size (); i++)
1040 if (configs[i]->done ())
1044 string card = best->score_card_ + to_string (" c%d/%d", completed, configs.size ());
1045 beam_->set_property ("annotation", ly_string2scm (card));
1049 junk_pointers (configs);
1050 if (align_broken_intos_)
1052 Interval normalized_endpoints = robust_scm2interval (beam_->get_property ("normalized-endpoints"), Interval (0, 1));
1053 Real y_length = final_positions[RIGHT] - final_positions[LEFT];
1055 final_positions[LEFT] += normalized_endpoints[LEFT] * y_length;
1056 final_positions[RIGHT] -= (1 - normalized_endpoints[RIGHT]) * y_length;
1059 return final_positions;
1063 Beam_scoring_problem::score_stem_lengths (Beam_configuration *config) const
1065 Real limit_penalty = parameters_.STEM_LENGTH_LIMIT_PENALTY;
1066 Drul_array<Real> score (0, 0);
1067 Drul_array<int> count (0, 0);
1069 for (vsize i = 0; i < stem_xpositions_.size (); i++)
1074 Real x = stem_xpositions_[i];
1077 ? config->y[RIGHT] * x / dx + config->y[LEFT] * (x_span_ - x) / dx
1078 : (config->y[RIGHT] + config->y[LEFT]) / 2;
1079 Real current_y = beam_y + base_lengths_[i];
1080 Real length_pen = parameters_.STEM_LENGTH_DEMERIT_FACTOR;
1082 Stem_info info = stem_infos_[i];
1083 Direction d = info.dir_;
1085 score[d] += limit_penalty * max (0.0, (d * (info.shortest_y_ - current_y)));
1087 Real ideal_diff = d * (current_y - info.ideal_y_);
1088 Real ideal_score = shrink_extra_weight (ideal_diff, 1.5);
1090 /* We introduce a power, to make the scoring strictly
1091 convex. Otherwise a symmetric knee beam (up/down/up/down)
1092 does not have an optimum in the middle. */
1094 ideal_score = pow (ideal_score, 1.1);
1096 score[d] += length_pen * ideal_score;
1100 /* Divide by number of stems, to make the measure scale-free. */
1103 score[d] /= max (count[d], 1);
1104 while (flip (&d) != DOWN);
1107 sometimes, two perfectly symmetric kneed beams will have the same score
1108 and can either be quanted up or down.
1110 we choose the quanting in the direction of the slope so that the first stem
1111 always seems longer, reaching to the second, rather than squashed.
1113 if (is_knee_ && count[LEFT] == count[RIGHT] && count[LEFT] == 1 && unquanted_y_.delta ())
1114 score[Direction (sign (unquanted_y_.delta ()))] += score[Direction (sign (unquanted_y_.delta ()))] < 1.0 ? 0.01 : 0.0;
1116 config->add (score[LEFT] + score[RIGHT], "L");
1120 Beam_scoring_problem::score_slope_direction (Beam_configuration *config) const
1122 Real dy = config->y.delta ();
1123 Real damped_dy = unquanted_y_.delta ();
1126 DAMPING_DIRECTION_PENALTY is a very harsh measure, while for
1127 complex beaming patterns, horizontal is often a good choice.
1129 TODO: find a way to incorporate the complexity of the beam in this
1132 if (sign (damped_dy) != sign (dy))
1136 if (fabs (damped_dy / x_span_) > parameters_.ROUND_TO_ZERO_SLOPE)
1137 dem += parameters_.DAMPING_DIRECTION_PENALTY;
1139 dem += parameters_.HINT_DIRECTION_PENALTY;
1142 dem += parameters_.DAMPING_DIRECTION_PENALTY;
1145 config->add (dem, "Sd");
1148 // Score for going against the direction of the musical pattern
1150 Beam_scoring_problem::score_slope_musical (Beam_configuration *config) const
1152 Real dy = config->y.delta ();
1153 Real dem = parameters_.MUSICAL_DIRECTION_FACTOR
1154 * max (0.0, (fabs (dy) - fabs (musical_dy_)));
1155 config->add (dem, "Sm");
1158 // Score deviation from calculated ideal slope.
1160 Beam_scoring_problem::score_slope_ideal (Beam_configuration *config) const
1162 Real dy = config->y.delta ();
1163 Real damped_dy = unquanted_y_.delta ();
1166 Real slope_penalty = parameters_.IDEAL_SLOPE_FACTOR;
1168 /* Xstaff beams tend to use extreme slopes to get short stems. We
1169 put in a penalty here. */
1171 slope_penalty *= 10;
1173 /* Huh, why would a too steep beam be better than a too flat one ? */
1174 dem += shrink_extra_weight (fabs (damped_dy) - fabs (dy), 1.5)
1177 config->add (dem, "Si");
1183 return x - floor (x);
1186 // TODO - there is some overlap with forbidden quants, but for
1187 // horizontal beams, it is much more serious to have stafflines
1188 // appearing in the wrong place, so we have a separate scorer.
1190 Beam_scoring_problem::score_horizontal_inter_quants (Beam_configuration *config) const
1192 if (config->y.delta () == 0.0
1193 && abs (config->y[LEFT]) < staff_radius_ * staff_space_)
1195 Real yshift = config->y[LEFT] - 0.5 * staff_space_;
1196 if (fabs (my_round (yshift) - yshift) < 0.01 * staff_space_)
1197 config->add (parameters_.HORIZONTAL_INTER_QUANT_PENALTY, "H");
1202 TODO: The fixed value SECONDARY_BEAM_DEMERIT is probably flawed:
1203 because for 32nd and 64th beams the forbidden quants are relatively
1204 more important than stem lengths.
1207 Beam_scoring_problem::score_forbidden_quants (Beam_configuration *config) const
1209 Real dy = config->y.delta ();
1211 Real extra_demerit = parameters_.SECONDARY_BEAM_DEMERIT
1212 / max (edge_beam_counts_[LEFT], edge_beam_counts_[RIGHT]);
1216 Real eps = parameters_.BEAM_EPS;
1220 for (int j = 1; j <= edge_beam_counts_[d]; j++)
1222 Direction stem_dir = edge_dirs_[d];
1225 The 2.2 factor is to provide a little leniency for
1226 borderline cases. If we do 2.0, then the upper outer line
1227 will be in the gap of the (2, sit) quant, leading to a
1230 Real gap1 = config->y[d] - stem_dir * ((j - 1) * beam_translation_ + beam_thickness_ / 2 - line_thickness_ / 2.2);
1231 Real gap2 = config->y[d] - stem_dir * (j * beam_translation_ - beam_thickness_ / 2 + line_thickness_ / 2.2);
1234 gap.add_point (gap1);
1235 gap.add_point (gap2);
1237 for (Real k = -staff_radius_;
1238 k <= staff_radius_ + eps; k += 1.0)
1239 if (gap.contains (k))
1241 Real dist = min (fabs (gap[UP] - k), fabs (gap[DOWN] - k));
1244 this parameter is tuned to grace-stem-length.ly
1245 retuned from 0.40 to 0.39 by MS because of slight increases
1246 in gap.length () resulting from measuring beams at real ends
1247 instead of from the middle of stems.
1250 This function needs better comments so we know what is forbidden
1253 Real fixed_demerit = 0.39;
1255 dem += extra_demerit
1257 + (1 - fixed_demerit) * (dist / gap.length ()) * 2);
1261 while ((flip (&d)) != LEFT);
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;
1273 if (edge_beam_counts_[d] >= 2
1274 && fabs (config->y[d] - edge_dirs_[d] * beam_translation_) < staff_radius_ + inter)
1276 // TODO up/down symmetry.
1277 if (edge_dirs_[d] == UP && dy <= eps
1278 && fabs (my_modf (config->y[d]) - sit) < eps)
1279 dem += extra_demerit;
1281 if (edge_dirs_[d] == DOWN && dy >= eps
1282 && fabs (my_modf (config->y[d]) - hang) < eps)
1283 dem += extra_demerit;
1286 if (edge_beam_counts_[d] >= 3
1287 && fabs (config->y[d] - 2 * edge_dirs_[d] * beam_translation_) < staff_radius_ + inter)
1289 // TODO up/down symmetry.
1290 if (edge_dirs_[d] == UP && dy <= eps
1291 && fabs (my_modf (config->y[d]) - straddle) < eps)
1292 dem += extra_demerit;
1294 if (edge_dirs_[d] == DOWN && dy >= eps
1295 && fabs (my_modf (config->y[d]) - straddle) < eps)
1296 dem += extra_demerit;
1299 while (flip (&d) != LEFT);
1302 config->add (dem, "F");
1306 Beam_scoring_problem::score_collisions (Beam_configuration *config) const
1308 Real demerits = 0.0;
1309 for (vsize i = 0; i < collisions_.size (); i++)
1311 Interval collision_y = collisions_[i].y_;
1312 Real x = collisions_[i].x_;
1314 Real center_beam_y = y_at (x, config);
1315 Interval beam_y = center_beam_y + collisions_[i].beam_y_;
1317 Real dist = infinity_f;
1318 if (!intersection (beam_y, collision_y).is_empty ())
1321 dist = min (beam_y.distance (collision_y[DOWN]),
1322 beam_y.distance (collision_y[UP]));
1325 = max (parameters_.COLLISION_PADDING - dist, 0.0)
1326 / parameters_.COLLISION_PADDING;
1328 += collisions_[i].base_penalty_ *
1329 pow (scale_free, 3) * parameters_.COLLISION_PENALTY;
1332 config->add (demerits, "C");