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 "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);
286 if (is_normal_.back ())
288 if (beam_width[LEFT] == -1.0)
289 beam_width[LEFT] = stem_xpositions_.back ();
290 beam_width[RIGHT] = stem_xpositions_.back ();
294 edge_dirs_ = Drul_array<Direction> (CENTER, CENTER);
295 normal_stem_count_ += Beam::normal_stem_count (beams[i]);
296 if (normal_stem_count_)
297 edge_dirs_ = Drul_array<Direction> (stem_infos_[0].dir_,
298 stem_infos_.back ().dir_);
300 is_xstaff_ = Align_interface::has_interface (common[Y_AXIS]);
301 is_knee_ |= dirs_found[DOWN] && dirs_found[UP];
303 staff_radius_ = Staff_symbol_referencer::staff_radius (beams[i]);
304 edge_beam_counts_ = Drul_array<int>
305 (Stem::beam_multiplicity (stems[0]).length () + 1,
306 Stem::beam_multiplicity (stems.back ()).length () + 1);
308 // TODO - why are we dividing by staff_space_?
309 beam_translation_ = Beam::get_beam_translation (beams[i]) / staff_space_;
314 quant_range_[d].set_full ();
318 Real stem_offset = edge_stems[d]->relative_coordinate (common[Y_AXIS], Y_AXIS)
319 - beams[i]->relative_coordinate (common[Y_AXIS], Y_AXIS);
320 Interval heads = Stem::head_positions (edge_stems[d]) * 0.5 * staff_space_;
322 Direction ed = edge_dirs_[d];
323 heads.widen (0.5 * staff_space_
324 + (edge_beam_counts_[d] - 1) * beam_translation_ + beam_thickness_ * .5);
325 quant_range_[d][-ed] = heads[ed] + stem_offset;
327 while (flip (&d) != LEFT);
329 segments_ = Beam::get_beam_segments (beams[i]);
330 vector_sort (segments_, beam_segment_less);
331 for (vsize j = 0; j < segments_.size (); j++)
332 segments_[j].horizontal_ += (x_span_ - x_pos[LEFT]);
334 set<Grob *> colliding_stems;
335 for (vsize j = 0; j < collisions.size (); j++)
337 if (!collisions[j]->is_live ())
340 if (Beam::has_interface (collisions[j]) && Beam::is_cross_staff (collisions[j]))
344 for (Axis a = X_AXIS; a < NO_AXES; incr (a))
345 b[a] = collisions[j]->extent (common[a], a);
347 if (b[X_AXIS][RIGHT] < x_pos[LEFT] || b[X_AXIS][LEFT] > x_pos[RIGHT])
349 if (b[X_AXIS].is_empty () || b[Y_AXIS].is_empty ())
352 b[X_AXIS] += (x_span_ - x_pos[LEFT]);
353 Real width = b[X_AXIS].length ();
354 Real width_factor = sqrt (width / staff_space_);
358 add_collision (b[X_AXIS][d], b[Y_AXIS], width_factor);
359 while (flip (&d) != LEFT);
361 Grob *stem = unsmob_grob (collisions[j]->get_object ("stem"));
362 if (stem && Stem::has_interface (stem) && Stem::is_normal_stem (stem))
364 colliding_stems.insert (stem);
368 for (set<Grob *>::const_iterator it (colliding_stems.begin ()); it != colliding_stems.end (); it++)
371 Real x = (s->extent (common[X_AXIS], X_AXIS) - x_pos[LEFT] + x_span_).center ();
373 Direction stem_dir = get_grob_direction (*it);
376 y[-stem_dir] = Stem::chord_start_y (*it) + (*it)->relative_coordinate (common[Y_AXIS], Y_AXIS)
377 - beams[i]->relative_coordinate (common[Y_AXIS], Y_AXIS);
379 Real factor = parameters_.STEM_COLLISION_FACTOR;
380 if (!unsmob_grob (s->get_object ("beam")))
382 add_collision (x, y, factor);
384 x_span_ += beams[i]->spanner_length ();
388 Beam_scoring_problem::Beam_scoring_problem (Grob *me, Drul_array<Real> ys, bool align_broken_intos)
390 beam_ = dynamic_cast<Spanner *> (me);
392 align_broken_intos_ = align_broken_intos;
394 parameters_.fill (me);
395 init_instance_variables (me, ys, align_broken_intos);
396 if (do_initial_slope_calculations_)
398 least_squares_positions ();
400 shift_region_to_valid ();
404 // Assuming V is not empty, pick a 'reasonable' point inside V.
406 point_in_interval (Interval v, Real dist)
410 else if (isinf (v[UP]))
411 return v[DOWN] + dist;
416 /* Set stem's shorten property if unset.
419 take some y-position (chord/beam/nearest?) into account
420 scmify forced-fraction
422 This is done in beam because the shorten has to be uniform over the
427 set_minimum_dy (Grob *me, Real *dy)
432 If dy is smaller than the smallest quant, we
433 get absurd direction-sign penalties.
436 Real ss = Staff_symbol_referencer::staff_space (me);
437 Real beam_thickness = Beam::get_beam_thickness (me) / ss;
438 Real slt = Staff_symbol_referencer::line_thickness (me) / ss;
439 Real sit = (beam_thickness - slt) / 2;
441 Real hang = 1.0 - (beam_thickness - slt) / 2;
443 *dy = sign (*dy) * max (fabs (*dy),
444 min (min (sit, inter), hang));
449 Beam_scoring_problem::no_visible_stem_positions ()
451 if (!head_positions_.size ())
453 unquanted_y_ = Interval (0, 0);
457 Interval head_positions;
459 for (vsize i = 0; i < head_positions_.size (); i++)
461 head_positions.unite (head_positions_[i]);
462 multiplicity.unite (beam_multiplicity_[i]);
465 Direction dir = get_grob_direction (beam_);
468 programming_error ("The beam should have a direction by now.");
470 Real y = head_positions.linear_combination (dir)
472 + dir * beam_translation_ * (multiplicity.length () + 1);
474 unquanted_y_ = Interval (y, y);
478 Beam_scoring_problem::first_normal_index ()
480 for (vsize i = 0; i < is_normal_.size (); i++)
484 beam_->programming_error ("No normal stems, but asking for first normal stem index.");
489 Beam_scoring_problem::last_normal_index ()
491 for (vsize i = is_normal_.size (); i--;)
495 beam_->programming_error ("No normal stems, but asking for first normal stem index.");
500 Beam_scoring_problem::least_squares_positions ()
502 if (!normal_stem_count_)
504 no_visible_stem_positions ();
508 if (stem_infos_.size () < 1)
511 vsize fnx = first_normal_index ();
512 vsize lnx = last_normal_index ();
514 Interval ideal (stem_infos_[fnx].ideal_y_ + stem_ypositions_[fnx],
515 stem_infos_[lnx].ideal_y_ + stem_ypositions_[lnx]);
523 Interval chord (chord_start_y_[0],
524 chord_start_y_.back ());
526 /* Simple beams (2 stems) on middle line should be allowed to be
529 However, if both stems reach middle line,
530 ideal[LEFT] == ideal[RIGHT] and ideal.delta () == 0.
532 For that case, we apply artificial slope */
533 if (!ideal[LEFT] && chord.delta () && stem_infos_.size () == 2)
536 Direction d = (Direction) (sign (chord.delta ()) * UP);
537 unquanted_y_[d] = Beam::get_beam_thickness (beam_) / 2;
538 unquanted_y_[-d] = -unquanted_y_[d];
541 unquanted_y_ = ideal;
543 ldy = unquanted_y_[RIGHT] - unquanted_y_[LEFT];
547 vector<Offset> ideals;
548 for (vsize i = 0; i < stem_infos_.size (); i++)
550 ideals.push_back (Offset (stem_xpositions_[i],
551 stem_infos_[i].ideal_y_
552 + stem_ypositions_[i]));
554 minimise_least_squares (&slope, &y, ideals);
556 dy = slope * x_span_;
558 set_minimum_dy (beam_, &dy);
561 unquanted_y_ = Interval (y, (y + dy));
565 beam_->set_property ("least-squares-dy", scm_from_double (musical_dy_));
569 Determine whether a beam is concave.
571 A beam is concave when the middle notes get closer to the
572 beam than the left and right edge notes.
574 This is determined in two ways: by looking at the positions of the
575 middle notes, or by looking at the deviation of the inside notes
576 compared to the line connecting first and last.
578 The tricky thing is what to do with beams with chords. There are no
579 real guidelines in this case.
583 is_concave_single_notes (vector<int> const &positions, Direction beam_dir)
586 covering.add_point (positions[0]);
587 covering.add_point (positions.back ());
591 bool concave = false;
594 notes above and below the interval covered by 1st and last note.
596 for (vsize i = 1; i + 1 < positions.size (); i++)
598 above = above || (positions[i] > covering[UP]);
599 below = below || (positions[i] < covering[DOWN]);
602 concave = concave || (above && below);
604 A note as close or closer to the beam than begin and end, but the
605 note is reached in the opposite direction as the last-first dy
607 int dy = positions.back () - positions[0];
608 int closest = max (beam_dir * positions.back (), beam_dir * positions[0]);
609 for (vsize i = 2; !concave && i + 1 < positions.size (); i++)
611 int inner_dy = positions[i] - positions[i - 1];
612 if (sign (inner_dy) != sign (dy)
613 && (beam_dir * positions[i] >= closest
614 || beam_dir * positions[i - 1] >= closest))
618 bool all_closer = true;
619 for (vsize i = 1; all_closer && i + 1 < positions.size (); i++)
621 all_closer = all_closer
622 && (beam_dir * positions[i] > closest);
625 concave = concave || all_closer;
630 calc_positions_concaveness (vector<int> const &positions, Direction beam_dir)
632 Real dy = positions.back () - positions[0];
633 Real slope = dy / Real (positions.size () - 1);
634 Real concaveness = 0.0;
635 for (vsize i = 1; i + 1 < positions.size (); i++)
637 Real line_y = slope * i + positions[0];
639 concaveness += max (beam_dir * (positions[i] - line_y), 0.0);
642 concaveness /= positions.size ();
645 Normalize. For dy = 0, the slope ends up as 0 anyway, so the
646 scaling of concaveness doesn't matter much.
649 concaveness /= fabs (dy);
654 Beam_scoring_problem::calc_concaveness ()
656 SCM conc = beam_->get_property ("concaveness");
657 if (scm_is_number (conc))
658 return scm_to_double (conc);
663 Direction beam_dir = CENTER;
664 for (vsize i = is_normal_.size (); i--;)
665 if (is_normal_[i] && stem_infos_[i].dir_)
666 beam_dir = stem_infos_[i].dir_;
668 if (normal_stem_count_ <= 2)
671 vector<int> close_positions;
672 vector<int> far_positions;
673 for (vsize i = 0; i < is_normal_.size (); i++)
677 For chords, we take the note head that is closest to the beam.
679 Hmmm.. wait, for the beams in the last measure of morgenlied,
680 this doesn't look so good. Let's try the heads farthest from
684 close_positions.push_back ((int) rint (head_positions_[i][beam_dir]));
685 far_positions.push_back ((int) rint (head_positions_[i][-beam_dir]));
688 Real concaveness = 0.0;
690 if (is_concave_single_notes (beam_dir == UP ? close_positions : far_positions, beam_dir))
696 concaveness = (calc_positions_concaveness (far_positions, beam_dir)
697 + calc_positions_concaveness (close_positions, beam_dir)) / 2;
704 Beam_scoring_problem::slope_damping ()
706 if (normal_stem_count_ <= 1)
709 SCM s = beam_->get_property ("damping");
710 Real damping = scm_to_double (s);
711 Real concaveness = calc_concaveness ();
712 if (concaveness >= 10000)
714 unquanted_y_[LEFT] = unquanted_y_[RIGHT];
721 Real dy = unquanted_y_[RIGHT] - unquanted_y_[LEFT];
723 Real slope = dy && x_span_ ? dy / x_span_ : 0;
725 slope = 0.6 * tanh (slope) / (damping + concaveness);
727 Real damped_dy = slope * x_span_;
729 set_minimum_dy (beam_, &damped_dy);
731 unquanted_y_[LEFT] += (dy - damped_dy) / 2;
732 unquanted_y_[RIGHT] -= (dy - damped_dy) / 2;
737 Beam_scoring_problem::shift_region_to_valid ()
739 if (!normal_stem_count_)
742 Real beam_dy = unquanted_y_[RIGHT] - unquanted_y_[LEFT];
743 Real slope = x_span_ ? beam_dy / x_span_ : 0.0;
746 Shift the positions so that we have a chance of finding good
747 quants (i.e. no short stem failures.)
749 Interval feasible_left_point;
750 feasible_left_point.set_full ();
752 for (vsize i = 0; i < stem_infos_.size (); i++)
754 // TODO - check for invisible here...
756 = stem_infos_[i].shortest_y_
757 - slope * stem_xpositions_ [i];
760 left_y is now relative to the stem S. We want relative to
761 ourselves, so translate:
763 left_y += stem_ypositions_[i];
766 flp[-stem_infos_[i].dir_] = left_y;
768 feasible_left_point.intersect (flp);
771 vector<Grob *> filtered;
773 We only update these for objects that are too large for quanting
774 to find a workaround. Typically, these are notes with
775 stems, and timesig/keysig/clef, which take out the entire area
776 inside the staff as feasible.
778 The code below disregards the thickness and multiplicity of the
779 beam. This should not be a problem, as the beam quanting will
780 take care of computing the impact those exactly.
782 Real min_y_size = 2.0;
784 // A list of intervals into which beams may not fall
785 vector<Interval> forbidden_intervals;
787 for (vsize i = 0; i < collisions_.size (); i++)
789 if (collisions_[i].x_ < 0 || collisions_[i].x_ > x_span_)
792 if (collisions_[i].y_.length () < min_y_size)
798 Real dy = slope * collisions_[i].x_;
804 Real left_y = collisions_[i].y_[yd] - dy;
805 disallowed[yd] = left_y;
807 while (flip (&yd) != DOWN);
809 forbidden_intervals.push_back (disallowed);
811 while (flip (&d) != LEFT);
814 vector_sort (forbidden_intervals, Interval::left_less);
815 Real beam_left_y = unquanted_y_[LEFT];
816 Interval feasible_beam_placements (beam_left_y, beam_left_y);
818 Interval_minefield minefield (feasible_beam_placements, 0.0);
819 for (vsize i = 0; i < forbidden_intervals.size (); i++)
820 minefield.add_forbidden_interval (forbidden_intervals[i]);
822 feasible_beam_placements = minefield.feasible_placements ();
824 // if the beam placement falls out of the feasible region, we push it
825 // to infinity so that it can never be a feasible candidate below
829 if (!feasible_left_point.contains (feasible_beam_placements[d]))
830 feasible_beam_placements[d] = d * infinity_f;
832 while (flip (&d) != DOWN);
834 if ((feasible_beam_placements[UP] == infinity_f && feasible_beam_placements[DOWN] == -infinity_f) && !feasible_left_point.is_empty ())
836 // We are somewhat screwed: we have a collision, but at least
837 // there is a way to satisfy stem length constraints.
838 beam_left_y = point_in_interval (feasible_left_point, 2.0);
840 else if (!feasible_left_point.is_empty ())
842 // Only one of them offers is feasible solution. Pick that one.
843 if (abs (beam_left_y - feasible_beam_placements[DOWN]) > abs (beam_left_y - feasible_beam_placements[UP]))
844 beam_left_y = feasible_beam_placements[UP];
846 beam_left_y = feasible_beam_placements[DOWN];
850 // We are completely screwed.
851 beam_->warning (_ ("no viable initial configuration found: may not find good beam slope"));
854 unquanted_y_ = Drul_array<Real> (beam_left_y, (beam_left_y + beam_dy));
858 Beam_scoring_problem::generate_quants (vector<Beam_configuration *> *scores) const
860 int region_size = (int) parameters_.REGION_SIZE;
862 // Knees and collisions are harder, lets try some more possibilities
865 if (collisions_.size ())
869 Real sit = (beam_thickness_ - line_thickness_) / 2;
871 Real hang = 1.0 - (beam_thickness_ - line_thickness_) / 2;
872 Real base_quants [] = {straddle, sit, inter, hang};
873 int num_base_quants = int (sizeof (base_quants) / sizeof (Real));
876 Asymetry ? should run to <= region_size ?
878 vector<Real> unshifted_quants;
879 for (int i = -region_size; i < region_size; i++)
880 for (int j = 0; j < num_base_quants; j++)
882 unshifted_quants.push_back (i + base_quants[j]);
885 for (vsize i = 0; i < unshifted_quants.size (); i++)
886 for (vsize j = 0; j < unshifted_quants.size (); j++)
888 Beam_configuration *c
889 = Beam_configuration::new_config (unquanted_y_,
890 Interval (unshifted_quants[i],
891 unshifted_quants[j]));
896 if (!quant_range_[d].contains (c->y[d]))
903 while (flip (&d) != LEFT);
905 scores->push_back (c);
910 void Beam_scoring_problem::one_scorer (Beam_configuration *config) const
913 switch (config->next_scorer_todo)
916 score_slope_ideal (config);
918 case SLOPE_DIRECTION:
919 score_slope_direction (config);
922 score_slope_musical (config);
925 score_forbidden_quants (config);
928 score_stem_lengths (config);
931 score_collisions (config);
933 case HORIZONTAL_INTER:
934 score_horizontal_inter_quants (config);
938 case ORIGINAL_DISTANCE:
942 config->next_scorer_todo++;
946 Beam_scoring_problem::force_score (SCM inspect_quants, const vector<Beam_configuration *> &configs) const
948 Drul_array<Real> ins = ly_scm2interval (inspect_quants);
950 Beam_configuration *best = NULL;
951 for (vsize i = 0; i < configs.size (); i++)
953 Real d = fabs (configs[i]->y[LEFT] - ins[LEFT]) + fabs (configs[i]->y[RIGHT] - ins[RIGHT]);
961 programming_error ("cannot find quant");
963 while (!best->done ())
970 Beam_scoring_problem::solve () const
972 vector<Beam_configuration *> configs;
973 generate_quants (&configs);
975 if (configs.empty ())
977 programming_error ("No viable beam quanting found. Using unquanted y value.");
981 if (to_boolean (beam_->get_property ("skip-quanting")))
984 Beam_configuration *best = NULL;
987 = to_boolean (beam_->layout ()->lookup_variable (ly_symbol2scm ("debug-beam-scoring")));
988 SCM inspect_quants = beam_->get_property ("inspect-quants");
989 if (scm_is_pair (inspect_quants))
992 best = force_score (inspect_quants, configs);
996 std::priority_queue < Beam_configuration *, std::vector<Beam_configuration *>,
997 Beam_configuration_less > queue;
998 for (vsize i = 0; i < configs.size (); i++)
999 queue.push (configs[i]);
1004 It would be neat if we generated new configurations on the
1005 fly, depending on the best complete score so far, eg.
1008 if (best->demerits < sqrt(queue.size())
1010 while (best->demerits > sqrt(queue.size()) {
1011 generate and insert new configuration
1015 that would allow us to do away with region_size altogether.
1019 best = queue.top ();
1029 Interval final_positions = best->y;
1031 #if DEBUG_BEAM_SCORING
1036 for (vsize i = 0; i < configs.size (); i++)
1038 if (configs[i]->done ())
1042 string card = best->score_card_ + to_string (" c%d/%d", completed, configs.size ());
1043 beam_->set_property ("annotation", ly_string2scm (card));
1047 junk_pointers (configs);
1048 if (align_broken_intos_)
1050 Interval normalized_endpoints = robust_scm2interval (beam_->get_property ("normalized-endpoints"), Interval (0, 1));
1051 Real y_length = final_positions[RIGHT] - final_positions[LEFT];
1053 final_positions[LEFT] += normalized_endpoints[LEFT] * y_length;
1054 final_positions[RIGHT] -= (1 - normalized_endpoints[RIGHT]) * y_length;
1057 return final_positions;
1061 Beam_scoring_problem::score_stem_lengths (Beam_configuration *config) const
1063 Real limit_penalty = parameters_.STEM_LENGTH_LIMIT_PENALTY;
1064 Drul_array<Real> score (0, 0);
1065 Drul_array<int> count (0, 0);
1067 for (vsize i = 0; i < stem_xpositions_.size (); i++)
1072 Real x = stem_xpositions_[i];
1075 ? config->y[RIGHT] * x / dx + config->y[LEFT] * (x_span_ - x) / dx
1076 : (config->y[RIGHT] + config->y[LEFT]) / 2;
1077 Real current_y = beam_y + base_lengths_[i];
1078 Real length_pen = parameters_.STEM_LENGTH_DEMERIT_FACTOR;
1080 Stem_info info = stem_infos_[i];
1081 Direction d = info.dir_;
1083 score[d] += limit_penalty * max (0.0, (d * (info.shortest_y_ - current_y)));
1085 Real ideal_diff = d * (current_y - info.ideal_y_);
1086 Real ideal_score = shrink_extra_weight (ideal_diff, 1.5);
1088 /* We introduce a power, to make the scoring strictly
1089 convex. Otherwise a symmetric knee beam (up/down/up/down)
1090 does not have an optimum in the middle. */
1092 ideal_score = pow (ideal_score, 1.1);
1094 score[d] += length_pen * ideal_score;
1098 /* Divide by number of stems, to make the measure scale-free. */
1101 score[d] /= max (count[d], 1);
1102 while (flip (&d) != DOWN);
1105 sometimes, two perfectly symmetric kneed beams will have the same score
1106 and can either be quanted up or down.
1108 we choose the quanting in the direction of the slope so that the first stem
1109 always seems longer, reaching to the second, rather than squashed.
1111 if (is_knee_ && count[LEFT] == count[RIGHT] && count[LEFT] == 1 && unquanted_y_.delta ())
1112 score[Direction (sign (unquanted_y_.delta ()))] += score[Direction (sign (unquanted_y_.delta ()))] < 1.0 ? 0.01 : 0.0;
1114 config->add (score[LEFT] + score[RIGHT], "L");
1118 Beam_scoring_problem::score_slope_direction (Beam_configuration *config) const
1120 Real dy = config->y.delta ();
1121 Real damped_dy = unquanted_y_.delta ();
1124 DAMPING_DIRECTION_PENALTY is a very harsh measure, while for
1125 complex beaming patterns, horizontal is often a good choice.
1127 TODO: find a way to incorporate the complexity of the beam in this
1130 if (sign (damped_dy) != sign (dy))
1134 if (fabs (damped_dy / x_span_) > parameters_.ROUND_TO_ZERO_SLOPE)
1135 dem += parameters_.DAMPING_DIRECTION_PENALTY;
1137 dem += parameters_.HINT_DIRECTION_PENALTY;
1140 dem += parameters_.DAMPING_DIRECTION_PENALTY;
1143 config->add (dem, "Sd");
1146 // Score for going against the direction of the musical pattern
1148 Beam_scoring_problem::score_slope_musical (Beam_configuration *config) const
1150 Real dy = config->y.delta ();
1151 Real dem = parameters_.MUSICAL_DIRECTION_FACTOR
1152 * max (0.0, (fabs (dy) - fabs (musical_dy_)));
1153 config->add (dem, "Sm");
1156 // Score deviation from calculated ideal slope.
1158 Beam_scoring_problem::score_slope_ideal (Beam_configuration *config) const
1160 Real dy = config->y.delta ();
1161 Real damped_dy = unquanted_y_.delta ();
1164 Real slope_penalty = parameters_.IDEAL_SLOPE_FACTOR;
1166 /* Xstaff beams tend to use extreme slopes to get short stems. We
1167 put in a penalty here. */
1169 slope_penalty *= 10;
1171 /* Huh, why would a too steep beam be better than a too flat one ? */
1172 dem += shrink_extra_weight (fabs (damped_dy) - fabs (dy), 1.5)
1175 config->add (dem, "Si");
1181 return x - floor (x);
1184 // TODO - there is some overlap with forbidden quants, but for
1185 // horizontal beams, it is much more serious to have stafflines
1186 // appearing in the wrong place, so we have a separate scorer.
1188 Beam_scoring_problem::score_horizontal_inter_quants (Beam_configuration *config) const
1190 if (config->y.delta () == 0.0
1191 && abs (config->y[LEFT]) < staff_radius_ * staff_space_)
1193 Real yshift = config->y[LEFT] - 0.5 * staff_space_;
1194 if (fabs (my_round (yshift) - yshift) < 0.01 * staff_space_)
1195 config->add (parameters_.HORIZONTAL_INTER_QUANT_PENALTY, "H");
1200 TODO: The fixed value SECONDARY_BEAM_DEMERIT is probably flawed:
1201 because for 32nd and 64th beams the forbidden quants are relatively
1202 more important than stem lengths.
1205 Beam_scoring_problem::score_forbidden_quants (Beam_configuration *config) const
1207 Real dy = config->y.delta ();
1209 Real extra_demerit = parameters_.SECONDARY_BEAM_DEMERIT
1210 / max (edge_beam_counts_[LEFT], edge_beam_counts_[RIGHT]);
1214 Real eps = parameters_.BEAM_EPS;
1218 for (int j = 1; j <= edge_beam_counts_[d]; j++)
1220 Direction stem_dir = edge_dirs_[d];
1223 The 2.2 factor is to provide a little leniency for
1224 borderline cases. If we do 2.0, then the upper outer line
1225 will be in the gap of the (2, sit) quant, leading to a
1228 Real gap1 = config->y[d] - stem_dir * ((j - 1) * beam_translation_ + beam_thickness_ / 2 - line_thickness_ / 2.2);
1229 Real gap2 = config->y[d] - stem_dir * (j * beam_translation_ - beam_thickness_ / 2 + line_thickness_ / 2.2);
1232 gap.add_point (gap1);
1233 gap.add_point (gap2);
1235 for (Real k = -staff_radius_;
1236 k <= staff_radius_ + eps; k += 1.0)
1237 if (gap.contains (k))
1239 Real dist = min (fabs (gap[UP] - k), fabs (gap[DOWN] - k));
1242 this parameter is tuned to grace-stem-length.ly
1243 retuned from 0.40 to 0.39 by MS because of slight increases
1244 in gap.length () resulting from measuring beams at real ends
1245 instead of from the middle of stems.
1248 This function needs better comments so we know what is forbidden
1251 Real fixed_demerit = 0.39;
1253 dem += extra_demerit
1255 + (1 - fixed_demerit) * (dist / gap.length ()) * 2);
1259 while ((flip (&d)) != LEFT);
1261 if (max (edge_beam_counts_[LEFT], edge_beam_counts_[RIGHT]) >= 2)
1263 Real straddle = 0.0;
1264 Real sit = (beam_thickness_ - line_thickness_) / 2;
1266 Real hang = 1.0 - (beam_thickness_ - line_thickness_) / 2;
1271 if (edge_beam_counts_[d] >= 2
1272 && fabs (config->y[d] - edge_dirs_[d] * beam_translation_) < staff_radius_ + inter)
1274 // TODO up/down symmetry.
1275 if (edge_dirs_[d] == UP && dy <= eps
1276 && fabs (my_modf (config->y[d]) - sit) < eps)
1277 dem += extra_demerit;
1279 if (edge_dirs_[d] == DOWN && dy >= eps
1280 && fabs (my_modf (config->y[d]) - hang) < eps)
1281 dem += extra_demerit;
1284 if (edge_beam_counts_[d] >= 3
1285 && fabs (config->y[d] - 2 * edge_dirs_[d] * beam_translation_) < staff_radius_ + inter)
1287 // TODO up/down symmetry.
1288 if (edge_dirs_[d] == UP && dy <= eps
1289 && fabs (my_modf (config->y[d]) - straddle) < eps)
1290 dem += extra_demerit;
1292 if (edge_dirs_[d] == DOWN && dy >= eps
1293 && fabs (my_modf (config->y[d]) - straddle) < eps)
1294 dem += extra_demerit;
1297 while (flip (&d) != LEFT);
1300 config->add (dem, "F");
1304 Beam_scoring_problem::score_collisions (Beam_configuration *config) const
1306 Real demerits = 0.0;
1307 for (vsize i = 0; i < collisions_.size (); i++)
1309 Interval collision_y = collisions_[i].y_;
1310 Real x = collisions_[i].x_;
1312 Real center_beam_y = y_at (x, config);
1313 Interval beam_y = center_beam_y + collisions_[i].beam_y_;
1315 Real dist = infinity_f;
1316 if (!intersection (beam_y, collision_y).is_empty ())
1319 dist = min (beam_y.distance (collision_y[DOWN]),
1320 beam_y.distance (collision_y[UP]));
1323 = max (parameters_.COLLISION_PADDING - dist, 0.0)
1324 / parameters_.COLLISION_PADDING;
1326 += collisions_[i].base_penalty_ *
1327 pow (scale_free, 3) * parameters_.COLLISION_PENALTY;
1330 config->add (demerits, "C");