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