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));
195 Grob *commony = fvs->common_refpoint (lvs, Y_AXIS);
196 xstaff = Align_interface::has_interface (commony);
199 Direction ldir = Direction (stem_infos[0].dir_);
200 Direction rdir = Direction (stem_infos.back ().dir_);
201 bool is_knee = dirs_found[LEFT] && dirs_found[RIGHT];
203 int region_size = (int) parameters.REGION_SIZE;
206 Knees are harder, lets try some more possibilities for knees.
212 Asymetry ? should run to <= region_size ?
214 for (int i = -region_size; i < region_size; i++)
215 for (int j = 0; j < num_quants; j++)
217 quantsl.push_back (i + quants[j] + int (yl));
218 quantsr.push_back (i + quants[j] + int (yr));
221 vector<Quant_score> qscores;
223 for (vsize l = 0; l < quantsl.size (); l++)
224 for (vsize r = 0; r < quantsr.size (); r++)
231 qscores.push_back (qs);
234 /* This is a longish function, but we don't separate this out into
235 neat modular separate subfunctions, as the subfunctions would be
236 called for many values of YL, YR. By precomputing various
237 parameters outside of the loop, we can save a lot of time. */
238 for (vsize i = qscores.size (); i--;)
240 Real d = score_slopes_dy (qscores[i].yl, qscores[i].yr,
243 xstaff, ¶meters);
244 qscores[i].demerits += d;
246 #if DEBUG_BEAM_SCORING
247 qscores[i].score_card_ += to_string ("S%.2f", d);
251 Real rad = Staff_symbol_referencer::staff_radius (me);
252 Drul_array<int> edge_beam_counts
253 (Stem::beam_multiplicity (stems[0]).length () + 1,
254 Stem::beam_multiplicity (stems.back ()).length () + 1);
256 Real beam_translation = get_beam_translation (me) / ss;
258 Real reasonable_score = (is_knee) ? 200000 : 100;
259 for (vsize i = qscores.size (); i--;)
260 if (qscores[i].demerits < reasonable_score)
262 Real d = score_forbidden_quants (qscores[i].yl, qscores[i].yr,
263 rad, slt, thickness, beam_translation,
264 edge_beam_counts, ldir, rdir, ¶meters);
265 qscores[i].demerits += d;
267 #if DEBUG_BEAM_SCORING
268 qscores[i].score_card_ += to_string (" F %.2f", d);
272 for (vsize i = qscores.size (); i--;)
273 if (qscores[i].demerits < reasonable_score)
275 Real d = score_stem_lengths (stems, stem_infos,
276 base_lengths, stem_xposns,
279 qscores[i].yl, qscores[i].yr, ¶meters);
280 qscores[i].demerits += d;
282 #if DEBUG_BEAM_SCORING
283 qscores[i].score_card_ += to_string (" L %.2f", d);
287 int best_idx = best_quant_score_idx (qscores);
289 #if DEBUG_BEAM_SCORING
290 SCM inspect_quants = me->get_property ("inspect-quants");
291 if (to_boolean (me->layout ()->lookup_variable (ly_symbol2scm ("debug-beam-scoring")))
292 && scm_is_pair (inspect_quants))
294 Drul_array<Real> ins = ly_scm2interval (inspect_quants);
297 for (vsize i = 0; i < qscores.size (); i++)
299 Real d = fabs (qscores[i].yl- ins[LEFT]) + fabs (qscores[i].yr - ins[RIGHT]);
307 programming_error ("cannot find quant");
311 Interval final_positions;
314 warning (_ ("no feasible beam position"));
315 final_positions = Interval (0, 0);
319 final_positions = Drul_array<Real> (qscores[best_idx].yl,
320 qscores[best_idx].yr);
323 #if DEBUG_BEAM_SCORING
325 && to_boolean (me->layout ()->lookup_variable (ly_symbol2scm ("debug-beam-scoring"))))
327 qscores[best_idx].score_card_ += to_string ("i%d", best_idx);
330 me->set_property ("quant-score",
331 ly_string2scm (qscores[best_idx].score_card_));
335 return ly_interval2scm (final_positions);
339 Beam::score_stem_lengths (vector<Grob*> const &stems,
340 vector<Stem_info> const &stem_infos,
341 vector<Real> const &base_stem_ys,
342 vector<Real> const &stem_xs,
347 Beam_quant_parameters const *parameters)
349 Real limit_penalty = parameters->STEM_LENGTH_LIMIT_PENALTY;
350 Drul_array<Real> score (0, 0);
351 Drul_array<int> count (0, 0);
353 for (vsize i = 0; i < stems.size (); i++)
356 if (!Stem::is_normal_stem (s))
361 Real beam_y = dx ? yr * (x - xl) / dx + yl * (xr - x) / dx : (yr + yl) / 2;
362 Real current_y = beam_y + base_stem_ys[i];
363 Real length_pen = parameters->STEM_LENGTH_DEMERIT_FACTOR;
365 Stem_info info = stem_infos[i];
366 Direction d = info.dir_;
368 score[d] += limit_penalty * max (0.0, (d * (info.shortest_y_ - current_y)));
370 Real ideal_diff = d * (current_y - info.ideal_y_);
371 Real ideal_score = shrink_extra_weight (ideal_diff, 1.5);
373 /* We introduce a power, to make the scoring strictly
374 convex. Otherwise a symmetric knee beam (up/down/up/down)
375 does not have an optimum in the middle. */
377 ideal_score = pow (ideal_score, 1.1);
379 score[d] += length_pen * ideal_score;
386 score[d] /= max (count[d], 1);
387 while (flip (&d) != DOWN)
390 return score[LEFT] + score[RIGHT];
394 Beam::score_slopes_dy (Real yl, Real yr,
395 Real dy_mus, Real dy_damp,
399 Beam_quant_parameters const *parameters)
405 DAMPING_DIRECTION_PENALTY is a very harsh measure, while for
406 complex beaming patterns, horizontal is often a good choice.
408 TODO: find a way to incorporate the complexity of the beam in this
411 if (sign (dy_damp) != sign (dy))
415 if (fabs (dy_damp / dx) > parameters->ROUND_TO_ZERO_SLOPE)
416 dem += parameters->DAMPING_DIRECTION_PENALTY;
418 dem += parameters->HINT_DIRECTION_PENALTY;
421 dem += parameters->DAMPING_DIRECTION_PENALTY;
424 dem += parameters->MUSICAL_DIRECTION_FACTOR
425 * max (0.0, (fabs (dy) - fabs (dy_mus)));
427 Real slope_penalty = parameters->IDEAL_SLOPE_FACTOR;
429 /* Xstaff beams tend to use extreme slopes to get short stems. We
430 put in a penalty here. */
434 /* Huh, why would a too steep beam be better than a too flat one ? */
435 dem += shrink_extra_weight (fabs (dy_damp) - fabs (dy), 1.5)
444 return x - floor (x);
448 TODO: The fixed value SECONDARY_BEAM_DEMERIT is probably flawed:
449 because for 32nd and 64th beams the forbidden quants are relatively
450 more important than stem lengths.
453 Beam::score_forbidden_quants (Real yl, Real yr,
456 Real thickness, Real beam_translation,
457 Drul_array<int> beam_counts,
458 Direction ldir, Direction rdir,
460 Beam_quant_parameters const *parameters)
463 Drul_array<Real> y (yl, yr);
464 Drul_array<Direction> dirs (ldir, rdir);
466 Real extra_demerit = parameters->SECONDARY_BEAM_DEMERIT / (max (beam_counts[LEFT], beam_counts[RIGHT]));
470 Real eps = parameters->BEAM_EPS;
474 for (int j = 1; j <= beam_counts[d]; j++)
476 Direction stem_dir = dirs[d];
479 The 2.2 factor is to provide a little leniency for
480 borderline cases. If we do 2.0, then the upper outer line
481 will be in the gap of the (2, sit) quant, leading to a
484 Real gap1 = y[d] - stem_dir * ((j - 1) * beam_translation + thickness / 2 - slt / 2.2);
485 Real gap2 = y[d] - stem_dir * (j * beam_translation - thickness / 2 + slt / 2.2);
488 gap.add_point (gap1);
489 gap.add_point (gap2);
491 for (Real k = -radius;
492 k <= radius + eps; k += 1.0)
493 if (gap.contains (k))
495 Real dist = min (fabs (gap[UP] - k), fabs (gap[DOWN] - k));
498 this parameter is tuned to grace-stem-length.ly
500 Real fixed_demerit = 0.4;
504 + (1 - fixed_demerit) * (dist / gap.length ()) * 2);
508 while ((flip (&d)) != LEFT);
510 if (max (beam_counts[LEFT], beam_counts[RIGHT]) >= 2)
513 Real sit = (thickness - slt) / 2;
515 Real hang = 1.0 - (thickness - slt) / 2;
520 if (beam_counts[d] >= 2
521 && fabs (y[d] - dirs[d] * beam_translation) < radius + inter)
523 if (dirs[d] == UP && dy <= eps
524 && fabs (my_modf (y[d]) - sit) < eps)
525 dem += extra_demerit;
527 if (dirs[d] == DOWN && dy >= eps
528 && fabs (my_modf (y[d]) - hang) < eps)
529 dem += extra_demerit;
532 if (beam_counts[d] >= 3
533 && fabs (y[d] - 2 * dirs[d] * beam_translation) < radius + inter)
535 if (dirs[d] == UP && dy <= eps
536 && fabs (my_modf (y[d]) - straddle) < eps)
537 dem += extra_demerit;
539 if (dirs[d] == DOWN && dy >= eps
540 && fabs (my_modf (y[d]) - straddle) < eps)
541 dem += extra_demerit;
544 while (flip (&d) != LEFT);