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.
165 Sometimes my head is screwed on backwards. The stemlength are
166 AFFINE linear in YL and YR. If YL == YR == 0, then we might have
167 stem_y != 0.0, when we're cross staff.
170 for (vsize i = 0; i < stems.size (); i++)
174 Stem_info si (Stem::get_stem_info (s));
176 stem_infos.push_back (si);
177 dirs_found[stem_infos.back ().dir_] = true;
179 bool f = to_boolean (s->get_property ("french-beaming"))
180 && s != lvs && s != fvs;
182 base_lengths.push_back (calc_stem_y (me, s, common, xl, xr,
183 Interval (0, 0), f) / ss);
184 stem_xposns.push_back (s->relative_coordinate (common[X_AXIS], X_AXIS));
190 Grob *commony = fvs->common_refpoint (lvs, Y_AXIS);
191 xstaff = Align_interface::has_interface (commony);
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_invisible (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)
385 return score[LEFT] + score[RIGHT];
389 Beam::score_slopes_dy (Real yl, Real yr,
390 Real dy_mus, Real dy_damp,
394 Beam_quant_parameters const *parameters)
400 DAMPING_DIRECTION_PENALTY is a very harsh measure, while for
401 complex beaming patterns, horizontal is often a good choice.
403 TODO: find a way to incorporate the complexity of the beam in this
406 if (sign (dy_damp) != sign (dy))
410 if (fabs (dy_damp / dx) > parameters->ROUND_TO_ZERO_SLOPE)
411 dem += parameters->DAMPING_DIRECTION_PENALTY;
413 dem += parameters->HINT_DIRECTION_PENALTY;
416 dem += parameters->DAMPING_DIRECTION_PENALTY;
419 dem += parameters->MUSICAL_DIRECTION_FACTOR
420 * max (0.0, (fabs (dy) - fabs (dy_mus)));
422 Real slope_penalty = parameters->IDEAL_SLOPE_FACTOR;
424 /* Xstaff beams tend to use extreme slopes to get short stems. We
425 put in a penalty here. */
429 /* Huh, why would a too steep beam be better than a too flat one ? */
430 dem += shrink_extra_weight (fabs (dy_damp) - fabs (dy), 1.5)
439 return x - floor (x);
443 TODO: The fixed value SECONDARY_BEAM_DEMERIT is probably flawed:
444 because for 32nd and 64th beams the forbidden quants are relatively
445 more important than stem lengths.
448 Beam::score_forbidden_quants (Real yl, Real yr,
451 Real thickness, Real beam_translation,
452 Drul_array<int> beam_counts,
453 Direction ldir, Direction rdir,
455 Beam_quant_parameters const *parameters)
458 Drul_array<Real> y (yl, yr);
459 Drul_array<Direction> dirs (ldir, rdir);
461 Real extra_demerit = parameters->SECONDARY_BEAM_DEMERIT / (max (beam_counts[LEFT], beam_counts[RIGHT]));
465 Real eps = parameters->BEAM_EPS;
469 for (int j = 1; j <= beam_counts[d]; j++)
471 Direction stem_dir = dirs[d];
474 The 2.2 factor is to provide a little leniency for
475 borderline cases. If we do 2.0, then the upper outer line
476 will be in the gap of the (2, sit) quant, leading to a
479 Real gap1 = y[d] - stem_dir * ((j - 1) * beam_translation + thickness / 2 - slt / 2.2);
480 Real gap2 = y[d] - stem_dir * (j * beam_translation - thickness / 2 + slt / 2.2);
483 gap.add_point (gap1);
484 gap.add_point (gap2);
486 for (Real k = -radius;
487 k <= radius + eps; k += 1.0)
488 if (gap.contains (k))
490 Real dist = min (fabs (gap[UP] - k), fabs (gap[DOWN] - k));
493 this parameter is tuned to grace-stem-length.ly
495 Real fixed_demerit = 0.4;
499 + (1 - fixed_demerit) * (dist / gap.length ()) * 2);
503 while ((flip (&d)) != LEFT);
505 if (max (beam_counts[LEFT], beam_counts[RIGHT]) >= 2)
508 Real sit = (thickness - slt) / 2;
510 Real hang = 1.0 - (thickness - slt) / 2;
515 if (beam_counts[d] >= 2
516 && fabs (y[d] - dirs[d] * beam_translation) < radius + inter)
518 if (dirs[d] == UP && dy <= eps
519 && fabs (my_modf (y[d]) - sit) < eps)
520 dem += extra_demerit;
522 if (dirs[d] == DOWN && dy >= eps
523 && fabs (my_modf (y[d]) - hang) < eps)
524 dem += extra_demerit;
527 if (beam_counts[d] >= 3
528 && fabs (y[d] - 2 * dirs[d] * beam_translation) < radius + inter)
530 if (dirs[d] == UP && dy <= eps
531 && fabs (my_modf (y[d]) - straddle) < eps)
532 dem += extra_demerit;
534 if (dirs[d] == DOWN && dy >= eps
535 && fabs (my_modf (y[d]) - straddle) < eps)
536 dem += extra_demerit;
539 while (flip (&d) != LEFT);