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_instance_variables (Grob *me, Drul_array<Real> ys, bool align_broken_intos)
186 beam_ = dynamic_cast<Spanner *> (me);
190 If 'ys' are finite, use them as starting points for y-positions of the
191 ends of the beam, instead of the best-fit through the natural ends of
192 the stems. Otherwise, we want to do initial slope calculations.
194 do_initial_slope_calculations_ = false;
197 do_initial_slope_calculations_ |= isinf (unquanted_y_[d]) || isnan (unquanted_y_[d]);
198 while (flip (&d) != LEFT);
201 Calculations are relative to a unit-scaled staff, i.e. the quants are
202 divided by the current staff_space_.
204 staff_space_ = Staff_symbol_referencer::staff_space (beam_);
205 beam_thickness_ = Beam::get_beam_thickness (beam_) / staff_space_;
206 line_thickness_ = Staff_symbol_referencer::line_thickness (beam_) / staff_space_;
208 // This is the least-squares DY, corrected for concave beams.
209 musical_dy_ = robust_scm2double (beam_->get_property ("least-squares-dy"), 0);
211 vector<Spanner *> beams;
212 align_broken_intos_ = align_broken_intos;
213 if (align_broken_intos_)
215 Spanner *orig = dynamic_cast<Spanner *> (beam_->original ());
217 align_broken_intos_ = false;
218 else if (!orig->broken_intos_.size ())
219 align_broken_intos_ = false;
221 beams.insert (beams.end (), orig->broken_intos_.begin (), orig->broken_intos_.end ());
223 if (!align_broken_intos_)
224 beams.push_back (beam_);
227 x_span_ is a single scalar, cumulatively summing the length of all the
228 segments the parent beam was broken-into.
232 normal_stem_count_ = 0;
233 for (vsize i = 0; i < beams.size (); i++)
235 extract_grob_set (beams[i], "stems", stems);
236 extract_grob_set (beams[i], "covered-grobs", fake_collisions);
237 vector<Grob *> collisions;
239 for (vsize j = 0; j < fake_collisions.size (); j++)
240 if (fake_collisions[j]->get_system () == beams[i]->get_system ())
241 collisions.push_back (fake_collisions[j]);
244 for (int a = 2; a--;)
245 common[a] = common_refpoint_of_array (stems, beams[i], Axis (a));
249 common[X_AXIS] = beams[i]->get_bound (d)->common_refpoint (common[X_AXIS], X_AXIS);
250 while (flip (&d) != LEFT);
252 // positions of the endpoints of this beam segment, including any overhangs
253 const Interval x_pos = robust_scm2interval (beams[i]->get_property ("X-positions"),
254 Interval (0.0, 0.0));
256 Drul_array<Grob *> edge_stems (Beam::first_normal_stem (beams[i]),
257 Beam::last_normal_stem (beams[i]));
259 Drul_array<bool> dirs_found (0, 0);
261 Real my_y = beams[i]->relative_coordinate (common[Y_AXIS], Y_AXIS);
263 Interval beam_width (-1.0, -1.0);
264 for (vsize j = 0; j < stems.size (); j++)
267 beam_multiplicity_.push_back (Stem::beam_multiplicity (stems[j]));
268 head_positions_.push_back (Stem::head_positions (stems[j]));
269 is_normal_.push_back (Stem::is_normal_stem (stems[j]));
271 Stem_info si (Stem::get_stem_info (s));
272 si.scale (1 / staff_space_);
273 stem_infos_.push_back (si);
274 chord_start_y_.push_back (Stem::chord_start_y (s));
275 dirs_found[si.dir_] = true;
277 bool f = to_boolean (s->get_property ("french-beaming"))
278 && s != edge_stems[LEFT] && s != edge_stems[RIGHT];
280 Real y = Beam::calc_stem_y (beams[i], s, common, x_pos[LEFT], x_pos[RIGHT], CENTER,
282 base_lengths_.push_back (y / staff_space_);
283 stem_xpositions_.push_back (s->relative_coordinate (common[X_AXIS], X_AXIS) - x_pos[LEFT] + x_span_);
284 stem_ypositions_.push_back (s->relative_coordinate (common[Y_AXIS], Y_AXIS) - my_y);
285 if (is_normal_.back ())
287 if (beam_width[LEFT] == -1.0)
288 beam_width[LEFT] = stem_xpositions_.back ();
289 beam_width[RIGHT] = stem_xpositions_.back ();
293 edge_dirs_ = Drul_array<Direction> (CENTER, CENTER);
294 normal_stem_count_ += Beam::normal_stem_count (beams[i]);
295 if (normal_stem_count_)
296 edge_dirs_ = Drul_array<Direction> (stem_infos_[0].dir_,
297 stem_infos_.back ().dir_);
299 is_xstaff_ = Align_interface::has_interface (common[Y_AXIS]);
300 is_knee_ |= dirs_found[DOWN] && dirs_found[UP];
302 staff_radius_ = Staff_symbol_referencer::staff_radius (beams[i]);
303 edge_beam_counts_ = Drul_array<int>
304 (Stem::beam_multiplicity (stems[0]).length () + 1,
305 Stem::beam_multiplicity (stems.back ()).length () + 1);
307 // TODO - why are we dividing by staff_space_?
308 beam_translation_ = Beam::get_beam_translation (beams[i]) / staff_space_;
313 quant_range_[d].set_full ();
317 Real stem_offset = edge_stems[d]->relative_coordinate (common[Y_AXIS], Y_AXIS)
318 - beams[i]->relative_coordinate (common[Y_AXIS], Y_AXIS);
319 Interval heads = Stem::head_positions (edge_stems[d]) * 0.5 * staff_space_;
321 Direction ed = edge_dirs_[d];
322 heads.widen (0.5 * staff_space_
323 + (edge_beam_counts_[d] - 1) * beam_translation_ + beam_thickness_ * .5);
324 quant_range_[d][-ed] = heads[ed] + stem_offset;
326 while (flip (&d) != LEFT);
328 segments_ = Beam::get_beam_segments (beams[i]);
329 vector_sort (segments_, beam_segment_less);
330 for (vsize j = 0; j < segments_.size (); j++)
331 segments_[j].horizontal_ += (x_span_ - x_pos[LEFT]);
333 set<Grob *> colliding_stems;
334 for (vsize j = 0; j < collisions.size (); j++)
336 if (!collisions[j]->is_live ())
339 if (Beam::has_interface (collisions[j]) && Beam::is_cross_staff (collisions[j]))
343 for (Axis a = X_AXIS; a < NO_AXES; incr (a))
344 b[a] = collisions[j]->extent (common[a], a);
346 if (b[X_AXIS][RIGHT] < x_pos[LEFT] || b[X_AXIS][LEFT] > x_pos[RIGHT])
348 if (b[X_AXIS].is_empty () || b[Y_AXIS].is_empty ())
351 b[X_AXIS] += (x_span_ - x_pos[LEFT]);
352 Real width = b[X_AXIS].length ();
353 Real width_factor = sqrt (width / staff_space_);
357 add_collision (b[X_AXIS][d], b[Y_AXIS], width_factor);
358 while (flip (&d) != LEFT);
360 Grob *stem = unsmob_grob (collisions[j]->get_object ("stem"));
361 if (stem && Stem::has_interface (stem) && Stem::is_normal_stem (stem))
363 colliding_stems.insert (stem);
367 for (set<Grob *>::const_iterator it (colliding_stems.begin ()); it != colliding_stems.end (); it++)
370 Real x = (s->extent (common[X_AXIS], X_AXIS) - x_pos[LEFT] + x_span_).center ();
372 Direction stem_dir = get_grob_direction (*it);
375 y[-stem_dir] = Stem::chord_start_y (*it) + (*it)->relative_coordinate (common[Y_AXIS], Y_AXIS)
376 - beams[i]->relative_coordinate (common[Y_AXIS], Y_AXIS);
378 Real factor = parameters_.STEM_COLLISION_FACTOR;
379 if (!unsmob_grob (s->get_object ("beam")))
381 add_collision (x, y, factor);
383 x_span_ += beams[i]->spanner_length ();
387 Beam_scoring_problem::Beam_scoring_problem (Grob *me, Drul_array<Real> ys, bool align_broken_intos)
389 beam_ = dynamic_cast<Spanner *> (me);
391 align_broken_intos_ = align_broken_intos;
393 parameters_.fill (me);
394 init_instance_variables (me, ys, align_broken_intos);
395 if (do_initial_slope_calculations_)
397 least_squares_positions ();
399 shift_region_to_valid ();
403 // Assuming V is not empty, pick a 'reasonable' point inside V.
405 point_in_interval (Interval v, Real dist)
409 else if (isinf (v[UP]))
410 return v[DOWN] + dist;
415 /* Set stem's shorten property if unset.
418 take some y-position (chord/beam/nearest?) into account
419 scmify forced-fraction
421 This is done in beam because the shorten has to be uniform over the
426 set_minimum_dy (Grob *me, Real *dy)
431 If dy is smaller than the smallest quant, we
432 get absurd direction-sign penalties.
435 Real ss = Staff_symbol_referencer::staff_space (me);
436 Real beam_thickness = Beam::get_beam_thickness (me) / ss;
437 Real slt = Staff_symbol_referencer::line_thickness (me) / ss;
438 Real sit = (beam_thickness - slt) / 2;
440 Real hang = 1.0 - (beam_thickness - slt) / 2;
442 *dy = sign (*dy) * max (fabs (*dy),
443 min (min (sit, inter), hang));
448 Beam_scoring_problem::no_visible_stem_positions ()
450 if (!head_positions_.size ())
452 unquanted_y_ = Interval (0, 0);
456 Interval head_positions;
458 for (vsize i = 0; i < head_positions_.size (); i++)
460 head_positions.unite (head_positions_[i]);
461 multiplicity.unite (beam_multiplicity_[i]);
464 Direction dir = get_grob_direction (beam_);
467 programming_error ("The beam should have a direction by now.");
469 Real y = head_positions.linear_combination (dir)
471 + dir * beam_translation_ * (multiplicity.length () + 1);
473 unquanted_y_ = Interval (y, y);
477 Beam_scoring_problem::first_normal_index ()
479 for (vsize i = 0; i < is_normal_.size (); i++)
483 beam_->programming_error ("No normal stems, but asking for first normal stem index.");
488 Beam_scoring_problem::last_normal_index ()
490 for (vsize i = is_normal_.size (); i--;)
494 beam_->programming_error ("No normal stems, but asking for first normal stem index.");
499 Beam_scoring_problem::least_squares_positions ()
501 if (!normal_stem_count_)
503 no_visible_stem_positions ();
507 if (stem_infos_.size () < 1)
510 vsize fnx = first_normal_index ();
511 vsize lnx = last_normal_index ();
513 Interval ideal (stem_infos_[fnx].ideal_y_ + stem_ypositions_[fnx],
514 stem_infos_[lnx].ideal_y_ + stem_ypositions_[lnx]);
522 Interval chord (chord_start_y_[0],
523 chord_start_y_.back ());
525 /* Simple beams (2 stems) on middle line should be allowed to be
528 However, if both stems reach middle line,
529 ideal[LEFT] == ideal[RIGHT] and ideal.delta () == 0.
531 For that case, we apply artificial slope */
532 if (!ideal[LEFT] && chord.delta () && stem_infos_.size () == 2)
535 Direction d = (Direction) (sign (chord.delta ()) * UP);
536 unquanted_y_[d] = Beam::get_beam_thickness (beam_) / 2;
537 unquanted_y_[-d] = -unquanted_y_[d];
540 unquanted_y_ = ideal;
542 ldy = unquanted_y_[RIGHT] - unquanted_y_[LEFT];
546 vector<Offset> ideals;
547 for (vsize i = 0; i < stem_infos_.size (); i++)
549 ideals.push_back (Offset (stem_xpositions_[i],
550 stem_infos_[i].ideal_y_
551 + stem_ypositions_[i]));
553 minimise_least_squares (&slope, &y, ideals);
555 dy = slope * x_span_;
557 set_minimum_dy (beam_, &dy);
560 unquanted_y_ = Interval (y, (y + dy));
564 beam_->set_property ("least-squares-dy", scm_from_double (musical_dy_));
568 Determine whether a beam is concave.
570 A beam is concave when the middle notes get closer to the
571 beam than the left and right edge notes.
573 This is determined in two ways: by looking at the positions of the
574 middle notes, or by looking at the deviation of the inside notes
575 compared to the line connecting first and last.
577 The tricky thing is what to do with beams with chords. There are no
578 real guidelines in this case.
582 is_concave_single_notes (vector<int> const &positions, Direction beam_dir)
585 covering.add_point (positions[0]);
586 covering.add_point (positions.back ());
590 bool concave = false;
593 notes above and below the interval covered by 1st and last note.
595 for (vsize i = 1; i + 1 < positions.size (); i++)
597 above = above || (positions[i] > covering[UP]);
598 below = below || (positions[i] < covering[DOWN]);
601 concave = concave || (above && below);
603 A note as close or closer to the beam than begin and end, but the
604 note is reached in the opposite direction as the last-first dy
606 int dy = positions.back () - positions[0];
607 int closest = max (beam_dir * positions.back (), beam_dir * positions[0]);
608 for (vsize i = 2; !concave && i + 1 < positions.size (); i++)
610 int inner_dy = positions[i] - positions[i - 1];
611 if (sign (inner_dy) != sign (dy)
612 && (beam_dir * positions[i] >= closest
613 || beam_dir * positions[i - 1] >= closest))
617 bool all_closer = true;
618 for (vsize i = 1; all_closer && i + 1 < positions.size (); i++)
620 all_closer = all_closer
621 && (beam_dir * positions[i] > closest);
624 concave = concave || all_closer;
629 calc_positions_concaveness (vector<int> const &positions, Direction beam_dir)
631 Real dy = positions.back () - positions[0];
632 Real slope = dy / Real (positions.size () - 1);
633 Real concaveness = 0.0;
634 for (vsize i = 1; i + 1 < positions.size (); i++)
636 Real line_y = slope * i + positions[0];
638 concaveness += max (beam_dir * (positions[i] - line_y), 0.0);
641 concaveness /= positions.size ();
644 Normalize. For dy = 0, the slope ends up as 0 anyway, so the
645 scaling of concaveness doesn't matter much.
648 concaveness /= fabs (dy);
653 Beam_scoring_problem::calc_concaveness ()
655 SCM conc = beam_->get_property ("concaveness");
656 if (scm_is_number (conc))
657 return scm_to_double (conc);
662 Direction beam_dir = CENTER;
663 for (vsize i = is_normal_.size (); i--;)
664 if (is_normal_[i] && stem_infos_[i].dir_)
665 beam_dir = stem_infos_[i].dir_;
667 if (normal_stem_count_ <= 2)
670 vector<int> close_positions;
671 vector<int> far_positions;
672 for (vsize i = 0; i < is_normal_.size (); i++)
676 For chords, we take the note head that is closest to the beam.
678 Hmmm.. wait, for the beams in the last measure of morgenlied,
679 this doesn't look so good. Let's try the heads farthest from
683 close_positions.push_back ((int) rint (head_positions_[i][beam_dir]));
684 far_positions.push_back ((int) rint (head_positions_[i][-beam_dir]));
687 Real concaveness = 0.0;
689 if (is_concave_single_notes (beam_dir == UP ? close_positions : far_positions, beam_dir))
695 concaveness = (calc_positions_concaveness (far_positions, beam_dir)
696 + calc_positions_concaveness (close_positions, beam_dir)) / 2;
703 Beam_scoring_problem::slope_damping ()
705 if (normal_stem_count_ <= 1)
708 SCM s = beam_->get_property ("damping");
709 Real damping = scm_to_double (s);
710 Real concaveness = calc_concaveness ();
711 if (concaveness >= 10000)
713 unquanted_y_[LEFT] = unquanted_y_[RIGHT];
720 Real dy = unquanted_y_[RIGHT] - unquanted_y_[LEFT];
722 Real slope = dy && x_span_ ? dy / x_span_ : 0;
724 slope = 0.6 * tanh (slope) / (damping + concaveness);
726 Real damped_dy = slope * x_span_;
728 set_minimum_dy (beam_, &damped_dy);
730 unquanted_y_[LEFT] += (dy - damped_dy) / 2;
731 unquanted_y_[RIGHT] -= (dy - damped_dy) / 2;
736 Beam_scoring_problem::shift_region_to_valid ()
738 if (!normal_stem_count_)
741 Real beam_dy = unquanted_y_[RIGHT] - unquanted_y_[LEFT];
742 Real slope = x_span_ ? beam_dy / x_span_ : 0.0;
745 Shift the positions so that we have a chance of finding good
746 quants (i.e. no short stem failures.)
748 Interval feasible_left_point;
749 feasible_left_point.set_full ();
751 for (vsize i = 0; i < stem_infos_.size (); i++)
753 // TODO - check for invisible here...
755 = stem_infos_[i].shortest_y_
756 - slope * stem_xpositions_ [i];
759 left_y is now relative to the stem S. We want relative to
760 ourselves, so translate:
762 left_y += stem_ypositions_[i];
765 flp[-stem_infos_[i].dir_] = left_y;
767 feasible_left_point.intersect (flp);
770 vector<Grob *> filtered;
772 We only update these for objects that are too large for quanting
773 to find a workaround. Typically, these are notes with
774 stems, and timesig/keysig/clef, which take out the entire area
775 inside the staff as feasible.
777 The code below disregards the thickness and multiplicity of the
778 beam. This should not be a problem, as the beam quanting will
779 take care of computing the impact those exactly.
781 Real min_y_size = 2.0;
783 // A list of intervals into which beams may not fall
784 vector<Interval> forbidden_intervals;
786 for (vsize i = 0; i < collisions_.size (); i++)
788 if (collisions_[i].x_ < 0 || collisions_[i].x_ > x_span_)
791 if (collisions_[i].y_.length () < min_y_size)
797 Real dy = slope * collisions_[i].x_;
803 Real left_y = collisions_[i].y_[yd] - dy;
804 disallowed[yd] = left_y;
806 while (flip (&yd) != DOWN);
808 forbidden_intervals.push_back (disallowed);
810 while (flip (&d) != LEFT);
813 vector_sort (forbidden_intervals, Interval::left_less);
814 Real epsilon = 1.0e-10;
815 Real beam_left_y = unquanted_y_[LEFT];
816 Interval feasible_beam_placements (beam_left_y, beam_left_y);
819 forbidden_intervals contains a vector of intervals in which
820 the beam cannot start. it iterates through these intervals,
821 pushing feasible_beam_placements epsilon over or epsilon under a
822 collision. when this type of change happens, the loop is marked
823 as "dirty" and re-iterated.
825 TODO: figure out a faster ways that this loop can happen via
826 a better search algorithm and/or OOP.
833 for (vsize i = 0; i < forbidden_intervals.size (); i++)
838 if (forbidden_intervals[i][d] == d * infinity_f)
839 feasible_beam_placements[d] = d * infinity_f;
840 else if (forbidden_intervals[i].contains (feasible_beam_placements[d]))
842 feasible_beam_placements[d] = d * epsilon + forbidden_intervals[i][d];
846 while (flip (&d) != DOWN);
851 // if the beam placement falls out of the feasible region, we push it
852 // to infinity so that it can never be a feasible candidate below
856 if (!feasible_left_point.contains (feasible_beam_placements[d]))
857 feasible_beam_placements[d] = d * infinity_f;
859 while (flip (&d) != DOWN);
861 if ((feasible_beam_placements[UP] == infinity_f && feasible_beam_placements[DOWN] == -infinity_f) && !feasible_left_point.is_empty ())
863 // We are somewhat screwed: we have a collision, but at least
864 // there is a way to satisfy stem length constraints.
865 beam_left_y = point_in_interval (feasible_left_point, 2.0);
867 else if (!feasible_left_point.is_empty ())
869 // Only one of them offers is feasible solution. Pick that one.
870 if (abs (beam_left_y - feasible_beam_placements[DOWN]) > abs (beam_left_y - feasible_beam_placements[UP]))
871 beam_left_y = feasible_beam_placements[UP];
873 beam_left_y = feasible_beam_placements[DOWN];
877 // We are completely screwed.
878 beam_->warning (_ ("no viable initial configuration found: may not find good beam slope"));
881 unquanted_y_ = Drul_array<Real> (beam_left_y, (beam_left_y + beam_dy));
885 Beam_scoring_problem::generate_quants (vector<Beam_configuration *> *scores) const
887 int region_size = (int) parameters_.REGION_SIZE;
889 // Knees and collisions are harder, lets try some more possibilities
892 if (collisions_.size ())
896 Real sit = (beam_thickness_ - line_thickness_) / 2;
898 Real hang = 1.0 - (beam_thickness_ - line_thickness_) / 2;
899 Real base_quants [] = {straddle, sit, inter, hang};
900 int num_base_quants = int (sizeof (base_quants) / sizeof (Real));
903 Asymetry ? should run to <= region_size ?
905 vector<Real> unshifted_quants;
906 for (int i = -region_size; i < region_size; i++)
907 for (int j = 0; j < num_base_quants; j++)
909 unshifted_quants.push_back (i + base_quants[j]);
912 for (vsize i = 0; i < unshifted_quants.size (); i++)
913 for (vsize j = 0; j < unshifted_quants.size (); j++)
915 Beam_configuration *c
916 = Beam_configuration::new_config (unquanted_y_,
917 Interval (unshifted_quants[i],
918 unshifted_quants[j]));
923 if (!quant_range_[d].contains (c->y[d]))
930 while (flip (&d) != LEFT);
932 scores->push_back (c);
937 void Beam_scoring_problem::one_scorer (Beam_configuration *config) const
940 switch (config->next_scorer_todo)
943 score_slope_ideal (config);
945 case SLOPE_DIRECTION:
946 score_slope_direction (config);
949 score_slope_musical (config);
952 score_forbidden_quants (config);
955 score_stem_lengths (config);
958 score_collisions (config);
960 case HORIZONTAL_INTER:
961 score_horizontal_inter_quants (config);
965 case ORIGINAL_DISTANCE:
969 config->next_scorer_todo++;
973 Beam_scoring_problem::force_score (SCM inspect_quants, const vector<Beam_configuration *> &configs) const
975 Drul_array<Real> ins = ly_scm2interval (inspect_quants);
977 Beam_configuration *best = NULL;
978 for (vsize i = 0; i < configs.size (); i++)
980 Real d = fabs (configs[i]->y[LEFT] - ins[LEFT]) + fabs (configs[i]->y[RIGHT] - ins[RIGHT]);
988 programming_error ("cannot find quant");
990 while (!best->done ())
997 Beam_scoring_problem::solve () const
999 vector<Beam_configuration *> configs;
1000 generate_quants (&configs);
1002 if (configs.empty ())
1004 programming_error ("No viable beam quanting found. Using unquanted y value.");
1005 return unquanted_y_;
1008 if (to_boolean (beam_->get_property ("skip-quanting")))
1009 return unquanted_y_;
1011 Beam_configuration *best = NULL;
1014 = to_boolean (beam_->layout ()->lookup_variable (ly_symbol2scm ("debug-beam-scoring")));
1015 SCM inspect_quants = beam_->get_property ("inspect-quants");
1016 if (scm_is_pair (inspect_quants))
1019 best = force_score (inspect_quants, configs);
1023 std::priority_queue < Beam_configuration *, std::vector<Beam_configuration *>,
1024 Beam_configuration_less > queue;
1025 for (vsize i = 0; i < configs.size (); i++)
1026 queue.push (configs[i]);
1031 It would be neat if we generated new configurations on the
1032 fly, depending on the best complete score so far, eg.
1035 if (best->demerits < sqrt(queue.size())
1037 while (best->demerits > sqrt(queue.size()) {
1038 generate and insert new configuration
1042 that would allow us to do away with region_size altogether.
1046 best = queue.top ();
1056 Interval final_positions = best->y;
1058 #if DEBUG_BEAM_SCORING
1063 for (vsize i = 0; i < configs.size (); i++)
1065 if (configs[i]->done ())
1069 string card = best->score_card_ + to_string (" c%d/%d", completed, configs.size ());
1070 beam_->set_property ("annotation", ly_string2scm (card));
1074 junk_pointers (configs);
1075 if (align_broken_intos_)
1077 Interval normalized_endpoints = robust_scm2interval (beam_->get_property ("normalized-endpoints"), Interval (0, 1));
1078 Real y_length = final_positions[RIGHT] - final_positions[LEFT];
1080 final_positions[LEFT] += normalized_endpoints[LEFT] * y_length;
1081 final_positions[RIGHT] -= (1 - normalized_endpoints[RIGHT]) * y_length;
1084 return final_positions;
1088 Beam_scoring_problem::score_stem_lengths (Beam_configuration *config) const
1090 Real limit_penalty = parameters_.STEM_LENGTH_LIMIT_PENALTY;
1091 Drul_array<Real> score (0, 0);
1092 Drul_array<int> count (0, 0);
1094 for (vsize i = 0; i < stem_xpositions_.size (); i++)
1099 Real x = stem_xpositions_[i];
1102 ? config->y[RIGHT] * x / dx + config->y[LEFT] * (x_span_ - x) / dx
1103 : (config->y[RIGHT] + config->y[LEFT]) / 2;
1104 Real current_y = beam_y + base_lengths_[i];
1105 Real length_pen = parameters_.STEM_LENGTH_DEMERIT_FACTOR;
1107 Stem_info info = stem_infos_[i];
1108 Direction d = info.dir_;
1110 score[d] += limit_penalty * max (0.0, (d * (info.shortest_y_ - current_y)));
1112 Real ideal_diff = d * (current_y - info.ideal_y_);
1113 Real ideal_score = shrink_extra_weight (ideal_diff, 1.5);
1115 /* We introduce a power, to make the scoring strictly
1116 convex. Otherwise a symmetric knee beam (up/down/up/down)
1117 does not have an optimum in the middle. */
1119 ideal_score = pow (ideal_score, 1.1);
1121 score[d] += length_pen * ideal_score;
1125 /* Divide by number of stems, to make the measure scale-free. */
1128 score[d] /= max (count[d], 1);
1129 while (flip (&d) != DOWN);
1132 sometimes, two perfectly symmetric kneed beams will have the same score
1133 and can either be quanted up or down.
1135 we choose the quanting in the direction of the slope so that the first stem
1136 always seems longer, reaching to the second, rather than squashed.
1138 if (is_knee_ && count[LEFT] == count[RIGHT] && count[LEFT] == 1 && unquanted_y_.delta ())
1139 score[Direction (sign (unquanted_y_.delta ()))] += score[Direction (sign (unquanted_y_.delta ()))] < 1.0 ? 0.01 : 0.0;
1141 config->add (score[LEFT] + score[RIGHT], "L");
1145 Beam_scoring_problem::score_slope_direction (Beam_configuration *config) const
1147 Real dy = config->y.delta ();
1148 Real damped_dy = unquanted_y_.delta ();
1151 DAMPING_DIRECTION_PENALTY is a very harsh measure, while for
1152 complex beaming patterns, horizontal is often a good choice.
1154 TODO: find a way to incorporate the complexity of the beam in this
1157 if (sign (damped_dy) != sign (dy))
1161 if (fabs (damped_dy / x_span_) > parameters_.ROUND_TO_ZERO_SLOPE)
1162 dem += parameters_.DAMPING_DIRECTION_PENALTY;
1164 dem += parameters_.HINT_DIRECTION_PENALTY;
1167 dem += parameters_.DAMPING_DIRECTION_PENALTY;
1170 config->add (dem, "Sd");
1173 // Score for going against the direction of the musical pattern
1175 Beam_scoring_problem::score_slope_musical (Beam_configuration *config) const
1177 Real dy = config->y.delta ();
1178 Real dem = parameters_.MUSICAL_DIRECTION_FACTOR
1179 * max (0.0, (fabs (dy) - fabs (musical_dy_)));
1180 config->add (dem, "Sm");
1183 // Score deviation from calculated ideal slope.
1185 Beam_scoring_problem::score_slope_ideal (Beam_configuration *config) const
1187 Real dy = config->y.delta ();
1188 Real damped_dy = unquanted_y_.delta ();
1191 Real slope_penalty = parameters_.IDEAL_SLOPE_FACTOR;
1193 /* Xstaff beams tend to use extreme slopes to get short stems. We
1194 put in a penalty here. */
1196 slope_penalty *= 10;
1198 /* Huh, why would a too steep beam be better than a too flat one ? */
1199 dem += shrink_extra_weight (fabs (damped_dy) - fabs (dy), 1.5)
1202 config->add (dem, "Si");
1208 return x - floor (x);
1211 // TODO - there is some overlap with forbidden quants, but for
1212 // horizontal beams, it is much more serious to have stafflines
1213 // appearing in the wrong place, so we have a separate scorer.
1215 Beam_scoring_problem::score_horizontal_inter_quants (Beam_configuration *config) const
1217 if (config->y.delta () == 0.0
1218 && abs (config->y[LEFT]) < staff_radius_ * staff_space_)
1220 Real yshift = config->y[LEFT] - 0.5 * staff_space_;
1221 if (fabs (my_round (yshift) - yshift) < 0.01 * staff_space_)
1222 config->add (parameters_.HORIZONTAL_INTER_QUANT_PENALTY, "H");
1227 TODO: The fixed value SECONDARY_BEAM_DEMERIT is probably flawed:
1228 because for 32nd and 64th beams the forbidden quants are relatively
1229 more important than stem lengths.
1232 Beam_scoring_problem::score_forbidden_quants (Beam_configuration *config) const
1234 Real dy = config->y.delta ();
1236 Real extra_demerit = parameters_.SECONDARY_BEAM_DEMERIT
1237 / max (edge_beam_counts_[LEFT], edge_beam_counts_[RIGHT]);
1241 Real eps = parameters_.BEAM_EPS;
1245 for (int j = 1; j <= edge_beam_counts_[d]; j++)
1247 Direction stem_dir = edge_dirs_[d];
1250 The 2.2 factor is to provide a little leniency for
1251 borderline cases. If we do 2.0, then the upper outer line
1252 will be in the gap of the (2, sit) quant, leading to a
1255 Real gap1 = config->y[d] - stem_dir * ((j - 1) * beam_translation_ + beam_thickness_ / 2 - line_thickness_ / 2.2);
1256 Real gap2 = config->y[d] - stem_dir * (j * beam_translation_ - beam_thickness_ / 2 + line_thickness_ / 2.2);
1259 gap.add_point (gap1);
1260 gap.add_point (gap2);
1262 for (Real k = -staff_radius_;
1263 k <= staff_radius_ + eps; k += 1.0)
1264 if (gap.contains (k))
1266 Real dist = min (fabs (gap[UP] - k), fabs (gap[DOWN] - k));
1269 this parameter is tuned to grace-stem-length.ly
1270 retuned from 0.40 to 0.39 by MS because of slight increases
1271 in gap.length () resulting from measuring beams at real ends
1272 instead of from the middle of stems.
1275 This function needs better comments so we know what is forbidden
1278 Real fixed_demerit = 0.39;
1280 dem += extra_demerit
1282 + (1 - fixed_demerit) * (dist / gap.length ()) * 2);
1286 while ((flip (&d)) != LEFT);
1288 if (max (edge_beam_counts_[LEFT], edge_beam_counts_[RIGHT]) >= 2)
1290 Real straddle = 0.0;
1291 Real sit = (beam_thickness_ - line_thickness_) / 2;
1293 Real hang = 1.0 - (beam_thickness_ - line_thickness_) / 2;
1298 if (edge_beam_counts_[d] >= 2
1299 && fabs (config->y[d] - edge_dirs_[d] * beam_translation_) < staff_radius_ + inter)
1301 // TODO up/down symmetry.
1302 if (edge_dirs_[d] == UP && dy <= eps
1303 && fabs (my_modf (config->y[d]) - sit) < eps)
1304 dem += extra_demerit;
1306 if (edge_dirs_[d] == DOWN && dy >= eps
1307 && fabs (my_modf (config->y[d]) - hang) < eps)
1308 dem += extra_demerit;
1311 if (edge_beam_counts_[d] >= 3
1312 && fabs (config->y[d] - 2 * edge_dirs_[d] * beam_translation_) < staff_radius_ + inter)
1314 // TODO up/down symmetry.
1315 if (edge_dirs_[d] == UP && dy <= eps
1316 && fabs (my_modf (config->y[d]) - straddle) < eps)
1317 dem += extra_demerit;
1319 if (edge_dirs_[d] == DOWN && dy >= eps
1320 && fabs (my_modf (config->y[d]) - straddle) < eps)
1321 dem += extra_demerit;
1324 while (flip (&d) != LEFT);
1327 config->add (dem, "F");
1331 Beam_scoring_problem::score_collisions (Beam_configuration *config) const
1333 Real demerits = 0.0;
1334 for (vsize i = 0; i < collisions_.size (); i++)
1336 Interval collision_y = collisions_[i].y_;
1337 Real x = collisions_[i].x_;
1339 Real center_beam_y = y_at (x, config);
1340 Interval beam_y = center_beam_y + collisions_[i].beam_y_;
1342 Real dist = infinity_f;
1343 if (!intersection (beam_y, collision_y).is_empty ())
1346 dist = min (beam_y.distance (collision_y[DOWN]),
1347 beam_y.distance (collision_y[UP]));
1350 = max (parameters_.COLLISION_PADDING - dist, 0.0)
1351 / parameters_.COLLISION_PADDING;
1353 += collisions_[i].base_penalty_ *
1354 pow (scale_free, 3) * parameters_.COLLISION_PENALTY;
1357 config->add (demerits, "C");