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 "international.hh"
34 #include "libc-extension.hh"
36 #include "output-def.hh"
37 #include "pointer-group-interface.hh"
38 #include "staff-symbol-referencer.hh"
44 get_detail (SCM alist
, SCM sym
, Real def
)
46 SCM entry
= scm_assq (sym
, alist
);
48 if (scm_is_pair (entry
))
49 return robust_scm2double (scm_cdr (entry
), def
);
54 Beam_quant_parameters::fill (Grob
*him
)
56 SCM details
= him
->get_property ("details");
59 BEAM_EPS
= get_detail (details
, ly_symbol2scm ("beam-eps"), 1e-3);
60 REGION_SIZE
= get_detail (details
, ly_symbol2scm ("region-size"), 2);
63 SECONDARY_BEAM_DEMERIT
= get_detail (details
, ly_symbol2scm ("secondary-beam-demerit"), 10.0);
64 STEM_LENGTH_DEMERIT_FACTOR
= get_detail (details
, ly_symbol2scm ("stem-length-demerit-factor"), 5);
65 HORIZONTAL_INTER_QUANT_PENALTY
= get_detail (details
, ly_symbol2scm ("horizontal-inter-quant"), 500);
67 STEM_LENGTH_LIMIT_PENALTY
= get_detail (details
, ly_symbol2scm ("stem-length-limit-penalty"), 5000);
68 DAMPING_DIRECTION_PENALTY
= get_detail (details
, ly_symbol2scm ("damping-direction-penalty"), 800);
69 HINT_DIRECTION_PENALTY
= get_detail (details
, ly_symbol2scm ("hint-direction-penalty"), 20);
70 MUSICAL_DIRECTION_FACTOR
= get_detail (details
, ly_symbol2scm ("musical-direction-factor"), 400);
71 IDEAL_SLOPE_FACTOR
= get_detail (details
, ly_symbol2scm ("ideal-slope-factor"), 10);
72 ROUND_TO_ZERO_SLOPE
= get_detail (details
, ly_symbol2scm ("round-to-zero-slope"), 0.02);
75 COLLISION_PENALTY
= get_detail (details
, ly_symbol2scm ("collision-penalty"), 500);
76 COLLISION_PADDING
= get_detail (details
, ly_symbol2scm ("collision-padding"), 0.5);
77 STEM_COLLISION_FACTOR
= get_detail (details
, ly_symbol2scm ("stem-collision-factor"), 0.1);
80 // Add x if x is positive, add |x|*fac if x is negative.
82 shrink_extra_weight (Real x
, Real fac
)
84 return fabs (x
) * ((x
< 0) ? fac
: 1.0);
87 /****************************************************************/
89 Beam_configuration::Beam_configuration ()
91 y
= Interval (0.0, 0.0);
93 next_scorer_todo
= ORIGINAL_DISTANCE
;
96 bool Beam_configuration::done () const
98 return next_scorer_todo
>= NUM_SCORERS
;
101 void Beam_configuration::add (Real demerit
, const string
&reason
)
105 #if DEBUG_BEAM_SCORING
107 score_card_
+= to_string (" %s %.2f", reason
.c_str (), demerit
);
111 Beam_configuration
* Beam_configuration::new_config (Interval start
,
114 Beam_configuration
* qs
= new Beam_configuration
;
115 qs
->y
= Interval (int (start
[LEFT
]) + offset
[LEFT
],
116 int (start
[RIGHT
]) + offset
[RIGHT
]);
118 // This orders the sequence so we try combinations closest to the
119 // the ideal offset first.
120 Real start_score
= abs (offset
[RIGHT
]) + abs (offset
[LEFT
]);
121 qs
->demerits
= start_score
/ 1000.0;
122 qs
->next_scorer_todo
= ORIGINAL_DISTANCE
+ 1;
128 Beam_scoring_problem::y_at (Real x
, Beam_configuration
const* p
) const {
129 return p
->y
[LEFT
] + (x
- x_span
[LEFT
]) * p
->y
.delta() / x_span
.delta();
132 /****************************************************************/
137 - Make all demerits customisable
139 - Add demerits for quants per se, as to forbid a specific quant
143 // This is a temporary hack to see how much we can gain by using a
144 // priority queue on the beams to score.
145 static int score_count
= 0;
146 LY_DEFINE (ly_beam_score_count
, "ly:beam-score-count", 0, 0, 0,
148 "count number of beam scores.") {
149 return scm_from_int (score_count
);
152 void Beam_scoring_problem::add_collision (Real x
, Interval y
,
155 if (edge_dirs
[LEFT
] == edge_dirs
[RIGHT
]) {
156 Direction d
= edge_dirs
[LEFT
];
158 Real quant_range_y
= quant_range
[LEFT
][-d
] +
159 (x
- x_span
[LEFT
]) * (quant_range
[RIGHT
][-d
] - quant_range
[LEFT
][-d
]) / x_span
.delta();
161 if (d
*(quant_range_y
- minmax(d
, y
[UP
], y
[DOWN
])) > 0) {
167 c
.beam_y_
.set_empty ();
169 for (vsize j
= 0; j
< segments_
.size (); j
++)
171 if (segments_
[j
].horizontal_
.contains(x
))
172 c
.beam_y_
.add_point (segments_
[j
].vertical_count_
* beam_translation
);
173 if (segments_
[j
].horizontal_
[LEFT
] > x
)
176 c
.beam_y_
.widen (0.5 * beam_thickness
);
180 c
.base_penalty_
= score_factor
;
181 collisions_
.push_back (c
);
184 void Beam_scoring_problem::init_collisions (vector
<Grob
*> grobs
)
186 Grob
* common_x
= NULL
;
187 segments_
= Beam::get_beam_segments (beam
, &common_x
);
188 vector_sort (segments_
, beam_segment_less
);
189 if (common
[X_AXIS
] != common_x
)
191 programming_error ("Disagree on common x. Skipping collisions in beam scoring.");
196 for (vsize i
= 0; i
< grobs
.size (); i
++) {
198 for (Axis a
= X_AXIS
; a
< NO_AXES
; incr (a
))
199 b
[a
] = grobs
[i
]->extent(common
[a
], a
);
201 Real width
= b
[X_AXIS
].length ();
202 Real width_factor
= sqrt (width
/ staff_space
);
206 add_collision (b
[X_AXIS
][d
], b
[Y_AXIS
], width_factor
);
207 while (flip (&d
) != LEFT
);
209 Grob
* stem
= unsmob_grob (grobs
[i
]->get_object ("stem"));
210 if (stem
&& Stem::has_interface (stem
) && Stem::is_normal_stem (stem
))
216 for (set
<Grob
*>::const_iterator
it(stems
.begin ()); it
!= stems
.end (); it
++)
219 Real x
= s
->extent (common
[X_AXIS
], X_AXIS
).center();
221 Direction stem_dir
= get_grob_direction (*it
);
224 y
[-stem_dir
] = Stem::chord_start_y (*it
) + (*it
)->relative_coordinate (common
[Y_AXIS
], Y_AXIS
)
225 - beam
->relative_coordinate (common
[Y_AXIS
], Y_AXIS
);
227 Real factor
= parameters
.STEM_COLLISION_FACTOR
;
228 if (!unsmob_grob (s
->get_object ("beam"))
229 && !Stem::flag (s
).is_empty ())
231 add_collision (x
, y
, factor
);
235 void Beam_scoring_problem::init_stems ()
237 extract_grob_set (beam
, "covered-grobs", collisions
);
238 extract_grob_set (beam
, "stems", stems
);
239 for (int a
= 2; a
--;)
241 common
[a
] = common_refpoint_of_array (stems
, beam
, Axis (a
));
242 common
[a
] = common_refpoint_of_array (collisions
, common
[a
], Axis (a
));
245 Drul_array
<Grob
*> edge_stems(Beam::first_normal_stem (beam
),
246 Beam::last_normal_stem (beam
));
249 x_span
[d
] = edge_stems
[d
] ? edge_stems
[d
]->relative_coordinate (common
[X_AXIS
], X_AXIS
) : 0.0;
250 while (flip (&d
) != LEFT
);
252 Drul_array
<bool> dirs_found (0, 0);
253 for (vsize i
= 0; i
< stems
.size (); i
++)
256 if (!Stem::is_normal_stem (s
))
259 Stem_info
si (Stem::get_stem_info (s
));
260 si
.scale (1 / staff_space
);
261 stem_infos
.push_back (si
);
262 dirs_found
[si
.dir_
] = true;
264 bool f
= to_boolean (s
->get_property ("french-beaming"))
265 && s
!= edge_stems
[LEFT
] && s
!= edge_stems
[RIGHT
];
267 Real y
= Beam::calc_stem_y (beam
, s
, common
, x_span
[LEFT
], x_span
[RIGHT
], CENTER
,
269 base_lengths
.push_back (y
/ staff_space
);
270 stem_xpositions
.push_back (s
->relative_coordinate (common
[X_AXIS
], X_AXIS
));
273 edge_dirs
= Drul_array
<Direction
> (CENTER
, CENTER
);
274 if (stem_infos
.size ())
276 edge_dirs
= Drul_array
<Direction
> (stem_infos
[0].dir_
,
277 stem_infos
.back().dir_
);
280 is_xstaff
= Align_interface::has_interface (common
[Y_AXIS
]);
281 is_knee
= dirs_found
[LEFT
] && dirs_found
[RIGHT
];
283 staff_radius
= Staff_symbol_referencer::staff_radius (beam
);
284 edge_beam_counts
= Drul_array
<int>
285 (Stem::beam_multiplicity (stems
[0]).length () + 1,
286 Stem::beam_multiplicity (stems
.back ()).length () + 1);
288 // TODO - why are we dividing by staff_space?
289 beam_translation
= Beam::get_beam_translation (beam
) / staff_space
;
294 quant_range
[d
].set_full ();
298 Real stem_offset
= edge_stems
[d
]->relative_coordinate (common
[Y_AXIS
], Y_AXIS
)
299 - beam
->relative_coordinate (common
[Y_AXIS
], Y_AXIS
);
300 Interval heads
= Stem::head_positions(edge_stems
[d
]) * 0.5 * staff_space
;
302 Direction ed
= edge_dirs
[d
];
303 heads
.widen(0.5 * staff_space
304 + (edge_beam_counts
[d
] - 1) * beam_translation
+ beam_thickness
* .5);
305 quant_range
[d
][-ed
] = heads
[ed
] + stem_offset
;
307 while (flip (&d
) != LEFT
);
309 init_collisions (collisions
);
312 Beam_scoring_problem::Beam_scoring_problem (Grob
*me
, Drul_array
<Real
> ys
)
318 Calculations are relative to a unit-scaled staff, i.e. the quants are
319 divided by the current staff_space.
321 staff_space
= Staff_symbol_referencer::staff_space (me
);
322 beam_thickness
= Beam::get_beam_thickness (me
) / staff_space
;
323 line_thickness
= Staff_symbol_referencer::line_thickness (me
) / staff_space
;
325 // This is the least-squares DY, corrected for concave beams.
326 musical_dy
= robust_scm2double (me
->get_property ("least-squares-dy"), 0);
328 parameters
.fill (me
);
333 Beam_scoring_problem::generate_quants (vector
<Beam_configuration
*> *scores
) const
335 int region_size
= (int) parameters
.REGION_SIZE
;
337 // Knees and collisions are harder, lets try some more possibilities
340 if (collisions_
.size ())
344 Real sit
= (beam_thickness
- line_thickness
) / 2;
346 Real hang
= 1.0 - (beam_thickness
- line_thickness
) / 2;
347 Real base_quants
[] = {straddle
, sit
, inter
, hang
};
348 int num_base_quants
= int (sizeof (base_quants
) / sizeof (Real
));
351 Asymetry ? should run to <= region_size ?
353 vector
<Real
> unshifted_quants
;
354 for (int i
= -region_size
; i
< region_size
; i
++)
355 for (int j
= 0; j
< num_base_quants
; j
++)
357 unshifted_quants
.push_back (i
+ base_quants
[j
]);
360 for (vsize i
= 0; i
< unshifted_quants
.size (); i
++)
361 for (vsize j
= 0; j
< unshifted_quants
.size (); j
++)
363 Beam_configuration
*c
=
364 Beam_configuration::new_config (unquanted_y
,
365 Interval (unshifted_quants
[i
],
366 unshifted_quants
[j
]));
371 if (!quant_range
[d
].contains (c
->y
[d
]))
378 while (flip (&d
) != LEFT
);
380 scores
->push_back (c
);
386 void Beam_scoring_problem::one_scorer (Beam_configuration
* config
) const
389 switch (config
->next_scorer_todo
) {
391 score_slope_ideal (config
);
393 case SLOPE_DIRECTION
:
394 score_slope_direction (config
);
397 score_slope_musical (config
);
400 score_forbidden_quants (config
);
403 score_stem_lengths (config
);
406 score_collisions (config
);
408 case HORIZONTAL_INTER
:
409 score_horizontal_inter_quants (config
);
413 case ORIGINAL_DISTANCE
:
417 config
->next_scorer_todo
++;
422 Beam_scoring_problem::force_score (SCM inspect_quants
, const vector
<Beam_configuration
*> &configs
) const
424 Drul_array
<Real
> ins
= ly_scm2interval (inspect_quants
);
426 Beam_configuration
*best
= NULL
;
427 for (vsize i
= 0; i
< configs
.size (); i
++)
429 Real d
= fabs (configs
[i
]->y
[LEFT
]- ins
[LEFT
]) + fabs (configs
[i
]->y
[RIGHT
] - ins
[RIGHT
]);
437 programming_error ("cannot find quant");
439 while (!best
->done ())
446 Beam_scoring_problem::solve () const {
447 vector
<Beam_configuration
*> configs
;
448 generate_quants (&configs
);
450 Beam_configuration
*best
= NULL
;
453 to_boolean (beam
->layout ()->lookup_variable (ly_symbol2scm ("debug-beam-scoring")));
454 SCM inspect_quants
= beam
->get_property ("inspect-quants");
455 if (scm_is_pair (inspect_quants
))
458 best
= force_score (inspect_quants
, configs
);
462 std::priority_queue
<Beam_configuration
*, std::vector
<Beam_configuration
*>,
463 Beam_configuration_less
> queue
;
464 for (vsize i
= 0; i
< configs
.size(); i
++)
465 queue
.push(configs
[i
]);
470 It would be neat if we generated new configurations on the
471 fly, depending on the best complete score so far, eg.
474 if (best->demerits < sqrt(queue.size())
476 while (best->demerits > sqrt(queue.size()) {
477 generate and insert new configuration
481 that would allow us to do away with region_size altogether.
494 Interval final_positions
= best
->y
;
496 #if DEBUG_BEAM_SCORING
501 for (vsize i
= 0; i
< configs
.size (); i
++)
503 if (configs
[i
]->done ())
507 string card
= best
->score_card_
+ to_string (" c%d/%d", completed
, configs
.size());
508 beam
->set_property ("annotation", ly_string2scm (card
));
512 junk_pointers (configs
);
513 return final_positions
;
517 Beam_scoring_problem::score_stem_lengths (Beam_configuration
* config
) const
519 Real limit_penalty
= parameters
.STEM_LENGTH_LIMIT_PENALTY
;
520 Drul_array
<Real
> score (0, 0);
521 Drul_array
<int> count (0, 0);
523 for (vsize i
= 0; i
< stem_xpositions
.size (); i
++)
525 Real x
= stem_xpositions
[i
];
526 Real dx
= x_span
.delta ();
528 ? config
->y
[RIGHT
] * (x
- x_span
[LEFT
]) / dx
+ config
->y
[LEFT
] * (x_span
[RIGHT
] - x
) / dx
529 : (config
->y
[RIGHT
] + config
->y
[LEFT
]) / 2;
530 Real current_y
= beam_y
+ base_lengths
[i
];
531 Real length_pen
= parameters
.STEM_LENGTH_DEMERIT_FACTOR
;
533 Stem_info info
= stem_infos
[i
];
534 Direction d
= info
.dir_
;
536 score
[d
] += limit_penalty
* max (0.0, (d
* (info
.shortest_y_
- current_y
)));
538 Real ideal_diff
= d
* (current_y
- info
.ideal_y_
);
539 Real ideal_score
= shrink_extra_weight (ideal_diff
, 1.5);
541 /* We introduce a power, to make the scoring strictly
542 convex. Otherwise a symmetric knee beam (up/down/up/down)
543 does not have an optimum in the middle. */
545 ideal_score
= pow (ideal_score
, 1.1);
547 score
[d
] += length_pen
* ideal_score
;
551 /* Divide by number of stems, to make the measure scale-free. */
554 score
[d
] /= max (count
[d
], 1);
555 while (flip (&d
) != DOWN
);
557 config
->add (score
[LEFT
] + score
[RIGHT
], "L");
561 Beam_scoring_problem::score_slope_direction (Beam_configuration
*config
) const
563 Real dy
= config
->y
.delta ();
564 Real damped_dy
= unquanted_y
.delta();
567 DAMPING_DIRECTION_PENALTY is a very harsh measure, while for
568 complex beaming patterns, horizontal is often a good choice.
570 TODO: find a way to incorporate the complexity of the beam in this
573 if (sign (damped_dy
) != sign (dy
))
577 if (fabs (damped_dy
/ x_span
.delta ()) > parameters
.ROUND_TO_ZERO_SLOPE
)
578 dem
+= parameters
.DAMPING_DIRECTION_PENALTY
;
580 dem
+= parameters
.HINT_DIRECTION_PENALTY
;
583 dem
+= parameters
.DAMPING_DIRECTION_PENALTY
;
586 config
->add (dem
, "Sd");
589 // Score for going against the direction of the musical pattern
591 Beam_scoring_problem::score_slope_musical (Beam_configuration
*config
) const
593 Real dy
= config
->y
.delta ();
594 Real dem
= parameters
.MUSICAL_DIRECTION_FACTOR
595 * max (0.0, (fabs (dy
) - fabs (musical_dy
)));
596 config
->add (dem
, "Sm");
599 // Score deviation from calculated ideal slope.
601 Beam_scoring_problem::score_slope_ideal (Beam_configuration
*config
) const
603 Real dy
= config
->y
.delta ();
604 Real damped_dy
= unquanted_y
.delta();
607 Real slope_penalty
= parameters
.IDEAL_SLOPE_FACTOR
;
609 /* Xstaff beams tend to use extreme slopes to get short stems. We
610 put in a penalty here. */
614 /* Huh, why would a too steep beam be better than a too flat one ? */
615 dem
+= shrink_extra_weight (fabs (damped_dy
) - fabs (dy
), 1.5)
618 config
->add (dem
, "Si");
624 return x
- floor (x
);
627 // TODO - there is some overlap with forbidden quants, but for
628 // horizontal beams, it is much more serious to have stafflines
629 // appearing in the wrong place, so we have a separate scorer.
631 Beam_scoring_problem::score_horizontal_inter_quants (Beam_configuration
*config
) const
633 if (config
->y
.delta () == 0.0
634 && abs (config
->y
[LEFT
]) < staff_radius
* staff_space
)
636 Real yshift
= config
->y
[LEFT
] - 0.5 * staff_space
;
637 if (fabs (my_round (yshift
) - yshift
) < 0.01 * staff_space
)
638 config
->add (parameters
.HORIZONTAL_INTER_QUANT_PENALTY
, "H");
643 TODO: The fixed value SECONDARY_BEAM_DEMERIT is probably flawed:
644 because for 32nd and 64th beams the forbidden quants are relatively
645 more important than stem lengths.
648 Beam_scoring_problem::score_forbidden_quants (Beam_configuration
*config
) const
650 Real dy
= config
->y
.delta ();
652 Real extra_demerit
= parameters
.SECONDARY_BEAM_DEMERIT
/
653 max (edge_beam_counts
[LEFT
], edge_beam_counts
[RIGHT
]);
657 Real eps
= parameters
.BEAM_EPS
;
661 for (int j
= 1; j
<= edge_beam_counts
[d
]; j
++)
663 Direction stem_dir
= edge_dirs
[d
];
666 The 2.2 factor is to provide a little leniency for
667 borderline cases. If we do 2.0, then the upper outer line
668 will be in the gap of the (2, sit) quant, leading to a
671 Real gap1
= config
->y
[d
] - stem_dir
* ((j
- 1) * beam_translation
+ beam_thickness
/ 2 - line_thickness
/ 2.2);
672 Real gap2
= config
->y
[d
] - stem_dir
* (j
* beam_translation
- beam_thickness
/ 2 + line_thickness
/ 2.2);
675 gap
.add_point (gap1
);
676 gap
.add_point (gap2
);
678 for (Real k
= -staff_radius
;
679 k
<= staff_radius
+ eps
; k
+= 1.0)
680 if (gap
.contains (k
))
682 Real dist
= min (fabs (gap
[UP
] - k
), fabs (gap
[DOWN
] - k
));
685 this parameter is tuned to grace-stem-length.ly
687 Real fixed_demerit
= 0.4;
691 + (1 - fixed_demerit
) * (dist
/ gap
.length ()) * 2);
695 while ((flip (&d
)) != LEFT
);
697 if (max (edge_beam_counts
[LEFT
], edge_beam_counts
[RIGHT
]) >= 2)
700 Real sit
= (beam_thickness
- line_thickness
) / 2;
702 Real hang
= 1.0 - (beam_thickness
- line_thickness
) / 2;
707 if (edge_beam_counts
[d
] >= 2
708 && fabs (config
->y
[d
] - edge_dirs
[d
] * beam_translation
) < staff_radius
+ inter
)
710 // TODO up/down symmetry.
711 if (edge_dirs
[d
] == UP
&& dy
<= eps
712 && fabs (my_modf (config
->y
[d
]) - sit
) < eps
)
713 dem
+= extra_demerit
;
715 if (edge_dirs
[d
] == DOWN
&& dy
>= eps
716 && fabs (my_modf (config
->y
[d
]) - hang
) < eps
)
717 dem
+= extra_demerit
;
720 if (edge_beam_counts
[d
] >= 3
721 && fabs (config
->y
[d
] - 2 * edge_dirs
[d
] * beam_translation
) < staff_radius
+ inter
)
723 // TODO up/down symmetry.
724 if (edge_dirs
[d
] == UP
&& dy
<= eps
725 && fabs (my_modf (config
->y
[d
]) - straddle
) < eps
)
726 dem
+= extra_demerit
;
728 if (edge_dirs
[d
] == DOWN
&& dy
>= eps
729 && fabs (my_modf (config
->y
[d
]) - straddle
) < eps
)
730 dem
+= extra_demerit
;
733 while (flip (&d
) != LEFT
);
736 config
->add (dem
, "F");
740 Beam_scoring_problem::score_collisions (Beam_configuration
*config
) const
743 for (vsize i
= 0; i
< collisions_
.size (); i
++)
745 Interval collision_y
= collisions_
[i
].y_
;
746 Real x
= collisions_
[i
].x_
;
748 Real center_beam_y
= y_at (x
, config
);
749 Interval beam_y
= center_beam_y
+ collisions_
[i
].beam_y_
;
751 Real dist
= infinity_f
;
752 if (!intersection (beam_y
, collision_y
).is_empty ())
755 dist
= min (beam_y
.distance (collision_y
[DOWN
]),
756 beam_y
.distance (collision_y
[UP
]));
759 max (parameters
.COLLISION_PADDING
- dist
, 0.0)/
760 parameters
.COLLISION_PADDING
;
762 collisions_
[i
].base_penalty_
*
763 pow (scale_free
, 3) * parameters
.COLLISION_PENALTY
;
766 config
->add (demerits
, "C");