]> git.donarmstrong.com Git - lilypond.git/blob - lily/beam-quanting.cc
Configure only pristine build tree or on user
[lilypond.git] / lily / beam-quanting.cc
1 /*
2   beam-quanting.cc -- implement Beam quanting functions
3   
4   source file of the GNU LilyPond music typesetter
5   
6   (c) 1997--2004 Han-Wen Nienhuys <hanwen@cs.uu.nl>
7   Jan Nieuwenhuizen <janneke@gnu.org>
8   
9
10   
11 */
12
13
14
15 #include <math.h>
16
17 #include "warn.hh"
18 #include "grob.hh"
19 #include "staff-symbol-referencer.hh"
20 #include "beam.hh"
21 #include "stem.hh"
22 #include "output-def.hh"
23 #include "group-interface.hh"
24 #include "align-interface.hh"
25
26 const int INTER_QUANT_PENALTY = 1000;
27 const Real SECONDARY_BEAM_DEMERIT  = 10.0;
28 const int STEM_LENGTH_DEMERIT_FACTOR = 5;
29
30 /*
31   threshold to combat rounding errors.
32  */
33 const Real BEAM_EPS = 1e-3; 
34
35 // possibly ridiculous, but too short stems just won't do
36 const int STEM_LENGTH_LIMIT_PENALTY = 5000;
37 const int DAMPING_DIRECTION_PENALTY = 800;
38 const int MUSICAL_DIRECTION_FACTOR = 400;
39 const int IDEAL_SLOPE_FACTOR = 10;
40 const Real ROUND_TO_ZERO_SLOPE = 0.02;
41 const int ROUND_TO_ZERO_POINTS = 4;
42
43 extern bool debug_beam_quanting_flag;
44
45 static Real
46 shrink_extra_weight (Real x, Real fac)
47 {
48   return fabs (x) * ((x < 0) ? fac : 1.0);
49 }
50
51
52 struct Quant_score
53 {
54   Real yl;
55   Real yr;
56   Real demerits;
57
58 #if DEBUG_QUANTING
59   String score_card_;
60 #endif
61 };
62
63
64 /*
65   TODO:
66   
67    - Make all demerits customisable
68
69    - One sensible check per demerit (what's this --hwn)
70
71    - Add demerits for quants per se, as to forbid a specific quant
72      entirely
73
74 */
75
76 int best_quant_score_idx (Array<Quant_score>  const & qscores)
77 {
78   Real best = 1e6;
79   int best_idx = -1;
80   for (int i = qscores.size (); i--;)
81     {
82       if (qscores[i].demerits < best)
83         {
84           best = qscores [i].demerits ;
85           best_idx = i;
86         }
87     }
88
89   return best_idx;
90 }
91   
92 MAKE_SCHEME_CALLBACK (Beam, quanting, 1);
93 SCM
94 Beam::quanting (SCM smob)
95 {
96   Grob *me = unsmob_grob (smob);
97
98   SCM s = me->get_property ("positions");
99   Real yl = ly_scm2double (ly_car (s));
100   Real yr = ly_scm2double (ly_cdr (s));
101
102
103   /*
104     Calculations are relative to a unit-scaled staff, i.e. the quants are
105     divided by the current staff_space.
106     
107    */
108   Real ss = Staff_symbol_referencer::staff_space (me);
109   Real thickness = Beam::get_thickness (me) / ss ;
110   Real slt = Staff_symbol_referencer::line_thickness (me) / ss;
111
112   SCM sdy = me->get_property ("least-squares-dy");
113   Real dy_mus = ly_c_number_p (sdy) ? ly_scm2double (sdy) : 0.0;
114   
115   Real straddle = 0.0;
116   Real sit = (thickness - slt) / 2;
117   Real inter = 0.5;
118   Real hang = 1.0 - (thickness - slt) / 2;
119   Real quants [] = {straddle, sit, inter, hang };
120   
121   int num_quants = int (sizeof (quants)/sizeof (Real));
122   Array<Real> quantsl;
123   Array<Real> quantsr;
124
125   /*
126     going to REGION_SIZE == 2, yields another 0.6 second with
127     wtk1-fugue2.
128
129
130     (result indexes between 70 and 575)  ? --hwn. 
131
132   */
133
134
135   
136   /*
137     Do stem computations.  These depend on YL and YR linearly, so we can
138     precompute for every stem 2 factors.
139    */
140   Link_array<Grob> stems=
141     Pointer_group_interface__extract_grobs (me, (Grob*)0, "stems");
142   Array<Stem_info> stem_infos;
143   Array<Real> base_lengths;
144   Array<Real> stem_xposns;  
145
146   Drul_array<bool> dirs_found (0,0);
147   Grob *common[2];
148   for (int a = 2; a--;)
149     common[a] = common_refpoint_of_array (stems, me, Axis (a));
150
151   Grob * fvs = first_visible_stem (me);
152   Grob *lvs = last_visible_stem (me);
153   Real xl = fvs ? fvs->relative_coordinate (common[X_AXIS], X_AXIS) : 0.0;
154   Real xr = fvs ? lvs->relative_coordinate (common[X_AXIS], X_AXIS) : 0.0;
155
156   /*
157     We store some info to quickly interpolate.
158
159     Sometimes my head is screwed on backwards.  The stemlength are
160     AFFINE linear in YL and YR. If YL == YR == 0, then we might have
161     stem_y != 0.0, when we're cross staff.
162     
163    */
164   for (int i= 0; i < stems.size (); i++)
165     {
166       Grob*s = stems[i];
167
168       Stem_info si (Stem::get_stem_info (s));
169       si.scale (1 / ss);
170       stem_infos.push (si);
171       dirs_found[stem_infos.top ().dir_] = true;
172
173       bool f = to_boolean (s->get_property ("french-beaming"))
174          && s != lvs && s != fvs;
175
176       base_lengths.push (calc_stem_y (me, s, common, xl, xr,
177                                       Interval (0,0), f) / ss);
178       stem_xposns.push (s->relative_coordinate (common[X_AXIS], X_AXIS));
179     }
180
181   bool xstaff= false;
182   if (lvs && fvs)
183     {
184       Grob *commony = fvs->common_refpoint (lvs, Y_AXIS);
185       xstaff = Align_interface::has_interface (commony);
186     }
187   
188   Direction ldir = Direction (stem_infos[0].dir_);
189   Direction rdir = Direction (stem_infos.top ().dir_);
190   bool is_knee = dirs_found[LEFT] && dirs_found[RIGHT];
191
192
193   int region_size = REGION_SIZE;
194   /*
195     Knees are harder, lets try some more possibilities for knees. 
196    */
197   if (is_knee)
198     region_size += 2;
199
200   /*
201     Asymetry ? should run to <= region_size ?
202    */
203   for (int i = -region_size ; i < region_size; i++)
204     for (int j = 0; j < num_quants; j++)
205       {
206         quantsl.push (i + quants[j] + int (yl));
207         quantsr.push (i + quants[j] + int (yr));
208       }
209
210   Array<Quant_score> qscores;
211   
212   for (int l =0; l < quantsl.size (); l++)  
213     for (int r =0; r < quantsr.size (); r++)
214       {
215         Quant_score qs;
216         qs.yl = quantsl[l];
217         qs.yr = quantsr[r];
218         qs.demerits = 0.0;
219         
220         qscores.push (qs);
221       }
222
223   /* This is a longish function, but we don't separate this out into
224      neat modular separate subfunctions, as the subfunctions would be
225      called for many values of YL, YR. By precomputing various
226      parameters outside of the loop, we can save a lot of time. */
227   for (int i = qscores.size (); i--;)
228     {
229       Real d =  score_slopes_dy (qscores[i].yl, qscores[i].yr,
230                                  dy_mus, yr- yl, 
231                                  xr - xl,
232                                  xstaff);
233       qscores[i].demerits += d;
234
235 #if DEBUG_QUANTING
236       qscores[i].score_card_ += to_string ("S%.2f",d);
237 #endif
238     }
239
240   Real rad = Staff_symbol_referencer::staff_radius (me);
241
242   
243   
244   Drul_array<int> edge_beam_counts
245     (Stem::beam_multiplicity (stems[0]).length  () + 1,
246      Stem::beam_multiplicity (stems.top ()).length  () + 1);
247   
248   Real beam_translation = get_beam_translation (me) / ss;
249
250   Real reasonable_score = (is_knee) ? 200000 : 100;
251   for (int i = qscores.size (); i--;)
252     if (qscores[i].demerits < reasonable_score)
253       {
254         Real d = score_forbidden_quants (qscores[i].yl, qscores[i].yr,
255                                      rad, slt, thickness, beam_translation,
256                                      edge_beam_counts, ldir, rdir); 
257         qscores[i].demerits += d;
258
259 #if DEBUG_QUANTING
260         qscores[i].score_card_ += to_string (" F %.2f", d);
261 #endif
262       }
263
264   for (int i = qscores.size (); i--;)
265     if (qscores[i].demerits < reasonable_score)
266       {
267         Real d=score_stem_lengths (stems, stem_infos,
268                                  base_lengths, stem_xposns,
269                                  xl, xr,
270                                  is_knee,
271                                  qscores[i].yl, qscores[i].yr);
272         qscores[i].demerits +=  d;
273
274 #if DEBUG_QUANTING
275         qscores[i].score_card_ += to_string (" L %.2f", d);
276 #endif
277       }
278
279   int best_idx = best_quant_score_idx (qscores);
280
281
282 #if DEBUG_QUANTING
283   SCM inspect_quants = me->get_property ("inspect-quants");
284   if (debug_beam_quanting_flag
285       && ly_c_pair_p (inspect_quants))
286     {
287       Drul_array<Real> ins = ly_scm2interval (inspect_quants);
288
289       int i = 0;
290
291       Real mindist = 1e6;
292       for (; i < qscores.size (); i ++)
293         {
294           Real d =fabs (qscores[i].yl- ins[LEFT]) + fabs (qscores[i].yr - ins[RIGHT]);
295           if (d < mindist)
296             {
297               best_idx = i;
298               mindist= d;
299             }
300         }
301       if (mindist > 1e5)
302         programming_error ("Could not find quant.");
303     }
304 #endif
305   
306   me->set_property ("positions",
307                     ly_interval2scm (Drul_array<Real> (qscores[best_idx].yl,
308                                                        qscores[best_idx].yr)));
309 #if DEBUG_QUANTING
310   if (debug_beam_quanting_flag)
311     {
312       qscores[best_idx].score_card_ += to_string ("i%d", best_idx);
313       
314       // debug quanting
315       me->set_property ("quant-score",
316                              scm_makfrom0str (qscores[best_idx].score_card_.to_str0 ()));
317     }
318 #endif
319
320   return SCM_UNSPECIFIED;
321 }
322
323 Real
324 Beam::score_stem_lengths (Link_array<Grob> const &stems,
325                           Array<Stem_info> const &stem_infos,
326                           Array<Real> const &base_stem_ys,
327                           Array<Real> const &stem_xs,
328                           Real xl, Real xr, 
329                           bool knee, 
330                           Real yl, Real yr)
331 {
332   Real limit_penalty = STEM_LENGTH_LIMIT_PENALTY;
333   Drul_array<Real> score (0, 0);
334   Drul_array<int> count (0, 0);
335   
336   for (int i=0; i < stems.size (); i++)
337     {
338       Grob* s = stems[i];
339       if (Stem::is_invisible (s))
340         continue;
341
342       Real x = stem_xs[i];
343       Real dx = xr-xl;
344       Real beam_y = dx ? yr *(x - xl)/dx + yl * ( xr - x)/dx : (yr + yl)/2;
345       Real current_y = beam_y + base_stem_ys[i];
346       Real length_pen = STEM_LENGTH_DEMERIT_FACTOR;
347       
348       Stem_info info = stem_infos[i];
349       Direction d = info.dir_;
350
351       score[d] += limit_penalty * (0 >? (d * (info.shortest_y_ - current_y)));
352       
353       Real ideal_diff = d * (current_y - info.ideal_y_);
354       Real ideal_score = shrink_extra_weight (ideal_diff, 1.5);
355       
356       /* We introduce a power, to make the scoring strictly
357          convex. Otherwise a symmetric knee beam (up/down/up/down)
358          does not have an optimum in the middle. */
359       if (knee)
360         ideal_score = pow (ideal_score, 1.1);
361       
362       score[d] += length_pen * ideal_score;
363
364       count[d] ++;
365     }
366
367   Direction d = DOWN;
368   do
369     { 
370       score[d] /= (count[d] >? 1);
371     }
372   while (flip (&d) != DOWN);
373
374   return score[LEFT]+score[RIGHT];
375 }
376
377 Real
378 Beam::score_slopes_dy (Real yl, Real yr,
379                        Real dy_mus, Real dy_damp,
380                        Real dx,
381                        bool xstaff)
382 {
383   Real dy = yr - yl;
384   Real dem = 0.0;
385
386   /*
387     DAMPING_DIRECTION_PENALTY is a very harsh measure, while for
388     complex beaming patterns, horizontal is often a good choice.
389
390     TODO: find a way to incorporate the complexity of the beam in this
391     penalty.
392    */
393   if (fabs (dy/dx) > ROUND_TO_ZERO_SLOPE
394       && sign (dy_damp) != sign (dy))
395     {
396       dem += DAMPING_DIRECTION_PENALTY;
397     }
398
399    dem += MUSICAL_DIRECTION_FACTOR * (0 >? (fabs (dy) - fabs (dy_mus)));
400
401
402    Real slope_penalty = IDEAL_SLOPE_FACTOR;
403
404    /* Xstaff beams tend to use extreme slopes to get short stems. We
405       put in a penalty here. */
406    if (xstaff)
407      slope_penalty *= 10;
408
409    /* Huh, why would a too steep beam be better than a too flat one ? */
410    dem += shrink_extra_weight (fabs (dy_damp) - fabs (dy), 1.5)
411      * slope_penalty;
412
413 #if 0
414    /*
415      almost zero slopes look like errors in horizontal beams. 
416     */
417    /*
418      This causes too much problems, because horizontal depends on
419      horizontal spacing details.  These errors should be dealt with
420      through concaveness. --hwn.
421     */
422    if (fabs (dy) > 1e-3
423        && fabs (dy / dx) < ROUND_TO_ZERO_SLOPE)
424      dem += ROUND_TO_ZERO_POINTS;
425 #endif
426    
427    return dem;
428 }
429
430 static Real
431 my_modf (Real x)
432 {
433   return x - floor (x);
434 }
435
436
437 /*
438   TODO: The fixed value SECONDARY_BEAM_DEMERIT is probably flawed:
439    because for 32nd and 64th beams the forbidden quants are relatively
440    more important than stem lengths.
441 */
442 Real
443 Beam::score_forbidden_quants (Real yl, Real yr,
444                               Real radius,
445                               Real slt,
446                               Real thickness, Real beam_translation,
447                               Drul_array<int> beam_counts,
448                               Direction ldir, Direction rdir)
449 {
450   Real dy = yr - yl;
451   Drul_array<Real> y (yl,yr);
452   Drul_array<Direction> dirs (ldir,rdir);
453   
454   Real extra_demerit = SECONDARY_BEAM_DEMERIT / (beam_counts[LEFT] >? beam_counts[RIGHT]);
455
456   /*
457     Inside the staff, inter quants are forbidden.
458    */
459   Real dem = 0.0;
460   Direction d = LEFT;
461   do
462     {
463       if (fabs (y[d]) <= (radius + 0.5) && fabs (my_modf (y[d]) - 0.5) < BEAM_EPS)
464         dem += INTER_QUANT_PENALTY;
465     }
466   while ((flip (&d))!= LEFT); 
467
468
469   do
470     {
471       for (int j = 1; j <= beam_counts[d]; j++)
472         {
473           /*
474             see if the outer staffline falls in a beam-gap
475             
476             This test is too weak; we should really check all lines.
477            */
478           Direction stem_dir = dirs[d];
479
480           /*
481             The 2.2 factor is to provide a little leniency for
482             borderline cases. If we do 2.0, then the upper outer line
483             will be in the gap of the (2,sit) quant, leading to a
484             false demerit.
485            */
486           Real gap1 =  y[d] - stem_dir * ((j-1) * beam_translation + thickness / 2 - slt/2.2 );
487           Real gap2 = y[d] - stem_dir * (j * beam_translation - thickness / 2 + slt/2.2);
488
489           Interval gap;
490           gap.add_point (gap1);
491           gap.add_point (gap2);
492
493           for (Real k = - radius ;
494                k <= radius + BEAM_EPS; k += 1.0) 
495             if (gap.contains (k))
496               dem += extra_demerit;
497         }
498     }
499   while ((flip (&d))!= LEFT); 
500
501
502   if ((beam_counts[LEFT] >? beam_counts[RIGHT]) >= 2)
503     {
504       Real straddle = 0.0;
505       Real sit = (thickness - slt) / 2;
506       Real inter = 0.5;
507       Real hang = 1.0 - (thickness - slt) / 2;
508
509
510       Direction d = LEFT;
511       do
512         {
513           if (beam_counts[d] >= 2
514               && fabs (y[d] - dirs[d] * beam_translation) < radius + inter)
515             {
516               if (dirs[d] == UP && dy <= BEAM_EPS
517                   && fabs (my_modf (y[d]) - sit) < BEAM_EPS)
518                 dem += extra_demerit;
519           
520               if (dirs[d] == DOWN && dy >= BEAM_EPS
521                   && fabs (my_modf (y[d]) - hang) < BEAM_EPS)
522                 dem += extra_demerit;
523             }
524
525           if (beam_counts[d] >= 3
526               && fabs (y[d] - 2 * dirs[d] * beam_translation) < radius + inter)
527             {
528               if (dirs[d] == UP && dy <= BEAM_EPS
529                   && fabs (my_modf (y[d]) - straddle) < BEAM_EPS)
530                 dem += extra_demerit;
531               
532               if (dirs[d] == DOWN && dy >= BEAM_EPS
533                   && fabs (my_modf (y[d]) - straddle) < BEAM_EPS)
534                 dem += extra_demerit;
535             }
536         }
537       while (flip (&d) != LEFT);
538     }
539   
540   return dem;
541 }
542
543