From 15feba22d437b566333c8c948a5780ce40c5953f Mon Sep 17 00:00:00 2001 From: Han-Wen Nienhuys Date: Wed, 9 Feb 2011 23:51:08 -0200 Subject: [PATCH] Beam collision scoring * Add separate scorer for horizontal inter quant * Split up slope scorers * Add collision precompute data and scoring pass * Add separate factor for lighter penalties of stem/beam collisions * Further decrease debug data fontsize * Add different testfiles. --- input/regression/beam-collision-basic.ly | 90 +++++++ input/regression/beam-collision-beamcount.ly | 41 +++ input/regression/beam-collision-classic.ly | 58 +++++ .../beam-collision-prefatory-matter.ly | 31 +++ lily/beam-quanting.cc | 236 +++++++++++++++--- lily/beam.cc | 9 +- lily/include/beam-scoring-problem.hh | 40 ++- lily/include/beam.hh | 2 + scm/define-grobs.scm | 2 + 9 files changed, 467 insertions(+), 42 deletions(-) create mode 100644 input/regression/beam-collision-basic.ly create mode 100644 input/regression/beam-collision-beamcount.ly create mode 100644 input/regression/beam-collision-classic.ly create mode 100644 input/regression/beam-collision-prefatory-matter.ly diff --git a/input/regression/beam-collision-basic.ly b/input/regression/beam-collision-basic.ly new file mode 100644 index 0000000000..5a86125466 --- /dev/null +++ b/input/regression/beam-collision-basic.ly @@ -0,0 +1,90 @@ +\version "2.13.47" +\header { + texidoc = "Manual beams do not collide with notes." +} + +\layout { +% debug-beam-scoring = ##t + indent = #0.0 +} + +\relative \new Staff { + + << + \new Voice { + \voiceOne + \repeat unfold 8 { c8[ c] } + } + \new Voice \relative c'' { + \voiceThree + \autoBeamOff + f r e r + d r c r + b r a r + g r f r + } + >> + \break + + %% The same with double collisions, to check for scaling problems. + << + \new Voice { + \voiceOne + \repeat unfold 8 { c8[ c] } + } + \new Voice \relative c'' { + \voiceThree + \autoBeamOff + f f e e + d d c c + b b a a + g g f f + } + >> + \break + + << + \new Voice { + \repeat unfold 8 \relative { + \voiceOne + c8[ + \voiceTwo + c''] + } + } + \new Voice \relative { + \voiceFour + s8 f + s8 g + s8 a + s8 b + s8 c + s8 d + s8 e + } + >> + + \break + << + \new Voice { + \repeat unfold 8 \relative { + \voiceOne + + %% We must use a wider interval, otherwise the beam will be + %% positioned to descend. + a8[ + \voiceTwo + c''] + } + } + \new Voice \relative { + \voiceFour + \autoBeamOff + \stemUp f' \stemDown f, + \stemUp e' \stemDown g, + \stemUp d' \stemDown a + \stemUp c \stemDown b + } + >> +} + diff --git a/input/regression/beam-collision-beamcount.ly b/input/regression/beam-collision-beamcount.ly new file mode 100644 index 0000000000..bb9d326ce9 --- /dev/null +++ b/input/regression/beam-collision-beamcount.ly @@ -0,0 +1,41 @@ +\version "2.13.47" +\header { + texidoc = "Manual beams do not collide with notes." +} + +\layout { +% debug-beam-scoring = ##t + indent = #0.0 +} + +\relative \new Staff { + + << + \new Voice { + \voiceOne + \repeat unfold 4 { c8[ c] } + } + \new Voice \relative c'' { + \voiceThree + \autoBeamOff + b r a r + g r f r + } + >> + + | + + << + \new Voice { + \voiceOne + \repeat unfold 4 { c16[ c] } + } + \new Voice \relative c'' { + \voiceThree + \autoBeamOff + b r a r + g r f r + } + >> + +} diff --git a/input/regression/beam-collision-classic.ly b/input/regression/beam-collision-classic.ly new file mode 100644 index 0000000000..cc3a7ba601 --- /dev/null +++ b/input/regression/beam-collision-classic.ly @@ -0,0 +1,58 @@ +\header { + texinfo = "Beam collisions from modern works" + } + +\layout { + ragged-right = ##t +% debug-beam-scoring = ##t +} + +\version "2.13.49" + +\new Staff +{ + % Stockhausen (without hemiolas) + \relative c''' { + \stemUp + a8[ \clef bass es,,,, + r8 + \clef G + gis'''] + } + r8 r4 | + + % Ligeti 1st etude. + \relative c'' + << + { g8[ a b c d] } \\ + { s4. 4. } + >> + r4. + + % Ligeti 1st etude. + \relative c'' + << + { + s4. 4. + } \\ + { +% \override Beam #'inspect-quants = #'(-4 . -3) + a8[ d e f g] + } + >> + r4. + + % Ligeti 1st etude. + \relative c' + << + { 2. } \\ + { a'8[ b c] } + >> + + % Schubert morgenlied. + \clef bass + \relative c { + a16[ d fis d a d] + } + +} diff --git a/input/regression/beam-collision-prefatory-matter.ly b/input/regression/beam-collision-prefatory-matter.ly new file mode 100644 index 0000000000..61622fb597 --- /dev/null +++ b/input/regression/beam-collision-prefatory-matter.ly @@ -0,0 +1,31 @@ +\header { + texinfo = "Beams do not collide with clefs, key signatures, time + signatures" +} + +\layout { + ragged-right = ##t +% debug-beam-scoring = ##t +} + +\version "2.13.49" + +\relative { + \time 2/4 + c8[ \clef "bass" e,, ] + r8 + e8[ | + \time 1/4 + e] + e[ + e] r8 + \time 4/4 + + e[ + \key f \major + e] + e[ + \key cis \major + e] + +} diff --git a/lily/beam-quanting.cc b/lily/beam-quanting.cc index 43c8f393b2..05fa591d7d 100644 --- a/lily/beam-quanting.cc +++ b/lily/beam-quanting.cc @@ -21,17 +21,21 @@ #include "beam-scoring-problem.hh" #include +#include #include using namespace std; #include "align-interface.hh" #include "beam.hh" +#include "direction.hh" +#include "directional-element-interface.hh" #include "grob.hh" #include "international.hh" #include "main.hh" #include "output-def.hh" #include "pointer-group-interface.hh" #include "staff-symbol-referencer.hh" +#include "stencil.hh" #include "stem.hh" #include "warn.hh" @@ -50,18 +54,29 @@ Beam_quant_parameters::fill (Grob *him) { SCM details = him->get_property ("details"); + // General + BEAM_EPS = get_detail (details, ly_symbol2scm ("beam-eps"), 1e-3); + REGION_SIZE = get_detail (details, ly_symbol2scm ("region-size"), 2); + + // forbidden quants SECONDARY_BEAM_DEMERIT = get_detail (details, ly_symbol2scm ("secondary-beam-demerit"), 10.0); STEM_LENGTH_DEMERIT_FACTOR = get_detail (details, ly_symbol2scm ("stem-length-demerit-factor"), 5); - REGION_SIZE = get_detail (details, ly_symbol2scm ("region-size"), 2); - BEAM_EPS = get_detail (details, ly_symbol2scm ("beam-eps"), 1e-3); + HORIZONTAL_INTER_QUANT_PENALTY = get_detail (details, ly_symbol2scm ("horizontal-inter-quant"), 500); + STEM_LENGTH_LIMIT_PENALTY = get_detail (details, ly_symbol2scm ("stem-length-limit-penalty"), 5000); DAMPING_DIRECTION_PENALTY = get_detail (details, ly_symbol2scm ("damping-direction-penalty"), 800); HINT_DIRECTION_PENALTY = get_detail (details, ly_symbol2scm ("hint-direction-penalty"), 20); MUSICAL_DIRECTION_FACTOR = get_detail (details, ly_symbol2scm ("musical-direction-factor"), 400); IDEAL_SLOPE_FACTOR = get_detail (details, ly_symbol2scm ("ideal-slope-factor"), 10); ROUND_TO_ZERO_SLOPE = get_detail (details, ly_symbol2scm ("round-to-zero-slope"), 0.02); + + // Collisions + COLLISION_PENALTY = get_detail (details, ly_symbol2scm ("collision-penalty"), 500); + COLLISION_DISTANCE = get_detail (details, ly_symbol2scm ("collision-distance"), 0.5); + STEM_COLLISION_FACTOR = get_detail (details, ly_symbol2scm ("stem-collision-factor"), 0.1); } +// Add x if x is positive, add |x|*fac if x is negative. static Real shrink_extra_weight (Real x, Real fac) { @@ -108,6 +123,11 @@ Beam_configuration* Beam_configuration::new_config (Interval start, return qs; } +Real +Beam_scoring_problem::y_at (Real x, Beam_configuration const* p) const { + return p->y[LEFT] + (x - x_span[LEFT]) * p->y.delta() / x_span.delta(); +} + /****************************************************************/ /* @@ -115,27 +135,9 @@ Beam_configuration* Beam_configuration::new_config (Interval start, - Make all demerits customisable - - One sensible check per demerit (what's this --hwn) - - Add demerits for quants per se, as to forbid a specific quant entirely */ -int -best_quant_score_idx (vector const &configs) -{ - Real best = 1e6; - int best_idx = -1; - for (vsize i = configs.size (); i--;) - { - if (configs[i]->demerits < best) - { - best = configs [i]->demerits; - best_idx = i; - } - } - - return best_idx; -} // This is a temporary hack to see how much we can gain by using a // priority queue on the beams to score. @@ -146,12 +148,101 @@ LY_DEFINE (ly_beam_score_count, "ly:beam-score-count", 0, 0, 0, return scm_from_int (score_count); } +void Beam_scoring_problem::add_collision (Real x, Interval y, + Real score_factor) +{ + if (edge_dirs[LEFT] == edge_dirs[RIGHT]) { + Direction d = edge_dirs[LEFT]; + + Real quant_range_y = quant_range[LEFT][-d] + + (x - x_span[LEFT]) * (quant_range[RIGHT][-d] - quant_range[LEFT][-d]) / x_span.delta(); + + if (d*(quant_range_y - minmax(d, y[UP], y[DOWN])) > 0) { + return; + } + } + + Beam_collision c; + c.beam_y_.set_empty (); + + for (vsize j = 0; j < segments_.size (); j++) + { + if (segments_[j].horizontal_.contains(x)) + c.beam_y_.add_point (segments_[j].vertical_count_ * beam_translation); + if (segments_[j].horizontal_[LEFT] > x) + break; + } + c.beam_y_.widen (0.5 * beam_thickness); + + c.x_ = x; + c.y_ = y; + c.base_penalty_ = score_factor; + collisions_.push_back (c); +} + +void Beam_scoring_problem::init_collisions (vector grobs) +{ + Grob* common_x = NULL; + segments_ = Beam::get_beam_segments (beam, &common_x); + vector_sort (segments_, beam_segment_less); + if (common[X_AXIS] != common_x) + { + programming_error ("Disagree on common x. Skipping collisions in beam scoring."); + return; + } + + set stems; + for (vsize i = 0; i < grobs.size (); i++) { + Box b; + + for (Axis a = X_AXIS; a < NO_AXES; incr (a)) + b[a] = grobs[i]->extent(common[a], a); + + Real width = b[X_AXIS].length(); + + Real width_factor = sqrt(width / staff_space); + + Direction d = LEFT; + do + add_collision (b[X_AXIS][d], b[Y_AXIS], width_factor); + while (flip (&d) != LEFT); + + Grob* stem = unsmob_grob (grobs[i]->get_object ("stem")); + if (stem && Stem::has_interface (stem)) + { + stems.insert (stem); + } + } + + for (set::const_iterator it(stems.begin ()); it != stems.end (); it++) + { + Grob *s = *it; + Real x = s->extent (common[X_AXIS], X_AXIS).center(); + + Direction stem_dir = get_grob_direction (*it); + Interval y; + y.set_full (); + y[-stem_dir] = Stem::chord_start_y (*it) + (*it)->relative_coordinate (common[Y_AXIS], Y_AXIS) + - beam->relative_coordinate (common[Y_AXIS], Y_AXIS); + + Real factor = parameters.STEM_COLLISION_FACTOR; + if (!unsmob_grob (s->get_object ("beam")) + && !Stem::flag (s).is_empty ()) + factor = 1.0; + add_collision (x, y, factor); + } +} + void Beam_scoring_problem::init_stems () { + extract_grob_set (beam, "covered-grobs", collisions); extract_grob_set (beam, "stems", stems); for (int a = 2; a--;) - common[a] = common_refpoint_of_array (stems, beam, Axis (a)); - + { + common[a] = common_refpoint_of_array (stems, beam, Axis (a)); + common[a] = common_refpoint_of_array (collisions, common[a], Axis (a)); + } + Drul_array edge_stems(Beam::first_normal_stem (beam), Beam::last_normal_stem (beam)); Direction d = LEFT; @@ -215,6 +306,8 @@ void Beam_scoring_problem::init_stems () quant_range[d][-ed] = heads[ed] + stem_offset; } while (flip (&d) != LEFT); + + init_collisions (collisions); } Beam_scoring_problem::Beam_scoring_problem (Grob *me, Drul_array ys) @@ -242,11 +335,11 @@ Beam_scoring_problem::generate_quants (vector *scores) cons { int region_size = (int) parameters.REGION_SIZE; - /* - Knees are harder, lets try some more possibilities for knees. - */ + // Knees and collisions are harder, lets try some more possibilities if (is_knee) region_size += 2; + if (collisions_.size ()) + region_size += 2; Real straddle = 0.0; Real sit = (beam_thickness - line_thickness) / 2; @@ -295,8 +388,14 @@ void Beam_scoring_problem::one_scorer (Beam_configuration* config) const { score_count ++; switch (config->next_scorer_todo) { - case SLOPES: - score_slopes_dy (config); + case SLOPE_IDEAL: + score_slope_ideal (config); + break; + case SLOPE_DIRECTION: + score_slope_direction (config); + break; + case SLOPE_MUSICAL: + score_slope_musical (config); break; case FORBIDDEN: score_forbidden_quants (config); @@ -304,7 +403,13 @@ void Beam_scoring_problem::one_scorer (Beam_configuration* config) const case STEM_LENGTHS: score_stem_lengths (config); break; - + case COLLISIONS: + score_collisions (config); + break; + case HORIZONTAL_INTER: + score_horizontal_inter_quants (config); + break; + case NUM_SCORERS: case ORIGINAL_DISTANCE: default: @@ -332,6 +437,9 @@ Beam_scoring_problem::force_score (SCM inspect_quants, const vector 1e5) programming_error ("cannot find quant"); + while (!best->done ()) + one_scorer (best); + return best; } @@ -450,12 +558,11 @@ Beam_scoring_problem::score_stem_lengths (Beam_configuration* config) const } void -Beam_scoring_problem::score_slopes_dy (Beam_configuration *config) const +Beam_scoring_problem::score_slope_direction (Beam_configuration *config) const { Real dy = config->y.delta (); Real damped_dy = unquanted_y.delta(); Real dem = 0.0; - /* DAMPING_DIRECTION_PENALTY is a very harsh measure, while for complex beaming patterns, horizontal is often a good choice. @@ -475,10 +582,28 @@ Beam_scoring_problem::score_slopes_dy (Beam_configuration *config) const else dem += parameters.DAMPING_DIRECTION_PENALTY; } - - dem += parameters.MUSICAL_DIRECTION_FACTOR + + config->add (dem, "Sd"); +} + +// Score for going against the direction of the musical pattern +void +Beam_scoring_problem::score_slope_musical (Beam_configuration *config) const +{ + Real dy = config->y.delta (); + Real dem = parameters.MUSICAL_DIRECTION_FACTOR * max (0.0, (fabs (dy) - fabs (musical_dy))); + config->add (dem, "Sm"); +} +// Score deviation from calculated ideal slope. +void +Beam_scoring_problem::score_slope_ideal (Beam_configuration *config) const +{ + Real dy = config->y.delta (); + Real damped_dy = unquanted_y.delta(); + Real dem = 0.0; + Real slope_penalty = parameters.IDEAL_SLOPE_FACTOR; /* Xstaff beams tend to use extreme slopes to get short stems. We @@ -490,7 +615,7 @@ Beam_scoring_problem::score_slopes_dy (Beam_configuration *config) const dem += shrink_extra_weight (fabs (damped_dy) - fabs (dy), 1.5) * slope_penalty; - config->add (dem, "S"); + config->add (dem, "Si"); } static Real @@ -499,6 +624,20 @@ my_modf (Real x) return x - floor (x); } +// TODO - there is some overlap with forbidden quants, but for +// horizontal beams, it is much more serious to have stafflines +// appearing in the wrong place, so we have a separate scorer. +void +Beam_scoring_problem::score_horizontal_inter_quants (Beam_configuration *config) const +{ + if (config->y.delta() == 0.0 && abs (config->y[LEFT]) < staff_radius * staff_space) + { + Real yshift = config->y[LEFT] - 0.5 * staff_space; + if (abs (round(yshift) - yshift) < 0.01 * staff_space) + config->add (parameters.HORIZONTAL_INTER_QUANT_PENALTY, "H"); + } +} + /* TODO: The fixed value SECONDARY_BEAM_DEMERIT is probably flawed: because for 32nd and 64th beams the forbidden quants are relatively @@ -515,7 +654,7 @@ Beam_scoring_problem::score_forbidden_quants (Beam_configuration *config) const Direction d = LEFT; Real dem = 0.0; Real eps = parameters.BEAM_EPS; - + do { for (int j = 1; j <= edge_beam_counts[d]; j++) @@ -596,3 +735,32 @@ Beam_scoring_problem::score_forbidden_quants (Beam_configuration *config) const config->add (dem, "F"); } +void +Beam_scoring_problem::score_collisions (Beam_configuration *config) const +{ + Real demerits = 0.0; + for (vsize i = 0; i < collisions_.size (); i++) + { + Interval collision_y = collisions_[i].y_; + Real x = collisions_[i].x_; + + Real center_beam_y = y_at (x, config); + Interval beam_y = center_beam_y + collisions_[i].beam_y_; + + Real dist = infinity_f; + if (!intersection (beam_y, collision_y).is_empty ()) + dist = 0.0; + else + dist = min (beam_y.distance (collision_y[DOWN]), + beam_y.distance (collision_y[UP])); + + Real scale_free = + max (parameters.COLLISION_DISTANCE - dist, 0.0)/ + parameters.COLLISION_DISTANCE; + demerits += + collisions_[i].base_penalty_ * + pow (scale_free, 3) * parameters.COLLISION_PENALTY; + } + + config->add (demerits, "C"); +} diff --git a/lily/beam.cc b/lily/beam.cc index 26404ce883..c485813a5a 100644 --- a/lily/beam.cc +++ b/lily/beam.cc @@ -74,6 +74,12 @@ Beam_stem_segment::Beam_stem_segment () dir_ = CENTER; } +bool +beam_segment_less (Beam_segment const& a, Beam_segment const& b) +{ + return a.horizontal_[LEFT] < b.horizontal_[LEFT]; +} + Beam_segment::Beam_segment () { vertical_count_ = 0; @@ -330,6 +336,7 @@ operator <(Beam_stem_segment const &a, typedef map > Position_stem_segments_map; +// TODO - should store result in a property? vector Beam::get_beam_segments (Grob *me_grob, Grob **common) { @@ -622,7 +629,7 @@ Beam::print (SCM grob) string str; SCM properties = Font_interface::text_font_alist_chain (me); - properties = scm_cons(scm_acons (ly_symbol2scm ("font-size"), scm_from_int (-3), SCM_EOL), + properties = scm_cons(scm_acons (ly_symbol2scm ("font-size"), scm_from_int (-5), SCM_EOL), properties); Direction stem_dir = stems.size () ? to_dir (stems[0]->get_property ("direction")) : UP; diff --git a/lily/include/beam-scoring-problem.hh b/lily/include/beam-scoring-problem.hh index ba244589be..7f6ce478d7 100644 --- a/lily/include/beam-scoring-problem.hh +++ b/lily/include/beam-scoring-problem.hh @@ -21,19 +21,24 @@ #ifndef BEAM_SCORING_PROBLEM_HH #define BEAM_SCORING_PROBLEM_HH +#include "beam.hh" #include "interval.hh" -#include "lily-proto.hh" #include "lily-guile.hh" +#include "lily-proto.hh" +#include "main.hh" // DEBUG_BEAM_SCORING #include "std-vector.hh" #include "stem-info.hh" -#include "main.hh" // DEBUG_BEAM_SCORING enum Scorers { // Should be ordered by increasing expensiveness. ORIGINAL_DISTANCE, - SLOPES, + SLOPE_IDEAL, + SLOPE_MUSICAL, + SLOPE_DIRECTION, + HORIZONTAL_INTER, FORBIDDEN, STEM_LENGTHS, + COLLISIONS, NUM_SCORERS, }; @@ -84,11 +89,23 @@ struct Beam_quant_parameters Real HINT_DIRECTION_PENALTY; Real IDEAL_SLOPE_FACTOR; Real ROUND_TO_ZERO_SLOPE; - + Real COLLISION_PENALTY; + Real COLLISION_DISTANCE; + Real HORIZONTAL_INTER_QUANT_PENALTY; + Real STEM_COLLISION_FACTOR; + void fill (Grob *him); }; +struct Beam_collision { + Real x_; + Interval y_; + Real base_penalty_; + // Need to add beam_config->y to get actual offsets. + Interval beam_y_; +}; + /* Parameters for a single beam. Precomputed to save time in @@ -144,18 +161,27 @@ private: // Beam_configurations. Drul_array quant_range; Real beam_translation; - + vector collisions_; + vector segments_; + void init_stems (); - + void init_collisions (vector grobs); + void add_collision (Real x, Interval y, Real factor); + void one_scorer (Beam_configuration* config) const; Beam_configuration *force_score (SCM inspect_quants, const vector &configs) const; + Real y_at (Real x, Beam_configuration const* c) const; // Scoring functions: void score_forbidden_quants (Beam_configuration *config) const; - void score_slopes_dy (Beam_configuration *config) const; + void score_horizontal_inter_quants (Beam_configuration *config) const; + void score_slope_ideal (Beam_configuration *config) const; + void score_slope_direction (Beam_configuration *config) const; + void score_slope_musical (Beam_configuration *config) const; void score_stem_lengths (Beam_configuration* config) const; void generate_quants(vector* scores) const; + void score_collisions (Beam_configuration *config) const; }; #endif /* BEAM_SCORING_PROBLEM_HH */ diff --git a/lily/include/beam.hh b/lily/include/beam.hh index 52be4c4447..f541a216be 100644 --- a/lily/include/beam.hh +++ b/lily/include/beam.hh @@ -33,6 +33,8 @@ struct Beam_segment Beam_segment (); }; +bool beam_segment_less (Beam_segment const& a, Beam_segment const& b); + struct Beam_stem_segment { Beam_stem_segment (); diff --git a/scm/define-grobs.scm b/scm/define-grobs.scm index 15a2695e5f..286490e81b 100644 --- a/scm/define-grobs.scm +++ b/scm/define-grobs.scm @@ -360,6 +360,8 @@ (hint-direction-penalty . 20) (musical-direction-factor . 400) (ideal-slope-factor . 10) + (collision-penalty . 500) + (collision-distance . 0.35) (round-to-zero-slope . 0.02))) (direction . ,ly:beam::calc-direction) -- 2.39.2