2 beam-quanting.cc -- implement Beam quanting functions
4 source file of the GNU LilyPond music typesetter
6 (c) 1997--2007 Han-Wen Nienhuys <hanwen@xs4all.nl>
7 Jan Nieuwenhuizen <janneke@gnu.org>
16 #include "align-interface.hh"
17 #include "international.hh"
18 #include "output-def.hh"
19 #include "pointer-group-interface.hh"
20 #include "staff-symbol-referencer.hh"
26 get_detail (SCM alist, SCM sym, Real def)
28 SCM entry = scm_assq (sym, alist);
30 if (scm_is_pair (entry))
31 return robust_scm2double (scm_cdr (entry), def);
36 Beam_quant_parameters::fill (Grob *him)
38 SCM details = him->get_property ("details");
41 TODO: put in define-grobs.scm
43 INTER_QUANT_PENALTY = get_detail (details, ly_symbol2scm ("inter-quant-penalty"), 1000.0);
44 SECONDARY_BEAM_DEMERIT = get_detail (details, ly_symbol2scm ("secondary-beam-demerit"), 10.0);
45 STEM_LENGTH_DEMERIT_FACTOR = get_detail (details, ly_symbol2scm ("stem-length-demerit-factor"), 5);
46 REGION_SIZE = get_detail (details, ly_symbol2scm ("region-size"), 2);
47 BEAM_EPS = get_detail (details, ly_symbol2scm ("beam-eps"), 1e-3);
48 STEM_LENGTH_LIMIT_PENALTY = get_detail (details, ly_symbol2scm ("stem-length-limit-penalty"), 5000);
49 DAMPING_DIRECTION_PENALTY = get_detail (details, ly_symbol2scm ("damping-direction-penalty"), 800);
50 HINT_DIRECTION_PENALTY = get_detail (details, ly_symbol2scm ("hint-direction-penalty"), 20);
51 MUSICAL_DIRECTION_FACTOR = get_detail (details, ly_symbol2scm ("musical-direction-factor"), 400);
52 IDEAL_SLOPE_FACTOR = get_detail (details, ly_symbol2scm ("ideal-slope-factor"), 10);
53 ROUND_TO_ZERO_SLOPE = get_detail (details, ly_symbol2scm ("round-to-zero-slope"), 0.02);
57 shrink_extra_weight (Real x, Real fac)
59 return fabs (x) * ((x < 0) ? fac : 1.0);
68 #if DEBUG_BEAM_SCORING
76 - Make all demerits customisable
78 - One sensible check per demerit (what's this --hwn)
80 - Add demerits for quants per se, as to forbid a specific quant
85 best_quant_score_idx (vector<Quant_score> const &qscores)
89 for (vsize i = qscores.size (); i--;)
91 if (qscores[i].demerits < best)
93 best = qscores [i].demerits;
101 MAKE_SCHEME_CALLBACK (Beam, quanting, 2);
103 Beam::quanting (SCM smob, SCM posns)
105 Grob *me = unsmob_grob (smob);
107 Beam_quant_parameters parameters;
108 parameters.fill (me);
110 Real yl = scm_to_double (scm_car (posns));
111 Real yr = scm_to_double (scm_cdr (posns));
114 Calculations are relative to a unit-scaled staff, i.e. the quants are
115 divided by the current staff_space.
118 Real ss = Staff_symbol_referencer::staff_space (me);
119 Real thickness = Beam::get_thickness (me) / ss;
120 Real slt = Staff_symbol_referencer::line_thickness (me) / ss;
122 Real dy_mus = robust_scm2double (me->get_property ("least-squares-dy"), 0);
124 Real sit = (thickness - slt) / 2;
126 Real hang = 1.0 - (thickness - slt) / 2;
127 Real quants [] = {straddle, sit, inter, hang };
129 int num_quants = int (sizeof (quants) / sizeof (Real));
130 vector<Real> quantsl;
131 vector<Real> quantsr;
134 going to REGION_SIZE == 2, yields another 0.6 second with
138 (result indexes between 70 and 575) ? --hwn.
143 Do stem computations. These depend on YL and YR linearly, so we can
144 precompute for every stem 2 factors.
147 = extract_grob_array (me, "stems");
148 vector<Stem_info> stem_infos;
149 vector<Real> base_lengths;
150 vector<Real> stem_xposns;
152 Drul_array<bool> dirs_found (0, 0);
154 for (int a = 2; a--;)
155 common[a] = common_refpoint_of_array (stems, me, Axis (a));
157 Grob *fvs = first_normal_stem (me);
158 Grob *lvs = last_normal_stem (me);
159 Real xl = fvs ? fvs->relative_coordinate (common[X_AXIS], X_AXIS) : 0.0;
160 Real xr = fvs ? lvs->relative_coordinate (common[X_AXIS], X_AXIS) : 0.0;
163 We store some info to quickly interpolate. The stemlength are
164 affine linear in YL and YR. If YL == YR == 0, then we might have
165 stem_y != 0.0, when we're cross staff.
168 for (vsize i = 0; i < stems.size (); i++)
172 Stem_info si (Stem::get_stem_info (s));
174 stem_infos.push_back (si);
175 dirs_found[stem_infos.back ().dir_] = true;
177 bool f = to_boolean (s->get_property ("french-beaming"))
178 && s != lvs && s != fvs;
180 if (Stem::is_normal_stem (s))
182 base_lengths.push_back (calc_stem_y (me, s, common, xl, xr,
183 Interval (0, 0), f) / ss);
187 base_lengths.push_back (0);
190 stem_xposns.push_back (s->relative_coordinate (common[X_AXIS], X_AXIS));
192 bool xstaff = Align_interface::has_interface (common[Y_AXIS]);
194 Direction ldir = Direction (stem_infos[0].dir_);
195 Direction rdir = Direction (stem_infos.back ().dir_);
196 bool is_knee = dirs_found[LEFT] && dirs_found[RIGHT];
198 int region_size = (int) parameters.REGION_SIZE;
201 Knees are harder, lets try some more possibilities for knees.
207 Asymetry ? should run to <= region_size ?
209 for (int i = -region_size; i < region_size; i++)
210 for (int j = 0; j < num_quants; j++)
212 quantsl.push_back (i + quants[j] + int (yl));
213 quantsr.push_back (i + quants[j] + int (yr));
216 vector<Quant_score> qscores;
218 for (vsize l = 0; l < quantsl.size (); l++)
219 for (vsize r = 0; r < quantsr.size (); r++)
226 qscores.push_back (qs);
229 /* This is a longish function, but we don't separate this out into
230 neat modular separate subfunctions, as the subfunctions would be
231 called for many values of YL, YR. By precomputing various
232 parameters outside of the loop, we can save a lot of time. */
233 for (vsize i = qscores.size (); i--;)
235 Real d = score_slopes_dy (qscores[i].yl, qscores[i].yr,
238 xstaff, ¶meters);
239 qscores[i].demerits += d;
241 #if DEBUG_BEAM_SCORING
242 qscores[i].score_card_ += to_string ("S%.2f", d);
246 Real rad = Staff_symbol_referencer::staff_radius (me);
247 Drul_array<int> edge_beam_counts
248 (Stem::beam_multiplicity (stems[0]).length () + 1,
249 Stem::beam_multiplicity (stems.back ()).length () + 1);
251 Real beam_translation = get_beam_translation (me) / ss;
253 Real reasonable_score = (is_knee) ? 200000 : 100;
254 for (vsize i = qscores.size (); i--;)
255 if (qscores[i].demerits < reasonable_score)
257 Real d = score_forbidden_quants (qscores[i].yl, qscores[i].yr,
258 rad, slt, thickness, beam_translation,
259 edge_beam_counts, ldir, rdir, ¶meters);
260 qscores[i].demerits += d;
262 #if DEBUG_BEAM_SCORING
263 qscores[i].score_card_ += to_string (" F %.2f", d);
267 for (vsize i = qscores.size (); i--;)
268 if (qscores[i].demerits < reasonable_score)
270 Real d = score_stem_lengths (stems, stem_infos,
271 base_lengths, stem_xposns,
274 qscores[i].yl, qscores[i].yr, ¶meters);
275 qscores[i].demerits += d;
277 #if DEBUG_BEAM_SCORING
278 qscores[i].score_card_ += to_string (" L %.2f", d);
282 int best_idx = best_quant_score_idx (qscores);
284 #if DEBUG_BEAM_SCORING
285 SCM inspect_quants = me->get_property ("inspect-quants");
286 if (to_boolean (me->layout ()->lookup_variable (ly_symbol2scm ("debug-beam-scoring")))
287 && scm_is_pair (inspect_quants))
289 Drul_array<Real> ins = ly_scm2interval (inspect_quants);
292 for (vsize i = 0; i < qscores.size (); i++)
294 Real d = fabs (qscores[i].yl- ins[LEFT]) + fabs (qscores[i].yr - ins[RIGHT]);
302 programming_error ("cannot find quant");
306 Interval final_positions;
309 warning (_ ("no feasible beam position"));
310 final_positions = Interval (0, 0);
314 final_positions = Drul_array<Real> (qscores[best_idx].yl,
315 qscores[best_idx].yr);
318 #if DEBUG_BEAM_SCORING
320 && to_boolean (me->layout ()->lookup_variable (ly_symbol2scm ("debug-beam-scoring"))))
322 qscores[best_idx].score_card_ += to_string ("i%d", best_idx);
325 me->set_property ("quant-score",
326 ly_string2scm (qscores[best_idx].score_card_));
330 return ly_interval2scm (final_positions);
334 Beam::score_stem_lengths (vector<Grob*> const &stems,
335 vector<Stem_info> const &stem_infos,
336 vector<Real> const &base_stem_ys,
337 vector<Real> const &stem_xs,
342 Beam_quant_parameters const *parameters)
344 Real limit_penalty = parameters->STEM_LENGTH_LIMIT_PENALTY;
345 Drul_array<Real> score (0, 0);
346 Drul_array<int> count (0, 0);
348 for (vsize i = 0; i < stems.size (); i++)
351 if (!Stem::is_normal_stem (s))
356 Real beam_y = dx ? yr * (x - xl) / dx + yl * (xr - x) / dx : (yr + yl) / 2;
357 Real current_y = beam_y + base_stem_ys[i];
358 Real length_pen = parameters->STEM_LENGTH_DEMERIT_FACTOR;
360 Stem_info info = stem_infos[i];
361 Direction d = info.dir_;
363 score[d] += limit_penalty * max (0.0, (d * (info.shortest_y_ - current_y)));
365 Real ideal_diff = d * (current_y - info.ideal_y_);
366 Real ideal_score = shrink_extra_weight (ideal_diff, 1.5);
368 /* We introduce a power, to make the scoring strictly
369 convex. Otherwise a symmetric knee beam (up/down/up/down)
370 does not have an optimum in the middle. */
372 ideal_score = pow (ideal_score, 1.1);
374 score[d] += length_pen * ideal_score;
381 score[d] /= max (count[d], 1);
382 while (flip (&d) != DOWN);
384 return score[LEFT] + score[RIGHT];
388 Beam::score_slopes_dy (Real yl, Real yr,
389 Real dy_mus, Real dy_damp,
393 Beam_quant_parameters const *parameters)
399 DAMPING_DIRECTION_PENALTY is a very harsh measure, while for
400 complex beaming patterns, horizontal is often a good choice.
402 TODO: find a way to incorporate the complexity of the beam in this
405 if (sign (dy_damp) != sign (dy))
409 if (fabs (dy_damp / dx) > parameters->ROUND_TO_ZERO_SLOPE)
410 dem += parameters->DAMPING_DIRECTION_PENALTY;
412 dem += parameters->HINT_DIRECTION_PENALTY;
415 dem += parameters->DAMPING_DIRECTION_PENALTY;
418 dem += parameters->MUSICAL_DIRECTION_FACTOR
419 * max (0.0, (fabs (dy) - fabs (dy_mus)));
421 Real slope_penalty = parameters->IDEAL_SLOPE_FACTOR;
423 /* Xstaff beams tend to use extreme slopes to get short stems. We
424 put in a penalty here. */
428 /* Huh, why would a too steep beam be better than a too flat one ? */
429 dem += shrink_extra_weight (fabs (dy_damp) - fabs (dy), 1.5)
438 return x - floor (x);
442 TODO: The fixed value SECONDARY_BEAM_DEMERIT is probably flawed:
443 because for 32nd and 64th beams the forbidden quants are relatively
444 more important than stem lengths.
447 Beam::score_forbidden_quants (Real yl, Real yr,
450 Real thickness, Real beam_translation,
451 Drul_array<int> beam_counts,
452 Direction ldir, Direction rdir,
454 Beam_quant_parameters const *parameters)
457 Drul_array<Real> y (yl, yr);
458 Drul_array<Direction> dirs (ldir, rdir);
460 Real extra_demerit = parameters->SECONDARY_BEAM_DEMERIT / (max (beam_counts[LEFT], beam_counts[RIGHT]));
464 Real eps = parameters->BEAM_EPS;
468 for (int j = 1; j <= beam_counts[d]; j++)
470 Direction stem_dir = dirs[d];
473 The 2.2 factor is to provide a little leniency for
474 borderline cases. If we do 2.0, then the upper outer line
475 will be in the gap of the (2, sit) quant, leading to a
478 Real gap1 = y[d] - stem_dir * ((j - 1) * beam_translation + thickness / 2 - slt / 2.2);
479 Real gap2 = y[d] - stem_dir * (j * beam_translation - thickness / 2 + slt / 2.2);
482 gap.add_point (gap1);
483 gap.add_point (gap2);
485 for (Real k = -radius;
486 k <= radius + eps; k += 1.0)
487 if (gap.contains (k))
489 Real dist = min (fabs (gap[UP] - k), fabs (gap[DOWN] - k));
492 this parameter is tuned to grace-stem-length.ly
494 Real fixed_demerit = 0.4;
498 + (1 - fixed_demerit) * (dist / gap.length ()) * 2);
502 while ((flip (&d)) != LEFT);
504 if (max (beam_counts[LEFT], beam_counts[RIGHT]) >= 2)
507 Real sit = (thickness - slt) / 2;
509 Real hang = 1.0 - (thickness - slt) / 2;
514 if (beam_counts[d] >= 2
515 && fabs (y[d] - dirs[d] * beam_translation) < radius + inter)
517 if (dirs[d] == UP && dy <= eps
518 && fabs (my_modf (y[d]) - sit) < eps)
519 dem += extra_demerit;
521 if (dirs[d] == DOWN && dy >= eps
522 && fabs (my_modf (y[d]) - hang) < eps)
523 dem += extra_demerit;
526 if (beam_counts[d] >= 3
527 && fabs (y[d] - 2 * dirs[d] * beam_translation) < radius + inter)
529 if (dirs[d] == UP && dy <= eps
530 && fabs (my_modf (y[d]) - straddle) < eps)
531 dem += extra_demerit;
533 if (dirs[d] == DOWN && dy >= eps
534 && fabs (my_modf (y[d]) - straddle) < eps)
535 dem += extra_demerit;
538 while (flip (&d) != LEFT);