]> git.donarmstrong.com Git - lilypond.git/blob - lily/beam.cc
*** empty log message ***
[lilypond.git] / lily / beam.cc
1 /*
2   beam.cc -- implement Beam
3   
4   source file of the GNU LilyPond music typesetter
5   
6   (c) 1997--2005 Han-Wen Nienhuys <hanwen@cs.uu.nl>
7   Jan Nieuwenhuizen <janneke@gnu.org>
8 */
9
10 /*
11 TODO:
12
13   - Determine auto knees based on positions if it's set by the user.
14
15   - the code is littered with * and / staff_space calls for
16     #'positions. Consider moving to real-world coordinates?
17
18     Problematic issue is user tweaks (user tweaks are in staff-coordinates.) 
19   
20 Notes:
21
22  - Stems run to the Y-center of the beam.
23   
24  - beam_translation is the offset between Y centers of the beam.
25
26 */
27
28
29
30 #include <math.h> // tanh.
31
32 #include "beam.hh"
33 #include "interval-set.hh"
34 #include "directional-element-interface.hh"
35 #include "beaming.hh"
36 #include "misc.hh"
37 #include "least-squares.hh"
38 #include "stem.hh"
39 #include "output-def.hh"
40 #include "lookup.hh"
41 #include "group-interface.hh"
42 #include "staff-symbol-referencer.hh"
43 #include "item.hh"
44 #include "spanner.hh"
45 #include "warn.hh"
46
47
48 #if DEBUG_QUANTING
49 #include "text-item.hh"  // debug output.
50 #include "font-interface.hh"  // debug output.
51 #endif
52
53
54 void
55 Beam::add_stem (Grob *me, Grob *s)
56 {
57   Pointer_group_interface::add_grob (me, ly_symbol2scm ("stems"), s);
58   
59   s->add_dependency (me);
60
61   assert (!Stem::get_beam (s));
62   s->set_property ("beam", me->self_scm ());
63
64   add_bound_item (dynamic_cast<Spanner*> (me), dynamic_cast<Item*> (s));
65 }
66
67
68 Real
69 Beam::get_thickness (Grob * me)
70 {
71   return robust_scm2double (me->get_property ("thickness"), 0)
72     * Staff_symbol_referencer::staff_space (me);
73 }
74
75 /* Return the translation between 2 adjoining beams. */
76 Real
77 Beam::get_beam_translation (Grob *me)
78 {
79   SCM func = me->get_property ("space-function");
80
81   if (ly_c_procedure_p (func))
82     {
83       SCM s = scm_call_2 (func, me->self_scm (), scm_int2num (get_beam_count (me)));
84       return scm_to_double (s);
85     }
86   else
87     {
88       return 0.81;
89     }
90 }
91
92 /* Maximum beam_count. */
93 int
94 Beam::get_beam_count (Grob *me) 
95 {
96   int m = 0;
97   for (SCM s = me->get_property ("stems"); scm_is_pair (s); s = scm_cdr (s))
98     {
99       Grob *stem = unsmob_grob (scm_car (s));
100       m = m >? (Stem::beam_multiplicity (stem).length () + 1);
101     }
102   return m;
103 }
104
105
106 /*
107   Space return space between beams.
108  */
109 MAKE_SCHEME_CALLBACK (Beam, space_function, 2);
110 SCM
111 Beam::space_function (SCM smob, SCM beam_count)
112 {
113   Grob *me = unsmob_grob (smob);
114   
115   Real staff_space = Staff_symbol_referencer::staff_space (me);
116   Real line = Staff_symbol_referencer::line_thickness (me);
117   Real thickness = get_thickness (me);
118   
119   Real beam_translation = scm_to_int (beam_count) < 4
120     ? (2*staff_space + line - thickness) / 2.0
121     : (3*staff_space + line - thickness) / 3.0;
122   
123   return scm_make_real (beam_translation);
124 }
125
126
127 /* After pre-processing all directions should be set.
128    Several post-processing routines (stem, slur, script) need stem/beam
129    direction.
130    Currenly, this means that beam has set all stem's directions.
131    [Alternatively, stems could set its own directions, according to
132    their beam, during 'final-pre-processing'.] */
133 MAKE_SCHEME_CALLBACK (Beam, before_line_breaking, 1);
134 SCM
135 Beam::before_line_breaking (SCM smob)
136 {
137   Grob *me =  unsmob_grob (smob);
138
139   /* Beams with less than 2 two stems don't make much sense, but could happen
140      when you do
141      
142      [r8 c8 r8].
143      
144     For a beam that  only has one stem, we try to do some disappearance magic:
145     we revert the flag, and move on to The Eternal Engraving Fields. */
146
147   int count = visible_stem_count (me);
148   if (count < 2)
149     {
150       me->warning (_ ("beam has less than two visible stems"));
151
152       SCM stems = me->get_property ("stems");
153       if (scm_ilength (stems) == 1)
154         {
155           me->warning (_ ("removing beam with less than two stems"));
156
157           unsmob_grob (scm_car (stems))->set_property ("beam", SCM_EOL);
158           me->suicide ();
159
160           return SCM_UNSPECIFIED;
161         }
162       else if (scm_ilength (stems) == 0)
163         {
164           me->suicide ();
165           return SCM_UNSPECIFIED;         
166         }
167     }
168   if (count >= 1)
169     {
170       Direction d = get_default_dir (me);
171
172       consider_auto_knees (me);
173       set_stem_directions (me, d);
174
175       connect_beams (me);
176
177       set_stem_shorten (me);
178     }
179
180   return SCM_EOL;
181 }
182
183
184 /*
185   We want a maximal number of shared beams, but if there is choice, we
186   take the one that is closest to the end of the stem. This is for situations like
187
188        x
189       |
190       |
191   |===|
192   |=
193   |
194   x
195
196   
197  */
198 int
199 position_with_maximal_common_beams (SCM left_beaming, SCM right_beaming,
200                                     Direction left_dir,
201                                     Direction right_dir)
202 {
203   Slice lslice = int_list_to_slice (scm_cdr (left_beaming));
204
205   int best_count = 0;
206   int best_start = 0;
207   for (int i = lslice[-left_dir];
208        (i - lslice[left_dir])* left_dir <= 0 ; i+= left_dir) 
209     {
210       int count = 0;
211       for ( SCM s = scm_car (right_beaming); scm_is_pair (s); s = scm_cdr (s))
212         {
213           int k = - right_dir * scm_to_int (scm_car (s)) + i;
214           if (scm_c_memq (scm_int2num (k), left_beaming) != SCM_BOOL_F)
215             count ++;
216         }
217
218       if (count >= best_count)
219         {
220           best_count = count; 
221           best_start = i;
222         }
223     }
224
225   return best_start;
226 }
227
228 void
229 Beam::connect_beams (Grob *me)
230 {
231   Link_array<Grob> stems =
232     Pointer_group_interface__extract_grobs (me, (Grob*)0, "stems");
233
234   Slice last_int;
235   last_int.set_empty ();
236   SCM last_beaming = SCM_EOL;
237   Direction last_dir = CENTER;
238   for (int i = 0; i< stems.size (); i++)
239     {
240       Grob *this_stem = stems[i];
241       SCM this_beaming = this_stem->get_property ("beaming");
242
243       Direction this_dir = get_grob_direction (this_stem);
244       if (scm_is_pair (last_beaming) && scm_is_pair (this_beaming))
245         {
246           int start_point = position_with_maximal_common_beams
247             (last_beaming, this_beaming,
248              last_dir, this_dir);
249           
250           Direction d = LEFT;
251           Slice new_slice ; 
252           do
253             {
254               if (d == RIGHT && i == stems.size ()-1)
255                 continue;
256               
257               new_slice.set_empty ();
258               SCM s = index_get_cell (this_beaming, d);
259               for (; scm_is_pair (s); s = scm_cdr (s))
260                 {
261                   int new_beam_pos =
262                     start_point - this_dir * scm_to_int (scm_car (s));
263
264                   new_slice.add_point (new_beam_pos);
265                   scm_set_car_x (s, scm_int2num (new_beam_pos));
266                 }
267
268
269             }
270           while (flip (&d) != LEFT);
271
272           if (!new_slice.is_empty ())
273             last_int =  new_slice;
274         }
275       else
276         {
277           scm_set_car_x ( this_beaming, SCM_EOL);
278           SCM s = scm_cdr (this_beaming);
279           for (; scm_is_pair (s); s = scm_cdr (s))
280             {
281               int np = - this_dir * scm_to_int (scm_car (s));
282               scm_set_car_x (s, scm_int2num (np));
283               last_int.add_point (np);
284             }
285         }
286
287       if (i == stems.size () -1)
288         {
289           scm_set_cdr_x (this_beaming, SCM_EOL);
290         }
291
292       if (scm_ilength (scm_cdr (this_beaming)) > 0)
293         {
294           last_beaming = this_beaming;
295           last_dir = this_dir;
296         }
297     }
298  }
299
300
301 /*
302   TODO: should not make beams per stem, but per Y-level.
303  */
304 MAKE_SCHEME_CALLBACK (Beam, print, 1);
305 SCM
306 Beam::print (SCM grob)
307 {
308   Spanner *me = unsmob_spanner (grob);
309   position_beam (me);
310   
311   Link_array<Grob> stems =
312     Pointer_group_interface__extract_grobs (me, (Grob*)0, "stems");
313   Grob* xcommon = common_refpoint_of_array (stems, me, X_AXIS);
314
315   xcommon = me->get_bound (LEFT)->common_refpoint (xcommon, X_AXIS);
316   xcommon = me->get_bound (RIGHT)->common_refpoint (xcommon, X_AXIS);
317
318   Real x0, dx;
319   if (visible_stem_count (me))
320     {
321       // ugh -> use commonx
322       x0 = first_visible_stem (me)->relative_coordinate (xcommon, X_AXIS);
323       dx = last_visible_stem (me)->relative_coordinate (xcommon, X_AXIS) - x0;
324     }
325   else
326     {
327       x0 = stems[0]->relative_coordinate (xcommon, X_AXIS);
328       dx = stems.top ()->relative_coordinate (xcommon, X_AXIS) - x0;
329     }
330
331   SCM posns = me->get_property ("positions");
332   Drul_array<Real> pos;
333   if (!is_number_pair (posns))
334     {
335       programming_error ("No beam posns");
336       pos = Interval (0,0);
337     }
338   else
339     pos = ly_scm2realdrul (posns);
340
341   scale_drul (&pos,  Staff_symbol_referencer::staff_space (me));
342   
343   Real dy = pos[RIGHT] - pos[LEFT];
344   Real slope = (dy && dx) ? dy/dx : 0;
345   
346   Real thick = get_thickness (me);
347   Real bdy = get_beam_translation (me);
348
349   SCM last_beaming = SCM_EOL;
350   Real last_xposn = -1;
351   Real last_stem_width = -1 ;
352
353   Real gap_length = robust_scm2double (me->get_property ("gap"), 0.0);
354   
355   Stencil the_beam;
356   Real lt = me->get_layout ()->get_dimension (ly_symbol2scm ("linethickness"));
357   
358   for (int i = 0; i<= stems.size (); i++)
359     {
360       Grob * st = (i < stems.size ()) ? stems[i] : 0;
361       
362       SCM this_beaming = st ? st->get_property ("beaming") : SCM_EOL;
363       Real xposn = st ? st->relative_coordinate (xcommon, X_AXIS) : 0.0;
364       Real stem_width = st ? robust_scm2double (st->get_property ("thickness"), 1.0) *lt : 0 ;
365       Direction stem_dir = st ? to_dir (st->get_property ("direction")) : CENTER;
366       /*
367         We do the space left of ST, with lfliebertjes pointing to the
368         right from the left stem, and rfliebertjes pointing left from
369         right stem.
370        */
371       SCM left = (i > 0) ? scm_cdr (last_beaming) : SCM_EOL;
372       SCM right = st ? scm_car (this_beaming) : SCM_EOL;
373
374       Array<int> full_beams;
375       Array<int> lfliebertjes;
376       Array<int> rfliebertjes;    
377
378       for (SCM s = left;
379            scm_is_pair (s); s = scm_cdr (s))
380         {
381           int b = scm_to_int (scm_car (s));
382           if (scm_c_memq (scm_car (s), right) != SCM_BOOL_F)
383             {
384               full_beams.push (b);
385             }
386           else
387             {
388               lfliebertjes.push (b); 
389             }
390         }
391       for (SCM s = right;
392            scm_is_pair (s); s = scm_cdr (s))
393         {
394           int b = scm_to_int (scm_car (s));
395           if (scm_c_memq (scm_car (s), left) == SCM_BOOL_F)
396             {
397               rfliebertjes.push (b);
398             }
399         }
400
401       /*
402         how much to stick out for beams across linebreaks
403        */
404       Real break_overshoot = 3.0;
405       Real w = (i > 0 && st) ? (xposn - last_xposn) : break_overshoot;
406
407       Real stem_offset = 0.0;
408       if (i > 0)
409         {
410           w += last_stem_width / 2;
411           stem_offset = -last_stem_width / 2;
412         }
413
414       if (st)
415         w += stem_width/ 2 ;
416       
417
418       Real blot = me->get_layout ()->get_dimension (ly_symbol2scm ("blotdiameter"));
419       Stencil whole = Lookup::beam (slope, w, thick, blot);
420       Stencil gapped;
421
422       int gap_count = 0;
423       if (scm_is_number (me->get_property ("gap-count")))
424         {
425           gap_count = scm_to_int (me->get_property ("gap-count"));
426           gapped = Lookup::beam (slope, w - 2 * gap_length, thick, blot);
427
428           full_beams.sort (default_compare);
429           if (stem_dir == UP)
430             full_beams.reverse ();
431         }
432
433       int k = 0;
434       for (int j = full_beams.size (); j--;)
435         {
436           Stencil b (whole);
437           
438           if (k++ < gap_count)
439             {
440               b = gapped;
441               b.translate_axis (gap_length, X_AXIS);
442             }
443           b.translate_axis (last_xposn -  x0 + stem_offset, X_AXIS);
444           b.translate_axis (slope * (last_xposn - x0) + bdy * full_beams[j], Y_AXIS);
445
446           the_beam.add_stencil (b);           
447         }
448           
449       if (lfliebertjes.size () || rfliebertjes.size ())
450         {
451           Real nw_f;
452
453           if (st)
454             {
455               int t = Stem::duration_log (st); 
456
457               SCM proc = me->get_property ("flag-width-function");
458               SCM result = scm_call_1 (proc, scm_int2num (t));
459               nw_f = scm_to_double (result);
460             }
461           else
462             nw_f = break_overshoot / 2;
463               
464           /* Half beam should be one note-width,
465              but let's make sure two half-beams never touch */
466           Real lw = nw_f;
467           Real rw = nw_f;
468           if (i > 0)
469             rw = nw_f <? ( (xposn - last_xposn) / 2);
470           else
471             /*
472               TODO: 0.5 is a guess.
473             */
474             rw = xposn - me->get_bound (LEFT)->extent (xcommon, X_AXIS)[RIGHT]
475               - 0.5;
476           
477           if (st)
478             lw = nw_f <? ( (xposn - last_xposn) / 2);
479           else
480             lw = me->get_bound (RIGHT)->relative_coordinate (xcommon, X_AXIS)
481               - last_xposn;
482
483           Stencil rhalf = Lookup::beam (slope, rw, thick, blot);
484           Stencil lhalf = Lookup::beam (slope, lw, thick, blot);
485           for (int j = lfliebertjes.size (); j--;)
486             {
487               Stencil b (lhalf);
488               b.translate_axis (last_xposn -  x0, X_AXIS);
489               b.translate_axis (slope * (last_xposn-x0) + bdy * lfliebertjes[j], Y_AXIS);
490               the_beam.add_stencil (b);       
491             }
492           for (int j = rfliebertjes.size (); j--;)
493             {
494               Stencil b (rhalf);
495               b.translate_axis (xposn -  x0 - rw , X_AXIS);
496               b.translate_axis (slope * (xposn-x0 -rw) + bdy * rfliebertjes[j], Y_AXIS);
497               the_beam.add_stencil (b);       
498             }
499         }
500
501
502       last_xposn = xposn;
503       last_stem_width = stem_width;
504       last_beaming = this_beaming;
505     }
506
507   the_beam.translate_axis (x0 - me->relative_coordinate (xcommon, X_AXIS), X_AXIS);
508   the_beam.translate_axis (pos[LEFT], Y_AXIS);
509
510 #if (DEBUG_QUANTING)
511   SCM quant_score = me->get_property ("quant-score");
512   if (to_boolean (me->get_layout ()->lookup_variable (ly_symbol2scm ("debug-beam-quanting")))
513       && scm_is_string (quant_score))
514     {
515       
516       /*
517         This code prints the demerits for each beam. Perhaps this
518         should be switchable for those who want to twiddle with the
519         parameters.
520       */
521       String str;
522       SCM properties = Font_interface::text_font_alist_chain (me);
523
524       Direction stem_dir = stems.size() ? to_dir (stems[0]->get_property ("direction")) : UP;
525     
526       Stencil tm = *unsmob_stencil (Text_interface::interpret_markup
527          (me->get_layout ()->self_scm (), properties, quant_score));
528       the_beam.add_at_edge (Y_AXIS, stem_dir, tm, 1.0, 0);
529     }
530 #endif
531   
532   return the_beam.smobbed_copy ();
533 }
534   
535
536
537
538 Direction
539 Beam::get_default_dir (Grob *me) 
540 {
541   Drul_array<int> total;
542   total[UP]  = total[DOWN] = 0;
543   Drul_array<int> count; 
544   count[UP]  = count[DOWN] = 0;
545   Direction d = DOWN;
546
547   Link_array<Grob> stems =
548         Pointer_group_interface__extract_grobs (me, (Grob*)0, "stems");
549
550   for (int i = 0; i < stems.size (); i++)
551     do {
552       Grob *s = stems[i];
553       Direction sd = get_grob_direction (s);
554
555       int center_distance = int (- d * Stem::head_positions (s) [-d]) >? 0;
556       int current = sd  ? (1 + d * sd)/2 : center_distance;
557
558       if (current)
559         {
560           total[d] += current;
561           count[d] ++;
562         }
563     } while (flip (&d) != DOWN);
564   
565   SCM func = me->get_property ("dir-function");
566   SCM s = scm_call_2 (func,
567                     scm_cons (scm_int2num (count[UP]),
568                              scm_int2num (count[DOWN])),
569                     scm_cons (scm_int2num (total[UP]),
570                              scm_int2num (total[DOWN])));
571
572   if (scm_is_number (s) && scm_to_int (s))
573     return to_dir (s);
574   
575   /* If dir is not determined: get default */
576   return to_dir (me->get_property ("neutral-direction"));
577 }
578
579
580 /* Set all stems with non-forced direction to beam direction.
581    Urg: non-forced should become `without/with unforced' direction,
582    once stem gets cleaned-up. */
583 void
584 Beam::set_stem_directions (Grob *me, Direction d)
585 {
586   Link_array<Grob> stems
587     = Pointer_group_interface__extract_grobs (me, (Grob*) 0, "stems");
588   
589   for (int i = 0; i <stems.size (); i++)
590     {
591       Grob *s = stems[i];
592   
593       SCM forcedir = s->get_property ("direction");
594       if (!to_dir (forcedir))
595         set_grob_direction (s,  d);
596     }
597 }
598
599 /*
600   Only try horizontal beams for knees.  No reliable detection of
601   anything else is possible here, since we don't know funky-beaming
602   settings, or X-distances (slopes!)  People that want sloped
603   knee-beams, should set the directions manually.
604  */
605 void
606 Beam::consider_auto_knees (Grob* me)
607 {
608   SCM scm = me->get_property ("auto-knee-gap");
609   if (!scm_is_number (scm))
610     return ;
611
612   Interval_set gaps;
613
614   gaps.set_full ();
615
616   Link_array<Grob> stems =
617     Pointer_group_interface__extract_grobs (me, (Grob*) 0, "stems");
618   
619   Grob *common = common_refpoint_of_array (stems, me,  Y_AXIS);
620   Real staff_space = Staff_symbol_referencer::staff_space (me);
621   
622   Array<Interval> head_positions_array;  
623   for (int i = 0; i < stems.size (); i++)
624     {
625       Grob* stem = stems[i];
626       if (Stem::is_invisible (stem))
627         continue;
628
629       Interval head_positions = Stem::head_positions (stem);
630       if (!head_positions.is_empty ())
631         {
632           head_positions[LEFT] += -1;
633           head_positions[RIGHT] += 1; 
634           head_positions *= staff_space * 0.5 ;
635
636           /*
637             We could subtract beam Y position, but this routine only
638             sets stem directions, a constant shift does not have an
639             influence.
640            */
641           head_positions += stem->relative_coordinate (common, Y_AXIS);
642
643           if (to_dir (stem->get_property ("direction")))
644             {
645               Direction stemdir = to_dir (stem->get_property ("direction"));
646               head_positions[-stemdir] = - stemdir * infinity_f;
647             }
648         }
649       head_positions_array.push (head_positions);
650
651       gaps.remove_interval (head_positions);
652     }
653
654   Interval max_gap;
655   Real max_gap_len = 0.0;
656
657   for (int i  = gaps.allowed_regions_.size () -1;  i >=  0 ; i--)
658     {
659       Interval gap = gaps.allowed_regions_[i];
660
661       /*
662         the outer gaps are not knees.
663        */
664       if (isinf (gap[LEFT]) || isinf (gap[RIGHT]))
665         continue;
666       
667       if (gap.length () >= max_gap_len)
668         {
669           max_gap_len = gap.length ();
670           max_gap = gap;
671         }
672     }
673
674   Real beam_translation = get_beam_translation (me);
675   Real beam_thickness = Beam::get_thickness (me);
676   int beam_count = Beam::get_beam_count (me);  
677   Real height_of_beams = beam_thickness / 2
678     + (beam_count - 1) * beam_translation;
679   Real threshold = scm_to_double (scm) +  height_of_beams;
680   
681   if (max_gap_len > threshold)
682     {
683       int j = 0;
684       for (int i = 0; i < stems.size (); i++)
685         {
686           Grob* stem = stems[i];
687           if (Stem::is_invisible (stem))
688             continue;
689
690           Interval head_positions = head_positions_array[j++];
691
692
693           Direction d =  (head_positions.center () < max_gap.center ()) ?
694             UP : DOWN ;
695           
696           stem->set_property ("direction", scm_int2num (d));
697           
698           head_positions.intersect (max_gap);
699           assert (head_positions.is_empty () || head_positions.length () < 1e-6 );
700         }
701     }
702 }
703
704
705
706 /* Set stem's shorten property if unset.
707
708  TODO:
709    take some y-position (chord/beam/nearest?) into account
710    scmify forced-fraction
711  
712   This is done in beam because the shorten has to be uniform over the
713   entire beam.
714
715 */
716 void
717 Beam::set_stem_shorten (Grob *me)
718 {
719   /*
720     shortening looks silly for x staff beams
721    */
722   if (is_knee (me))
723     return ;
724   
725   Real forced_fraction = 1.0 * forced_stem_count (me)
726     / visible_stem_count (me);
727
728   int beam_count = get_beam_count (me);
729
730   SCM shorten_list = me->get_property ("beamed-stem-shorten");
731   if (shorten_list == SCM_EOL)
732     return;
733
734   Real staff_space = Staff_symbol_referencer::staff_space (me);
735   
736   SCM shorten_elt =
737     robust_list_ref (beam_count -1, shorten_list);
738   Real shorten_f = scm_to_double (shorten_elt) * staff_space;
739
740   /* your similar cute comment here */
741   shorten_f *= forced_fraction;
742
743   if (shorten_f)
744     me->set_property ("shorten", scm_make_real (shorten_f));
745 }
746
747 /*  Call list of y-dy-callbacks, that handle setting of
748     grob-properties
749
750 */
751 MAKE_SCHEME_CALLBACK (Beam, after_line_breaking, 1);
752 SCM
753 Beam::after_line_breaking (SCM smob)
754 {
755   Grob *me = unsmob_grob (smob);
756
757   position_beam (me);
758   return SCM_UNSPECIFIED;
759 }
760
761 void
762 Beam::position_beam (Grob *me)
763 {
764   if (!me->is_live ())
765     return ;
766   if (to_boolean (me->get_property ("positioning-done")))
767     return ;
768
769   me->set_property ("positioning-done", SCM_BOOL_T);
770
771   /* Copy to mutable list. */
772   SCM s = ly_deep_copy (me->get_property ("positions"));
773   me->set_property ("positions", s);
774
775   if (scm_car (s) == SCM_BOOL_F)
776     {
777       // one wonders if such genericity is necessary  --hwn.
778       SCM callbacks = me->get_property ("position-callbacks");
779       for (SCM i = callbacks; scm_is_pair (i); i = scm_cdr (i))
780         scm_call_1 (scm_car (i), me->self_scm ());
781     }
782
783   set_stem_lengths (me);  
784 }
785
786
787 void
788 set_minimum_dy (Grob *me, Real * dy)
789 {
790   if (*dy)
791     {
792       /*
793         If dy is smaller than the smallest quant, we
794         get absurd direction-sign penalties. 
795       */
796           
797       Real ss = Staff_symbol_referencer::staff_space (me);
798       Real thickness = Beam::get_thickness (me) / ss ;
799       Real slt = Staff_symbol_referencer::line_thickness (me) / ss;
800       Real sit = (thickness - slt) / 2;
801       Real inter = 0.5;
802       Real hang = 1.0 - (thickness - slt) / 2;
803           
804       *dy = sign (*dy) * (fabs (*dy)
805                         >?
806                         (sit <? inter <? hang));
807     }
808 }
809
810 /*
811   Compute  a first approximation to the beam slope.
812  */
813 MAKE_SCHEME_CALLBACK (Beam, least_squares, 1);
814 SCM
815 Beam::least_squares (SCM smob)
816 {
817   Grob *me = unsmob_grob (smob);
818
819   int count = visible_stem_count (me);
820   Interval pos (0, 0);
821   
822   if (count < 1)
823     {
824       me->set_property ("positions", ly_interval2scm (pos));
825       return SCM_UNSPECIFIED;
826     }
827
828
829   Array<Real> x_posns ;
830   Link_array<Grob> stems =
831     Pointer_group_interface__extract_grobs (me, (Grob*)0, "stems");
832   Grob *commonx = common_refpoint_of_array (stems, me, X_AXIS);
833   Grob *commony = common_refpoint_of_array (stems, me, Y_AXIS);  
834
835   Real my_y = me->relative_coordinate (commony, Y_AXIS);
836   
837   Grob *fvs  = first_visible_stem (me);
838   Grob *lvs  = last_visible_stem (me);
839   
840   Interval ideal (Stem::get_stem_info (fvs).ideal_y_
841                   + fvs->relative_coordinate (commony, Y_AXIS) -my_y,
842                   Stem::get_stem_info (lvs).ideal_y_
843                   + lvs->relative_coordinate (commony, Y_AXIS) - my_y);
844   
845   Real x0 = first_visible_stem (me)->relative_coordinate (commonx, X_AXIS);
846   for (int i = 0; i < stems.size (); i++)
847     {
848       Grob* s = stems[i];
849
850       Real x = s->relative_coordinate (commonx, X_AXIS) - x0;
851       x_posns.push (x);
852     }
853   Real dx = last_visible_stem (me)->relative_coordinate (commonx, X_AXIS) - x0;
854
855   
856   Real y = 0;  
857   Real slope = 0;
858   Real dy = 0;
859   
860   if (!ideal.delta ())
861     {
862       Interval chord (Stem::chord_start_y (first_visible_stem (me)),
863                       Stem::chord_start_y (last_visible_stem (me)));
864
865       /* Simple beams (2 stems) on middle line should be allowed to be
866          slightly sloped.
867          
868          However, if both stems reach middle line,
869          ideal[LEFT] == ideal[RIGHT] and ideal.delta () == 0.
870
871          For that case, we apply artificial slope */
872       if (!ideal[LEFT] && chord.delta () && count == 2)
873         {
874           /* FIXME. -> UP */
875           Direction d = (Direction) (sign (chord.delta ()) * UP);
876           pos[d] = get_thickness (me) / 2;
877           pos[-d] = - pos[d];
878         }
879       else
880         {
881           pos = ideal;
882         }
883
884       /*
885         For broken beams this doesn't work well. In this case, the
886         slope esp. of the first part of a broken beam should predict
887         where the second part goes.
888       */
889       me->set_property ("least-squares-dy",
890                         scm_make_real (pos[RIGHT] - pos[LEFT]));
891     }
892   else
893     {
894       Array<Offset> ideals;
895       for (int i = 0; i < stems.size (); i++)
896         {
897           Grob* s = stems[i];
898           if (Stem::is_invisible (s))
899             continue;
900           ideals.push (Offset (x_posns[i],
901                                Stem::get_stem_info (s).ideal_y_
902                                + s->relative_coordinate (commony, Y_AXIS)
903                                - my_y));
904         }
905       
906       minimise_least_squares (&slope, &y, ideals);
907
908       dy = slope * dx;
909
910       set_minimum_dy (me,&dy);
911       me->set_property ("least-squares-dy", scm_make_real (dy));
912       pos = Interval (y, (y+dy));
913     }
914
915   /*
916     "position" is relative to the staff.
917    */
918   scale_drul (&pos,  1/ Staff_symbol_referencer::staff_space (me)); 
919   
920   me->set_property ("positions", ly_interval2scm (pos));
921  
922   return SCM_UNSPECIFIED;
923 }
924
925
926 /*
927   We can't combine with previous function, since check concave and
928   slope damping comes first.
929
930   TODO: we should use the concaveness to control the amount of damping
931   applied.
932   
933 */
934 MAKE_SCHEME_CALLBACK (Beam, shift_region_to_valid, 1);
935 SCM
936 Beam::shift_region_to_valid (SCM grob)
937 {
938   Grob *me = unsmob_grob (grob);
939   /*
940     Code dup.
941    */
942   Array<Real> x_posns ;
943   Link_array<Grob> stems =
944     Pointer_group_interface__extract_grobs (me, (Grob*)0, "stems");
945   Grob *commonx = common_refpoint_of_array (stems, me, X_AXIS);
946   Grob *commony = common_refpoint_of_array (stems, me, Y_AXIS);  
947
948   Grob *fvs = first_visible_stem (me);
949
950   if (!fvs)
951     return SCM_UNSPECIFIED;
952     
953   Real x0 = fvs->relative_coordinate (commonx, X_AXIS);
954   for (int i = 0; i < stems.size (); i++)
955     {
956       Grob* s = stems[i];
957
958       Real x = s->relative_coordinate (commonx, X_AXIS) - x0;
959       x_posns.push (x);
960     }
961
962   Grob *lvs = last_visible_stem (me);
963   if (!lvs)
964     return SCM_UNSPECIFIED;
965   
966   Real dx = lvs->relative_coordinate (commonx, X_AXIS) - x0;
967
968   Drul_array<Real> pos = ly_scm2interval ( me->get_property ("positions"));
969
970   scale_drul (&pos,  Staff_symbol_referencer::staff_space (me));
971   
972   Real dy = pos[RIGHT] - pos[LEFT];
973   Real y = pos[LEFT];
974   Real slope = dy/dx;
975
976   
977   /*
978     Shift the positions so that we have a chance of finding good
979     quants (i.e. no short stem failures.)
980    */
981   Interval feasible_left_point;
982   feasible_left_point.set_full ();
983   for (int i = 0; i < stems.size (); i++)
984     {
985       Grob* s = stems[i];
986       if (Stem::is_invisible (s))
987         continue;
988
989       Direction d = Stem::get_direction (s);
990
991       Real left_y =
992         Stem::get_stem_info (s).shortest_y_
993         - slope * x_posns [i];
994
995       /*
996         left_y is now relative to the stem S. We want relative to
997         ourselves, so translate:
998        */
999       left_y += 
1000         + s->relative_coordinate (commony, Y_AXIS)
1001         - me->relative_coordinate (commony, Y_AXIS);
1002
1003       Interval flp ;
1004       flp.set_full ();
1005       flp[-d] = left_y;
1006
1007       feasible_left_point.intersect (flp);
1008     }
1009       
1010   if (feasible_left_point.is_empty ())
1011     warning (_ ("no viable initial configuration found: may not find good beam slope"));
1012   else if (!feasible_left_point.contains (y))
1013     {
1014       if (isinf (feasible_left_point[DOWN]))
1015         y = feasible_left_point[UP] - REGION_SIZE;
1016       else if (isinf (feasible_left_point[UP]))
1017         y = feasible_left_point[DOWN]+ REGION_SIZE;
1018       else
1019         y = feasible_left_point.center ();
1020     }
1021   
1022   pos = Drul_array<Real> (y, (y+dy));
1023   scale_drul (&pos, 1/ Staff_symbol_referencer::staff_space (me));
1024   
1025   me->set_property ("positions", ly_interval2scm (pos));
1026   return SCM_UNSPECIFIED;
1027 }
1028
1029 /* This neat trick is by Werner Lemberg,
1030    damped = tanh (slope)
1031    corresponds with some tables in [Wanske] CHECKME */
1032 MAKE_SCHEME_CALLBACK (Beam, slope_damping, 1);
1033 SCM
1034 Beam::slope_damping (SCM smob)
1035 {
1036   Grob *me = unsmob_grob (smob);
1037
1038   if (visible_stem_count (me) <= 1)
1039     return SCM_UNSPECIFIED;
1040
1041   SCM s = me->get_property ("damping"); 
1042   Real damping = scm_to_double (s);
1043
1044   if (damping)
1045     {
1046       Drul_array<Real> pos = ly_scm2interval (me->get_property ("positions"));
1047       scale_drul (&pos,  Staff_symbol_referencer::staff_space (me));
1048       
1049       Real dy = pos[RIGHT] - pos[LEFT];
1050
1051       Grob *fvs  = first_visible_stem (me);
1052       Grob *lvs  = last_visible_stem (me);
1053
1054       Grob *commonx = fvs->common_refpoint (lvs, X_AXIS);
1055
1056
1057       Real dx = last_visible_stem (me)->relative_coordinate (commonx, X_AXIS)
1058         - first_visible_stem (me)->relative_coordinate (commonx, X_AXIS);
1059
1060       Real slope = dy && dx ? dy/dx : 0;
1061
1062       Real concaveness = robust_scm2double (me->get_property ("concaveness"), 0.0);
1063       
1064       slope = 0.6 * tanh (slope) / (damping + concaveness);
1065
1066       Real damped_dy = slope * dx;
1067
1068       set_minimum_dy (me, &damped_dy);
1069       
1070       pos[LEFT] += (dy - damped_dy) / 2;
1071       pos[RIGHT] -= (dy - damped_dy) / 2;
1072
1073       scale_drul (&pos, 1/Staff_symbol_referencer::staff_space (me));
1074       
1075       me->set_property ("positions", ly_interval2scm (pos));
1076     }
1077   return SCM_UNSPECIFIED;
1078 }
1079
1080 /*
1081   Report slice containing the numbers that are both in (car BEAMING)
1082   and (cdr BEAMING)
1083  */
1084 Slice
1085 where_are_the_whole_beams (SCM beaming)
1086 {
1087   Slice l; 
1088   
1089   for ( SCM s = scm_car (beaming); scm_is_pair (s) ; s = scm_cdr (s))
1090     {
1091       if (scm_c_memq (scm_car (s), scm_cdr (beaming)) != SCM_BOOL_F)
1092         
1093         l.add_point (scm_to_int (scm_car (s)));
1094     }
1095
1096   return l;
1097 }
1098
1099 /* Return the Y position of the stem-end, given the Y-left, Y-right
1100    in POS for stem S.  This Y position is relative to S. */
1101 Real
1102 Beam::calc_stem_y (Grob *me, Grob* s, Grob ** common,
1103                    Real xl, Real xr,
1104                    Drul_array<Real> pos, bool french) 
1105 {
1106   Real beam_translation = get_beam_translation (me);
1107
1108     
1109   Real r = s->relative_coordinate (common[X_AXIS], X_AXIS) - xl;
1110   Real dy = pos[RIGHT] - pos[LEFT];
1111   Real dx = xr - xl;
1112   Real stem_y_beam0 = (dy && dx
1113                        ? r / dx
1114                        * dy
1115                        : 0) + pos[LEFT];
1116   
1117   Direction my_dir = get_grob_direction (s);
1118   SCM beaming = s->get_property ("beaming");
1119  
1120   Real stem_y = stem_y_beam0;
1121   if (french)
1122     {
1123       Slice bm = where_are_the_whole_beams (beaming);
1124       if (!bm.is_empty ())
1125         stem_y += beam_translation * bm[-my_dir];
1126     }
1127   else
1128     {
1129       Slice bm = Stem::beam_multiplicity (s);
1130       if (!bm.is_empty ())
1131         stem_y += bm[my_dir] * beam_translation;
1132     }
1133   
1134   Real id = me->relative_coordinate (common[Y_AXIS], Y_AXIS)
1135     - s->relative_coordinate (common[Y_AXIS], Y_AXIS);
1136   
1137   return stem_y + id;
1138 }
1139
1140 /*
1141   Hmm.  At this time, beam position and slope are determined.  Maybe,
1142   stem directions and length should set to relative to the chord's
1143   position of the beam.  */
1144 void
1145 Beam::set_stem_lengths (Grob *me)
1146 {
1147   Link_array<Grob> stems =
1148     Pointer_group_interface__extract_grobs (me, (Grob*)0, "stems");
1149
1150   if (!stems.size ())
1151     return;
1152   
1153   Grob *common[2];
1154   for (int a = 2; a--;)
1155     common[a] = common_refpoint_of_array (stems, me, Axis (a));
1156   
1157   Drul_array<Real> pos = ly_scm2realdrul (me->get_property ("positions"));
1158   Real staff_space = Staff_symbol_referencer::staff_space (me);
1159   scale_drul (&pos,  staff_space);
1160
1161   bool gap = false;
1162   Real thick = 0.0;
1163   if (scm_is_number (me->get_property ("gap-count"))
1164       &&scm_to_int (me->get_property ("gap-count")))
1165     {
1166       gap = true;
1167       thick = get_thickness (me);
1168     }
1169       
1170   // ugh -> use commonx
1171   Grob * fvs = first_visible_stem (me);
1172   Grob *lvs = last_visible_stem (me);
1173     
1174   Real xl = fvs ? fvs->relative_coordinate (common[X_AXIS], X_AXIS) : 0.0;
1175   Real xr = lvs ? lvs->relative_coordinate (common[X_AXIS], X_AXIS) : 0.0;
1176   
1177   for (int i = 0; i < stems.size (); i++)
1178     {
1179       Grob* s = stems[i];
1180       if (Stem::is_invisible (s))
1181         continue;
1182
1183       bool french = to_boolean (s->get_property ("french-beaming"));
1184       Real stem_y = calc_stem_y (me, s, common,
1185                                  xl, xr,
1186                                  pos, french && s != lvs && s!= fvs);
1187
1188       /*
1189         Make the stems go up to the end of the beam. This doesn't matter
1190         for normal beams, but for tremolo beams it looks silly otherwise.
1191        */
1192       if (gap)
1193         stem_y += thick * 0.5 * get_grob_direction (s);
1194
1195       Stem::set_stemend (s, 2* stem_y / staff_space);
1196     }
1197 }
1198
1199 void
1200 Beam::set_beaming (Grob *me, Beaming_info_list *beaming)
1201 {
1202   Link_array<Grob> stems =
1203     Pointer_group_interface__extract_grobs (me, (Grob *)0, "stems");
1204   
1205   Direction d = LEFT;
1206   for (int i = 0; i  < stems.size (); i++)
1207     {
1208       /*
1209         Don't overwrite user settings.
1210        */
1211       
1212       do
1213         {
1214           /* Don't set beaming for outside of outer stems */      
1215           if ( (d == LEFT && i == 0)
1216               || (d == RIGHT && i == stems.size () -1))
1217             continue;
1218
1219           Grob *st =  stems[i];
1220           SCM beaming_prop = st->get_property ("beaming");
1221           if (beaming_prop == SCM_EOL ||
1222               index_get_cell (beaming_prop, d) == SCM_EOL)
1223             {
1224               int b = beaming->infos_.elem (i).beams_i_drul_[d];
1225               if (i>0
1226                   && i < stems.size () -1
1227                   && Stem::is_invisible (st))
1228                 b = b <? beaming->infos_.elem (i).beams_i_drul_[-d];
1229               
1230               Stem::set_beaming (st, b, d);
1231             }
1232         }
1233       while (flip (&d) != LEFT);
1234     }
1235 }
1236
1237 int
1238 Beam::forced_stem_count (Grob *me) 
1239 {
1240   Link_array<Grob>stems = 
1241     Pointer_group_interface__extract_grobs (me, (Grob*) 0, "stems");
1242   int f = 0;
1243   for (int i = 0; i < stems.size (); i++)
1244     {
1245       Grob *s = stems[i];
1246
1247       if (Stem::is_invisible (s))
1248         continue;
1249
1250       /* I can imagine counting those boundaries as a half forced stem,
1251          but let's count them full for now. */
1252       if (abs (Stem::chord_start_y (s)) > 0.1
1253         && (Stem::get_direction (s) != Stem::get_default_dir (s)))
1254         f++;
1255     }
1256   return f;
1257 }
1258
1259
1260
1261
1262 int
1263 Beam::visible_stem_count (Grob *me) 
1264 {
1265   Link_array<Grob>stems = 
1266     Pointer_group_interface__extract_grobs (me, (Grob*) 0, "stems");
1267   int c = 0;
1268   for (int i = stems.size (); i--;)
1269     {
1270       if (!Stem::is_invisible (stems[i]))
1271         c++;
1272     }
1273   return c;
1274 }
1275
1276 Grob*
1277 Beam::first_visible_stem (Grob *me) 
1278 {
1279   Link_array<Grob>stems = 
1280     Pointer_group_interface__extract_grobs (me, (Grob*) 0, "stems");
1281   
1282   for (int i = 0; i < stems.size (); i++)
1283     {
1284       if (!Stem::is_invisible (stems[i]))
1285         return stems[i];
1286     }
1287   return 0;
1288 }
1289
1290 Grob*
1291 Beam::last_visible_stem (Grob *me) 
1292 {
1293   Link_array<Grob>stems = 
1294     Pointer_group_interface__extract_grobs (me, (Grob*) 0, "stems");
1295   for (int i = stems.size (); i--;)
1296     {
1297       if (!Stem::is_invisible (stems[i]))
1298         return stems[i];
1299     }
1300   return 0;
1301 }
1302
1303
1304 /*
1305   [TODO]
1306   
1307   handle rest under beam (do_post: beams are calculated now)
1308   what about combination of collisions and rest under beam.
1309
1310   Should lookup
1311     
1312     rest -> stem -> beam -> interpolate_y_position ()
1313 */
1314 MAKE_SCHEME_CALLBACK (Beam, rest_collision_callback, 2);
1315 SCM
1316 Beam::rest_collision_callback (SCM element_smob, SCM axis)
1317 {
1318   Grob *rest = unsmob_grob (element_smob);
1319   Axis a = (Axis) scm_to_int (axis);
1320
1321   if (scm_is_number (rest->get_property ("staff-position")))
1322     return scm_int2num (0);
1323   
1324   assert (a == Y_AXIS);
1325
1326   Grob *st = unsmob_grob (rest->get_property ("stem"));
1327   Grob *stem = st;
1328   if (!stem)
1329     return scm_make_real (0.0);
1330   Grob *beam = unsmob_grob (stem->get_property ("beam"));
1331   if (!beam
1332       || !Beam::has_interface (beam)
1333       || !Beam::visible_stem_count (beam))
1334     return scm_make_real (0.0);
1335
1336   Drul_array<Real> pos (0, 0);
1337   SCM s = beam->get_property ("positions");
1338   if (scm_is_pair (s) && scm_is_number (scm_car (s)))
1339     pos = ly_scm2interval (s);
1340   Real staff_space = Staff_symbol_referencer::staff_space (rest);
1341
1342   scale_drul (&pos, staff_space);
1343   
1344
1345   Real dy = pos[RIGHT] - pos[LEFT];
1346   
1347   // ugh -> use commonx
1348   Real x0 = first_visible_stem (beam)->relative_coordinate (0, X_AXIS);
1349   Real dx = last_visible_stem (beam)->relative_coordinate (0, X_AXIS) - x0;
1350   Real slope = dy && dx ? dy/dx : 0;
1351   
1352   Direction d = Stem::get_direction (stem);
1353   Real stem_y = pos[LEFT] + (stem->relative_coordinate (0, X_AXIS) - x0) * slope;
1354   
1355   Real beam_translation = get_beam_translation (beam);
1356   Real beam_thickness = Beam::get_thickness (beam);
1357
1358   /*
1359     TODO: this is not strictly correct for 16th knee beams. 
1360    */
1361   int beam_count = 
1362     Stem::beam_multiplicity (stem).length() + 1;
1363   
1364   Real height_of_my_beams = beam_thickness / 2
1365     + (beam_count - 1) * beam_translation;
1366   Real beam_y = stem_y - d * height_of_my_beams;
1367
1368   Grob *common_y = rest->common_refpoint (beam, Y_AXIS);
1369
1370   Real rest_dim = rest->extent (common_y, Y_AXIS)[d];
1371   Real minimum_distance =
1372     + staff_space * (robust_scm2double (stem->get_property ("stemlet-length"), 0.0)
1373                      + robust_scm2double (rest->get_property ("minimum-distance"), 0.0));
1374
1375   Real shift = d * ( ((beam_y - d * minimum_distance) - rest_dim) * d  <? 0.0);
1376
1377   shift /= staff_space;
1378   Real rad = Staff_symbol_referencer::line_count (rest) * staff_space / 2;
1379
1380   /* Always move discretely by half spaces */
1381   shift = ceil (fabs (shift * 2.0)) / 2.0 * sign (shift);
1382
1383   /* Inside staff, move by whole spaces*/
1384   if ( (rest->extent (common_y, Y_AXIS)[d] + staff_space * shift) * d
1385       < rad
1386       || (rest->extent (common_y, Y_AXIS)[-d] + staff_space * shift) * -d
1387       < rad)
1388     shift = ceil (fabs (shift)) *sign (shift);
1389
1390   return scm_make_real (staff_space * shift);
1391 }
1392
1393 bool
1394 Beam::is_knee (Grob* me)
1395 {
1396   SCM k = me->get_property ("knee");
1397   if (scm_is_bool (k))
1398     return ly_scm2bool (k);
1399
1400   bool knee = false;
1401   int d = 0;
1402   for (SCM s = me->get_property ("stems"); scm_is_pair (s); s = scm_cdr (s))
1403     {
1404       Direction dir = get_grob_direction (unsmob_grob (scm_car (s)));
1405       if (d && d != dir)
1406         {
1407           knee = true;
1408           break;
1409         }
1410       d = dir;
1411     }
1412   
1413   me->set_property ("knee", ly_bool2scm (knee));
1414
1415   return knee;
1416 }
1417
1418 int
1419 Beam::get_direction_beam_count (Grob *me, Direction d )
1420 {
1421   Link_array<Grob>stems = 
1422     Pointer_group_interface__extract_grobs (me, (Grob*) 0, "stems");
1423   int bc = 0;
1424   
1425   for (int i = stems.size (); i--;)
1426     {
1427       /*
1428         Should we take invisible stems into account?
1429        */
1430       if (Stem::get_direction (stems[i]) == d)
1431         bc = bc >? (Stem::beam_multiplicity (stems[i]).length () + 1);
1432     }
1433
1434   return bc;
1435 }
1436
1437
1438 ADD_INTERFACE (Beam, "beam-interface",
1439                "A beam. \n\n"
1440                "The @code{thickness} property is the weight of beams, and is measured "
1441                "in  staffspace"
1442                ,
1443                "knee positioning-done position-callbacks "
1444                "concaveness dir-function quant-score auto-knee-gap gap "
1445                "gap-count chord-tremolo beamed-stem-shorten shorten least-squares-dy "
1446                "damping inspect-quants flag-width-function neutral-direction positions space-function "
1447                "thickness");
1448
1449