2 beam-quanting.cc -- implement Beam quanting functions
4 source file of the GNU LilyPond music typesetter
6 (c) 1997--2005 Han-Wen Nienhuys <hanwen@cs.uu.nl>
7 Jan Nieuwenhuizen <janneke@gnu.org>
16 #include "staff-symbol-referencer.hh"
18 #include "output-def.hh"
19 #include "pointer-group-interface.hh"
20 #include "align-interface.hh"
23 get_detail (SCM alist, SCM sym, Real def)
25 SCM entry = scm_assq (sym, alist);
27 if (scm_is_pair (entry))
28 return robust_scm2double (scm_cdr (entry), def);
33 Beam_quant_parameters::fill (Grob *him)
35 SCM details = him->get_property ("details");
37 INTER_QUANT_PENALTY = get_detail (details, ly_symbol2scm ("inter-quant-penalty"), 1000.0);
38 SECONDARY_BEAM_DEMERIT = get_detail (details, ly_symbol2scm ("secondary-beam-demerit"), 10.0);
39 STEM_LENGTH_DEMERIT_FACTOR = get_detail (details, ly_symbol2scm ("stem-length-demerit-factor"), 5);
40 REGION_SIZE = get_detail (details, ly_symbol2scm ("region-size"), 2);
41 BEAM_EPS = get_detail (details, ly_symbol2scm ("beam-eps"), 1e-3);
43 // possibly ridiculous, but too short stems just won't do
44 STEM_LENGTH_LIMIT_PENALTY = get_detail (details, ly_symbol2scm ("stem-length-limit-penalty"), 5000);
45 DAMPING_DIRECTION_PENALTY = get_detail (details, ly_symbol2scm ("damping-direction-penalty"), 800);
46 MUSICAL_DIRECTION_FACTOR = get_detail (details, ly_symbol2scm ("musical-direction-factor"), 400);
47 IDEAL_SLOPE_FACTOR = get_detail (details, ly_symbol2scm ("ideal-slope-factor"), 10);
48 ROUND_TO_ZERO_SLOPE = get_detail (details, ly_symbol2scm ("round-to-zero-slope"), 0.02);
52 shrink_extra_weight (Real x, Real fac)
54 return fabs (x) * ((x < 0) ? fac : 1.0);
71 - Make all demerits customisable
73 - One sensible check per demerit (what's this --hwn)
75 - Add demerits for quants per se, as to forbid a specific quant
80 best_quant_score_idx (Array<Quant_score> const &qscores)
84 for (int i = qscores.size (); i--;)
86 if (qscores[i].demerits < best)
88 best = qscores [i].demerits;
96 MAKE_SCHEME_CALLBACK (Beam, quanting, 2);
98 Beam::quanting (SCM smob, SCM posns)
100 Grob *me = unsmob_grob (smob);
102 Beam_quant_parameters parameters;
103 parameters.fill (me);
105 Real yl = scm_to_double (scm_car (posns));
106 Real yr = scm_to_double (scm_cdr (posns));
109 Calculations are relative to a unit-scaled staff, i.e. the quants are
110 divided by the current staff_space.
113 Real ss = Staff_symbol_referencer::staff_space (me);
114 Real thickness = Beam::get_thickness (me) / ss;
115 Real slt = Staff_symbol_referencer::line_thickness (me) / ss;
117 Real dy_mus = robust_scm2double (me->get_property ("least-squares-dy"), 0);
119 Real sit = (thickness - slt) / 2;
121 Real hang = 1.0 - (thickness - slt) / 2;
122 Real quants [] = {straddle, sit, inter, hang };
124 int num_quants = int (sizeof (quants) / sizeof (Real));
129 going to REGION_SIZE == 2, yields another 0.6 second with
133 (result indexes between 70 and 575) ? --hwn.
138 Do stem computations. These depend on YL and YR linearly, so we can
139 precompute for every stem 2 factors.
141 Link_array<Grob> stems
142 = extract_grob_array (me, "stems");
143 Array<Stem_info> stem_infos;
144 Array<Real> base_lengths;
145 Array<Real> stem_xposns;
147 Drul_array<bool> dirs_found (0, 0);
149 for (int a = 2; a--;)
150 common[a] = common_refpoint_of_array (stems, me, Axis (a));
152 Grob *fvs = first_visible_stem (me);
153 Grob *lvs = last_visible_stem (me);
154 Real xl = fvs ? fvs->relative_coordinate (common[X_AXIS], X_AXIS) : 0.0;
155 Real xr = fvs ? lvs->relative_coordinate (common[X_AXIS], X_AXIS) : 0.0;
158 We store some info to quickly interpolate.
160 Sometimes my head is screwed on backwards. The stemlength are
161 AFFINE linear in YL and YR. If YL == YR == 0, then we might have
162 stem_y != 0.0, when we're cross staff.
165 for (int i = 0; i < stems.size (); i++)
169 Stem_info si (Stem::get_stem_info (s));
171 stem_infos.push (si);
172 dirs_found[stem_infos.top ().dir_] = true;
174 bool f = to_boolean (s->get_property ("french-beaming"))
175 && s != lvs && s != fvs;
177 base_lengths.push (calc_stem_y (me, s, common, xl, xr,
178 Interval (0, 0), f) / ss);
179 stem_xposns.push (s->relative_coordinate (common[X_AXIS], X_AXIS));
185 Grob *commony = fvs->common_refpoint (lvs, Y_AXIS);
186 xstaff = Align_interface::has_interface (commony);
189 Direction ldir = Direction (stem_infos[0].dir_);
190 Direction rdir = Direction (stem_infos.top ().dir_);
191 bool is_knee = dirs_found[LEFT] && dirs_found[RIGHT];
193 int region_size = (int) parameters.REGION_SIZE;
196 Knees are harder, lets try some more possibilities for knees.
202 Asymetry ? should run to <= region_size ?
204 for (int i = -region_size; i < region_size; i++)
205 for (int j = 0; j < num_quants; j++)
207 quantsl.push (i + quants[j] + int (yl));
208 quantsr.push (i + quants[j] + int (yr));
211 Array<Quant_score> qscores;
213 for (int l = 0; l < quantsl.size (); l++)
214 for (int r = 0; r < quantsr.size (); r++)
224 /* This is a longish function, but we don't separate this out into
225 neat modular separate subfunctions, as the subfunctions would be
226 called for many values of YL, YR. By precomputing various
227 parameters outside of the loop, we can save a lot of time. */
228 for (int i = qscores.size (); i--;)
230 Real d = score_slopes_dy (qscores[i].yl, qscores[i].yr,
233 xstaff, ¶meters);
234 qscores[i].demerits += d;
237 qscores[i].score_card_ += to_string ("S%.2f", d);
241 Real rad = Staff_symbol_referencer::staff_radius (me);
242 Drul_array<int> edge_beam_counts
243 (Stem::beam_multiplicity (stems[0]).length () + 1,
244 Stem::beam_multiplicity (stems.top ()).length () + 1);
246 Real beam_translation = get_beam_translation (me) / ss;
248 Real reasonable_score = (is_knee) ? 200000 : 100;
249 for (int i = qscores.size (); i--;)
250 if (qscores[i].demerits < reasonable_score)
252 Real d = score_forbidden_quants (qscores[i].yl, qscores[i].yr,
253 rad, slt, thickness, beam_translation,
254 edge_beam_counts, ldir, rdir, ¶meters);
255 qscores[i].demerits += d;
258 qscores[i].score_card_ += to_string (" F %.2f", d);
262 for (int i = qscores.size (); i--;)
263 if (qscores[i].demerits < reasonable_score)
265 Real d = score_stem_lengths (stems, stem_infos,
266 base_lengths, stem_xposns,
269 qscores[i].yl, qscores[i].yr, ¶meters);
270 qscores[i].demerits += d;
273 qscores[i].score_card_ += to_string (" L %.2f", d);
277 int best_idx = best_quant_score_idx (qscores);
280 SCM inspect_quants = me->get_property ("inspect-quants");
281 if (to_boolean (me->get_layout ()->lookup_variable (ly_symbol2scm ("debug-beam-quanting")))
282 && scm_is_pair (inspect_quants))
284 Drul_array<Real> ins = ly_scm2interval (inspect_quants);
289 for (; i < qscores.size (); i++)
291 Real d = fabs (qscores[i].yl- ins[LEFT]) + fabs (qscores[i].yr - ins[RIGHT]);
299 programming_error ("can't find quant");
303 Interval final_positions;
306 warning (_ ("no feasible beam position"));
307 final_positions = Interval (0, 0);
311 final_positions = Drul_array<Real> (qscores[best_idx].yl,
312 qscores[best_idx].yr);
317 && to_boolean (me->get_layout ()->lookup_variable (ly_symbol2scm ("debug-beam-quanting"))))
319 qscores[best_idx].score_card_ += to_string ("i%d", best_idx);
322 me->set_property ("quant-score",
323 scm_makfrom0str (qscores[best_idx].score_card_.to_str0 ()));
327 return ly_interval2scm (final_positions);
331 Beam::score_stem_lengths (Link_array<Grob> const &stems,
332 Array<Stem_info> const &stem_infos,
333 Array<Real> const &base_stem_ys,
334 Array<Real> const &stem_xs,
339 Beam_quant_parameters const *parameters)
341 Real limit_penalty = parameters->STEM_LENGTH_LIMIT_PENALTY;
342 Drul_array<Real> score (0, 0);
343 Drul_array<int> count (0, 0);
345 for (int i = 0; i < stems.size (); i++)
348 if (Stem::is_invisible (s))
353 Real beam_y = dx ? yr * (x - xl) / dx + yl * (xr - x) / dx : (yr + yl) / 2;
354 Real current_y = beam_y + base_stem_ys[i];
355 Real length_pen = parameters->STEM_LENGTH_DEMERIT_FACTOR;
357 Stem_info info = stem_infos[i];
358 Direction d = info.dir_;
360 score[d] += limit_penalty * max (0.0, (d * (info.shortest_y_ - current_y)));
362 Real ideal_diff = d * (current_y - info.ideal_y_);
363 Real ideal_score = shrink_extra_weight (ideal_diff, 1.5);
365 /* We introduce a power, to make the scoring strictly
366 convex. Otherwise a symmetric knee beam (up/down/up/down)
367 does not have an optimum in the middle. */
369 ideal_score = pow (ideal_score, 1.1);
371 score[d] += length_pen * ideal_score;
378 score[d] /= max (count[d], 1);
379 while (flip (&d) != DOWN)
382 return score[LEFT] + score[RIGHT];
386 Beam::score_slopes_dy (Real yl, Real yr,
387 Real dy_mus, Real dy_damp,
391 Beam_quant_parameters const *parameters)
397 DAMPING_DIRECTION_PENALTY is a very harsh measure, while for
398 complex beaming patterns, horizontal is often a good choice.
400 TODO: find a way to incorporate the complexity of the beam in this
403 if (fabs (dy / dx) > parameters->ROUND_TO_ZERO_SLOPE
404 && sign (dy_damp) != sign (dy))
405 dem += parameters->DAMPING_DIRECTION_PENALTY;
407 dem += parameters->MUSICAL_DIRECTION_FACTOR
408 * max (0.0, (fabs (dy) - fabs (dy_mus)));
410 Real slope_penalty = parameters->IDEAL_SLOPE_FACTOR;
412 /* Xstaff beams tend to use extreme slopes to get short stems. We
413 put in a penalty here. */
417 /* Huh, why would a too steep beam be better than a too flat one ? */
418 dem += shrink_extra_weight (fabs (dy_damp) - fabs (dy), 1.5)
427 return x - floor (x);
431 TODO: The fixed value SECONDARY_BEAM_DEMERIT is probably flawed:
432 because for 32nd and 64th beams the forbidden quants are relatively
433 more important than stem lengths.
436 Beam::score_forbidden_quants (Real yl, Real yr,
439 Real thickness, Real beam_translation,
440 Drul_array<int> beam_counts,
441 Direction ldir, Direction rdir,
443 Beam_quant_parameters const *parameters)
446 Drul_array<Real> y (yl, yr);
447 Drul_array<Direction> dirs (ldir, rdir);
449 Real extra_demerit = parameters->SECONDARY_BEAM_DEMERIT / (max (beam_counts[LEFT], beam_counts[RIGHT]));
453 Real eps = parameters->BEAM_EPS;
457 for (int j = 1; j <= beam_counts[d]; j++)
459 Direction stem_dir = dirs[d];
462 The 2.2 factor is to provide a little leniency for
463 borderline cases. If we do 2.0, then the upper outer line
464 will be in the gap of the (2, sit) quant, leading to a
467 Real gap1 = y[d] - stem_dir * ((j - 1) * beam_translation + thickness / 2 - slt / 2.2);
468 Real gap2 = y[d] - stem_dir * (j * beam_translation - thickness / 2 + slt / 2.2);
471 gap.add_point (gap1);
472 gap.add_point (gap2);
474 for (Real k = -radius;
475 k <= radius + eps; k += 1.0)
476 if (gap.contains (k))
478 Real dist = min (fabs (gap[UP] - k), fabs (gap[DOWN] - k));
481 this parameter is tuned to grace-stem-length.ly
483 Real fixed_demerit = 0.4;
487 + (1 - fixed_demerit) * (dist / gap.length ()) * 2);
491 while ((flip (&d)) != LEFT);
493 if (max (beam_counts[LEFT], beam_counts[RIGHT]) >= 2)
496 Real sit = (thickness - slt) / 2;
498 Real hang = 1.0 - (thickness - slt) / 2;
503 if (beam_counts[d] >= 2
504 && fabs (y[d] - dirs[d] * beam_translation) < radius + inter)
506 if (dirs[d] == UP && dy <= eps
507 && fabs (my_modf (y[d]) - sit) < eps)
508 dem += extra_demerit;
510 if (dirs[d] == DOWN && dy >= eps
511 && fabs (my_modf (y[d]) - hang) < eps)
512 dem += extra_demerit;
515 if (beam_counts[d] >= 3
516 && fabs (y[d] - 2 * dirs[d] * beam_translation) < radius + inter)
518 if (dirs[d] == UP && dy <= eps
519 && fabs (my_modf (y[d]) - straddle) < eps)
520 dem += extra_demerit;
522 if (dirs[d] == DOWN && dy >= eps
523 && fabs (my_modf (y[d]) - straddle) < eps)
524 dem += extra_demerit;
527 while (flip (&d) != LEFT);