diff options
| author | Mike Solomon <mike@apollinemike.com> | 2012-08-27 23:47:04 +0200 |
|---|---|---|
| committer | Mike Solomon <mike@apollinemike.com> | 2012-08-27 23:47:04 +0200 |
| commit | 28f3294954eff1f263d3b2e3de1c520f4d2fbdfc (patch) | |
| tree | 8216447e447a4f84c1fb472b1da4e16e7469d691 | |
| parent | 6f4893fa86378aa4a637eedbde5efc4680efa5bf (diff) | |
Improvements in vertical skyline approximations (issue 2148).
The file stencil-integral.cc provides a suite of functions that
traverse a stencil and do linear approximations of its components.
These are then turned into boxes that are passed to the Skyline
constructor. This approximation is used for several vertical skylines
including those of VerticalAxisGroup and System. As a result of these
more accurate approximations, vertical spacing is more snug between
grobs.
Additionally, in axis-group-interface.cc, skylines of grobs are no
longer compared to a monolithic axis-group skyline but rather all
of the component skylines of the axis-group, allowing grobs to
be fit under other ones if there is space instead of always shifted over.
Two new python scripts allow to visualize the position of skylines.
All other changes provide functions that allow for better debugging
of Skylines, better approximations of grobs via skylines, and changes
to the measurement of distance between grobs via the new Skyline API.
This results in a significant time increase in score compilation for
objects with complex skylines such as all text grobs. For orchestral
scores, the increase is not as steep.
69 files changed, 3454 insertions, 514 deletions
diff --git a/flower/include/interval-set.hh b/flower/include/interval-set.hh index b0acda6509..6ea7b43173 100644 --- a/flower/include/interval-set.hh +++ b/flower/include/interval-set.hh @@ -23,20 +23,20 @@ #include "std-vector.hh" #include "interval.hh" -/* - A union of intervals in the real line. - - Abysmal performance (quadratic) for large N, hopefully we don't have - that large N. In any case, this should probably be rewritten to use - a balanced tree. -*/ -struct Interval_set +class Interval_set { - vector<Interval> allowed_regions_; - +public: Interval_set (); - void set_full (); - void remove_interval (Interval rm); + + static Interval_set interval_union (vector<Interval>); + + vector<Interval> const &intervals () const { return intervals_; } + vector<Interval>::const_iterator upper_bound (Real x) const; + Real nearest_point (Real x, Direction dir = CENTER) const; + Interval_set complement () const; + +private: + vector<Interval> intervals_; }; #endif /* INTERVAL_SET_HH */ diff --git a/flower/include/yaffut.hh b/flower/include/yaffut.hh index 8b10d23aa5..148d1a8801 100644 --- a/flower/include/yaffut.hh +++ b/flower/include/yaffut.hh @@ -21,6 +21,7 @@ #include <memory> #include <sstream> #include <stdexcept> +#include <unistd.h> #define YAFFUT_STRINGIZE(x) YAFFUT_STRINGIZE_(x) #define YAFFUT_STRINGIZE_(x) #x diff --git a/flower/interval-set.cc b/flower/interval-set.cc index 84bde76a9c..f1aaea59fc 100644 --- a/flower/interval-set.cc +++ b/flower/interval-set.cc @@ -22,55 +22,106 @@ /* A union of intervals in the real line. - Abysmal performance (quadratic) for large N, hopefully we don't have - that large N. In any case, this should probably be rewritten to use - a balanced tree. + This class gives good performance for finding the union of + a collection of intervals (n log n) and for testing if a point + belongs to the union (log n). It does not give an efficient way to + update the set (ie. by adding more intervals); to do this + efficiently would require a self-balancing tree, and it would not + be currently useful in lilypond anyway. */ Interval_set::Interval_set () { - set_full (); } -void -Interval_set::set_full () +Interval_set +Interval_set::interval_union (vector<Interval> ivs) { - allowed_regions_.clear (); - Interval s; - s.set_full (); - allowed_regions_.push_back (s); + vector_sort (ivs, Interval::left_less); + + Interval_set ret; + + if (ivs.empty ()) + return ret; + + ret.intervals_.push_back (ivs.front ()); + + // Go over the intervals from left to right. If the current interval + // overlaps with the last one, merge them. Otherwise, append the + // current interval to the list. + for (vsize i = 1; i < ivs.size (); ++i) + { + Interval iv = ivs[i]; + Interval &last = ret.intervals_.back (); + + if (last[RIGHT] >= iv[LEFT]) + // overlapping intervals: merge them + last[RIGHT] = max (last[RIGHT], iv[RIGHT]); + else if (!iv.is_empty ()) + ret.intervals_.push_back (iv); + } + + return ret; +} + +// Returns an iterator pointing to the first interval whose left +// endpoint is at least x. That interval may or may not contain x. +vector<Interval>::const_iterator +Interval_set::upper_bound (Real x) const +{ + Interval xx (x, x); + return std::upper_bound (intervals_.begin (), intervals_.end (), xx, Interval::left_less); } -void -Interval_set::remove_interval (Interval rm) +Real +Interval_set::nearest_point (Real x, Direction d) const { - for (vsize i = 0; i < allowed_regions_.size ();) + Real left = -infinity_f; // The closest point to the left of x. + Real right = infinity_f; // The closest point to the right of x. + + vector<Interval>::const_iterator i = upper_bound (x); + if (i != intervals_.end ()) + right = (*i)[LEFT]; + + if (i != intervals_.begin ()) { - Interval s = rm; - - s.intersect (allowed_regions_[i]); - - if (!s.is_empty ()) - { - Interval before = allowed_regions_[i]; - Interval after = allowed_regions_[i]; - - before[RIGHT] = s[LEFT]; - after[LEFT] = s[RIGHT]; - - if (!before.is_empty () && before.length () > 0.0) - { - allowed_regions_.insert (allowed_regions_.begin () + (long)i, before); - i++; - } - allowed_regions_.erase (allowed_regions_.begin () + (long)i); - if (!after.is_empty () && after.length () > 0.0) - { - allowed_regions_.insert (allowed_regions_.begin () + (long)i, after); - i++; - } - } - else - i++; + Interval left_iv = *(i - 1); + // left_iv[LEFT] is guaranteed to be less than x. So if + // left_iv[RIGHT] >= x then left_iv contains x, which must then + // be the nearest point to x. + if (left_iv[RIGHT] >= x) + return x; + + left = left_iv[RIGHT]; + } + + if (d == RIGHT) + return right; + if (d == LEFT) + return left; + else + return (right - x) < (x - left) ? right : left; +} + +Interval_set +Interval_set::complement () const +{ + Interval_set ret; + + if (intervals_.empty ()) + { + ret.intervals_.push_back (Interval (-infinity_f, infinity_f)); + return ret; } + + if (intervals_[0][LEFT] > -infinity_f) + ret.intervals_.push_back (Interval (-infinity_f, intervals_[0][LEFT])); + + for (vsize i = 1; i < intervals_.size (); ++i) + ret.intervals_.push_back (Interval (intervals_[i - 1][RIGHT], intervals_[i][LEFT])); + + if (intervals_.back ()[RIGHT] < infinity_f) + ret.intervals_.push_back (Interval (intervals_.back ()[RIGHT], infinity_f)); + + return ret; } diff --git a/flower/test-interval-set.cc b/flower/test-interval-set.cc new file mode 100644 index 0000000000..5b4d1f637e --- /dev/null +++ b/flower/test-interval-set.cc @@ -0,0 +1,110 @@ +/* + This file is part of LilyPond, the GNU music typesetter. + + Copyright (C) 2012 Joe Neeman <joeneeman@gmail.com> + + LilyPond is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + LilyPond is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with LilyPond. If not, see <http://www.gnu.org/licenses/>. +*/ + +#include "interval-set.hh" + +#include "yaffut.hh" + +using namespace std; + +FUNC (interval_set_union) +{ + vector<Interval> ivs; + + // Overlapping intervals. + ivs.push_back (Interval (-1, 1)); + ivs.push_back (Interval (0, 3)); + ivs.push_back (Interval (1, 2)); + Interval_set result = Interval_set::interval_union (ivs); + EQUAL (result.intervals ().size (), 1); + // Compare intervals using to_string, since yaffut doesn't know how to compare intervals. + EQUAL (result.intervals ()[0].to_string (), Interval (-1, 3).to_string ()); + + // Non-overlapping intervals. + ivs.push_back (Interval (-5, -4)); + result = Interval_set::interval_union (ivs); + EQUAL (result.intervals ().size (), 2); + EQUAL (result.intervals ()[0].to_string (), Interval (-5, -4).to_string ()); + EQUAL (result.intervals ()[1].to_string (), Interval (-1, 3).to_string ()); + + // Infinite intervals. + ivs.push_back (Interval (-infinity_f, -4)); + result = Interval_set::interval_union (ivs); + EQUAL (result.intervals ().size (), 2); + EQUAL (result.intervals ()[0].to_string (), Interval (-infinity_f, -4).to_string ()); + EQUAL (result.intervals ()[1].to_string (), Interval (-1, 3).to_string ()); + + // Empty intervals. + ivs.push_back (Interval (infinity_f, -infinity_f)); + result = Interval_set::interval_union (ivs); + EQUAL (result.intervals ().size (), 2); +} + +FUNC (interval_set_nearest_point) +{ + vector<Interval> ivs; + + ivs.push_back (Interval (-3, -1)); + ivs.push_back (Interval (1, 3)); + Interval_set set = Interval_set::interval_union (ivs); + + // If the point is in the set, direction does not matter. + EQUAL (set.nearest_point (-2, UP), -2); + EQUAL (set.nearest_point (-2, DOWN), -2); + EQUAL (set.nearest_point (-2, CENTER), -2); + + // If the point is not in the set, direction does matter. + EQUAL (set.nearest_point (-0.5, UP), 1); + EQUAL (set.nearest_point (-0.5, DOWN), -1); + EQUAL (set.nearest_point (-0.5, CENTER), -1); + EQUAL (set.nearest_point (0.5, CENTER), 1); + + // The return value can be +- infinity. + EQUAL (set.nearest_point (5, UP), infinity_f); + EQUAL (set.nearest_point (5, DOWN), 3); + EQUAL (set.nearest_point (-5, DOWN), -infinity_f); + EQUAL (set.nearest_point (-5, UP), -3); +} + +FUNC (interval_set_complement) +{ + vector<Interval> ivs; + + ivs.push_back (Interval (-3, -1)); + ivs.push_back (Interval (1, 3)); + Interval_set set = Interval_set::interval_union (ivs).complement (); + EQUAL (set.intervals ().size (), 3); + EQUAL (set.intervals ()[0].to_string (), Interval (-infinity_f, -3).to_string ()); + EQUAL (set.intervals ()[1].to_string (), Interval (-1, 1).to_string ()); + EQUAL (set.intervals ()[2].to_string (), Interval (3, infinity_f).to_string ()); + + // Half-infinite sets are handled correctly. + ivs.push_back (Interval (-infinity_f, -2)); + set = Interval_set::interval_union (ivs).complement (); + EQUAL (set.intervals ().size (), 2); + EQUAL (set.intervals ()[0].to_string (), Interval (-1, 1).to_string ()); + EQUAL (set.intervals ()[1].to_string (), Interval (3, infinity_f).to_string ()); + + // Full and empty sets are handled correctly. + set = Interval_set ().complement (); + EQUAL (set.intervals ().size (), 1); + EQUAL (set.intervals ()[0].to_string (), Interval (-infinity_f, infinity_f).to_string ()); + set = set.complement (); + EQUAL (set.intervals ().size (), 0); +} diff --git a/input/regression/hairpin-clef.ly b/input/regression/hairpin-clef.ly new file mode 100644 index 0000000000..8450129f72 --- /dev/null +++ b/input/regression/hairpin-clef.ly @@ -0,0 +1,10 @@ +\version "2.15.28" + +\header { + texidoc = "Broken hairpins are not printed too high after treble clefs. +" +} + +\relative c'' { + c4^\< c c c \break c c c c\! | +} diff --git a/input/regression/hairpin-key-signature.ly b/input/regression/hairpin-key-signature.ly new file mode 100644 index 0000000000..ff88aa19aa --- /dev/null +++ b/input/regression/hairpin-key-signature.ly @@ -0,0 +1,11 @@ +\version "2.15.28" + +\header { + texidoc = "Broken hairpins are not printed too high after key signatures. +" +} + +\relative c'' { + \key e \major + c4^\< c c c \break c c c c\! | +} diff --git a/input/regression/outside-staff-placement-directive.ly b/input/regression/outside-staff-placement-directive.ly new file mode 100644 index 0000000000..0e1871cc45 --- /dev/null +++ b/input/regression/outside-staff-placement-directive.ly @@ -0,0 +1,106 @@ +\version "2.17.0" + +\header { + texidoc = "@code{VerticalAxisGroup} grobs can place outside staff objects +using one of the four directives shown below. +" +} + + +\layout { + ragged-right = ##t + indent = 0.0 + \context { + \Voice + \remove "Ligature_bracket_engraver" + \consists "Mensural_ligature_engraver" + } + \context { + \Score + \override SpacingSpanner #'packed-spacing = ##t + \override PaperColumn #'keep-inside-line = ##f + } +} + +music = \context Voice { + \clef "petrucci-c4" + \set Staff.printKeyCancellation = ##f + \cadenzaOn % turn off bar lines + \accidentalStyle "forget" + \textLengthOn + +% ligaturae binaria + + \[ + b\breve^\markup { \column { { \bold "ligaturae binaria" } "BL" } } + g\longa + \] + + \[ + g\breve^\markup { "BL" } + b\longa + \] + + \[ + b\longa^\markup { "LL" } + g + \] + + \[ + g\longa^\markup { "LL" } + b + \] + + \[ + b\breve^\markup { "BB" } + g + \] + + \[ + g\breve^\markup { "BB" } + b + \] + + \[ + b\longa^\markup { "LB" } + g\breve + \] + + \[ + g\longa^\markup { "LB" } + b\breve + \] + + \[ + b1^\markup { "SS" } + g + \] + + \[ + g1^\markup { "SS" } + b + \] + + \bar "|" +} + +{ + \override Staff.VerticalAxisGroup #'outside-staff-placement-directive = + #'left-to-right-polite + \music +} +{ + \override Staff.VerticalAxisGroup #'outside-staff-placement-directive = + #'left-to-right-greedy + \music +} +{ + \override Staff.VerticalAxisGroup #'outside-staff-placement-directive = + #'right-to-left-polite + \music +} +{ + \override Staff.VerticalAxisGroup #'outside-staff-placement-directive = + #'right-to-left-greedy + \music +} diff --git a/input/regression/skiptypesetting-all-true.ly b/input/regression/skiptypesetting-all-true.ly index d33f2c5ac2..171cae4084 100644 --- a/input/regression/skiptypesetting-all-true.ly +++ b/input/regression/skiptypesetting-all-true.ly @@ -1,10 +1,4 @@ \version "2.16.0" -#(ly:expect-warning (_ "didn't find a vertical alignment in this system")) -#(ly:expect-warning (_ "didn't find a vertical alignment in this system")) -#(ly:expect-warning (_ "didn't find a vertical alignment in this system")) -#(ly:expect-warning (_ "didn't find a vertical alignment in this system")) -#(ly:expect-warning (_ "didn't find a vertical alignment in this system")) -#(ly:expect-warning (_ "didn't find a vertical alignment in this system")) #(ly:expect-warning (_ "system with empty extent")) #(ly:expect-warning (_ "didn't find a vertical alignment in this system")) diff --git a/input/regression/slur-dynamics.ly b/input/regression/slur-dynamics.ly index 6e76f750c7..38a9c3288d 100644 --- a/input/regression/slur-dynamics.ly +++ b/input/regression/slur-dynamics.ly @@ -11,7 +11,7 @@ } \relative { - b(^"dyn outside" b f'\p b,) + b( b f'\p b,) g( d'\< d \! g,) } diff --git a/input/regression/text-script-vertical-skylines.ly b/input/regression/text-script-vertical-skylines.ly new file mode 100644 index 0000000000..1eab7f15aa --- /dev/null +++ b/input/regression/text-script-vertical-skylines.ly @@ -0,0 +1,13 @@ +\version "2.15.28" + +\header { + texidoc = "By default, @code{TextScript} vertical skylines allow +for stack @code{TextScript} grobs to fit snugly over each other instead +of moving the entire distance of the bounding box. +" +} + +\relative c' { + a^\markup { \filled-box #'(0 . 2) #'(0 . 20) #0 hello} + a^\markup { world } +}
\ No newline at end of file diff --git a/input/regression/tuplet-bracket-vertical-skylines.ly b/input/regression/tuplet-bracket-vertical-skylines.ly new file mode 100644 index 0000000000..74e1d9aeb8 --- /dev/null +++ b/input/regression/tuplet-bracket-vertical-skylines.ly @@ -0,0 +1,12 @@ +\version "2.15.28" + +\header { + texidoc = "Tuplet brackets do not push objects with outside-staff-priority +too high. +" +} + +\relative c' { + \override TupletBracket #'direction = #UP + \times 1/1 { a^"foo" a' a' a' } +} diff --git a/input/regression/tuplet-number-outside-staff-positioning.ly b/input/regression/tuplet-number-outside-staff-positioning.ly new file mode 100644 index 0000000000..702535200c --- /dev/null +++ b/input/regression/tuplet-number-outside-staff-positioning.ly @@ -0,0 +1,17 @@ +\version "2.17.0" + +\header { + + texidoc = "Grobs whose parents have @code{outside-staff-priority} set +should figure into the vertical skyline of the @code{VerticalAxisGroup} +such that grobs with a higher @code{outside-staff-priority} are correctly +positioned above them. +" + +} + +\relative c'' { + \override TupletBracket #'outside-staff-priority = #1 + \override TupletNumber #'font-size = #5 + \times 2/3 { a4\trill a\trill^"foo" a\trill } +}
\ No newline at end of file diff --git a/input/regression/volta-bracket-vertical-skylines.ly b/input/regression/volta-bracket-vertical-skylines.ly new file mode 100644 index 0000000000..20ebcb95a0 --- /dev/null +++ b/input/regression/volta-bracket-vertical-skylines.ly @@ -0,0 +1,13 @@ +\version "2.15.28" + +\header { + texidoc = "Volta brackets are vertically fit to objects below them. +" +} + +\new Staff { + \repeat volta 3 { r2 a''''4 r4 } + \alternative { { r2 d''''4 r4 } { r2 d''''4 r4 } { r2 d''''4 r4 } } + \repeat volta 3 { r2 a''''4 r4 } + \alternative { { r2 a''''4 r4 } { r2 a''''4 r4 } { r2 a''''4 r4 } } +}
\ No newline at end of file diff --git a/lily/accidental-placement.cc b/lily/accidental-placement.cc index ff67181434..5b6cfb735b 100644 --- a/lily/accidental-placement.cc +++ b/lily/accidental-placement.cc @@ -270,8 +270,8 @@ set_ape_skylines (Accidental_placement_entry *ape, last_octave = p->get_octave (); last_alteration = p->get_alteration (); } - ape->left_skyline_ = Skyline (ape->extents_, 0, Y_AXIS, LEFT); - ape->right_skyline_ = Skyline (ape->extents_, 0, Y_AXIS, RIGHT); + ape->left_skyline_ = Skyline (ape->extents_, Y_AXIS, LEFT); + ape->right_skyline_ = Skyline (ape->extents_, Y_AXIS, RIGHT); } static vector<Grob *> @@ -350,7 +350,7 @@ build_heads_skyline (vector<Grob *> const &heads_and_stems, head_extents.push_back (Box (heads_and_stems[i]->extent (common[X_AXIS], X_AXIS), heads_and_stems[i]->pure_height (common[Y_AXIS], 0, INT_MAX))); - return Skyline (head_extents, 0, Y_AXIS, LEFT); + return Skyline (head_extents, Y_AXIS, LEFT); } /* diff --git a/lily/accidental.cc b/lily/accidental.cc index 77129b6f9d..3cc399f84d 100644 --- a/lily/accidental.cc +++ b/lily/accidental.cc @@ -231,6 +231,7 @@ ADD_INTERFACE (Accidental_interface, "avoid-slur " "forced " "glyph-name-alist " + "glyph-name " "hide-tied-accidental-after-break " "parenthesized " "restore-first " diff --git a/lily/align-interface.cc b/lily/align-interface.cc index 0e350c1426..e32cd11b2b 100644 --- a/lily/align-interface.cc +++ b/lily/align-interface.cc @@ -121,7 +121,7 @@ get_skylines (Grob *me, Box b; b[a] = begin_of_line_extent; b[other_axis (a)] = Interval (-infinity_f, -1); - skylines.insert (b, 0, other_axis (a)); + skylines.insert (b, other_axis (a)); } } @@ -130,7 +130,7 @@ get_skylines (Grob *me, Box b; b[a] = extent; b[other_axis (a)] = Interval (0, infinity_f); - skylines.insert (b, 0, other_axis (a)); + skylines.insert (b, other_axis (a)); } } diff --git a/lily/axis-group-interface.cc b/lily/axis-group-interface.cc index febff36afb..707e045c9b 100644 --- a/lily/axis-group-interface.cc +++ b/lily/axis-group-interface.cc @@ -19,11 +19,14 @@ #include "axis-group-interface.hh" +#include <map> + #include "align-interface.hh" #include "directional-element-interface.hh" #include "grob-array.hh" #include "hara-kiri-group-spanner.hh" #include "international.hh" +#include "interval-set.hh" #include "lookup.hh" #include "paper-column.hh" #include "paper-score.hh" @@ -40,6 +43,14 @@ static bool pure_staff_priority_less (Grob *const &g1, Grob *const &g2); +Real Axis_group_interface::default_outside_staff_padding_ = 0.46; + +Real +Axis_group_interface::get_default_outside_staff_padding () +{ + return default_outside_staff_padding_; +} + void Axis_group_interface::add_element (Grob *me, Grob *e) { @@ -233,7 +244,7 @@ Axis_group_interface::adjacent_pure_heights (SCM smob) continue; bool outside_staff = scm_is_number (g->get_property ("outside-staff-priority")); - Real padding = robust_scm2double (g->get_property ("outside-staff-padding"), 0.5); + Real padding = robust_scm2double (g->get_property ("outside-staff-padding"), get_default_outside_staff_padding ()); // When we encounter the first outside-staff grob, make a copy // of the current heights to use as an estimate for the staff heights. @@ -381,7 +392,7 @@ SCM Axis_group_interface::calc_skylines (SCM smob) { Grob *me = unsmob_grob (smob); - extract_grob_set (me, "elements", elts); + extract_grob_set (me, Grob_array::unsmob (me->get_object ("vertical-skyline-elements")) ? "vertical-skyline-elements" : "elements", elts); Skyline_pair skylines = skyline_spacing (me, elts); return skylines.smobbed_copy (); @@ -603,116 +614,217 @@ pure_staff_priority_less (Grob *const &g1, Grob *const &g2) } static void -add_boxes (Grob *me, Grob *x_common, Grob *y_common, vector<Box> *const boxes, Skyline_pair *skylines) +add_interior_skylines (Grob *me, Grob *x_common, Grob *y_common, vector<Skyline_pair> *skylines) { - /* if a child has skylines, use them instead of the extent box */ - if (Skyline_pair *pair = Skyline_pair::unsmob (me->get_property ("vertical-skylines"))) - { - Skyline_pair s = *pair; - s.shift (me->relative_coordinate (x_common, X_AXIS)); - s.raise (me->relative_coordinate (y_common, Y_AXIS)); - skylines->merge (s); - } - else if (Grob_array *elements = unsmob_grob_array (me->get_object ("elements"))) + if (Grob_array *elements = unsmob_grob_array (me->get_object ("elements"))) { for (vsize i = 0; i < elements->size (); i++) - add_boxes (elements->grob (i), x_common, y_common, boxes, skylines); + add_interior_skylines (elements->grob (i), x_common, y_common, skylines); } else if (!scm_is_number (me->get_property ("outside-staff-priority")) && !to_boolean (me->get_property ("cross-staff"))) { - boxes->push_back (Box (me->extent (x_common, X_AXIS), - me->extent (y_common, Y_AXIS))); + Skyline_pair *maybe_pair = Skyline_pair::unsmob (me->get_property ("vertical-skylines")); + if (!maybe_pair) + return; + if (maybe_pair->is_empty ()) + return; + skylines->push_back (Skyline_pair (*maybe_pair)); + skylines->back ().shift (me->relative_coordinate (x_common, X_AXIS)); + skylines->back ().raise (me->relative_coordinate (y_common, Y_AXIS)); } } -/* We want to avoid situations like this: - still more text - more text - text - ------------------- - staff - ------------------- - - The point is that "still more text" should be positioned under - "more text". In order to achieve this, we place the grobs in several - passes. We keep track of the right-most horizontal position that has been - affected by the current pass so far (actually we keep track of 2 - positions, one for above the staff, one for below). - - In each pass, we loop through the unplaced grobs from left to right. - If the grob doesn't overlap the right-most affected position, we place it - (and then update the right-most affected position to point to the right - edge of the just-placed grob). Otherwise, we skip it until the next pass. -*/ +// Raises the grob elt (whose skylines are given by h_skyline +// and v_skyline) so that it doesn't intersect with staff_skyline, +// or with anything in other_h_skylines and other_v_skylines. +void +avoid_outside_staff_collisions (Grob *elt, + Skyline_pair *v_skyline, + Real padding, + Real horizon_padding, + vector<Skyline_pair> const &other_v_skylines, + vector<Real> const &other_padding, + vector<Real> const &other_horizon_padding, + Direction const dir) +{ + assert (other_v_skylines.size () == other_padding.size ()); + assert (other_v_skylines.size () == other_horizon_padding.size ()); + vector<Interval> forbidden_intervals; + for (vsize j = 0; j < other_v_skylines.size (); j++) + { + Skyline_pair const &v_other = other_v_skylines[j]; + Real pad = (padding + other_padding[j]); + Real horizon_pad = (horizon_padding + other_horizon_padding[j]); + + // We need to push elt up by at least this much to be above v_other. + Real up = (*v_skyline)[DOWN].distance (v_other[UP], horizon_pad) + pad; + // We need to push elt down by at least this much to be below v_other. + Real down = (*v_skyline)[UP].distance (v_other[DOWN], horizon_pad) + pad; + + forbidden_intervals.push_back (Interval (-down, up)); + } + + Interval_set allowed_shifts + = Interval_set::interval_union (forbidden_intervals).complement (); + Real move = allowed_shifts.nearest_point (0, dir); + v_skyline->raise (move); + elt->translate_axis (move, Y_AXIS); +} + +SCM +valid_outside_staff_placement_directive (Grob *me) +{ + SCM directive = me->get_property ("outside-staff-placement-directive"); + + if ((directive == ly_symbol2scm ("left-to-right-greedy")) + || (directive == ly_symbol2scm ("left-to-right-polite")) + || (directive == ly_symbol2scm ("right-to-left-greedy")) + || (directive == ly_symbol2scm ("right-to-left-polite"))) + return directive; + + me->warning (_f ("\"%s\" is not a valid outside-staff-placement-directive", + robust_symbol2string (directive, "").c_str ())); + + return ly_symbol2scm ("left-to-right-polite"); +} + +// Shifts the grobs in elements to ensure that they (and any +// connected riders) don't collide with the staff skylines +// or anything in all_X_skylines. Afterwards, the skylines +// of the grobs in elements will be added to all_v_skylines. static void -add_grobs_of_one_priority (Skyline_pair *const skylines, +add_grobs_of_one_priority (Grob *me, + Drul_array<vector<Skyline_pair> > *all_v_skylines, + Drul_array<vector<Real> > *all_paddings, + Drul_array<vector<Real> > *all_horizon_paddings, vector<Grob *> elements, Grob *x_common, - Grob *y_common) + Grob *y_common, + multimap<Grob *, Grob *> const &riders) { - vector<Box> boxes; - Drul_array<Real> last_affected_position; - reverse (elements); + SCM directive + = valid_outside_staff_placement_directive (me); + + bool l2r = ((directive == ly_symbol2scm ("left-to-right-greedy")) + || (directive == ly_symbol2scm ("left-to-right-polite"))); + + bool polite = ((directive == ly_symbol2scm ("left-to-right-polite")) + || (directive == ly_symbol2scm ("right-to-left-polite"))); + + vector<Box> boxes; + vector<Skyline_pair> skylines_to_merge; + + // We want to avoid situations like this: + // still more text + // more text + // text + // ------------------- + // staff + // ------------------- + + // The point is that "still more text" should be positioned under + // "more text". In order to achieve this, we place the grobs in several + // passes. We keep track of the right-most horizontal position that has been + // affected by the current pass so far (actually we keep track of 2 + // positions, one for above the staff, one for below). + + // In each pass, we loop through the unplaced grobs from left to right. + // If the grob doesn't overlap the right-most affected position, we place it + // (and then update the right-most affected position to point to the right + // edge of the just-placed grob). Otherwise, we skip it until the next pass. while (!elements.empty ()) { - last_affected_position[UP] = -infinity_f; - last_affected_position[DOWN] = -infinity_f; - /* do one pass */ - for (vsize i = elements.size (); i--;) + Drul_array<Real> last_end (-infinity_f, -infinity_f); + vector<Grob *> skipped_elements; + for (vsize i = l2r ? 0 : elements.size (); + l2r ? i < elements.size () : i--; + l2r ? i++ : 0) { - Direction dir = get_grob_direction (elements[i]); + Grob *elt = elements[i]; + Real padding + = robust_scm2double (elt->get_property ("outside-staff-padding"), 0.25); + Real horizon_padding + = robust_scm2double (elt->get_property ("outside-staff-horizontal-padding"), 0.0); + Interval x_extent = elt->extent (x_common, X_AXIS); + x_extent.widen (horizon_padding); + + Direction dir = get_grob_direction (elt); if (dir == CENTER) { warning (_ ("an outside-staff object should have a direction, defaulting to up")); dir = UP; } - Box b (elements[i]->extent (x_common, X_AXIS), - elements[i]->extent (y_common, Y_AXIS)); - SCM horizon_padding_scm = elements[i]->get_property ("outside-staff-horizontal-padding"); - Real horizon_padding = robust_scm2double (horizon_padding_scm, 0.0); + if (x_extent[LEFT] <= last_end[dir] && polite) + { + skipped_elements.push_back (elt); + continue; + } + last_end[dir] = x_extent[RIGHT]; - if (b[X_AXIS][LEFT] - 2 * horizon_padding < last_affected_position[dir]) + Skyline_pair *v_orig = Skyline_pair::unsmob (elt->get_property ("vertical-skylines")); + if (v_orig->is_empty ()) continue; - if (!b[X_AXIS].is_empty () && !b[Y_AXIS].is_empty ()) + // Find the riders associated with this grob, and merge their + // skylines with elt's skyline. + typedef multimap<Grob *, Grob *>::const_iterator GrobMapIterator; + pair<GrobMapIterator, GrobMapIterator> range = riders.equal_range (elt); + vector<Skyline_pair> rider_v_skylines; + for (GrobMapIterator j = range.first; j != range.second; j++) { - boxes.clear (); - boxes.push_back (b); - Skyline other = Skyline (boxes, horizon_padding, X_AXIS, -dir); - Real padding = robust_scm2double (elements[i]->get_property ("outside-staff-padding"), 0.5); - Real dist = (*skylines)[dir].distance (other) + padding; - - if (dist > 0) + Grob *rider = j->second; + Skyline_pair *v_rider = Skyline_pair::unsmob (rider->get_property ("vertical-skylines")); + if (v_rider) { - b.translate (Offset (0, dir * dist)); - elements[i]->translate_axis (dir * dist, Y_AXIS); + Skyline_pair copy (*v_rider); + copy.shift (rider->relative_coordinate (x_common, X_AXIS)); + copy.raise (rider->relative_coordinate (y_common, Y_AXIS)); + rider_v_skylines.push_back (copy); } - skylines->insert (b, 0, X_AXIS); - elements[i]->set_property ("outside-staff-priority", SCM_BOOL_F); - last_affected_position[dir] = b[X_AXIS][RIGHT]; } - - /* - Ugh: quadratic. --hwn - */ - elements.erase (elements.begin () + i); + Skyline_pair v_skylines (*v_orig); + v_skylines.shift (elt->relative_coordinate (x_common, X_AXIS)); + v_skylines.raise (elt->relative_coordinate (y_common, Y_AXIS)); + v_skylines.merge (Skyline_pair (rider_v_skylines)); + + avoid_outside_staff_collisions (elt, + &v_skylines, + padding, + horizon_padding, + (*all_v_skylines)[dir], + (*all_paddings)[dir], + (*all_horizon_paddings)[dir], + dir); + + elt->set_property ("outside-staff-priority", SCM_BOOL_F); + (*all_v_skylines)[dir].push_back (v_skylines); + (*all_paddings)[dir].push_back (padding); + (*all_horizon_paddings)[dir].push_back (horizon_padding); } + swap (elements, skipped_elements); + skipped_elements.clear (); } } -bool -Axis_group_interface::has_outside_staff_parent (Grob *me) +// If the Grob has a Y-ancestor with outside-staff-priority, return it. +// Otherwise, return 0. +Grob * +Axis_group_interface::outside_staff_ancestor (Grob *me) { - return (me - ? (scm_is_number (me->get_property ("outside-staff-priority")) - || has_outside_staff_parent (me->get_parent (Y_AXIS))) - : false); + Grob *parent = me->get_parent (Y_AXIS); + if (!parent) + return 0; + + if (scm_is_number (parent->get_property ("outside-staff-priority"))) + return parent; + + return outside_staff_ancestor (parent); } -// TODO: it is tricky to correctly handle skyline placement of cross-staff grobs. +// It is tricky to correctly handle skyline placement of cross-staff grobs. // For example, cross-staff beams cannot be formatted until the distance between // staves is known and therefore any grobs that depend on the beam cannot be placed // until the skylines are known. On the other hand, the distance between staves should @@ -724,6 +836,19 @@ Axis_group_interface::has_outside_staff_parent (Grob *me) Skyline_pair Axis_group_interface::skyline_spacing (Grob *me, vector<Grob *> elements) { + for (vsize i = 0; i < elements.size (); i++) + /* + As a sanity check, we make sure that no grob with an outside staff priority + has a Y-parent that also has an outside staff priority, which would result + in two movings. + */ + if (scm_is_number (elements[i]->get_property ("outside-staff-priority")) + && outside_staff_ancestor (elements[i])) + { + elements[i]->warning ("Cannot set outside-staff-priority for element and elements' Y parent."); + elements[i]->set_property ("outside-staff-priority", SCM_BOOL_F); + } + /* For grobs with an outside-staff-priority, the sorting function might call extent and cause suicide. This breaks the contract that is required for the STL sort function. To avoid this, we make sure that any suicides @@ -739,23 +864,44 @@ Axis_group_interface::skyline_spacing (Grob *me, vector<Grob *> elements) assert (y_common == me); - vsize i = 0; - vector<Box> boxes; + // A rider is a grob that is not outside-staff, but has an outside-staff + // ancestor. In that case, the rider gets moved along with its ancestor. + multimap<Grob *, Grob *> riders; - Skyline_pair skylines; + vsize i = 0; + vector<Skyline_pair> inside_staff_skylines; for (i = 0; i < elements.size () && !scm_is_number (elements[i]->get_property ("outside-staff-priority")); i++) - if (!(to_boolean (elements[i]->get_property ("cross-staff")) || has_outside_staff_parent (elements[i]))) - add_boxes (elements[i], x_common, y_common, &boxes, &skylines); + { + Grob *elt = elements[i]; + Grob *ancestor = outside_staff_ancestor (elt); + if (!(to_boolean (elt->get_property ("cross-staff")) || ancestor)) + add_interior_skylines (elt, x_common, y_common, &inside_staff_skylines); + if (ancestor) + riders.insert (pair<Grob *, Grob *> (ancestor, elt)); + } + + Skyline_pair skylines (inside_staff_skylines); + + // These are the skylines of all outside-staff grobs + // that have already been processed. We keep them around in order to + // check them for collisions with the currently active outside-staff grob. + Drul_array<vector<Skyline_pair> > all_v_skylines; + Drul_array<vector<Real> > all_paddings; + Drul_array<vector<Real> > all_horizon_paddings; + for (UP_and_DOWN (d)) + { + all_v_skylines[d].push_back (skylines); + all_paddings[d].push_back (0); + all_horizon_paddings[d].push_back (0); + } - SCM padding_scm = me->get_property ("skyline-horizontal-padding"); - Real padding = robust_scm2double (padding_scm, 0.1); - skylines.merge (Skyline_pair (boxes, padding, X_AXIS)); for (; i < elements.size (); i++) { if (to_boolean (elements[i]->get_property ("cross-staff"))) continue; + // Collect all the outside-staff grobs that have a particular priority. SCM priority = elements[i]->get_property ("outside-staff-priority"); vector<Grob *> current_elts; current_elts.push_back (elements[i]); @@ -767,9 +913,26 @@ Axis_group_interface::skyline_spacing (Grob *me, vector<Grob *> elements) ++i; } - add_grobs_of_one_priority (&skylines, current_elts, x_common, y_common); + add_grobs_of_one_priority (me, + &all_v_skylines, + &all_paddings, + &all_horizon_paddings, + current_elts, + x_common, + y_common, + riders); } + + // Now everything in all_v_skylines has been shifted appropriately; merge + // them all into skylines to get the complete outline. + Skyline_pair other_skylines (all_v_skylines[UP]); + other_skylines.merge (Skyline_pair (all_v_skylines[DOWN])); + skylines.merge (other_skylines); + + // We began by shifting my skyline to be relative to the common refpoint; now + // shift it back. skylines.shift (-me->relative_coordinate (x_common, X_AXIS)); + return skylines; } @@ -845,6 +1008,7 @@ ADD_INTERFACE (Axis_group_interface, "nonstaff-nonstaff-spacing " "nonstaff-relatedstaff-spacing " "nonstaff-unrelatedstaff-spacing " + "outside-staff-placement-directive " "pure-relevant-grobs " "pure-relevant-items " "pure-relevant-spanners " @@ -853,7 +1017,7 @@ ADD_INTERFACE (Axis_group_interface, "staff-grouper " "staff-staff-spacing " "system-Y-offset " - "vertical-skylines " + "vertical-skyline-elements " "X-common " "Y-common " ); diff --git a/lily/beam.cc b/lily/beam.cc index d73169a917..e5ea57d53b 100644 --- a/lily/beam.cc +++ b/lily/beam.cc @@ -848,9 +848,7 @@ Beam::consider_auto_knees (Grob *me) if (!scm_is_number (scm)) return; - Interval_set gaps; - - gaps.set_full (); + vector<Interval> forbidden_intervals; extract_grob_set (me, "normal-stems", stems); @@ -884,15 +882,17 @@ Beam::consider_auto_knees (Grob *me) } head_extents_array.push_back (head_extents); - gaps.remove_interval (head_extents); + forbidden_intervals.push_back (head_extents); } Interval max_gap; Real max_gap_len = 0.0; - for (vsize i = gaps.allowed_regions_.size () - 1; i != VPOS; i--) + vector<Interval> allowed_regions + = Interval_set::interval_union (forbidden_intervals).complement ().intervals (); + for (vsize i = allowed_regions.size () - 1; i != VPOS; i--) { - Interval gap = gaps.allowed_regions_[i]; + Interval gap = allowed_regions[i]; /* the outer gaps are not knees. @@ -1361,6 +1361,12 @@ Beam::pure_rest_collision_callback (SCM smob, rest_max_pos[UP] ) * ss / 2.0 - previous; + + // So that ceil below kicks in for rests that would otherwise brush + // up against a beam quanted to a ledger line, add a bit of space + // between the beam and the rest. + shift += (0.01 * beamdir); + /* Always move by a whole number of staff spaces */ shift = ceil (fabs (shift / ss)) * ss * sign (shift); diff --git a/lily/bezier.cc b/lily/bezier.cc index c4cdbb1c7b..d926712403 100644 --- a/lily/bezier.cc +++ b/lily/bezier.cc @@ -140,6 +140,24 @@ Bezier::curve_point (Real t) const return o; } +Real +Bezier::slope_at_point (Real t) const +{ + Offset second_order[3]; + Offset third_order[2]; + + for (vsize i = 0; i < 3; i++) + second_order[i] = ((control_[i + 1] - control_[i]) * t) + control_[i]; + + for (vsize i = 0; i < 2; i++) + third_order[i] = ((second_order[i + 1] - second_order[i]) * t) + second_order[i]; + + if (third_order[1][X_AXIS] - third_order[0][X_AXIS] == 0) + return infinity_f; + + return (third_order[1][Y_AXIS] - third_order[0][Y_AXIS]) / (third_order[1][X_AXIS] - third_order[0][X_AXIS]); +} + /* Cache binom (3, j) t^j (1-t)^{3-j} */ diff --git a/lily/box.cc b/lily/box.cc index df4770ff78..52af33a142 100644 --- a/lily/box.cc +++ b/lily/box.cc @@ -33,6 +33,13 @@ Box::unite (Box b) interval_a_[i].unite (b[i]); } +Real +Box::area () const +{ + return interval_a_[X_AXIS].length () + * interval_a_[Y_AXIS].length (); +} + Box::Box () { } diff --git a/lily/clef.cc b/lily/clef.cc index 3c1ca37525..b58bef9987 100644 --- a/lily/clef.cc +++ b/lily/clef.cc @@ -63,6 +63,7 @@ Clef::print (SCM smob) Stencil out = fm->find_by_name (glyph); if (out.is_empty ()) me->warning (_f ("clef `%s' not found", glyph.c_str ())); + return out.smobbed_copy (); } diff --git a/lily/dot-formatting-problem.cc b/lily/dot-formatting-problem.cc index be375b540d..863aa5fc02 100644 --- a/lily/dot-formatting-problem.cc +++ b/lily/dot-formatting-problem.cc @@ -45,7 +45,7 @@ Dot_formatting_problem::best () const Dot_formatting_problem::Dot_formatting_problem (vector<Box> const &boxes, Interval base_x) - : head_skyline_ (boxes, 0.2, Y_AXIS, RIGHT) + : head_skyline_ (boxes, Y_AXIS, RIGHT) { best_ = 0; head_skyline_.set_minimum_height (base_x[RIGHT]); diff --git a/lily/flag.cc b/lily/flag.cc index f997d6fe45..77491befd6 100644 --- a/lily/flag.cc +++ b/lily/flag.cc @@ -33,6 +33,7 @@ class Flag { public: DECLARE_SCHEME_CALLBACK (print, (SCM)); + DECLARE_SCHEME_CALLBACK (glyph_name, (SCM)); DECLARE_SCHEME_CALLBACK (width, (SCM)); DECLARE_SCHEME_CALLBACK (calc_y_offset, (SCM)); DECLARE_SCHEME_CALLBACK (pure_calc_y_offset, (SCM, SCM, SCM)); @@ -61,9 +62,10 @@ Flag::width (SCM smob) return ly_interval2scm (sten->extent (X_AXIS) - stem->extent (stem, X_AXIS)[RIGHT]); } -MAKE_SCHEME_CALLBACK (Flag, print, 1); + +MAKE_SCHEME_CALLBACK (Flag, glyph_name, 1); SCM -Flag::print (SCM smob) +Flag::glyph_name (SCM smob) { Grob *me = unsmob_grob (smob); Grob *stem = me->get_parent (X_AXIS); @@ -76,9 +78,6 @@ Flag::print (SCM smob) if (scm_is_symbol (flag_style_scm)) flag_style = ly_symbol2string (flag_style_scm); - if (flag_style == "no-flag") - return Stencil ().smobbed_copy (); - bool adjust = true; string staffline_offs; @@ -107,8 +106,30 @@ Flag::print (SCM smob) char dir = (d == UP) ? 'u' : 'd'; string font_char = flag_style + to_string (dir) + staffline_offs + to_string (log); + return ly_string2scm ("flags." + font_char); +} + +MAKE_SCHEME_CALLBACK (Flag, print, 1); +SCM +Flag::print (SCM smob) +{ + Grob *me = unsmob_grob (smob); + Grob *stem = me->get_parent (X_AXIS); + + Direction d = get_grob_direction (stem); + string flag_style; + + SCM flag_style_scm = me->get_property ("style"); + if (scm_is_symbol (flag_style_scm)) + flag_style = ly_symbol2string (flag_style_scm); + + if (flag_style == "no-flag") + return Stencil ().smobbed_copy (); + + char dir = (d == UP) ? 'u' : 'd'; Font_metric *fm = Font_interface::get_default_font (me); - Stencil flag = fm->find_by_name ("flags." + font_char); + string font_char = robust_scm2string (me->get_property ("glyph-name"), ""); + Stencil flag = fm->find_by_name (font_char); if (flag.is_empty ()) me->warning (_f ("flag `%s' not found", font_char)); @@ -190,6 +211,7 @@ ADD_INTERFACE (Flag, " @code{'no-flag}, which switches off the flag.", /* properties */ + "glyph-name " "style " "stroke-style " ); diff --git a/lily/freetype.cc b/lily/freetype.cc index f19b164968..c48ef614c6 100644 --- a/lily/freetype.cc +++ b/lily/freetype.cc @@ -20,6 +20,9 @@ #include "freetype.hh" #include "warn.hh" +#include <freetype/ftoutln.h> +#include <freetype/ftbbox.h> + FT_Library freetype2_library; void @@ -30,3 +33,172 @@ init_freetype () error ("cannot initialize FreeType"); } +Box +ly_FT_get_unscaled_indexed_char_dimensions (FT_Face const &face, size_t signed_idx) +{ + FT_UInt idx = FT_UInt (signed_idx); + FT_Load_Glyph (face, idx, FT_LOAD_NO_SCALE); + + FT_Glyph_Metrics m = face->glyph->metrics; + FT_Pos hb = m.horiBearingX; + FT_Pos vb = m.horiBearingY; + + // is this viable for all grobs? + return Box (Interval (Real (hb), Real (hb + m.width)), + Interval (Real (vb - m.height), Real (vb))); +} + +SCM +box_to_scheme_lines (Box b) +{ + return scm_list_4 (scm_list_4 (scm_from_double (b[X_AXIS][LEFT]), + scm_from_double (b[Y_AXIS][DOWN]), + scm_from_double (b[X_AXIS][RIGHT]), + scm_from_double (b[Y_AXIS][DOWN])), + scm_list_4 (scm_from_double (b[X_AXIS][RIGHT]), + scm_from_double (b[Y_AXIS][DOWN]), + scm_from_double (b[X_AXIS][RIGHT]), + scm_from_double (b[Y_AXIS][UP])), + scm_list_4 (scm_from_double (b[X_AXIS][RIGHT]), + scm_from_double (b[Y_AXIS][UP]), + scm_from_double (b[X_AXIS][LEFT]), + scm_from_double (b[Y_AXIS][UP])), + scm_list_4 (scm_from_double (b[X_AXIS][LEFT]), + scm_from_double (b[Y_AXIS][UP]), + scm_from_double (b[X_AXIS][LEFT]), + scm_from_double (b[Y_AXIS][DOWN]))); +} + +Box +ly_FT_get_glyph_outline_bbox (FT_Face const &face, size_t signed_idx) +{ + FT_UInt idx = FT_UInt (signed_idx); + FT_Load_Glyph (face, idx, FT_LOAD_NO_SCALE); + + if (!(face->glyph->format == FT_GLYPH_FORMAT_OUTLINE)) + { +#if 0 + // will generate a lot of warnings + warning ("Cannot make glyph outline"); +#endif + return Box (Interval (infinity_f, -infinity_f), Interval (infinity_f, -infinity_f)); + } + FT_Outline *outline; + outline = &(face->glyph->outline); + + FT_BBox bbox; + FT_Outline_Get_BBox (outline, &bbox); + + return Box (Interval (bbox.xMin, bbox.xMax), Interval (bbox.yMin, bbox.yMax)); +} + +SCM +ly_FT_get_glyph_outline (FT_Face const &face, size_t signed_idx) +{ + FT_UInt idx = FT_UInt (signed_idx); + FT_Load_Glyph (face, idx, FT_LOAD_NO_SCALE); + + if (!(face->glyph->format == FT_GLYPH_FORMAT_OUTLINE)) + { +#if 0 + // will generate a lot of warnings + warning ("Cannot make glyph outline"); +#endif + return box_to_scheme_lines (ly_FT_get_unscaled_indexed_char_dimensions (face, signed_idx)); + } + + FT_Outline *outline; + outline = &(face->glyph->outline); + SCM out = SCM_EOL; + Offset lastpos; + Offset firstpos; + vsize j = 0; + while (j < outline->n_points) + { + if (j == 0) + { + firstpos = Offset (outline->points[j].x, outline->points[j].y); + lastpos = firstpos; + j++; + } + else if (outline->tags[j] & 1) + { + // it is a line + out = scm_cons (scm_list_4 (scm_from_double (lastpos[X_AXIS]), + scm_from_double (lastpos[Y_AXIS]), + scm_from_double (outline->points[j].x), + scm_from_double (outline->points[j].y)), + out); + lastpos = Offset (outline->points[j].x, outline->points[j].y); + j++; + } + else if (outline->tags[j] & 2) + { + // it is a third order bezier + out = scm_cons (scm_list_n (scm_from_double (lastpos[X_AXIS]), + scm_from_double (lastpos[Y_AXIS]), + scm_from_double (outline->points[j].x), + scm_from_double (outline->points[j].y), + scm_from_double (outline->points[j + 1].x), + scm_from_double (outline->points[j + 1].y), + scm_from_double (outline->points[j + 2].x), + scm_from_double (outline->points[j + 2].y), + SCM_UNDEFINED), + out); + lastpos = Offset (outline->points[j + 2].x, outline->points[j + 2].y); + j += 3; + } + else + { + // it is a second order bezier + Real x0 = lastpos[X_AXIS]; + Real x1 = outline->points[j].x; + Real x2 = outline->points[j + 1].x; + + Real y0 = lastpos[Y_AXIS]; + Real y1 = outline->points[j].y; + Real y2 = outline->points[j + 1].y; + + Real qx2 = x0 + x2 - (2 * x1); + Real qx1 = (2 * x1) - (2 * x0); + Real qx0 = x0; + + Real qy2 = y0 + y2 - (2 * y1); + Real qy1 = (2 * y1) - (2 * y0); + Real qy0 = y0; + + Real cx0 = qx0; + Real cx1 = qx0 + (qx1 / 3); + Real cx2 = qx0 + (2 * qx1 / 3) + (qx2 / 3); + Real cx3 = qx0 + qx1 + qx2; + + Real cy0 = qy0; + Real cy1 = qy0 + (qy1 / 3); + Real cy2 = qy0 + (2 * qy1 / 3) + (qy2 / 3); + Real cy3 = qy0 + qy1 + qy2; + + out = scm_cons (scm_list_n (scm_from_double (cx0), + scm_from_double (cy0), + scm_from_double (cx1), + scm_from_double (cy1), + scm_from_double (cx2), + scm_from_double (cy2), + scm_from_double (cx3), + scm_from_double (cy3), + SCM_UNDEFINED), + out); + lastpos = Offset (outline->points[j + 1].x, outline->points[j + 1].y); + j += 2; + } + } + + // just in case, close the figure + out = scm_cons (scm_list_4 (scm_from_double (lastpos[X_AXIS]), + scm_from_double (lastpos[Y_AXIS]), + scm_from_double (firstpos[X_AXIS]), + scm_from_double (firstpos[Y_AXIS])), + out); + + out = scm_reverse_x (out, SCM_EOL); + return out; +} diff --git a/lily/global-vars.cc b/lily/global-vars.cc new file mode 100644 index 0000000000..f12e957d5e --- /dev/null +++ b/lily/global-vars.cc @@ -0,0 +1,59 @@ +/* + This file is part of LilyPond, the GNU music typesetter. + + Copyright (C) 1997--2012 Han-Wen Nienhuys <hanwen@xs4all.nl> + + LilyPond is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + LilyPond is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with LilyPond. If not, see <http://www.gnu.org/licenses/>. +*/ + +#include "file-path.hh" +#include "main.hh" + +/* + * Global options that can be overridden through command line. + */ + +/* Names of header fields to be dumped to a separate file. */ +vector<string> dump_header_fieldnames_global; + +/* Name of initialisation file. */ +string init_name_global; + +/* Output formats to generate. */ +string output_format_global = ""; + +/* Current output name. */ +string output_name_global; + +/* Run in safe mode? */ +bool be_safe_global = false; + +/* Scheme code to execute before parsing, after .scm init. + This is where -e arguments are appended to. */ +string init_scheme_code_global; +string init_scheme_variables_global; + +bool relocate_binary = true; + +/* + * Miscellaneous global stuff. + */ +File_path global_path; + +/* Where the init files live. Typically: + LILYPOND_DATADIR = /usr/share/lilypond +*/ +string lilypond_datadir; + +vector<string> start_environment_global; diff --git a/lily/grob.cc b/lily/grob.cc index 828ae7f07b..593b0814a6 100644 --- a/lily/grob.cc +++ b/lily/grob.cc @@ -79,6 +79,10 @@ Grob::Grob (SCM basicprops) set_property ("X-extent", Grob::stencil_width_proc); if (get_property_data ("Y-extent") == SCM_EOL) set_property ("Y-extent", Grob::stencil_height_proc); + if (get_property_data ("vertical-skylines") == SCM_EOL) + set_property ("vertical-skylines", Grob::simple_vertical_skylines_from_stencil_proc); + if (get_property_data ("horizontal-skylines") == SCM_EOL) + set_property ("horizontal-skylines", Grob::simple_horizontal_skylines_from_stencil_proc); } Grob::Grob (Grob const &s) @@ -804,6 +808,7 @@ ADD_INTERFACE (Grob, "extra-offset " "footnote-music " "forced-spacing " + "horizontal-skylines " "interfaces " "layer " "meta " @@ -814,10 +819,12 @@ ADD_INTERFACE (Grob, "outside-staff-priority " "pure-Y-offset-in-progress " "rotation " + "skyline-horizontal-padding " "springs-and-rods " "staff-symbol " "stencil " "transparent " + "vertical-skylines " "whiteout " ); diff --git a/lily/include/axis-group-interface.hh b/lily/include/axis-group-interface.hh index 19bdc1e2ee..4098a19514 100644 --- a/lily/include/axis-group-interface.hh +++ b/lily/include/axis-group-interface.hh @@ -25,9 +25,13 @@ #include "grob-interface.hh" #include "skyline.hh" -struct Axis_group_interface +class Axis_group_interface { + static Real default_outside_staff_padding_; + public +: static SCM generic_group_extent (Grob *me, Axis a); + static Real get_default_outside_staff_padding (); static Interval generic_bound_extent (Grob *me, Grob *common, Axis a); static Interval pure_group_height (Grob *me, int start, int end); DECLARE_SCHEME_CALLBACK (width, (SCM smob)); @@ -57,7 +61,7 @@ struct Axis_group_interface static Interval rest_of_line_pure_height (Grob *me, int, int); static Interval part_of_line_pure_height (Grob *me, bool begin, int, int); - static bool has_outside_staff_parent (Grob *me); + static Grob *outside_staff_ancestor (Grob *me); static Skyline_pair skyline_spacing (Grob *me, vector<Grob *> elements); static void add_element (Grob *me, Grob *); static void set_axes (Grob *, Axis, Axis); diff --git a/lily/include/bezier.hh b/lily/include/bezier.hh index 1e88dbb764..d09c0ac8be 100644 --- a/lily/include/bezier.hh +++ b/lily/include/bezier.hh @@ -48,6 +48,7 @@ public: Polynomial polynomial (Axis)const; Offset curve_point (Real t) const; + Real slope_at_point (Real t) const; Real curve_coordinate (Real t, Axis) const; static const int CONTROL_COUNT = 4; diff --git a/lily/include/box.hh b/lily/include/box.hh index af5695b3bc..ab0d3f5300 100644 --- a/lily/include/box.hh +++ b/lily/include/box.hh @@ -20,6 +20,7 @@ public: Interval y () const {return interval_a_[Y_AXIS]; } Interval operator [] (Axis a) const; Interval &operator [] (Axis a); + Real area () const; Offset center () const; @@ -36,4 +37,6 @@ public: Box (Interval ix, Interval iy); }; +DECLARE_UNSMOB (Box, box); + #endif diff --git a/lily/include/freetype.hh b/lily/include/freetype.hh index 3ddc07e67f..14f14d92c0 100644 --- a/lily/include/freetype.hh +++ b/lily/include/freetype.hh @@ -24,10 +24,16 @@ #include FT_FREETYPE_H #include "std-string.hh" +#include "box.hh" void init_freetype (); extern FT_Library freetype2_library; string freetype_error_string (FT_Error code); +SCM box_to_scheme_lines (Box b); +Box ly_FT_get_unscaled_indexed_char_dimensions (FT_Face const &face, size_t signed_idx); +Box ly_FT_get_glyph_outline_bbox (FT_Face const &face, size_t signed_idx); +SCM ly_FT_get_glyph_outline (FT_Face const &face, size_t signed_idx); + #endif /* FREETYPE_HH */ diff --git a/lily/include/grob.hh b/lily/include/grob.hh index fd55dbf209..14a7b47925 100644 --- a/lily/include/grob.hh +++ b/lily/include/grob.hh @@ -69,6 +69,12 @@ public: DECLARE_SCHEME_CALLBACK (y_parent_positioning, (SCM)); DECLARE_SCHEME_CALLBACK (stencil_height, (SCM smob)); DECLARE_SCHEME_CALLBACK (stencil_width, (SCM smob)); + DECLARE_SCHEME_CALLBACK (simple_vertical_skylines_from_stencil, (SCM smob)); + DECLARE_SCHEME_CALLBACK (vertical_skylines_from_stencil, (SCM smob)); + DECLARE_SCHEME_CALLBACK (vertical_skylines_from_element_stencils, (SCM smob)); + DECLARE_SCHEME_CALLBACK (simple_horizontal_skylines_from_stencil, (SCM smob)); + DECLARE_SCHEME_CALLBACK (horizontal_skylines_from_stencil, (SCM smob)); + DECLARE_SCHEME_CALLBACK (horizontal_skylines_from_element_stencils, (SCM smob)); /* R/O access */ Output_def *layout () const { return layout_; } @@ -141,17 +147,20 @@ public: void fixup_refpoint (); /* vertical ordering */ + static bool internal_vertical_less (Grob *g1, Grob *g2, bool pure); static Grob *get_root_vertical_alignment (Grob *g); static Grob *get_vertical_axis_group (Grob *g); static bool vertical_less (Grob *g1, Grob *g2); static bool pure_vertical_less (Grob *g1, Grob *g2); - static bool internal_vertical_less (Grob *g1, Grob *g2, bool pure); static int get_vertical_axis_group_index (Grob *g); + /* skylines */ virtual Interval_t<int> spanned_rank_interval () const; virtual bool pure_is_visible (int start, int end) const; bool check_cross_staff (Grob *common); static bool less (Grob *g1, Grob *g2); + static SCM internal_simple_skylines_from_stencil (SCM, Axis); + static SCM internal_skylines_from_element_stencils (SCM, Axis); }; /* smob utilities */ diff --git a/lily/include/misc.hh b/lily/include/misc.hh index b70d2c2ce2..511fc0545f 100644 --- a/lily/include/misc.hh +++ b/lily/include/misc.hh @@ -61,6 +61,7 @@ normalize (Real x, Real x1, Real x2) Real directed_round (Real f, Direction d); +Offset get_point_in_y_direction (Offset orig, Real slope, Real dist, Direction dir); Real peak_around (Real epsilon, Real threshold, Real x); Real convex_amplifier (Real standard_x, Real increase_factor, Real x); string camel_case_to_lisp_identifier (string in); diff --git a/lily/include/modified-font-metric.hh b/lily/include/modified-font-metric.hh index cd5cd6116f..6bf2d8d6d0 100644 --- a/lily/include/modified-font-metric.hh +++ b/lily/include/modified-font-metric.hh @@ -27,6 +27,7 @@ struct Modified_font_metric : public Font_metric { public: Stencil text_stencil (Output_def *output_state, string, bool) const; + Real get_magnification () const; static SCM make_scaled_font_metric (Font_metric *fm, Real magnification); size_t count () const; diff --git a/lily/include/open-type-font.hh b/lily/include/open-type-font.hh index 6ee62823ec..e3789d0685 100644 --- a/lily/include/open-type-font.hh +++ b/lily/include/open-type-font.hh @@ -41,11 +41,13 @@ class Open_type_font : public Font_metric DECLARE_CLASSNAME (Open_type_font); public: + Real get_units_per_EM () const; SCM get_subfonts () const; SCM get_global_table () const; SCM get_char_table () const; SCM glyph_list () const; - + SCM get_glyph_outline (size_t signed_idx) const; + Box get_glyph_outline_bbox (size_t signed_idx) const; string get_otf_table (string tag) const; static SCM make_otf (string); string font_name () const; @@ -53,6 +55,7 @@ public: Offset attachment_point (string) const; size_t count () const; Box get_indexed_char_dimensions (size_t) const; + Box get_unscaled_indexed_char_dimensions (size_t) const; size_t name_to_index (string) const; //size_t glyph_name_to_charcode (string) const; size_t index_to_charcode (size_t) const; diff --git a/lily/include/pango-font.hh b/lily/include/pango-font.hh index 6b4ad4b68f..f57b5d5b76 100644 --- a/lily/include/pango-font.hh +++ b/lily/include/pango-font.hh @@ -50,6 +50,12 @@ public: SCM font_file_name () const; void register_font_file (string, string, int); + size_t name_to_index (string) const; + SCM get_glyph_outline (size_t signed_idx) const; + Box get_glyph_outline_bbox (size_t signed_idx) const; + Box get_unscaled_indexed_char_dimensions (size_t) const; + Box get_scaled_indexed_char_dimensions (size_t) const; + Stencil pango_item_string_stencil (PangoGlyphItem const *) const; virtual Stencil text_stencil (Output_def *output_state, diff --git a/lily/include/skyline-pair.hh b/lily/include/skyline-pair.hh index 22dd639332..604d2fb4df 100644 --- a/lily/include/skyline-pair.hh +++ b/lily/include/skyline-pair.hh @@ -30,14 +30,25 @@ private: DECLARE_SIMPLE_SMOBS (Skyline_pair); public: Skyline_pair (); - Skyline_pair (vector<Box> const &boxes, Real horizon_padding, Axis a); - Skyline_pair (Box const &, Real horizon_padding, Axis a); + Skyline_pair (vector<Box> const &boxes, Axis a); + Skyline_pair (vector<Drul_array<Offset> > const &buildings, Axis a); + Skyline_pair (vector<Skyline_pair> const &skypairs); + Skyline_pair (Box const &, Axis a); + void raise (Real); + void grow (Real); void shift (Real); - void insert (Box const &, Real horizon_padding, Axis); + void deholify (); + Real smallest_shift (Skyline_pair const &other, Direction d, + Real h_padding = 0, Real v_padding = 0); + Real left () const; + Real right () const; + bool intersects (Skyline_pair const &other) const; + void insert (Box const &, Axis); void merge (Skyline_pair const &other); Skyline &operator [] (Direction d); Skyline const &operator [] (Direction d) const; + bool is_singleton () const; bool is_empty () const; void print () const; void print_points () const; diff --git a/lily/include/skyline.hh b/lily/include/skyline.hh index ceedf24007..a93316d935 100644 --- a/lily/include/skyline.hh +++ b/lily/include/skyline.hh @@ -32,20 +32,22 @@ struct Building { + Real start_; Real end_; Real y_intercept_; Real slope_; void precompute (Real start, Real start_height, Real end_height, Real end); Building (Real start, Real start_height, Real end_height, Real end); - Building (Box const &b, Real horizon_padding, Axis a, Direction d); + Building (Box const &b, Axis a, Direction d); void print () const; Real height (Real x) const; Real intersection_x (Building const &other) const; void leading_part (Real chop); bool conceals (Building const &other, Real x) const; - Building sloped_neighbour (Real start, Real horizon_padding, Direction d) const; + Real shift_to_intersect (Real x, Real y) const; + Interval overlapping_shift_interval (Building const &other) const; }; class Skyline @@ -55,43 +57,57 @@ private: Direction sky_; void internal_merge_skyline (list<Building> *, list<Building> *, - list<Building> *const result); - list<Building> internal_build_skyline (list<Box> *, Real, Axis, Direction); + list<Building> *const result) const; + list<Building> internal_build_skyline (list<Building> *) const; + Real internal_distance (Skyline const &, Real horizon_padding, Real *touch_point) const; + Real internal_distance (Skyline const &, Real *touch_point) const; + void normalize (); DECLARE_SIMPLE_SMOBS (Skyline); public: Skyline (); Skyline (Skyline const &src); - Skyline (Skyline const &src, Real horizon_padding, Axis a); Skyline (Direction sky); - Skyline (vector<Box> const &bldgs, Real horizon_padding, Axis a, Direction sky); - Skyline (Box const &b, Real horizon_padding, Axis a, Direction sky); + Skyline (vector<Box> const &bldgs, Axis a, Direction sky); + Skyline (vector<Drul_array<Offset> > const &bldgs, Axis a, Direction sky); + Skyline (vector<Skyline_pair> const &skypairs, Direction sky); + Skyline (Box const &b, Axis a, Direction sky); vector<Offset> to_points (Axis) const; + void deholify (); void merge (Skyline const &); - void insert (Box const &, Real horizon_padding, Axis); + void insert (Box const &, Axis); void print () const; void print_points () const; void raise (Real); void shift (Real); + void invert (); Real distance (Skyline const &, Real horizon_padding = 0) const; + Real smallest_shift (Skyline const &, Direction d, + Real horizon_padding = 0, + Real vertical_padding = 0) const; Real touching_point (Skyline const &, Real horizon_padding = 0) const; + Real shift_to_avoid (Skyline const &other, Real, Direction d, Real horizon_padding = 0); + Real raise_to_avoid (Skyline const &other, Real, Direction d, Real horizon_padding = 0); + Drul_array<Real> shifts_to_avoid_intersection (Skyline const &, Real horizon_padding = 0) const; + Interval raises_to_avoid_intersection (Skyline const &, Real horizon_padding = 0) const; Real height (Real airplane) const; Real max_height () const; Real max_height_position () const; void set_minimum_height (Real height); void clear (); bool is_empty () const; + bool is_singleton () const; + Real left () const; + Real right () const; + Skyline padded (Real horizon_padding) const; DECLARE_SCHEME_CALLBACK (get_touching_point, (SCM, SCM, SCM)); DECLARE_SCHEME_CALLBACK (get_distance, (SCM, SCM, SCM)); DECLARE_SCHEME_CALLBACK (get_max_height, (SCM)); DECLARE_SCHEME_CALLBACK (get_max_height_position, (SCM)); DECLARE_SCHEME_CALLBACK (get_height, (SCM, SCM)); - -protected: - Real internal_distance (Skyline const &, Real horizon_padding, Real *touch_point) const; }; extern bool debug_skylines; diff --git a/lily/include/stencil.hh b/lily/include/stencil.hh index 00c295316c..65c0b7a0f1 100644 --- a/lily/include/stencil.hh +++ b/lily/include/stencil.hh @@ -85,6 +85,7 @@ public: Box extent_box () const; bool is_empty () const; Stencil in_color (Real r, Real g, Real b) const; + static SCM skylines_from_stencil (SCM, Real, Axis); }; DECLARE_UNSMOB (Stencil, stencil); diff --git a/lily/include/system.hh b/lily/include/system.hh index 453e48234d..a5efe750ad 100644 --- a/lily/include/system.hh +++ b/lily/include/system.hh @@ -39,7 +39,6 @@ class System : public Spanner public: Paper_score *paper_score () const; - Grob *get_vertical_alignment (); Grob *get_extremal_staff (Direction dir, Interval const &); Grob *get_neighboring_staff (Direction dir, Grob *vertical_axis_group, Interval_t<int> bounds); Grob *get_pure_bound (Direction dir, int start, int end); @@ -59,12 +58,14 @@ public: DECLARE_SCHEME_CALLBACK (footnotes_before_line_breaking, (SCM)); DECLARE_SCHEME_CALLBACK (footnotes_after_line_breaking, (SCM)); + DECLARE_SCHEME_CALLBACK (vertical_skyline_elements, (SCM)); DECLARE_SCHEME_CALLBACK (calc_pure_relevant_grobs, (SCM)); DECLARE_SCHEME_CALLBACK (height, (SCM)); DECLARE_SCHEME_CALLBACK (calc_pure_height, (SCM, SCM, SCM)); DECLARE_SCHEME_CALLBACK (get_staves, (SCM)); DECLARE_SCHEME_CALLBACK (get_spaceable_staves, (SCM)); DECLARE_SCHEME_CALLBACK (get_nonspaceable_staves, (SCM)); + DECLARE_SCHEME_CALLBACK (get_vertical_alignment, (SCM)); System (SCM); System (System const &); diff --git a/lily/line-spanner.cc b/lily/line-spanner.cc index f42628820e..2be8d1e503 100644 --- a/lily/line-spanner.cc +++ b/lily/line-spanner.cc @@ -356,9 +356,9 @@ Line_spanner::print (SCM smob) } Offset adjust = dz.direction () * Staff_symbol_referencer::staff_space (me); - Offset line_left = span_points[LEFT] + (arrows[LEFT] ? adjust * 1.4 : Offset (0, 0)); Offset line_right = span_points[RIGHT] - (arrows[RIGHT] ? adjust * 0.55 : Offset (0, 0)); + if (line_right[X_AXIS] > line_left[X_AXIS]) { line.add_stencil (Line_interface::line (me, line_left, line_right)); diff --git a/lily/main.cc b/lily/main.cc index 239ff1b39d..d4016e21f7 100644 --- a/lily/main.cc +++ b/lily/main.cc @@ -56,37 +56,6 @@ using namespace std; #include "warn.hh" /* - * Global options that can be overridden through command line. - */ - -/* Names of header fields to be dumped to a separate file. */ -vector<string> dump_header_fieldnames_global; - -/* Name of initialisation file. */ -string init_name_global; - -/* Output formats to generate. */ -string output_format_global = ""; - -/* Current output name. */ -string output_name_global; - -/* Run in safe mode? */ -bool be_safe_global = false; - -/* Scheme code to execute before parsing, after .scm init. - This is where -e arguments are appended to. */ -string init_scheme_code_global; -string init_scheme_variables_global; - -bool relocate_binary = true; - -/* - * Miscellaneous global stuff. - */ -File_path global_path; - -/* * File globals. */ @@ -119,13 +88,8 @@ static char const *WARRANTY "the Free Software Foundation, Inc., 59 Temple Place - Suite 330,\n" "Boston, MA 02111-1307, USA.\n"); -/* Where the init files live. Typically: - LILYPOND_DATADIR = /usr/share/lilypond -*/ -string lilypond_datadir; - /* The jail specification: USER, GROUP, JAIL, DIR. */ -string jail_spec; +static string jail_spec; /* The option parser */ static Getopt_long *option_parser = 0; @@ -605,8 +569,6 @@ setup_guile_env () "104857600", overwrite); } -vector<string> start_environment_global; - int main (int argc, char **argv, char **envp) { diff --git a/lily/misc.cc b/lily/misc.cc index 801266d79b..f90d641a60 100644 --- a/lily/misc.cc +++ b/lily/misc.cc @@ -18,7 +18,10 @@ along with LilyPond. If not, see <http://www.gnu.org/licenses/>. */ +#include <complex> + #include "misc.hh" +#include "offset.hh" #include "warn.hh" /* @@ -94,3 +97,20 @@ camel_case_to_lisp_identifier (string in) return result; } + +Offset +get_point_in_y_direction (Offset orig, Real slope, Real dist, Direction dir) +{ + if (slope == infinity_f) + return orig + Offset (dir * dist, 0.0); + + Real x = slope == 0.0 ? 1.0 * dir : 1.0 * sign (slope) * dir; + Real y = slope * x; + Real angle = atan2 (y, x); + + complex<Real> orig_c (orig[X_AXIS], orig[Y_AXIS]); + complex<Real> to_move = polar (dist, angle); + complex<Real> res = orig_c + to_move; + + return Offset (real (res), imag (res)); +}
\ No newline at end of file diff --git a/lily/modified-font-metric.cc b/lily/modified-font-metric.cc index 0acee12649..7a54948fed 100644 --- a/lily/modified-font-metric.cc +++ b/lily/modified-font-metric.cc @@ -61,6 +61,12 @@ Modified_font_metric::get_indexed_char_dimensions (vsize i) const return b; } +Real +Modified_font_metric::get_magnification () const +{ + return magnification_; +} + vsize Modified_font_metric::count () const { diff --git a/lily/note-spacing.cc b/lily/note-spacing.cc index 477236775d..1d0d21fbbb 100644 --- a/lily/note-spacing.cc +++ b/lily/note-spacing.cc @@ -79,7 +79,7 @@ Note_spacing::get_spacing (Grob *me, Item *right_col, adjust things so there are no collisions. */ Drul_array<Skyline> skys = Spacing_interface::skylines (me, right_col); - Real distance = skys[LEFT].distance (skys[RIGHT]); + Real distance = skys[LEFT].distance (skys[RIGHT], robust_scm2double (right_col->get_property ("skyline-vertical-padding"), 0.0)); Real min_dist = max (0.0, distance); Real min_desired_space = left_head_end + (min_dist - left_head_end + base_space - increment) / 2; Real ideal = base_space - increment + left_head_end; diff --git a/lily/open-type-font.cc b/lily/open-type-font.cc index fc97b99687..680dfe9234 100644 --- a/lily/open-type-font.cc +++ b/lily/open-type-font.cc @@ -26,6 +26,7 @@ using namespace std; #include <freetype/tttables.h> #include "dimensions.hh" +#include "freetype.hh" #include "international.hh" #include "modified-font-metric.hh" #include "warn.hh" @@ -213,19 +214,18 @@ Open_type_font::get_indexed_char_dimensions (size_t signed_idx) const } } - FT_UInt idx = FT_UInt (signed_idx); - FT_Load_Glyph (face_, idx, FT_LOAD_NO_SCALE); - - FT_Glyph_Metrics m = face_->glyph->metrics; - FT_Pos hb = m.horiBearingX; - FT_Pos vb = m.horiBearingY; - Box b (Interval (Real (-hb), Real (m.width - hb)), - Interval (Real (-vb), Real (m.height - vb))); + Box b = get_unscaled_indexed_char_dimensions (signed_idx); b.scale (design_size () / Real (face_->units_per_EM)); return b; } +Real +Open_type_font::get_units_per_EM () const +{ + return face_->units_per_EM; +} + size_t Open_type_font::name_to_index (string nm) const { @@ -236,6 +236,24 @@ Open_type_font::name_to_index (string nm) const return (size_t) - 1; } +Box +Open_type_font::get_unscaled_indexed_char_dimensions (size_t signed_idx) const +{ + return ly_FT_get_unscaled_indexed_char_dimensions (face_, signed_idx); +} + +Box +Open_type_font::get_glyph_outline_bbox (size_t signed_idx) const +{ + return ly_FT_get_glyph_outline_bbox (face_, signed_idx); +} + +SCM +Open_type_font::get_glyph_outline (size_t signed_idx) const +{ + return ly_FT_get_glyph_outline (face_, signed_idx); +} + size_t Open_type_font::index_to_charcode (size_t i) const { diff --git a/lily/page-layout-problem.cc b/lily/page-layout-problem.cc index 7c99670551..11177be03a 100644 --- a/lily/page-layout-problem.cc +++ b/lily/page-layout-problem.cc @@ -539,7 +539,7 @@ Page_layout_problem::set_footer_height (Real height) void Page_layout_problem::append_system (System *sys, Spring const &spring, Real indent, Real padding) { - Grob *align = sys->get_vertical_alignment (); + Grob *align = unsmob_grob (sys->get_object ("vertical-alignment")); if (!align) return; diff --git a/lily/pango-font.cc b/lily/pango-font.cc index 32e7a89c02..a1d3024abb 100644 --- a/lily/pango-font.cc +++ b/lily/pango-font.cc @@ -91,6 +91,22 @@ Pango_font::register_font_file (string filename, scm_from_int (face_index))); } +size_t +Pango_font::name_to_index (string nm) const +{ + PangoFcFont *fcfont = PANGO_FC_FONT (pango_context_load_font (context_, pango_description_)); + FT_Face face = pango_fc_font_lock_face (fcfont); + char *nm_str = (char *) nm.c_str (); + if (FT_UInt idx = FT_Get_Name_Index (face, nm_str)) + { + pango_fc_font_unlock_face (fcfont); + return (size_t) idx; + } + + pango_fc_font_unlock_face (fcfont); + return (size_t) - 1; +} + void Pango_font::derived_mark () const { @@ -114,6 +130,51 @@ get_unicode_name (char *s, sprintf (s, "uni%04lX", code); } +Box +Pango_font::get_unscaled_indexed_char_dimensions (size_t signed_idx) const +{ + PangoFcFont *fcfont = PANGO_FC_FONT (pango_context_load_font (context_, pango_description_)); + FT_Face face = pango_fc_font_lock_face (fcfont); + Box b = ly_FT_get_unscaled_indexed_char_dimensions (face, signed_idx); + pango_fc_font_unlock_face (fcfont); + return b; +} + +Box +Pango_font::get_scaled_indexed_char_dimensions (size_t signed_idx) const +{ + PangoFont *font = pango_context_load_font (context_, pango_description_); + PangoRectangle logical_rect; + PangoRectangle ink_rect; + pango_font_get_glyph_extents (font, signed_idx, &ink_rect, &logical_rect); + Box out (Interval (PANGO_LBEARING (ink_rect), + PANGO_RBEARING (ink_rect)), + Interval (-PANGO_DESCENT (ink_rect), + PANGO_ASCENT (ink_rect))); + out.scale (scale_); + return out; +} + +Box +Pango_font::get_glyph_outline_bbox (size_t signed_idx) const +{ + PangoFcFont *fcfont = PANGO_FC_FONT (pango_context_load_font (context_, pango_description_)); + FT_Face face = pango_fc_font_lock_face (fcfont); + Box b = ly_FT_get_glyph_outline_bbox (face, signed_idx); + pango_fc_font_unlock_face (fcfont); + return b; +} + +SCM +Pango_font::get_glyph_outline (size_t signed_idx) const +{ + PangoFcFont *fcfont = PANGO_FC_FONT (pango_context_load_font (context_, pango_description_)); + FT_Face face = pango_fc_font_lock_face (fcfont); + SCM s = ly_FT_get_glyph_outline (face, signed_idx); + pango_fc_font_unlock_face (fcfont); + return s; +} + Stencil Pango_font::pango_item_string_stencil (PangoGlyphItem const *glyph_item) const { @@ -128,7 +189,6 @@ Pango_font::pango_item_string_stencil (PangoGlyphItem const *glyph_item) const pango_glyph_string_extents (pgs, pa->font, &ink_rect, &logical_rect); PangoFcFont *fcfont = PANGO_FC_FONT (pa->font); - FT_Face ftface = pango_fc_font_lock_face (fcfont); Box b (Interval (PANGO_LBEARING (logical_rect), @@ -224,7 +284,20 @@ Pango_font::pango_item_string_stencil (PangoGlyphItem const *glyph_item) const else char_id = scm_from_locale_string (glyph_name); - *tail = scm_cons (scm_list_4 (scm_from_double (ggeo.width * scale_), + PangoRectangle logical_sub_rect; + PangoRectangle ink_sub_rect; + + pango_glyph_string_extents_range (pgs, i, i + 1, pa->font, &ink_sub_rect, &logical_sub_rect); + Box b_sub (Interval (PANGO_LBEARING (logical_sub_rect), + PANGO_RBEARING (logical_sub_rect)), + Interval (-PANGO_DESCENT (ink_sub_rect), + PANGO_ASCENT (ink_sub_rect))); + + b_sub.scale (scale_); + + *tail = scm_cons (scm_list_5 (scm_from_double (b_sub[X_AXIS][RIGHT] - b_sub[X_AXIS][LEFT]), + scm_cons (scm_from_double (b_sub[Y_AXIS][DOWN]), + scm_from_double (b_sub[Y_AXIS][UP])), scm_from_double (ggeo.x_offset * scale_), scm_from_double (- ggeo.y_offset * scale_), char_id), @@ -277,13 +350,14 @@ Pango_font::pango_item_string_stencil (PangoGlyphItem const *glyph_item) const ((Pango_font *) this)->register_font_file (file_name, ps_name, face_index); - pango_fc_font_unlock_face (fcfont); - SCM expr = scm_list_5 (ly_symbol2scm ("glyph-string"), + SCM expr = scm_list_n (ly_symbol2scm ("glyph-string"), + self_scm (), ly_string2scm (ps_name), scm_from_double (size), scm_from_bool (cid_keyed), - ly_quote_scm (glyph_exprs)); + ly_quote_scm (glyph_exprs), + SCM_UNDEFINED); return Stencil (b, expr); } diff --git a/lily/script-interface.cc b/lily/script-interface.cc index 40a251a077..28b978d329 100644 --- a/lily/script-interface.cc +++ b/lily/script-interface.cc @@ -138,7 +138,6 @@ ADD_INTERFACE (Text_script, "An object that is put above or below a note.", /* properties */ - "add-stem-support " "avoid-slur " "script-priority " "slur " @@ -151,7 +150,6 @@ ADD_INTERFACE (Script_interface, "An object that is put above or below a note.", /* properties */ - "add-stem-support " "avoid-slur " "direction-source " "positioning-done " diff --git a/lily/separation-item.cc b/lily/separation-item.cc index b3e574dad8..6ff2928072 100644 --- a/lily/separation-item.cc +++ b/lily/separation-item.cc @@ -80,8 +80,7 @@ Skyline Separation_item::conditional_skyline (Grob *me, Grob *left) { vector<Box> bs = boxes (me, left); - Real horizon_padding = robust_scm2double (me->get_property ("skyline-vertical-padding"), 0.0); - return Skyline (bs, horizon_padding, Y_AXIS, LEFT); + return Skyline (bs, Y_AXIS, LEFT); } MAKE_SCHEME_CALLBACK (Separation_item, calc_skylines, 1); @@ -90,8 +89,19 @@ Separation_item::calc_skylines (SCM smob) { Item *me = unsmob_item (smob); vector<Box> bs = boxes (me, 0); - Real horizon_padding = robust_scm2double (me->get_property ("skyline-vertical-padding"), 0.0); - return Skyline_pair (bs, horizon_padding, Y_AXIS).smobbed_copy (); + Skyline_pair sp (bs, Y_AXIS); + /* + TODO: We need to decide if padding is 'intrinsic' + to a skyline or if it is something that is only added on in + distance calculations. Here, we make it intrinsic, which copies + the behavior from the old code but no longer corresponds to how + vertical skylines are handled (where padding is not built into + the skyline). + */ + Real vp = robust_scm2double (me->get_property ("skyline-vertical-padding"), 0.0); + sp[LEFT] = sp[LEFT].padded (vp); + sp[RIGHT] = sp[RIGHT].padded (vp); + return sp.smobbed_copy (); } /* if left is non-NULL, get the boxes corresponding to the diff --git a/lily/side-position-interface.cc b/lily/side-position-interface.cc index 6fad89ea54..75104e44b9 100644 --- a/lily/side-position-interface.cc +++ b/lily/side-position-interface.cc @@ -21,6 +21,7 @@ #include <cmath> // ceil. #include <algorithm> +#include <map> using namespace std; @@ -32,7 +33,9 @@ using namespace std; #include "main.hh" #include "misc.hh" #include "note-head.hh" +#include "note-column.hh" #include "pointer-group-interface.hh" +#include "skyline-pair.hh" #include "staff-symbol-referencer.hh" #include "staff-symbol.hh" #include "stem.hh" @@ -172,23 +175,32 @@ Side_position_interface::skyline_side_position (Grob *me, Axis a, Grob *staff_symbol = Staff_symbol_referencer::get_staff_symbol (me); Direction dir = get_grob_direction (me); - Box off; - for (Axis ax = X_AXIS; ax < NO_AXES; incr (ax)) + Skyline my_dim; + Skyline_pair *sp = Skyline_pair::unsmob (me->get_property ("vertical-skylines")); + if (sp && a == Y_AXIS && !pure) { - if (ax == a) - off[ax] = me->get_parent (ax)->maybe_pure_coordinate (common[ax], ax, pure, start, end) - + me->maybe_pure_extent (me, ax, pure, start, end); - else - off[ax] = me->maybe_pure_extent (common[ax], ax, pure, start, end); + Skyline_pair copy = Skyline_pair (*sp); + copy.shift (me->relative_coordinate (common[X_AXIS], X_AXIS)); + copy.raise (me->get_parent (Y_AXIS)->relative_coordinate (common[Y_AXIS], Y_AXIS)); + my_dim = copy[-dir]; } + else + { + Box off; + for (Axis ax = X_AXIS; ax < NO_AXES; incr (ax)) + { + if (ax == a) + off[ax] = me->get_parent (ax)->maybe_pure_coordinate (common[ax], ax, pure, start, end) + + me->maybe_pure_extent (me, ax, pure, start, end); + else + off[ax] = me->maybe_pure_extent (common[ax], ax, pure, start, end); + } - if (off[X_AXIS].is_empty () || off[Y_AXIS].is_empty ()) - return scm_from_double (0.0); - - Real skyline_padding = 0.1; - - Skyline my_dim (off, skyline_padding, other_axis (a), -dir); + if (off[X_AXIS].is_empty () || off[Y_AXIS].is_empty ()) + return scm_from_double (0.0); + my_dim = Skyline (off, other_axis (a), -dir); + } bool include_staff = staff_symbol && a == Y_AXIS @@ -196,7 +208,9 @@ Side_position_interface::skyline_side_position (Grob *me, Axis a, && !to_boolean (me->get_property ("quantize-position")); vector<Box> boxes; + vector<Skyline_pair> skyps; Real min_h = dir == LEFT ? infinity_f : -infinity_f; + map<Grob *, vector<Grob *> > note_column_map; // for parts of a note column for (vsize i = 0; i < support.size (); i++) { Grob *e = support[i]; @@ -218,6 +232,22 @@ Side_position_interface::skyline_side_position (Grob *me, Axis a, } else { + if (Note_column::has_interface (e->get_parent (X_AXIS)) + && to_boolean (me->get_property ("add-stem-support"))) + { + note_column_map[e->get_parent (X_AXIS)].push_back (e); + continue; + } + + Skyline_pair *sp = Skyline_pair::unsmob (e->get_property ("vertical-skylines")); + if (sp && a == Y_AXIS && !pure) + { + Skyline_pair copy = Skyline_pair (*sp); + copy.shift (e->relative_coordinate (common[X_AXIS], X_AXIS)); + copy.raise (e->relative_coordinate (common[Y_AXIS], Y_AXIS)); + skyps.push_back (copy); + continue; + } Box b; for (Axis ax = X_AXIS; ax < NO_AXES; incr (ax)) b[ax] = e->maybe_pure_extent (common[ax], ax, pure, start, end); @@ -231,7 +261,33 @@ Side_position_interface::skyline_side_position (Grob *me, Axis a, } } - Skyline dim (boxes, skyline_padding, other_axis (a), dir); + // this loop ensures that parts of a note column will be in the same box + // pushes scripts and such over stems instead of just over heads + for (map<Grob *, vector<Grob *> >::iterator i = note_column_map.begin (); i != note_column_map.end (); i++) + { + Box big; + for (vsize j = 0; j < (*i).second.size (); j++) + { + Grob *e = (*i).second[j]; + Box b; + for (Axis ax = X_AXIS; ax < NO_AXES; incr (ax)) + b[ax] = e->maybe_pure_extent (common[ax], ax, pure, start, end); + + if (b[X_AXIS].is_empty () || b[Y_AXIS].is_empty ()) + continue; + + big.unite (b); + } + if (!big[X_AXIS].is_empty () && !big[Y_AXIS].is_empty ()) + boxes.push_back (big); + } + + Skyline dim (boxes, other_axis (a), dir); + if (skyps.size ()) + { + Skyline_pair merged (skyps); + dim.merge (merged[dir]); + } if (!boxes.size ()) dim.set_minimum_height (0.0); else @@ -245,7 +301,9 @@ Side_position_interface::skyline_side_position (Grob *me, Axis a, dim.set_minimum_height (minmax (dir, min_h, staff_extents[dir])); } - Real total_off = dir * dim.distance (my_dim); + Real dist = dim.distance (my_dim, 0.1); // 0.1 m4g1c value...fix... + Real total_off = !isinf (dist) ? dir * dist : 0.0; + return finish_offset (me, dir, total_off, current_offset); } @@ -327,7 +385,7 @@ Side_position_interface::aligned_side (Grob *me, Axis a, bool pure, int start, i Direction dir = get_grob_direction (me); bool skyline = to_boolean (me->get_property ("use-skylines")); - Real o = scm_to_double (skyline + Real o = scm_to_double (skyline && !pure ? skyline_side_position (me, a, pure, start, end, current_off) : general_side_position (me, a, true, true, pure, start, end, current_off)); @@ -465,6 +523,7 @@ ADD_INTERFACE (Side_position_interface, " is ignored.", /* properties */ + "add-stem-support " "direction " "minimum-space " "padding " diff --git a/lily/skyline-pair.cc b/lily/skyline-pair.cc index 6f6b4e1b88..6175d1e275 100644 --- a/lily/skyline-pair.cc +++ b/lily/skyline-pair.cc @@ -28,13 +28,23 @@ Skyline_pair::Skyline_pair () { } -Skyline_pair::Skyline_pair (vector<Box> const &boxes, Real padding, Axis a) - : skylines_ (Skyline (boxes, padding, a, DOWN), Skyline (boxes, padding, a, UP)) +Skyline_pair::Skyline_pair (vector<Box> const &boxes, Axis a) + : skylines_ (Skyline (boxes, a, DOWN), Skyline (boxes, a, UP)) { } -Skyline_pair::Skyline_pair (Box const &b, Real padding, Axis a) - : skylines_ (Skyline (b, padding, a, DOWN), Skyline (b, padding, a, UP)) +Skyline_pair::Skyline_pair (vector<Drul_array<Offset> > const &buildings, Axis a) + : skylines_ (Skyline (buildings, a, DOWN), Skyline (buildings, a, UP)) +{ +} + +Skyline_pair::Skyline_pair (vector<Skyline_pair> const &skypairs) + : skylines_ (Skyline (skypairs, DOWN), Skyline (skypairs, UP)) +{ +} + +Skyline_pair::Skyline_pair (Box const &b, Axis a) + : skylines_ (Skyline (b, a, DOWN), Skyline (b, a, UP)) { } @@ -46,6 +56,13 @@ Skyline_pair::raise (Real r) } void +Skyline_pair::deholify () +{ + skylines_[UP].deholify (); + skylines_[DOWN].deholify (); +} + +void Skyline_pair::shift (Real r) { skylines_[UP].shift (r); @@ -53,10 +70,56 @@ Skyline_pair::shift (Real r) } void -Skyline_pair::insert (Box const &b, Real padding, Axis a) +Skyline_pair::insert (Box const &b, Axis a) { - skylines_[UP].insert (b, padding, a); - skylines_[DOWN].insert (b, padding, a); + skylines_[UP].insert (b, a); + skylines_[DOWN].insert (b, a); +} + +Real +Skyline_pair::left () const +{ + return min (skylines_[UP].left (), skylines_[DOWN].left ()); +} + +Real +Skyline_pair::right () const +{ + return max (skylines_[UP].right (), skylines_[DOWN].right ()); +} + +// This function comes with the same caveats as smallest_shift: +// if the skylines are not contiguous, we may report false +// intersections. +bool +Skyline_pair::intersects (Skyline_pair const &other) const +{ + return skylines_[UP].distance (other[DOWN]) > 0 + && other[UP].distance (skylines_[DOWN]) > 0; +} + +Real +Skyline_pair::smallest_shift (Skyline_pair const &other, Direction d, + Real h_pad, Real v_pad) +{ + // If skylines_[UP] avoids other[DOWN] or skylines_[DOWN] avoids + // other[UP] then we will not intersect. + // Note that this is not guaranteed to return the smallest shift + // if one Skyline_pair is not connected: the smallest_shift left + // in the case of + // AAA + // BBBBBB + // AAA + // will result in + // AAA + // BBBBBB + // AAA + // even though the originals did not collide. If it becomes necessary, + // this case could be handled by splitting the Skyline_pairs up into + // their connected components. + + return d * min (d * skylines_[UP].smallest_shift (other[DOWN], d, h_pad, v_pad), + d * skylines_[DOWN].smallest_shift (other[UP], d, h_pad, v_pad)); } void @@ -76,8 +139,8 @@ Skyline_pair::print () const void Skyline_pair::print_points () const { - skylines_[UP].print (); - skylines_[DOWN].print (); + skylines_[UP].print_points (); + skylines_[DOWN].print_points (); } bool @@ -87,6 +150,13 @@ Skyline_pair::is_empty () const && skylines_[DOWN].is_empty (); } +bool +Skyline_pair::is_singleton () const +{ + return skylines_[UP].is_singleton () + && skylines_[DOWN].is_singleton (); +} + Skyline & Skyline_pair::operator [] (Direction d) { diff --git a/lily/skyline.cc b/lily/skyline.cc index 0250fc07f4..9bbd7e9752 100644 --- a/lily/skyline.cc +++ b/lily/skyline.cc @@ -18,6 +18,7 @@ */ #include "skyline.hh" +#include "skyline-pair.hh" #include <deque> #include <cstdio> @@ -87,16 +88,18 @@ Building::Building (Real start, Real start_height, Real end_height, Real end) if (isinf (start) || isinf (end)) assert (start_height == end_height); + start_ = start; end_ = end; precompute (start, start_height, end_height, end); } -Building::Building (Box const &b, Real horizon_padding, Axis horizon_axis, Direction sky) +Building::Building (Box const &b, Axis horizon_axis, Direction sky) { - Real start = b[horizon_axis][LEFT] - horizon_padding; - Real end = b[horizon_axis][RIGHT] + horizon_padding; + Real start = b[horizon_axis][LEFT]; + Real end = b[horizon_axis][RIGHT]; Real height = sky * b[other_axis (horizon_axis)][sky]; + start_ = start; end_ = end; precompute (start, height, height, end); } @@ -104,9 +107,9 @@ Building::Building (Box const &b, Real horizon_padding, Axis horizon_axis, Direc void Building::precompute (Real start, Real start_height, Real end_height, Real end) { - slope_ = (end_height - start_height) / (end - start); - if (start_height == end_height) /* if they were both infinite, we would get nan, not 0, from the prev line */ - slope_ = 0; + slope_ = 0.0; /* if they were both infinite, we would get nan, not 0, from the prev line */ + if (start_height != end_height) + slope_ = (end_height - start_height) / (end - start); assert (!isinf (slope_) && !isnan (slope_)); @@ -119,7 +122,7 @@ Building::precompute (Real start, Real start_height, Real end_height, Real end) y_intercept_ = start_height - slope_ * start; } -Real +inline Real Building::height (Real x) const { return isinf (x) ? y_intercept_ : slope_ * x + y_intercept_; @@ -128,10 +131,10 @@ Building::height (Real x) const void Building::print () const { - printf ("%f x + %f ends at %f\n", slope_, y_intercept_, end_); + printf ("%f x + %f from %f to %f\n", slope_, y_intercept_, start_, end_); } -Real +inline Real Building::intersection_x (Building const &other) const { Real ret = (y_intercept_ - other.y_intercept_) / (other.slope_ - slope_); @@ -145,20 +148,71 @@ Building::leading_part (Real chop) end_ = chop; } -Building -Building::sloped_neighbour (Real start, Real horizon_padding, Direction d) const +// Returns a shift s such that (x + s, y) intersects the roof of +// this building. If no such shift exists, returns infinity_f. +Real +Building::shift_to_intersect (Real x, Real y) const { - Real x = (d == LEFT) ? start : end_; - Real left = x; - Real right = x + d * horizon_padding; - Real left_height = height (x); - Real right_height = left_height - horizon_padding; - if (d == LEFT) - { - swap (left, right); - swap (left_height, right_height); - } - return Building (left, left_height, right_height, right); + // Solve for s: y = (x + s)*m + b + Real ret = (y - y_intercept_ - slope_ * x) / slope_; + + if (ret >= start_ && ret <= end_ && !isinf (ret)) + return ret; + return infinity_f; +} + +// Returns the interval of horizontal shifts for which this +// building (pointing up) overlaps the other building (pointing down). +Interval +Building::overlapping_shift_interval (Building const &other) const +{ + Interval iv; + + // If one building is empty, there will never be an overlap. + if (y_intercept_ == -infinity_f || other.y_intercept_ == -infinity_f) + return iv; + + // There are two kinds of interesting positions: + // - when the horizontal extents of the buildings just touch + // - when an endpoint of one building intersects the roof of the other. + // The interval we are looking for is the smallest one that + // contains all of the interesting points. + + + Real my_y1 = height (start_); + Real my_y2 = height (end_); + Real his_y1 = -other.height (other.start_); // "-" because OTHER points down + Real his_y2 = -other.height (other.end_); + + // If both buildings are infinite in the same direction, + // the return value is either empty or full. + if ((isinf (start_) && isinf (other.start_)) + || (isinf (end_) && isinf (other.end_))) + return (y_intercept_ > other.y_intercept_) + ? Interval (-infinity_f, infinity_f) : Interval (); + + // ...when the horizontal extents of the buildings just touch... + if (my_y1 >= his_y2) + iv.add_point (other.end_ - start_); + if (my_y2 >= his_y1) + iv.add_point (other.start_ - end_); + + // ...when an endpoint of one building intersects the roof of the other. + Real p1 = shift_to_intersect (other.start_, his_y1); + Real p2 = shift_to_intersect (other.end_, his_y2); + // "-my_y1" because OTHER points down: + Real p3 = other.shift_to_intersect (start_, -my_y1); + Real p4 = other.shift_to_intersect (end_, -my_y2); + if (!isinf (p1)) + iv.add_point (p1); + if (!isinf (p2)) + iv.add_point (p2); + if (!isinf (p3)) + iv.add_point (p3); + if (!isinf (p4)) + iv.add_point (p4); + + return iv; } static Real @@ -167,6 +221,18 @@ first_intersection (Building const &b, list<Building> *const s, Real start_x) while (!s->empty () && start_x < b.end_) { Building c = s->front (); + + // conceals and intersection_x involve multiplication and + // division. Avoid that, if we can. + if (c.y_intercept_ == -infinity_f) + { + if (c.end_ > b.end_) + return b.end_; + start_x = c.end_; + s->pop_front (); + continue; + } + if (c.conceals (b, start_x)) return start_x; @@ -193,9 +259,58 @@ Building::conceals (Building const &other, Real x) const || (i > x && slope_ < other.slope_); } +// Remove redundant empty buildings from the skyline. +// If there are two adjacent empty buildings, they can be +// turned into one. +void +Skyline::normalize () +{ + bool last_empty = false; + list<Building>::iterator i; + for (i = buildings_.begin (); i != buildings_.end (); i++) + { + if (last_empty && i->y_intercept_ == -infinity_f) + { + list<Building>::iterator last = i; + last--; + last->end_ = i->end_; + buildings_.erase (i); + i = last; + } + last_empty = (i->y_intercept_ == -infinity_f); + } + + assert (buildings_.front ().start_ == -infinity_f); + assert (buildings_.back ().end_ == infinity_f); +} + +void +Skyline::deholify () +{ + // Since a skyline should always be normalized, we can + // assume that there are never two adjacent empty buildings. + // That is, if center is empty then left and right are not. + list<Building>::iterator left = buildings_.begin (); + list<Building>::iterator center = buildings_.begin (); + list<Building>::iterator right; + + for (right = buildings_.begin (); right != buildings_.end (); right++) + { + if (center != buildings_.begin () && center->y_intercept_ == -infinity_f) + { + Real p1 = left->height (left->end_); + Real p2 = right->height (right->start_); + *center = Building (center->start_, p1, p2, center->end_); + + left = center; + center = right; + } + } +} + void Skyline::internal_merge_skyline (list<Building> *s1, list<Building> *s2, - list<Building> *const result) + list<Building> *const result) const { if (s1->empty () || s2->empty ()) { @@ -204,17 +319,38 @@ Skyline::internal_merge_skyline (list<Building> *s1, list<Building> *s2, } Real x = -infinity_f; + Real last_end = -infinity_f; while (!s1->empty ()) { if (s2->front ().conceals (s1->front (), x)) swap (s1, s2); Building b = s1->front (); - Real end = first_intersection (b, s2, x); + Building c = s2->front (); + // Optimization: if the other skyline is empty at this point, + // we can avoid testing some intersections. Just grab as many + // buildings from s1 as we can, and shove them onto the output. + if (c.y_intercept_ == -infinity_f + && c.end_ >= b.end_) + { + list<Building>::iterator i = s1->begin (); + i++; + while (i != s1->end () && i->end_ <= c.end_) + i++; + + s1->front ().start_ = x; + result->splice (result->end (), *s1, s1->begin (), i); + x = result->back ().end_; + last_end = x; + continue; + } + + Real end = first_intersection (b, s2, x); if (s2->empty ()) { - result->push_front (b); + b.start_ = last_end; + result->push_back (b); break; } @@ -222,7 +358,9 @@ Skyline::internal_merge_skyline (list<Building> *s1, list<Building> *s2, if (end > x + EPS) { b.leading_part (end); - result->push_front (b); + b.start_ = last_end; + last_end = b.end_; + result->push_back (b); } if (end >= s1->front ().end_) @@ -230,7 +368,6 @@ Skyline::internal_merge_skyline (list<Building> *s1, list<Building> *s2, x = end; } - result->reverse (); } static void @@ -240,89 +377,91 @@ empty_skyline (list<Building> *const ret) } /* - Given Building 'b' with starting wall location 'start', extend each side - with a sloped roofline of width 'horizon_padding'; put the skyline in 'ret' + Given Building 'b', build a skyline containing only that building. */ static void -single_skyline (Building b, Real start, Real horizon_padding, list<Building> *const ret) +single_skyline (Building b, list<Building> *const ret) { - bool sloped_neighbours = horizon_padding > 0 && !isinf (start) && !isinf (b.end_); - if (!isinf (b.end_)) - ret->push_front (Building (b.end_ + horizon_padding, -infinity_f, - -infinity_f, infinity_f)); - if (sloped_neighbours) - ret->push_front (b.sloped_neighbour (start, horizon_padding, RIGHT)); - - if (b.end_ > start + EPS) - ret->push_front (b); - - if (sloped_neighbours) - ret->push_front (b.sloped_neighbour (start, horizon_padding, LEFT)); - - if (!isinf (start)) - ret->push_front (Building (-infinity_f, -infinity_f, - -infinity_f, start - horizon_padding)); + if (b.end_ > b.start_ + EPS) + { + ret->push_back (Building (-infinity_f, -infinity_f, + -infinity_f, b.start_)); + ret->push_back (b); + ret->push_back (Building (b.end_, -infinity_f, + -infinity_f, infinity_f)); + } + else + { + empty_skyline (ret); + } } /* remove a non-overlapping set of boxes from BOXES and build a skyline out of them */ static list<Building> -non_overlapping_skyline (list<Box> *const boxes, Real horizon_padding, Axis horizon_axis, Direction sky) +non_overlapping_skyline (list<Building> *const buildings) { list<Building> result; Real last_end = -infinity_f; - list<Box>::iterator i = boxes->begin (); - while (i != boxes->end ()) + Building last_building (-infinity_f, -infinity_f, -infinity_f, infinity_f); + list<Building>::iterator i = buildings->begin (); + while (i != buildings->end ()) { - Interval iv = (*i)[horizon_axis]; + Real x1 = i->start_; + Real y1 = i->height (i->start_); + Real x2 = i->end_; + Real y2 = i->height (i->end_); + + // Drop buildings that will obviously have no effect. + if (last_building.height (x1) >= y1 + && last_building.end_ >= x2 + && last_building.height (x2) >= y2) + { + list<Building>::iterator j = i++; + buildings->erase (j); + continue; + } - if (iv[LEFT] - horizon_padding < last_end) + if (x1 < last_end) { i++; continue; } - if (iv[LEFT] - horizon_padding > last_end + EPS) - result.push_front (Building (last_end, -infinity_f, -infinity_f, iv[LEFT] - 2 * horizon_padding)); + if (x1 > last_end + EPS) + result.push_back (Building (last_end, -infinity_f, -infinity_f, x1)); - Building b (*i, horizon_padding, horizon_axis, sky); - bool sloped_neighbours = horizon_padding > 0 && !isinf (iv.length ()); - if (sloped_neighbours) - result.push_front (b.sloped_neighbour (iv[LEFT] - horizon_padding, horizon_padding, LEFT)); - result.push_front (b); - if (sloped_neighbours) - result.push_front (b.sloped_neighbour (iv[LEFT] - horizon_padding, horizon_padding, RIGHT)); + result.push_back (*i); + last_building = *i; + last_end = i->end_; - list<Box>::iterator j = i++; - boxes->erase (j); - last_end = result.front ().end_; + list<Building>::iterator j = i++; + buildings->erase (j); } + if (last_end < infinity_f) - result.push_front (Building (last_end, -infinity_f, -infinity_f, infinity_f)); - result.reverse (); + result.push_back (Building (last_end, -infinity_f, -infinity_f, infinity_f)); return result; } -class LessThanBox +class LessThanBuilding { - Axis a_; - public: - LessThanBox (Axis a) + bool operator () (Building const &b1, Building const &b2) { - a_ = a; - } - - bool operator () (Box const &b1, Box const &b2) - { - return b1[a_][LEFT] < b2[a_][LEFT]; + return b1.start_ < b2.start_ + || (b1.start_ == b2.start_ && b1.height (b1.start_) > b2.height (b1.start_)); } }; +/** + BUILDINGS is a list of buildings, but they could be overlapping + and in any order. The returned list of buildings is ordered and non-overlapping. +*/ list<Building> -Skyline::internal_build_skyline (list<Box> *boxes, Real horizon_padding, Axis horizon_axis, Direction sky) +Skyline::internal_build_skyline (list<Building> *buildings) const { - vsize size = boxes->size (); + vsize size = buildings->size (); if (size == 0) { @@ -333,16 +472,14 @@ Skyline::internal_build_skyline (list<Box> *boxes, Real horizon_padding, Axis ho else if (size == 1) { list<Building> result; - single_skyline (Building (boxes->front (), horizon_padding, horizon_axis, sky), - boxes->front ()[horizon_axis][LEFT] - horizon_padding, - horizon_padding, &result); + single_skyline (buildings->front (), &result); return result; } deque<list<Building> > partials; - boxes->sort (LessThanBox (horizon_axis)); - while (!boxes->empty ()) - partials.push_back (non_overlapping_skyline (boxes, horizon_padding, horizon_axis, sky)); + buildings->sort (LessThanBuilding ()); + while (!buildings->empty ()) + partials.push_back (non_overlapping_skyline (buildings)); /* we'd like to say while (partials->size () > 1) but that's O (n). Instead, we exit in the middle of the loop */ @@ -388,68 +525,88 @@ Skyline::Skyline (Direction sky) } /* - build padded skyline from an existing skyline with padding - added to it. -*/ + Build skyline from a set of boxes. -Skyline::Skyline (Skyline const &src, Real horizon_padding, Axis /*a*/) + Boxes should have fatness in the horizon_axis, otherwise they are ignored. + */ +Skyline::Skyline (vector<Box> const &boxes, Axis horizon_axis, Direction sky) { - /* - We extract boxes from the skyline, then build a new skyline from - the boxes. - A box is created for every horizontal portion of the skyline - Because skylines are defined positive, and then inverted if they - are to be down-facing, we create the new skyline in the UP - direction, then give it the down direction if needed. - */ - Real start = -infinity_f; - list<Box> boxes; - - // establish a baseline box - // FIXME: This has hardcoded logic, assuming a == X_AXIS! - boxes.push_back (Box (Interval (-infinity_f, infinity_f), - Interval (0, 0))); - list<Building>::const_iterator end = src.buildings_.end (); - for (list<Building>::const_iterator i = src.buildings_.begin (); i != end; start = i->end_, i++) - if ((i->slope_ == 0) && !isinf (i->y_intercept_)) - boxes.push_back (Box (Interval (start, i->end_), - Interval (-infinity_f, i->y_intercept_))); - buildings_ = internal_build_skyline (&boxes, horizon_padding, X_AXIS, UP); - sky_ = src.sky_; + list<Building> buildings; + sky_ = sky; + + Axis vert_axis = other_axis (horizon_axis); + for (vsize i = 0; i < boxes.size (); i++) + { + Interval iv = boxes[i][horizon_axis]; + if (iv.length () > EPS && !boxes[i][vert_axis].is_empty ()) + buildings.push_front (Building (boxes[i], horizon_axis, sky)); + } + + buildings_ = internal_build_skyline (&buildings); + normalize (); } /* - build skyline from a set of boxes. If horizon_padding > 0, expand all the boxes - by that amount and add 45-degree sloped boxes to the edges of each box (of - width horizon_padding). That is, the total amount of horizontal expansion is - horizon_padding*4, half of which is sloped and half of which is flat. + build skyline from a set of line segments. - Boxes should have fatness in the horizon_axis (after they are expanded by - horizon_padding), otherwise they are ignored. + Buildings should have fatness in the horizon_axis, otherwise they are ignored. */ -Skyline::Skyline (vector<Box> const &boxes, Real horizon_padding, Axis horizon_axis, Direction sky) +Skyline::Skyline (vector<Drul_array<Offset> > const &segments, Axis horizon_axis, Direction sky) { - list<Box> filtered_boxes; + list<Building> buildings; sky_ = sky; - Axis vert_axis = other_axis (horizon_axis); - for (vsize i = 0; i < boxes.size (); i++) + for (vsize i = 0; i < segments.size (); i++) { - Interval iv = boxes[i][horizon_axis]; - iv.widen (horizon_padding); - if (iv.length () > EPS && !boxes[i][vert_axis].is_empty ()) - filtered_boxes.push_front (boxes[i]); + Drul_array<Offset> const &seg = segments[i]; + Offset left = seg[LEFT]; + Offset right = seg[RIGHT]; + if (left[horizon_axis] > right[horizon_axis]) + swap (left, right); + + Real x1 = left[horizon_axis]; + Real x2 = right[horizon_axis]; + Real y1 = left[other_axis (horizon_axis)] * sky; + Real y2 = right[other_axis (horizon_axis)] * sky; + + if (x1 + EPS < x2) + buildings.push_back (Building (x1, y1, y2, x2)); + } + + buildings_ = internal_build_skyline (&buildings); + normalize (); +} + +Skyline::Skyline (vector<Skyline_pair> const &skypairs, Direction sky) +{ + sky_ = sky; + + deque<Skyline> partials; + for (vsize i = 0; i < skypairs.size (); i++) + partials.push_back (Skyline ((skypairs[i])[sky])); + + while (partials.size () > 1) + { + Skyline one = partials.front (); + partials.pop_front (); + Skyline two = partials.front (); + partials.pop_front (); + + one.merge (two); + partials.push_back (one); } - buildings_ = internal_build_skyline (&filtered_boxes, horizon_padding, horizon_axis, sky); + if (partials.size ()) + buildings_.swap (partials.front ().buildings_); + else + buildings_.clear (); } -Skyline::Skyline (Box const &b, Real horizon_padding, Axis horizon_axis, Direction sky) +Skyline::Skyline (Box const &b, Axis horizon_axis, Direction sky) { sky_ = sky; - Building front (b, horizon_padding, horizon_axis, sky); - single_skyline (front, b[horizon_axis][LEFT] - horizon_padding, - horizon_padding, &buildings_); + Building front (b, horizon_axis, sky); + single_skyline (front, &buildings_); } void @@ -457,14 +614,24 @@ Skyline::merge (Skyline const &other) { assert (sky_ == other.sky_); + if (other.is_empty ()) + return; + + if (is_empty ()) + { + buildings_ = other.buildings_; + return; + } + list<Building> other_bld (other.buildings_); list<Building> my_bld; my_bld.splice (my_bld.begin (), buildings_); internal_merge_skyline (&other_bld, &my_bld, &buildings_); + normalize (); } void -Skyline::insert (Box const &b, Real horizon_padding, Axis a) +Skyline::insert (Box const &b, Axis a) { list<Building> other_bld; list<Building> my_bld; @@ -478,14 +645,13 @@ Skyline::insert (Box const &b, Real horizon_padding, Axis a) /* do the same filtering as in Skyline (vector<Box> const&, etc.) */ Interval iv = b[a]; - iv.widen (horizon_padding); if (iv.length () <= EPS || b[other_axis (a)].is_empty ()) return; my_bld.splice (my_bld.begin (), buildings_); - single_skyline (Building (b, horizon_padding, a, sky_), b[a][LEFT] - horizon_padding, - horizon_padding, &other_bld); + single_skyline (Building (b, a, sky_), &other_bld); internal_merge_skyline (&other_bld, &my_bld, &buildings_); + normalize (); } void @@ -502,6 +668,7 @@ Skyline::shift (Real s) list<Building>::iterator end = buildings_.end (); for (list<Building>::iterator i = buildings_.begin (); i != end; i++) { + i->start_ += s; i->end_ += s; i->y_intercept_ -= s * i->slope_; } @@ -525,32 +692,81 @@ Skyline::touching_point (Skyline const &other, Real horizon_padding) const Real Skyline::internal_distance (Skyline const &other, Real horizon_padding, Real *touch_point) const { - assert (sky_ == -other.sky_); + if (horizon_padding == 0.0) + return internal_distance (other, touch_point); - Skyline const *padded_this = this; - Skyline const *padded_other = &other; - bool created_tmp_skylines = false; - - /* - For systems, padding is not added at creation time. Padding is - added to AxisGroup objects when outside-staff objects are added. - Thus, when we want to place systems with horizontal padding, - we do it at distance calculation time. - */ - if (horizon_padding != 0.0) + // Note that it is not necessary to build a padded version of other, + // because the same effect can be achieved just by doubling horizon_padding. + Skyline padded_this = padded (horizon_padding); + return padded_this.internal_distance (other, touch_point); +} + +Skyline +Skyline::padded (Real horizon_padding) const +{ + list<Building> pad_buildings; + for (list<Building>::const_iterator i = buildings_.begin (); i != buildings_.end (); ++i) { - padded_this = new Skyline (*padded_this, horizon_padding, X_AXIS); - padded_other = new Skyline (*padded_other, horizon_padding, X_AXIS); - created_tmp_skylines = true; + if (i->start_ > -infinity_f) + { + Real height = i->height (i->start_); + if (height > -infinity_f) + { + // Add the sloped building that pads the left side of the current building. + Real start = i->start_ - 2 * horizon_padding; + Real end = i->start_ - horizon_padding; + pad_buildings.push_back (Building (start, height - horizon_padding, height, end)); + + // Add the flat building that pads the left side of the current building. + start = i->start_ - horizon_padding; + end = i->start_; + pad_buildings.push_back (Building (start, height, height, end)); + } + } + + if (i->end_ < infinity_f) + { + Real height = i->height (i->end_); + if (height > -infinity_f) + { + // Add the flat building that pads the right side of the current building. + Real start = i->end_; + Real end = start + horizon_padding; + pad_buildings.push_back (Building (start, height, height, end)); + + // Add the sloped building that pads the right side of the current building. + start = end; + end += horizon_padding; + pad_buildings.push_back (Building (start, height, height - horizon_padding, end)); + } + } } - list<Building>::const_iterator i = padded_this->buildings_.begin (); - list<Building>::const_iterator j = padded_other->buildings_.begin (); + // The buildings may be overlapping, so resolve that. + list<Building> pad_skyline = internal_build_skyline (&pad_buildings); + + // Merge the padding with the original, to make a new skyline. + Skyline padded (sky_); + list<Building> my_buildings = buildings_; + padded.buildings_.clear (); + internal_merge_skyline (&pad_skyline, &my_buildings, &padded.buildings_); + padded.normalize (); + + return padded; +} + +Real +Skyline::internal_distance (Skyline const &other, Real *touch_point) const +{ + assert (sky_ == -other.sky_); + + list<Building>::const_iterator i = buildings_.begin (); + list<Building>::const_iterator j = other.buildings_.begin (); Real dist = -infinity_f; Real start = -infinity_f; Real touch = -infinity_f; - while (i != padded_this->buildings_.end () && j != padded_other->buildings_.end ()) + while (i != buildings_.end () && j != other.buildings_.end ()) { Real end = min (i->end_, j->end_); Real start_dist = i->height (start) + j->height (start); @@ -569,16 +785,25 @@ Skyline::internal_distance (Skyline const &other, Real horizon_padding, Real *to start = end; } - if (created_tmp_skylines) - { - delete padded_this; - delete padded_other; - } - *touch_point = touch; return dist; } +// changes the direction that the skyline is pointing +void +Skyline::invert () +{ + list<Building>::iterator i; + for (i = buildings_.begin (); i != buildings_.end (); i++) + if (!isinf (i->y_intercept_)) + { + i->y_intercept_ *= -1; + i->slope_ *= -1; + } + + sky_ = -sky_; +} + Real Skyline::height (Real airplane) const { @@ -598,9 +823,16 @@ Skyline::height (Real airplane) const Real Skyline::max_height () const { - Skyline s (-sky_); - s.set_minimum_height (0); - return sky_ * distance (s); + Real ret = -infinity_f; + + list<Building>::const_iterator i; + for (i = buildings_.begin (); i != buildings_.end (); ++i) + { + ret = max (ret, i->height (i->start_)); + ret = max (ret, i->height (i->end_)); + } + + return sky_ * ret; } Real @@ -640,13 +872,105 @@ Skyline::to_points (Axis horizon_axis) const return out; } +// Returns the smallest (non-negative) shift in the given +// direction which will result in THIS and OTHER not overlapping. +// Warning: this function is O(n^2 log n). Use sparingly. +Real +Skyline::smallest_shift (Skyline const &other, + Direction d, + Real horizon_padding, + Real vertical_padding) const +{ + // If one or both of the paddings is zero, this can + // be optimized... + Skyline padded_me = padded (horizon_padding); + padded_me.raise (vertical_padding); + + list<Building>::const_iterator i = padded_me.buildings_.begin (); + list<Building>::const_iterator j = other.buildings_.begin (); + list<Building>::const_iterator i_end = padded_me.buildings_.end (); + list<Building>::const_iterator j_end = other.buildings_.end (); + + // Find all shifts that are not allowed. + vector<Interval> forbidden_shifts; + for (; i != i_end; ++i) + if (i->y_intercept_ != -infinity_f) + for (j = other.buildings_.begin (); j != j_end; ++j) + { + Interval iv = i->overlapping_shift_interval (*j); + if (!iv.is_empty ()) + forbidden_shifts.push_back (iv); + } + + // Now comes the trick: we want to find the smallest point + // that is not in the union of forbidden_shifts. We can represent + // the union of forbidden_shifts as a skyline, where a point is + // allowed if it has height -infinity_f and forbidden otherwise. + vector<Box> boxes; + for (vector<Interval>::iterator k = forbidden_shifts.begin (); + k != forbidden_shifts.end (); ++k) + boxes.push_back (Box (*k, Interval (-1, 0))); + Skyline s (boxes, X_AXIS, UP); + + // Find the smallest (ie. closest to zero, in the appropriate direction) + // coordinate where the height of s is -infinity_f. + Real last_good_point = -infinity_f; + for (i = s.buildings_.begin (); i != s.buildings_.end (); ++i) + { + if (d == LEFT && i->start_ > 0) + return last_good_point; + + if (i->y_intercept_ == -infinity_f) + { + if (i->start_ <= 0 && i->end_ >= 0) + return 0; + if (d == RIGHT && i->start_ >= 0) + return i->start_; + + last_good_point = i->end_; + } + } + + return infinity_f * d; +} + +Real +Skyline::left () const +{ + for (list<Building>::const_iterator i (buildings_.begin ()); + i != buildings_.end (); i++) + if (i->y_intercept_ > -infinity_f) + return i->start_; + + return infinity_f; +} + +Real +Skyline::right () const +{ + for (list<Building>::const_reverse_iterator i (buildings_.rbegin ()); + i != buildings_.rend (); ++i) + if (i->y_intercept_ > -infinity_f) + return i->end_; + + return -infinity_f; +} + bool Skyline::is_empty () const { + if (!buildings_.size ()) + return true; Building b = buildings_.front (); return b.end_ == infinity_f && b.y_intercept_ == -infinity_f; } +bool +Skyline::is_singleton () const +{ + return buildings_.size () == 3; +} + void Skyline::clear () { diff --git a/lily/slur.cc b/lily/slur.cc index 6d0d84203e..eb9913dc16 100644 --- a/lily/slur.cc +++ b/lily/slur.cc @@ -31,8 +31,8 @@ #include "main.hh" // DEBUG_SLUR_SCORING #include "note-column.hh" #include "output-def.hh" -#include "spanner.hh" #include "skyline-pair.hh" +#include "spanner.hh" #include "staff-symbol-referencer.hh" #include "stem.hh" #include "text-interface.hh" @@ -364,7 +364,7 @@ Slur::outside_slur_callback (SCM grob, SCM offset_scm) return scm_from_double (offset + avoidance_offset); } -MAKE_SCHEME_CALLBACK_WITH_OPTARGS (Slur, vertical_skylines, 1, 0, ""); +MAKE_SCHEME_CALLBACK (Slur, vertical_skylines, 1); SCM Slur::vertical_skylines (SCM smob) { @@ -372,7 +372,7 @@ Slur::vertical_skylines (SCM smob) vector<Box> boxes; if (!me) - return Skyline_pair (boxes, 0.0, X_AXIS).smobbed_copy (); + return Skyline_pair (boxes, X_AXIS).smobbed_copy (); Bezier curve = Slur::get_curve (me); vsize box_count = robust_scm2vsize (me->get_property ("skyline-quantizing"), 10); @@ -384,7 +384,7 @@ Slur::vertical_skylines (SCM smob) boxes.push_back (b); } - return Skyline_pair (boxes, 0.0, X_AXIS).smobbed_copy (); + return Skyline_pair (boxes, X_AXIS).smobbed_copy (); } /* @@ -562,10 +562,8 @@ ADD_INTERFACE (Slur, "inspect-index " "line-thickness " "note-columns " - "skyline-quantizing " "positions " "ratio " "thickness " - "vertical-skylines " ); diff --git a/lily/stencil-integral.cc b/lily/stencil-integral.cc new file mode 100644 index 0000000000..9a26ae2060 --- /dev/null +++ b/lily/stencil-integral.cc @@ -0,0 +1,1116 @@ +/* + This file is part of LilyPond, the GNU music typesetter. + + Copyright (C) 2012 Mike Solomon <mike@apollinemike.com> + + LilyPond is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + LilyPond is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with LilyPond. If not, see <http://www.gnu.org/licenses/>. +*/ + +/* +tools for transform-matrices following the standard at +http://www.w3.org/TR/SVG/coords.html + +a list in the form +(list a b c d e f g) +becomes this matrix: +[ a c e ] +[ b d f ] +[ 0 0 1 ] +when this transforms a point (x,y), the point is written as matrix: +[ x ] +[ y ] +[ 1 ] +*/ + +#include <pango/pango-matrix.h> +#include <complex> +#include "box.hh" +#include "bezier.hh" +#include "dimensions.hh" +#include "font-metric.hh" +#include "grob.hh" +#include "interval.hh" +#include "freetype.hh" +#include "misc.hh" +#include "offset.hh" +#include "modified-font-metric.hh" +#include "open-type-font.hh" +#include "pango-font.hh" +#include "pointer-group-interface.hh" +#include "lily-guile.hh" +#include "real.hh" +#include "stencil.hh" +#include "string-convert.hh" +#include "skyline.hh" +#include "skyline-pair.hh" +using namespace std; + +Real QUANTIZATION_UNIT = 0.2; + +void create_path_cap (vector<Box> &boxes, vector<Drul_array<Offset> > &buildings, PangoMatrix trans, Offset pt, Real rad, Real slope, Direction d); + +struct Transform_matrix_and_expression +{ + PangoMatrix tm_; + SCM expr_; + + Transform_matrix_and_expression (PangoMatrix tm, SCM expr); +}; + +Transform_matrix_and_expression::Transform_matrix_and_expression (PangoMatrix tm, SCM expr) +{ + tm_ = tm; + expr_ = expr; +} + +PangoMatrix +make_transform_matrix (Real p0, Real p1, Real p2, Real p3, Real p4, Real p5) +{ + PangoMatrix out; + out.xx = p0; + out.xy = p1; + out.yx = p2; + out.yy = p3; + out.x0 = p4; + out.y0 = p5; + return out; +} + +//// UTILITY FUNCTIONS + +/* + map x's placement between orig_l and orig_r onto + the interval final_l final_r +*/ +Real +linear_map (Real final_l, Real final_r, Real orig_l, Real orig_r, Real x) +{ + return final_l + ((final_r - final_l) * ((x - orig_l) / (orig_r - orig_l))); +} + +/* + from a nested SCM list, return the first list of numbers + useful for polygons +*/ +SCM +get_number_list (SCM l) +{ + if (scm_is_pair (l)) + { + if (scm_is_number (scm_car (l))) + return l; + SCM res = get_number_list (scm_car (l)); + if (res == SCM_BOOL_F) + return get_number_list (scm_cdr (l)); + return res; + } + return SCM_BOOL_F; +} + +/* + from a nested SCM list, return the first list of numbers + useful for paths +*/ +SCM +get_path_list (SCM l) +{ + if (scm_is_pair (l)) + { + if (scm_memv (scm_car (l), + scm_list_n (ly_symbol2scm ("moveto"), + ly_symbol2scm ("rmoveto"), + ly_symbol2scm ("lineto"), + ly_symbol2scm ("rlineto"), + ly_symbol2scm ("curveto"), + ly_symbol2scm ("rcurveto"), + ly_symbol2scm ("closepath"), + SCM_UNDEFINED)) + != SCM_BOOL_F) + return l; + SCM res = get_path_list (scm_car (l)); + if (res == SCM_BOOL_F) + return get_path_list (scm_cdr (l)); + return res; + } + return SCM_BOOL_F; +} + +Real +perpendicular_slope (Real s) +{ + if (s == 0.0) + return infinity_f; + if (s == infinity_f) + return 0.0; + return -1.0 / s; +} + +//// END UTILITY FUNCTIONS + +/* + below, for all of the functions make_X_boxes, the expression + is always unpacked into variables. + then, after a line of /////, there are manipulations of these variables + (there may be no manipulations necessary depending on the function) + afterwards, there is another ///// followed by the creation of points + and boxes +*/ + +void +make_draw_line_boxes (vector<Box> &boxes, vector<Drul_array<Offset> > &buildings, PangoMatrix trans, SCM expr, bool use_building) +{ + Real thick = robust_scm2double (scm_car (expr), 0.0); + expr = scm_cdr (expr); + Real x0 = robust_scm2double (scm_car (expr), 0.0); + expr = scm_cdr (expr); + Real y0 = robust_scm2double (scm_car (expr), 0.0); + expr = scm_cdr (expr); + Real x1 = robust_scm2double (scm_car (expr), 0.0); + expr = scm_cdr (expr); + Real y1 = robust_scm2double (scm_car (expr), 0.0); + Real slope = x1 == x0 ? infinity_f : (y1 - y0) / (x1 - x0); + ////////////////////// + if (x1 < x0) + { + swap (x0, x1); + swap (y0, y1); + } + Offset left (x0, y0); + Offset right (x1, y1); + Direction d = DOWN; + do + { + Offset inter_l = get_point_in_y_direction (left, perpendicular_slope (slope), thick / 2, d); + Offset inter_r = get_point_in_y_direction (right, perpendicular_slope (slope), thick / 2, d);//printf ("O %4.4f %4.4f\n", inter_l[X_AXIS], inter_r[X_AXIS]);printf ("TRANNY %4.4f %4.4f %4.4f %4.4f %4.4f %4.4f\n", trans.xx, trans.xy, trans.yx, trans.yy, trans.x0, trans.y0); + pango_matrix_transform_point (&trans, &inter_l[X_AXIS], &inter_l[Y_AXIS]); + pango_matrix_transform_point (&trans, &inter_r[X_AXIS], &inter_r[Y_AXIS]); + if ((inter_l[X_AXIS] == inter_r[X_AXIS]) || (inter_l[Y_AXIS] == inter_r[Y_AXIS])) + { + //printf ("OO %4.4f %4.4f\n", inter_l[X_AXIS], inter_r[X_AXIS]); + Box b; + b.add_point (inter_l); + b.add_point (inter_r); + boxes.push_back (b); + } + else if (use_building) + buildings.push_back (Drul_array<Offset> (inter_l, inter_r)); + else + { + Offset inter_l = get_point_in_y_direction (left, perpendicular_slope (slope), thick / 2, d); + Offset inter_r = get_point_in_y_direction (right, perpendicular_slope (slope), thick / 2, d); + pango_matrix_transform_point (&trans, &inter_l[X_AXIS], &inter_l[Y_AXIS]); + pango_matrix_transform_point (&trans, &inter_r[X_AXIS], &inter_r[Y_AXIS]); + Real length = sqrt (((inter_l[X_AXIS] - inter_r[X_AXIS]) * (inter_l[X_AXIS] - inter_r[X_AXIS])) + ((inter_l[Y_AXIS] - inter_r[Y_AXIS]) * (inter_l[Y_AXIS] - inter_r[Y_AXIS]))); + + vsize passes = (vsize) ((length * 2) + 1); + vector<Offset> points; + + for (vsize i = 0; i < 1 + passes; i++) + { + Offset pt (linear_map (x0, x1, 0, passes, i), + linear_map (y0, y1, 0, passes, i)); + Offset inter = get_point_in_y_direction (pt, perpendicular_slope (slope), thick / 2, d); + pango_matrix_transform_point (&trans, &inter[X_AXIS], &inter[Y_AXIS]); + points.push_back (inter); + } + for (vsize i = 0; i < points.size () - 1; i++) + { + Box b; + b.add_point (points[i]); + b.add_point (points[i + 1]); + boxes.push_back (b); + } + } + } + while (flip (&d) != DOWN); + + if (thick > 0.0) + { + // beg line cap + create_path_cap (boxes, + buildings, + trans, + Offset (x0, y0), + thick / 2, + perpendicular_slope (slope), + Direction (sign (slope))); + + // end line cap + create_path_cap (boxes, + buildings, + trans, + Offset (x1, y1), + thick / 2, + perpendicular_slope (slope), + Direction (sign (-slope))); + } +} + +void +make_partial_ellipse_boxes (vector<Box> &boxes, vector<Drul_array<Offset> > &buildings, PangoMatrix trans, SCM expr) +{ + Real x_rad = robust_scm2double (scm_car (expr), 0.0); + expr = scm_cdr (expr); + Real y_rad = robust_scm2double (scm_car (expr), 0.0); + expr = scm_cdr (expr); + Real start = robust_scm2double (scm_car (expr), 0.0); + expr = scm_cdr (expr); + Real end = robust_scm2double (scm_car (expr), 0.0); + expr = scm_cdr (expr); + Real th = robust_scm2double (scm_car (expr), 0.0); + expr = scm_cdr (expr); + bool connect = to_boolean (scm_car (expr)); + expr = scm_cdr (expr); + bool fill = to_boolean (scm_car (expr)); + ////////////////////// + start = M_PI * start / 180; + end = M_PI * end / 180; + if (end == start) + end += (2 * M_PI); + complex<Real> sunit = polar (1.0, start); + complex<Real> eunit = polar (1.0, end); + Offset sp (real (sunit) * x_rad, imag (sunit) * y_rad); + Offset ep (real (eunit) * x_rad, imag (eunit) * y_rad); + ////////////////////// + Drul_array<vector<Offset> > points; + Direction d = DOWN; + int quantization = max (1, (int) (((x_rad * trans.xx) + (y_rad * trans.yy)) * M_PI / QUANTIZATION_UNIT)); + do + { + for (vsize i = 0; i < 1 + quantization; i++) + { + Real ang = linear_map (start, end, 0, quantization, i); + complex<Real> coord = polar (1.0, ang); + Offset pt (real (coord) * x_rad, + imag (coord) * y_rad); + Real slope = pt[Y_AXIS] / pt[X_AXIS]; + Offset inter = get_point_in_y_direction (pt, perpendicular_slope (slope), th / 2, d); + pango_matrix_transform_point (&trans, &inter[X_AXIS], &inter[Y_AXIS]); + points[d].push_back (inter); + } + } + while (flip (&d) != DOWN); + + for (vsize i = 0; i < points[DOWN].size () - 1; i++) + { + Box b; + do + { + b.add_point (points[d][i]); + b.add_point (points[d][i + 1]); + } + while (flip (&d) != DOWN); + boxes.push_back (b); + } + + if (connect || fill) + { + make_draw_line_boxes (boxes, buildings, trans, scm_list_5 (scm_from_double (th), + scm_from_double (sp[X_AXIS]), + scm_from_double (sp[Y_AXIS]), + scm_from_double (ep[X_AXIS]), + scm_from_double (ep[Y_AXIS])), + false); + } + + if (th > 0.0) + { + // beg line cap + complex<Real> coord = polar (1.0, start); + Offset pt (real (coord) * x_rad, + imag (coord) * y_rad); + Real slope = pt[Y_AXIS] / pt[X_AXIS]; + create_path_cap (boxes, + buildings, + trans, + pt, + th / 2, + perpendicular_slope (slope), + Direction (sign (slope))); + + // end line cap + coord = polar (1.0, start); + pt = Offset (real (coord) * x_rad, + imag (coord) * y_rad); + slope = pt[Y_AXIS] / pt[X_AXIS]; + create_path_cap (boxes, + buildings, + trans, + pt, + th / 2, + perpendicular_slope (slope), + Direction (sign (-slope))); + } +} + +void +make_round_filled_box_boxes (vector<Box> &boxes, PangoMatrix trans, SCM expr) +{ + Real left = robust_scm2double (scm_car (expr), 0.0); + expr = scm_cdr (expr); + Real right = robust_scm2double (scm_car (expr), 0.0); + expr = scm_cdr (expr); + Real bottom = robust_scm2double (scm_car (expr), 0.0); + expr = scm_cdr (expr); + Real top = robust_scm2double (scm_car (expr), 0.0); + expr = scm_cdr (expr); + Real th = robust_scm2double (scm_car (expr), 0.0); + ////////////////////// + vector<Offset> points; + Box b; + Offset p0 = Offset (-left - (th / 2), -bottom - (th / 2)); + Offset p1 = Offset (right + (th / 2), top + (th / 2)); + pango_matrix_transform_point (&trans, &p0[X_AXIS], &p0[Y_AXIS]); + pango_matrix_transform_point (&trans, &p1[X_AXIS], &p1[Y_AXIS]); + b.add_point (p0); + b.add_point (p1); + boxes.push_back (b); +} + +void +create_path_cap (vector<Box> &boxes, vector<Drul_array<Offset> > &buildings, PangoMatrix trans, Offset pt, Real rad, Real slope, Direction d) +{ + Real angle = atan (slope) * 180 / M_PI; + Real other = angle > 180 ? angle - 180 : angle + 180; + if (angle < other) + { + Real holder = other; + other = angle; + angle = holder; + } + other = (slope >= 0 && d == DOWN) || (slope < 0 && d == UP) + ? other + 360.0 + : other; + PangoMatrix new_trans (trans); + pango_matrix_translate (&new_trans, pt[X_AXIS], pt[Y_AXIS]); + make_partial_ellipse_boxes (boxes, buildings, new_trans, + scm_list_n (scm_from_double (rad), + scm_from_double (rad), + scm_from_double (angle), + scm_from_double (other), + scm_from_double (0.0), + SCM_BOOL_F, + SCM_BOOL_F, + SCM_UNDEFINED)); +} + +void +make_draw_bezier_boxes (vector<Box> &boxes, vector<Drul_array<Offset> > &buildings, PangoMatrix trans, SCM expr) +{ + Real th = robust_scm2double (scm_car (expr), 0.0); + expr = scm_cdr (expr); + Real x0 = robust_scm2double (scm_car (expr), 0.0); + expr = scm_cdr (expr); + Real y0 = robust_scm2double (scm_car (expr), 0.0); + expr = scm_cdr (expr); + Real x1 = robust_scm2double (scm_car (expr), 0.0); + expr = scm_cdr (expr); + Real y1 = robust_scm2double (scm_car (expr), 0.0); + expr = scm_cdr (expr); + Real x2 = robust_scm2double (scm_car (expr), 0.0); + expr = scm_cdr (expr); + Real y2 = robust_scm2double (scm_car (expr), 0.0); + expr = scm_cdr (expr); + Real x3 = robust_scm2double (scm_car (expr), 0.0); + expr = scm_cdr (expr); + Real y3 = robust_scm2double (scm_car (expr), 0.0); + ////////////////////// + Bezier curve; + curve.control_[0] = Offset (x0, y0); + curve.control_[1] = Offset (x1, y1); + curve.control_[2] = Offset (x2, y2); + curve.control_[3] = Offset (x3, y3); + Offset temp0 (x0, y0); + Offset temp1 (x1, y1); + Offset temp2 (x2, y2); + Offset temp3 (x3, y3); + pango_matrix_transform_point (&trans, &temp0[X_AXIS], &temp0[Y_AXIS]); + pango_matrix_transform_point (&trans, &temp1[X_AXIS], &temp1[Y_AXIS]); + pango_matrix_transform_point (&trans, &temp2[X_AXIS], &temp2[Y_AXIS]); + pango_matrix_transform_point (&trans, &temp3[X_AXIS], &temp3[Y_AXIS]); + ////////////////////// + Drul_array<vector<Offset> > points; + Direction d = DOWN; + int quantization = int (((temp1 - temp0).length () + + (temp2 - temp1).length () + + (temp3 - temp2).length ()) + / QUANTIZATION_UNIT); + do + { + Offset first = get_point_in_y_direction (curve.control_[0], perpendicular_slope (curve.slope_at_point (0.0)), th / 2, d); + pango_matrix_transform_point (&trans, &first[X_AXIS], &first[Y_AXIS]); + points[d].push_back (first); + for (vsize i = 1; i < quantization; i++) + { + Real pt = (i * 1.0) / quantization; + Offset inter = get_point_in_y_direction (curve.curve_point (pt), perpendicular_slope (curve.slope_at_point (pt)), th / 2, d); + pango_matrix_transform_point (&trans, &inter[X_AXIS], &inter[Y_AXIS]); + points[d].push_back (inter); + } + Offset last = get_point_in_y_direction (curve.control_[3], curve.slope_at_point (1.0), th / 2, d); + pango_matrix_transform_point (&trans, &last[X_AXIS], &last[Y_AXIS]); + points[d].push_back (last); + } + while (flip (&d) != DOWN); + + for (vsize i = 0; i < points[DOWN].size () - 1; i++) + { + Box b; + do + { + b.add_point (points[d][i]); + b.add_point (points[d][i + 1]); + } + while (flip (&d) != DOWN); + boxes.push_back (b); + } + + // beg line cap + if (th >= 0) + { + Real slope = curve.slope_at_point (0.0); + d = Direction (sign (slope == 0.0 || abs (slope) == infinity_f + ? curve.slope_at_point (0.0001) + : slope)); + + create_path_cap (boxes, + buildings, + trans, + curve.control_[0], + th / 2, + perpendicular_slope (curve.slope_at_point (0.0)), + d); + + // end line cap + slope = curve.slope_at_point (1.0); + d = Direction (sign (slope == 0.0 || abs (slope) == infinity_f + ? curve.slope_at_point (0.9999) + : slope)); + + create_path_cap (boxes, + buildings, + trans, + curve.control_[3], + th / 2, + perpendicular_slope (curve.slope_at_point (1.0)), + d); + } +} + +/* + converts a path into lists of 4 (line) or 8 (curve) absolute coordinates + for example: + '(moveto 1 2 lineto 3 4 rlineto -1 -1 curveto 3 3 5 5 6 6 rcurveto -1 -1 -1 -1 -1 -1 closepath) + becomes + '((1 2 3 4) + (3 4 2 3) + (2 3 3 3 5 5 6 6) + (6 6 5 5 4 4 3 3) + (3 3 1 2)) +*/ + +SCM +all_commands_to_absolute_and_group (SCM expr) +{ + SCM out = SCM_EOL; + Offset start (0, 0); + Offset current (0, 0); + bool first = true; + while (scm_is_pair (expr)) + { + if (scm_car (expr) == ly_symbol2scm ("moveto") + || (scm_car (expr) == ly_symbol2scm ("rmoveto") && first)) + { + Real x = robust_scm2double (scm_cadr (expr), 0.0); + Real y = robust_scm2double (scm_caddr (expr), 0.0); + start = Offset (x, y); + current = start; + expr = scm_cdddr (expr); + } + if (scm_car (expr) == ly_symbol2scm ("rmoveto")) + { + Real x = robust_scm2double (scm_cadr (expr), 0.0); + Real y = robust_scm2double (scm_caddr (expr), 0.0); + start = (Offset (x, y) + current); + current = start; + expr = scm_cdddr (expr); + } + else if (scm_car (expr) == ly_symbol2scm ("lineto")) + { + Real x = robust_scm2double (scm_cadr (expr), 0.0); + Real y = robust_scm2double (scm_caddr (expr), 0.0); + out = scm_cons (scm_list_4 (scm_from_double (current[X_AXIS]), + scm_from_double (current[Y_AXIS]), + scm_from_double (x), + scm_from_double (y)), + out); + current = Offset (x, y); + expr = scm_cdddr (expr); + } + else if (scm_car (expr) == ly_symbol2scm ("rlineto")) + { + Real x = robust_scm2double (scm_cadr (expr), 0.0); + Real y = robust_scm2double (scm_caddr (expr), 0.0); + out = scm_cons (scm_list_4 (scm_from_double (current[X_AXIS]), + scm_from_double (current[Y_AXIS]), + scm_from_double (x + current[X_AXIS]), + scm_from_double (y + current[Y_AXIS])), + out); + current = (Offset (x, y) + current); + expr = scm_cdddr (expr); + } + else if (scm_car (expr) == ly_symbol2scm ("curveto")) + { + Real x1 = robust_scm2double (scm_cadr (expr), 0.0); + expr = scm_cddr (expr); + Real y1 = robust_scm2double (scm_car (expr), 0.0); + expr = scm_cdr (expr); + Real x2 = robust_scm2double (scm_car (expr), 0.0); + expr = scm_cdr (expr); + Real y2 = robust_scm2double (scm_car (expr), 0.0); + expr = scm_cdr (expr); + Real x3 = robust_scm2double (scm_car (expr), 0.0); + expr = scm_cdr (expr); + Real y3 = robust_scm2double (scm_car (expr), 0.0); + expr = scm_cdr (expr); + out = scm_cons (scm_list_n (scm_from_double (current[X_AXIS]), + scm_from_double (current[Y_AXIS]), + scm_from_double (x1), + scm_from_double (y1), + scm_from_double (x2), + scm_from_double (y2), + scm_from_double (x3), + scm_from_double (y3), + SCM_UNDEFINED), + out); + current = Offset (x3, y3); + } + else if (scm_car (expr) == ly_symbol2scm ("rcurveto")) + { + Real x1 = robust_scm2double (scm_cadr (expr), 0.0); + expr = scm_cddr (expr); + Real y1 = robust_scm2double (scm_car (expr), 0.0); + expr = scm_cdr (expr); + Real x2 = robust_scm2double (scm_car (expr), 0.0); + expr = scm_cdr (expr); + Real y2 = robust_scm2double (scm_car (expr), 0.0); + expr = scm_cdr (expr); + Real x3 = robust_scm2double (scm_car (expr), 0.0); + expr = scm_cdr (expr); + Real y3 = robust_scm2double (scm_car (expr), 0.0); + expr = scm_cdr (expr); + out = scm_cons (scm_list_n (scm_from_double (current[X_AXIS]), + scm_from_double (current[Y_AXIS]), + scm_from_double (x1 + current[X_AXIS]), + scm_from_double (y1 + current[Y_AXIS]), + scm_from_double (x2 + current[X_AXIS]), + scm_from_double (y2 + current[Y_AXIS]), + scm_from_double (x3 + current[X_AXIS]), + scm_from_double (y3 + current[Y_AXIS]), + SCM_UNDEFINED), + out); + current = (Offset (x3, y3) + current); + } + else if (scm_car (expr) == ly_symbol2scm ("closepath")) + { + if ((current[X_AXIS] != start[X_AXIS]) || (current[Y_AXIS] != start[Y_AXIS])) + { + out = scm_cons (scm_list_4 (scm_from_double (current[X_AXIS]), + scm_from_double (current[Y_AXIS]), + scm_from_double (start[X_AXIS]), + scm_from_double (start[Y_AXIS])), + out); + current = start; + } + expr = scm_cdr (expr); + } + else + { + warning ("Malformed path for path stencil."); + return out; + } + first = false; + } + return scm_reverse_x (out, SCM_EOL); +} + +void +internal_make_path_boxes (vector<Box> &boxes, vector<Drul_array<Offset> > &buildings, PangoMatrix trans, SCM expr, bool use_building) +{ + SCM blot = scm_car (expr); + expr = scm_cdr (expr); + SCM path = all_commands_to_absolute_and_group (expr); + // note that expr has more stuff that we don't need after this - simply ignore it + ////////////////////// + for (SCM s = path; scm_is_pair (s); s = scm_cdr (s)) + { + scm_to_int (scm_length (scm_car (s))) == 4 + ? make_draw_line_boxes (boxes, buildings, trans, scm_cons (blot, scm_car (s)), use_building) + : make_draw_bezier_boxes (boxes, buildings, trans, scm_cons (blot, scm_car (s))); + } +} + +void +make_path_boxes (vector<Box> &boxes, vector<Drul_array<Offset> > &buildings, PangoMatrix trans, SCM expr) +{ + return internal_make_path_boxes (boxes, buildings, trans, scm_cons (scm_car (expr), get_path_list (scm_cdr (expr))), false); +} + +void +make_polygon_boxes (vector<Box> &boxes, vector<Drul_array<Offset> > &buildings, PangoMatrix trans, SCM expr) +{ + SCM coords = get_number_list (scm_car (expr)); + expr = scm_cdr (expr); + SCM blot_diameter = scm_car (expr); + ////////////////////// + bool first = true; + SCM l = SCM_EOL; + for (SCM s = coords; scm_is_pair (s); s = scm_cddr (s)) + { + l = scm_cons (first ? ly_symbol2scm ("moveto") : ly_symbol2scm ("lineto"), l); + l = scm_cons (scm_car (s), l); + l = scm_cons (scm_cadr (s), l); + first = false; + } + l = scm_cons (ly_symbol2scm ("closepath"), l); + internal_make_path_boxes (boxes, buildings, trans, scm_cons (blot_diameter, scm_reverse_x (l, SCM_EOL)), true); +} + +void +make_named_glyph_boxes (vector<Box> &boxes, vector<Drul_array<Offset> > &buildings, PangoMatrix trans, SCM expr) +{ + SCM fm_scm = scm_car (expr); + Font_metric *fm = unsmob_metrics (fm_scm); + expr = scm_cdr (expr); + SCM glyph = scm_car (expr); + string glyph_s = ly_scm2string (glyph); + + ////////////////////// + Open_type_font *open_fm + = dynamic_cast<Open_type_font *> + (dynamic_cast<Modified_font_metric *>(fm)->original_font ()); + SCM_ASSERT_TYPE (open_fm, fm_scm, SCM_ARG1, __FUNCTION__, "OpenType font"); + + size_t gidx = open_fm->name_to_index (glyph_s); + // Bbox is the best approximation of the width based on how it would be + // calculated in open-type-font.cc if it were based on real extents + Box bbox = open_fm->get_unscaled_indexed_char_dimensions (gidx); + bbox.scale (dynamic_cast<Modified_font_metric *>(fm)->get_magnification () * open_fm->design_size () / open_fm->get_units_per_EM ()); + // Real bbox is the real bbox of the object + Box real_bbox = open_fm->get_glyph_outline_bbox (gidx); + + Real scale = bbox[X_AXIS].length () / real_bbox[X_AXIS].length (); + + pango_matrix_scale (&trans, scale, scale); + + SCM outline = open_fm->get_glyph_outline (gidx); + ////////////////////// + for (SCM s = outline; + scm_is_pair (s); + s = scm_cdr (s)) + { + scm_to_int (scm_length (scm_car (s))) == 4 + ? make_draw_line_boxes (boxes, buildings, trans, scm_cons (scm_from_double (0), scm_car (s)), false) + : make_draw_bezier_boxes (boxes, buildings, trans, scm_cons (scm_from_double (0), scm_car (s))); + } +} + +void +make_glyph_string_boxes (vector<Box> &boxes, vector<Drul_array<Offset> > &buildings, PangoMatrix trans, SCM expr) +{ + SCM fm_scm = scm_car (expr); + Font_metric *fm = unsmob_metrics (fm_scm); + expr = scm_cdr (expr); + expr = scm_cdr (expr); // font-name + expr = scm_cdr (expr); // size + expr = scm_cdr (expr); // cid? + SCM whxy = scm_cadar (expr); + vector<Real> widths; + vector<Interval> heights; + vector<Real> xos; + vector<Real> yos; + vector<string> char_ids; + ////////////////////// + Pango_font *pango_fm = dynamic_cast<Pango_font *> (fm); + SCM_ASSERT_TYPE (pango_fm, fm_scm, SCM_ARG1, __FUNCTION__, "Pango font"); + + for (SCM s = whxy; scm_is_pair (s); s = scm_cdr (s)) + { + SCM now = scm_car (s); + widths.push_back (robust_scm2double (scm_car (now), 0.0)); + now = scm_cdr (now); + heights.push_back (robust_scm2interval (scm_car (now), Interval (0, 0))); + now = scm_cdr (now); + xos.push_back (robust_scm2double (scm_car (now), 0.0)); + now = scm_cdr (now); + yos.push_back (robust_scm2double (scm_car (now), 0.0)); + now = scm_cdr (now); + char_ids.push_back (robust_scm2string (scm_car (now), "")); + } + Real cumulative_x = 0.0; + for (vsize i = 0; i < widths.size (); i++) + { + PangoMatrix transcopy (trans); + Offset pt0 (cumulative_x + xos[i], heights[i][DOWN] + yos[i]); + Offset pt1 (cumulative_x + widths[i] + xos[i], heights[i][UP] + yos[i]); + cumulative_x += widths[i]; + + Box kerned_bbox; + kerned_bbox.add_point (pt0); + kerned_bbox.add_point (pt1); + size_t gidx = pango_fm->name_to_index (char_ids[i]); + Box real_bbox = pango_fm->get_scaled_indexed_char_dimensions (gidx); + Box bbox = pango_fm->get_unscaled_indexed_char_dimensions (gidx); + SCM outline = pango_fm->get_glyph_outline (gidx); + + // scales may have rounding error but should be close + Real xlen = real_bbox[X_AXIS].length () / bbox[X_AXIS].length (); + Real ylen = real_bbox[Y_AXIS].length () / bbox[Y_AXIS].length (); + + /* + TODO: + + The value will be nan for whitespace, in which case we just want + filler, so the kerned bbox is ok. + + However, if the value is inf, this likely means that LilyPond is + using a font that is currently difficult to get the measurements + from the Pango_font. This should eventually be fixed. The solution + for now is just to use the bounding box. + */ + if (isnan (xlen) || isnan (ylen) || isinf (xlen) || isinf (ylen)) + outline = box_to_scheme_lines (kerned_bbox); + else + { + assert (abs (xlen - ylen) < 10e-3); + + Real scale_factor = max (xlen, ylen); + // the three operations below move the stencil from its original coordinates to current coordinates + pango_matrix_translate (&transcopy, kerned_bbox[X_AXIS][LEFT], kerned_bbox[Y_AXIS][DOWN] - real_bbox[Y_AXIS][DOWN]); + pango_matrix_translate (&transcopy, real_bbox[X_AXIS][LEFT], real_bbox[Y_AXIS][DOWN]); + pango_matrix_scale (&transcopy, scale_factor, scale_factor); + pango_matrix_translate (&transcopy, -bbox[X_AXIS][LEFT], -bbox[Y_AXIS][DOWN]); + } + ////////////////////// + for (SCM s = outline; + scm_is_pair (s); + s = scm_cdr (s)) + { + scm_to_int (scm_length (scm_car (s))) == 4 + ? make_draw_line_boxes (boxes, buildings, transcopy, scm_cons (scm_from_double (0), scm_car (s)), false) + : make_draw_bezier_boxes (boxes, buildings, transcopy, scm_cons (scm_from_double (0), scm_car (s))); + } + } +} + +/* + receives a stencil expression and a transform matrix + depending on the stencil name, dispatches it to the appropriate function +*/ + +void +stencil_dispatcher (vector<Box> &boxes, vector<Drul_array<Offset> > &buildings, PangoMatrix trans, SCM expr) +{ + if (not scm_is_pair (expr)) + return; + if (scm_car (expr) == ly_symbol2scm ("draw-line")) + make_draw_line_boxes (boxes, buildings, trans, scm_cdr (expr), true); + else if (scm_car (expr) == ly_symbol2scm ("dashed-line")) + { + expr = scm_cdr (expr); + SCM th = scm_car (expr); + expr = scm_cdr (expr); + expr = scm_cdr (expr); // on + expr = scm_cdr (expr); // off + SCM x1 = scm_car (expr); + expr = scm_cdr (expr); + SCM x2 = scm_car (expr); + make_draw_line_boxes (boxes, buildings, trans, scm_list_5 (th, scm_from_double (0.0), scm_from_double (0.0), x1, x2), true); + } + else if (scm_car (expr) == ly_symbol2scm ("circle")) + { + expr = scm_cdr (expr); + SCM rad = scm_car (expr); + expr = scm_cdr (expr); + SCM th = scm_car (expr); + make_partial_ellipse_boxes (boxes, buildings, trans, + scm_list_n (rad, + rad, + scm_from_double (0.0), + scm_from_double (360.0), + th, + SCM_BOOL_F, + SCM_BOOL_T, + SCM_UNDEFINED)); + } + else if (scm_car (expr) == ly_symbol2scm ("ellipse")) + { + expr = scm_cdr (expr); + SCM x_rad = scm_car (expr); + expr = scm_cdr (expr); + SCM y_rad = scm_car (expr); + expr = scm_cdr (expr); + SCM th = scm_car (expr); + make_partial_ellipse_boxes (boxes, buildings, trans, + scm_list_n (x_rad, + y_rad, + scm_from_double (0.0), + scm_from_double (360.0), + th, + SCM_BOOL_F, + SCM_BOOL_T, + SCM_UNDEFINED)); + } + else if (scm_car (expr) == ly_symbol2scm ("partial-ellipse")) + make_partial_ellipse_boxes (boxes, buildings, trans, scm_cdr (expr)); + else if (scm_car (expr) == ly_symbol2scm ("round-filled-box")) + make_round_filled_box_boxes (boxes, trans, scm_cdr (expr)); + else if (scm_car (expr) == ly_symbol2scm ("named-glyph")) + make_named_glyph_boxes (boxes, buildings, trans, scm_cdr (expr)); + else if (scm_car (expr) == ly_symbol2scm ("polygon")) + make_polygon_boxes (boxes, buildings, trans, scm_cdr (expr)); + else if (scm_car (expr) == ly_symbol2scm ("path")) + make_path_boxes (boxes, buildings, trans, scm_cdr (expr)); + else if (scm_car (expr) == ly_symbol2scm ("glyph-string")) + make_glyph_string_boxes (boxes, buildings, trans, scm_cdr (expr)); + else + { +#if 0 + warning ("Stencil expression not supported by the veritcal skylines."); +#endif + /* + We don't issue a warning here, as we assume that stencil-expression.cc + is doing stencil-checking correctly. + */ + } +} + +/* + traverses a stencil expression, returning a vector of Transform_matrix_and_expression + the struct Transform_matrix_and_expression contains two members, + a Transform_matrix that indicates where to move a stencil and the stencil expression + to show how to construct the stencil +*/ +vector<Transform_matrix_and_expression> +stencil_traverser (PangoMatrix trans, SCM expr) +{ + if (scm_is_null (expr)) + return vector<Transform_matrix_and_expression> (); + else if (expr == ly_string2scm ("")) + return vector<Transform_matrix_and_expression> (); + else if (scm_car (expr) == ly_symbol2scm ("combine-stencil")) + { + vector<Transform_matrix_and_expression> out; + for (SCM s = scm_cdr (expr); scm_is_pair (s); s = scm_cdr (s)) + { + vector<Transform_matrix_and_expression> res = stencil_traverser (trans, scm_car (s)); + out.insert (out.end (), res.begin (), res.end ()); + } + return out; + } + else if (scm_car (expr) == ly_symbol2scm ("footnote")) + return vector<Transform_matrix_and_expression> (); + else if (scm_car (expr) == ly_symbol2scm ("translate-stencil")) + { + Real x = robust_scm2double (scm_caadr (expr), 0.0); + Real y = robust_scm2double (scm_cdadr (expr), 0.0); + pango_matrix_translate (&trans, x, y); + return stencil_traverser (trans, scm_caddr (expr)); + } + else if (scm_car (expr) == ly_symbol2scm ("scale-stencil")) + { + Real x = robust_scm2double (scm_caadr (expr), 0.0); + Real y = robust_scm2double (scm_cadadr (expr), 0.0); + pango_matrix_scale (&trans, x, y); + return stencil_traverser (trans, scm_caddr (expr)); + } + else if (scm_car (expr) == ly_symbol2scm ("rotate-stencil")) + { + Real ang = robust_scm2double (scm_caadr (expr), 0.0); + Real x = robust_scm2double (scm_car (scm_cadadr (expr)), 0.0); + Real y = robust_scm2double (scm_cdr (scm_cadadr (expr)), 0.0); + pango_matrix_translate (&trans, x, y); + pango_matrix_rotate (&trans, -ang); + pango_matrix_translate (&trans, -x, -y); + return stencil_traverser (trans, scm_caddr (expr)); + } + else if (scm_car (expr) == ly_symbol2scm ("delay-stencil-evaluation")) + return stencil_traverser (trans, scm_force (scm_cadr (expr))); + else if (scm_car (expr) == ly_symbol2scm ("grob-cause")) + return stencil_traverser (trans, scm_caddr (expr)); + else if (scm_car (expr) == ly_symbol2scm ("color")) + return stencil_traverser (trans, scm_caddr (expr)); + else if (scm_car (expr) == ly_symbol2scm ("id")) + return stencil_traverser (trans, scm_caddr (expr)); + else + { + vector<Transform_matrix_and_expression> out; + out.push_back (Transform_matrix_and_expression (trans, expr)); + return out; + } + warning ("Stencil expression not supported by the veritcal skylines."); + return vector<Transform_matrix_and_expression> (); +} + +SCM +Grob::internal_simple_skylines_from_stencil (SCM smob, Axis a) +{ + Grob *me = unsmob_grob (smob); + + if (to_boolean (me->get_property ("cross-staff"))) + return Skyline_pair ().smobbed_copy (); + + extract_grob_set (me, "elements", elts); + if (elts.size ()) + return internal_skylines_from_element_stencils (smob, a); + + Stencil *s = unsmob_stencil (me->get_property ("stencil")); + if (!s) + return Skyline_pair ().smobbed_copy (); + + vector<Box> boxes; + boxes.push_back (Box (s->extent (X_AXIS), s->extent (Y_AXIS))); + return Skyline_pair (boxes, a).smobbed_copy (); +} + +MAKE_SCHEME_CALLBACK (Grob, simple_vertical_skylines_from_stencil, 1); +SCM +Grob::simple_vertical_skylines_from_stencil (SCM smob) +{ + return internal_simple_skylines_from_stencil (smob, X_AXIS); +} + +MAKE_SCHEME_CALLBACK (Grob, simple_horizontal_skylines_from_stencil, 1); +SCM +Grob::simple_horizontal_skylines_from_stencil (SCM smob) +{ + return internal_simple_skylines_from_stencil (smob, Y_AXIS); +} + +SCM +Stencil::skylines_from_stencil (SCM sten, Real pad, Axis a) +{ + Stencil *s = unsmob_stencil (sten); + if (!s) + return Skyline_pair ().smobbed_copy (); + + vector<Transform_matrix_and_expression> data + = stencil_traverser (make_transform_matrix (1.0, 0.0, 0.0, 1.0, 0.0, 0.0), + s->expr ()); + vector<Box> boxes; + vector<Drul_array<Offset> > buildings; + for (vsize i = 0; i < data.size (); i++) + stencil_dispatcher (boxes, buildings, data[i].tm_, data[i].expr_); + + // we use the bounding box if there are no boxes + if (!boxes.size () && !buildings.size ()) + boxes.push_back (Box (s->extent (X_AXIS), s->extent (Y_AXIS))); + + Skyline_pair out (boxes, a); + out.merge (Skyline_pair (buildings, a)); + + for (DOWN_and_UP (d)) + out[d] = out[d].padded (pad); + + out.deholify (); + return out.smobbed_copy (); +} + +MAKE_SCHEME_CALLBACK (Grob, vertical_skylines_from_stencil, 1); +SCM +Grob::vertical_skylines_from_stencil (SCM smob) +{ + Grob *me = unsmob_grob (smob); + + Real pad = robust_scm2double (me->get_property ("skyline-horizontal-padding"), 0.0); + SCM out = Stencil::skylines_from_stencil (me->get_property ("stencil"), pad, X_AXIS); + + return out; +} + +MAKE_SCHEME_CALLBACK (Grob, horizontal_skylines_from_stencil, 1); +SCM +Grob::horizontal_skylines_from_stencil (SCM smob) +{ + Grob *me = unsmob_grob (smob); + + Real pad = robust_scm2double (me->get_property ("skyline-vertical-padding"), 0.0); + SCM out = Stencil::skylines_from_stencil (me->get_property ("stencil"), pad, Y_AXIS); + + return out; +} + +SCM +Grob::internal_skylines_from_element_stencils (SCM smob, Axis a) +{ + Grob *me = unsmob_grob (smob); + + extract_grob_set (me, "elements", elts); + vector<Real> x_pos; + vector<Real> y_pos; + Grob *x_common = common_refpoint_of_array (elts, me, X_AXIS); + Grob *y_common = common_refpoint_of_array (elts, me, Y_AXIS); + for (vsize i = 0; i < elts.size (); i++) + { + x_pos.push_back (elts[i]->relative_coordinate (x_common, X_AXIS)); + y_pos.push_back (elts[i]->relative_coordinate (y_common, Y_AXIS)); + } + Real my_x = me->relative_coordinate (x_common, X_AXIS); + Real my_y = me->relative_coordinate (y_common, Y_AXIS); + Skyline_pair res; + for (vsize i = 0; i < elts.size (); i++) + { + Skyline_pair *skyp = Skyline_pair::unsmob (elts[i]->get_property (a == X_AXIS ? "vertical-skylines" : "horizontal-skylines")); + if (skyp) + { + /* + Here, copying is essential. Otherwise, the skyline pair will + get doubly shifted! + */ + /* + It took Mike about 6 months of his life to add the `else' clause + below. For horizontal skylines, the raise and shift calls need + to be reversed. This is what was causing the problems in the + shifting with all of the tests. RIP 6 months! + */ + Skyline_pair copy = Skyline_pair (*skyp); + if (a == X_AXIS) + { + copy.shift (x_pos[i] - my_x); + copy.raise (y_pos[i] - my_y); + } + else + { + copy.raise (x_pos[i] - my_x); + copy.shift (y_pos[i] - my_y); + } + res.merge (copy); + } + } + return res.smobbed_copy (); +} + +MAKE_SCHEME_CALLBACK (Grob, vertical_skylines_from_element_stencils, 1); +SCM +Grob::vertical_skylines_from_element_stencils (SCM smob) +{ + return internal_skylines_from_element_stencils (smob, X_AXIS); +} + +MAKE_SCHEME_CALLBACK (Grob, horizontal_skylines_from_element_stencils, 1); +SCM +Grob::horizontal_skylines_from_element_stencils (SCM smob) +{ + return internal_skylines_from_element_stencils (smob, Y_AXIS); +} diff --git a/lily/stencil-scheme.cc b/lily/stencil-scheme.cc index 7e346ca7f8..7791f02d5a 100644 --- a/lily/stencil-scheme.cc +++ b/lily/stencil-scheme.cc @@ -34,6 +34,7 @@ LY_DEFINE (ly_stencil_translate_axis, "ly:stencil-translate-axis", Stencil *s = unsmob_stencil (stil); LY_ASSERT_SMOB (Stencil, stil, 1); LY_ASSERT_TYPE (scm_is_number, amount, 2); + LY_ASSERT_TYPE (is_axis, axis, 3); Real real_amount = scm_to_double (amount); diff --git a/lily/system.cc b/lily/system.cc index be3c9ec192..e3da76687d 100644 --- a/lily/system.cc +++ b/lily/system.cc @@ -36,6 +36,7 @@ #include "pointer-group-interface.hh" #include "skyline-pair.hh" #include "staff-symbol-referencer.hh" +#include "system-start-delimiter.hh" #include "text-interface.hh" #include "warn.hh" #include "unpure-pure-container.hh" @@ -404,6 +405,37 @@ System::footnotes_after_line_breaking (SCM smob) return grobs_scm; } +MAKE_SCHEME_CALLBACK (System, vertical_skyline_elements, 1); +SCM +System::vertical_skyline_elements (SCM smob) +{ + Grob *me_grob = unsmob_grob (smob); + vector<Grob *> vertical_skyline_grobs; + extract_grob_set (me_grob, "elements", my_elts); + for (vsize i = 0; i < my_elts.size (); i++) + if (System_start_delimiter::has_interface (my_elts[i])) + vertical_skyline_grobs.push_back (my_elts[i]); + + System *me = dynamic_cast<System *> (me_grob); + Grob *align = unsmob_grob (me->get_object ("vertical-alignment")); + if (!align) + { + SCM grobs_scm = Grob_array::make_array (); + unsmob_grob_array (grobs_scm)->set_array (vertical_skyline_grobs); + return grobs_scm; + } + + extract_grob_set (align, "elements", elts); + + for (vsize i = 0; i < elts.size (); i++) + if (Hara_kiri_group_spanner::has_interface (elts[i])) + vertical_skyline_grobs.push_back (elts[i]); + + SCM grobs_scm = Grob_array::make_array (); + unsmob_grob_array (grobs_scm)->set_array (vertical_skyline_grobs); + return grobs_scm; +} + void System::break_into_pieces (vector<Column_x_positions> const &breaking) { @@ -622,7 +654,7 @@ System::get_paper_system () pl->set_property ("last-in-score", SCM_BOOL_T); Interval staff_refpoints; - if (Grob *align = get_vertical_alignment ()) + if (Grob *align = unsmob_grob (get_object ("vertical-alignment"))) { extract_grob_set (align, "elements", staves); for (vsize i = 0; i < staves.size (); i++) @@ -723,22 +755,27 @@ get_root_system (Grob *me) return dynamic_cast<System *> (system_grob); } -Grob * -System::get_vertical_alignment () +MAKE_SCHEME_CALLBACK (System, get_vertical_alignment, 1); +SCM +System::get_vertical_alignment (SCM smob) { - extract_grob_set (this, "elements", elts); + Grob *me = unsmob_grob (smob); + extract_grob_set (me, "elements", elts); Grob *ret = 0; for (vsize i = 0; i < elts.size (); i++) if (Align_interface::has_interface (elts[i])) { if (ret) - programming_error ("found multiple vertical alignments in this system"); + me->programming_error ("found multiple vertical alignments in this system"); ret = elts[i]; } if (!ret) - programming_error ("didn't find a vertical alignment in this system"); - return ret; + { + me->programming_error ("didn't find a vertical alignment in this system"); + return SCM_EOL; + } + return ret->self_scm (); } // Finds the furthest staff in the given direction whose x-extent @@ -746,7 +783,7 @@ System::get_vertical_alignment () Grob * System::get_extremal_staff (Direction dir, Interval const &iv) { - Grob *align = get_vertical_alignment (); + Grob *align = unsmob_grob (get_object ("vertical-alignment")); if (!align) return 0; @@ -770,7 +807,7 @@ System::get_extremal_staff (Direction dir, Interval const &iv) Grob * System::get_neighboring_staff (Direction dir, Grob *vertical_axis_group, Interval_t<int> bounds) { - Grob *align = get_vertical_alignment (); + Grob *align = unsmob_grob (get_object ("vertical-alignment")); if (!align) return 0; @@ -800,7 +837,7 @@ Interval System::pure_refpoint_extent (vsize start, vsize end) { Interval ret; - Grob *alignment = get_vertical_alignment (); + Grob *alignment = unsmob_grob (get_object ("vertical-alignment")); if (!alignment) return Interval (); @@ -827,7 +864,7 @@ System::pure_refpoint_extent (vsize start, vsize end) Interval System::part_of_line_pure_height (vsize start, vsize end, bool begin) { - Grob *alignment = get_vertical_alignment (); + Grob *alignment = unsmob_grob (get_object ("vertical-alignment")); if (!alignment) return Interval (); @@ -960,7 +997,7 @@ static SCM get_maybe_spaceable_staves (SCM smob, int filter) { System *me = dynamic_cast<System *> (unsmob_grob (smob)); - Grob *align = me->get_vertical_alignment (); + Grob *align = unsmob_grob (me->get_object ("vertical_alignment")); SCM ret = SCM_EOL; if (align) @@ -1022,5 +1059,5 @@ ADD_INTERFACE (System, "in-note-stencil " "labels " "pure-Y-extent " - "skyline-horizontal-padding " + "vertical-alignment " ); diff --git a/lily/text-interface.cc b/lily/text-interface.cc index cd906c2e8e..862e7af0b5 100644 --- a/lily/text-interface.cc +++ b/lily/text-interface.cc @@ -19,7 +19,9 @@ */ #include "text-interface.hh" +#include "skyline-pair.hh" +#include "lookup.hh" #include "config.hh" #include "font-interface.hh" #include "grob.hh" diff --git a/lily/tie-formatting-problem.cc b/lily/tie-formatting-problem.cc index f514b39095..304e4b3b2a 100644 --- a/lily/tie-formatting-problem.cc +++ b/lily/tie-formatting-problem.cc @@ -243,8 +243,7 @@ Tie_formatting_problem::set_column_chord_outline (vector<Item *> bounds, boxes.push_back (Box (x, y)); } - /* todo: the horizon_padding is somewhat arbitrary */ - chord_outlines_[key] = Skyline (boxes, details_.skyline_padding_, Y_AXIS, -dir); + chord_outlines_[key] = Skyline (boxes, Y_AXIS, -dir).padded (details_.skyline_padding_); if (bounds[0]->break_status_dir ()) { Interval iv (Axis_group_interface::staff_extent (bounds[0], x_refpoint_, X_AXIS, y_refpoint_, Y_AXIS)); diff --git a/lily/tuplet-engraver.cc b/lily/tuplet-engraver.cc index 1b75bf923c..4348044fbe 100644 --- a/lily/tuplet-engraver.cc +++ b/lily/tuplet-engraver.cc @@ -217,7 +217,8 @@ Tuplet_engraver::acknowledge_script (Grob_info inf) if (tuplets_[j].bracket_) { Item *i = dynamic_cast<Item *> (inf.grob ()); - Tuplet_bracket::add_script (tuplets_[j].bracket_, i); + if (!i->internal_has_interface (ly_symbol2scm ("dynamic-interface"))) + Tuplet_bracket::add_script (tuplets_[j].bracket_, i); } } diff --git a/scm/define-grob-properties.scm b/scm/define-grob-properties.scm index 6502dd9d72..25ad864833 100644 --- a/scm/define-grob-properties.scm +++ b/scm/define-grob-properties.scm @@ -660,6 +660,24 @@ is raised so that it is not so close to its neighbor.") (outside-staff-padding ,number? "The padding to place between this grob and the staff when spacing according to @code{outside-staff-priority}.") + (outside-staff-placement-directive ,symbol? "One of four directives +telling how outside staff objects should be placed. +@itemize @bullet +@item +@code{left-to-right-greedy} -- Place each successive grob from left to +right. +@item +@code{left-to-right-polite} -- Place a grob from left to right only if +it does not potentially overlap with another grob that has been placed +on a pass through a grob array. If there is overlap, do another pass to +determine placement. +@item +@code{right-to-left-greedy} -- Same as @code{left-to-right-greedy}, but +from right to left. +@item +@code{right-to-left-polite} -- Same as @code{left-to-right-polite}, but +from right to left. +@end itemize") (outside-staff-priority ,number? "If set, the grob is positioned outside the staff in such a way as to avoid all collisions. In case of a potential collision, the grob with the smaller @@ -943,7 +961,6 @@ positioning?") (vertical-skylines ,ly:skyline-pair? "Two skylines, one above and one below this grob.") - ;; ;; w ;; @@ -1108,8 +1125,6 @@ relevant for finding the @code{pure-Y-extent}.") (side-support-elements ,ly:grob-array? "The side support, an array of grobs.") - (skyline-quantizing ,index? "The number of boxes to break a -slur into when calculating its skyline.") (slur ,ly:grob? "A pointer to a @code{Slur} object.") (spacing ,ly:grob? "The spacing spanner governing this section.") (spacing-wishes ,ly:grob-array? "An array of note spacing or staff spacing @@ -1134,6 +1149,11 @@ results, use @code{LEFT} and @code{RIGHT}.") (tuplet-number ,ly:grob? "The number for a bracket.") (tuplet-start ,boolean? "Is stem at the start of a tuplet?") (tuplets ,ly:grob-array? "An array of smaller tuplet brackets.") + + (vertical-alignment ,ly:grob? "The VerticalAlignment in a System.") + (vertical-skyline-elements ,ly:grob-array? "An array of grobs +used to create vertical skylines.") + (X-colliding-grobs ,ly:grob-array? "Grobs that can collide with a self-aligned grob on the X-axis.") (Y-colliding-grobs ,ly:grob-array? "Grobs that can collide diff --git a/scm/define-grobs.scm b/scm/define-grobs.scm index 76f578ab4a..c18116db87 100644 --- a/scm/define-grobs.scm +++ b/scm/define-grobs.scm @@ -30,8 +30,10 @@ . ( (alteration . ,accidental-interface::calc-alteration) (avoid-slur . inside) + (glyph-name . ,accidental-interface::glyph-name) (glyph-name-alist . ,standard-alteration-glyph-name-alist) (stencil . ,ly:accidental-interface::print) + (vertical-skylines . ,ly:grob::vertical-skylines-from-stencil) (X-extent . ,ly:accidental-interface::width) (Y-extent . ,ly:accidental-interface::height) (meta . ((class . Item) @@ -396,6 +398,7 @@ (quantized-positions . ,ly:beam::set-stem-lengths) (shorten . ,ly:beam::calc-stem-shorten) + (vertical-skylines . ,ly:grob::vertical-skylines-from-stencil) (stencil . ,ly:beam::print) (meta . ((class . Spanner) @@ -533,6 +536,7 @@ (next-note . (extra-space . 1.0)) (right-edge . (extra-space . 0.5)))) (stencil . ,ly:clef::print) + (vertical-skylines . ,ly:grob::vertical-skylines-from-stencil) (Y-offset . ,ly:staff-symbol-referencer::callback) (meta . ((class . Item) (object-callbacks . ((pure-Y-common . ,ly:axis-group-interface::calc-pure-y-common) @@ -751,6 +755,8 @@ (side-axis . ,Y) (slur-padding . 0.3) (staff-padding . 0.1) + (vertical-skylines . ,ly:grob::vertical-skylines-from-element-stencils) + (use-skylines . #t) (X-extent . ,ly:axis-group-interface::width) (Y-extent . ,ly:axis-group-interface::height) (Y-offset . ,ly:side-position-interface::y-aligned-side) @@ -774,12 +780,12 @@ (font-encoding . fetaText) (font-series . bold) (font-shape . italic) - (outside-staff-priority . 250) (positioning-done . ,ly:script-interface::calc-positioning-done) (right-padding . 0.5) (self-alignment-X . ,CENTER) (self-alignment-Y . ,CENTER) (stencil . ,ly:text-interface::print) + (vertical-skylines . ,ly:grob::vertical-skylines-from-stencil) (X-offset . ,ly:self-alignment-interface::x-aligned-on-self) (Y-offset . ,ly:self-alignment-interface::y-aligned-on-self) (meta . ((class . Item) @@ -830,6 +836,7 @@ (springs-and-rods . ,ly:spanner::set-spacing-rods) (stencil . ,ly:line-spanner::print) (style . dashed-line) + (vertical-skylines . ,ly:grob::vertical-skylines-from-stencil) (meta . ((class . Spanner) (interfaces . (dynamic-interface dynamic-text-spanner-interface @@ -896,10 +903,12 @@ (Flag . ( + (glyph-name . ,ly:flag::glyph-name) (stencil . ,ly:flag::print) (X-extent . ,ly:flag::width) (X-offset . ,ly:flag::calc-x-offset) (Y-offset . ,ly:flag::calc-y-offset) + (vertical-skylines . ,ly:grob::vertical-skylines-from-stencil) (meta . ((class . Item) (interfaces . (flag-interface font-interface)))))) @@ -978,6 +987,7 @@ (simple-Y . #t) (stencil . ,ly:line-spanner::print) (style . line) + (vertical-skylines . ,ly:grob::vertical-skylines-from-stencil) (X-extent . #f) (Y-extent . #f) (zigzag-width . 0.75) @@ -1035,6 +1045,7 @@ (stencil . ,ly:hairpin::print) (thickness . 1.0) (to-barline . #t) + (vertical-skylines . ,ly:grob::vertical-skylines-from-stencil) (Y-offset . ,ly:self-alignment-interface::y-aligned-on-self) (meta . ((class . Spanner) (interfaces . (dynamic-interface @@ -1109,6 +1120,7 @@ (right-edge . (extra-space . 0.5)) (first-note . (fixed-space . 2.5)))) (stencil . ,ly:key-signature-interface::print) + (vertical-skylines . ,ly:grob::vertical-skylines-from-stencil) (extra-spacing-width . (0.0 . 1.0)) (extra-spacing-height . ,pure-from-neighbor-interface::extra-spacing-height-including-staff) (Y-offset . ,ly:staff-symbol-referencer::callback) @@ -1139,6 +1151,7 @@ (stencil . ,ly:key-signature-interface::print) (extra-spacing-width . (0.0 . 1.0)) (extra-spacing-height . ,pure-from-neighbor-interface::extra-spacing-height-including-staff) + (vertical-skylines . ,ly:grob::vertical-skylines-from-stencil) (Y-offset . ,ly:staff-symbol-referencer::callback) (meta . ((class . Item) (object-callbacks . ((pure-Y-common . ,ly:axis-group-interface::calc-pure-y-common) @@ -1160,6 +1173,7 @@ (stencil . ,laissez-vibrer::print) (thickness . 1.0) (extra-spacing-height . (-0.5 . 0.5)) + (vertical-skylines . ,ly:grob::vertical-skylines-from-stencil) (meta . ((class . Item) (interfaces . (semi-tie-interface)))))) @@ -1249,6 +1263,7 @@ (padding . 0.07) (springs-and-rods . ,ly:lyric-hyphen::set-spacing-rods) (stencil . ,ly:lyric-hyphen::print) + (vertical-skylines . ,ly:grob::vertical-skylines-from-stencil) (thickness . 1.3) (Y-extent . (0 . 0)) (meta . ((class . Spanner) @@ -1280,6 +1295,8 @@ (stencil . ,lyric-text::print) (text . ,(grob::calc-property-by-copy 'text)) (word-space . 0.6) + (skyline-horizontal-padding . 0.1) + (vertical-skylines . ,ly:grob::vertical-skylines-from-stencil) (X-offset . ,ly:self-alignment-interface::aligned-on-x-parent) (meta . ((class . Item) (interfaces . (font-interface @@ -1288,7 +1305,6 @@ self-alignment-interface text-interface)))))) - (MeasureGrouping . ( (direction . ,UP) @@ -1323,10 +1339,12 @@ (break-visibility . ,end-of-line-invisible) (direction . ,UP) (extra-spacing-width . (+inf.0 . -inf.0)) + (outside-staff-horizontal-padding . 0.12) (outside-staff-priority . 1000) (padding . 0.8) (side-axis . ,Y) (stencil . ,ly:text-interface::print) + (vertical-skylines . ,ly:grob::vertical-skylines-from-stencil) (Y-offset . ,ly:side-position-interface::y-aligned-side) (X-offset . ,(ly:make-simple-closure `(,+ @@ -1547,6 +1565,7 @@ (staff-padding . 1.0) (stencil . ,ly:ottava-bracket::print) (style . dashed-line) + (vertical-skylines . ,ly:grob::vertical-skylines-from-stencil) (Y-offset . ,ly:side-position-interface::y-aligned-side) (meta . ((class . Spanner) (interfaces . (font-interface @@ -1565,6 +1584,9 @@ (bound-alignment-interfaces . (note-column-interface)) (horizontal-skylines . ,ly:separation-item::calc-skylines) (keep-inside-line . #t) + ; 0.08 comes from spacing-horizontal-skyline.ly + ; allows double flat of F to be nestled over dots of C + (skyline-vertical-padding . 0.08) ;; (stencil . ,ly:paper-column::print) (X-extent . ,ly:axis-group-interface::width) @@ -1655,6 +1677,7 @@ (stencil . ,ly:piano-pedal-bracket::print) (style . line) (thickness . 1.0) + (vertical-skylines . ,ly:grob::vertical-skylines-from-stencil) (meta . ((class . Spanner) (interfaces . (line-interface piano-pedal-bracket-interface @@ -1671,10 +1694,12 @@ (extra-spacing-width . (+inf.0 . -inf.0)) (font-size . 2) (non-musical . #t) + (outside-staff-horizontal-padding . 0.12) (outside-staff-priority . 1500) (padding . 0.8) (self-alignment-X . ,CENTER) (stencil . ,ly:text-interface::print) + (vertical-skylines . ,ly:grob::vertical-skylines-from-stencil) (X-offset . ,(ly:make-simple-closure `(,+ ,(ly:make-simple-closure @@ -1711,6 +1736,7 @@ (stencil . ,ly:tie::print) (thickness . 1.0) (extra-spacing-height . (-0.5 . 0.5)) + (vertical-skylines . ,ly:grob::vertical-skylines-from-stencil) (meta . ((class . Item) (interfaces . (semi-tie-interface)))))) @@ -1763,6 +1789,7 @@ (stencil . ,ly:script-interface::print) (use-skylines . #t) + (vertical-skylines . ,ly:grob::vertical-skylines-from-stencil) (X-offset . ,script-interface::calc-x-offset) (Y-offset . ,ly:side-position-interface::y-aligned-side) (meta . ((class . Item) @@ -1810,6 +1837,7 @@ (padding . 0.0) ;; padding relative to SostenutoPedalLineSpanner (self-alignment-X . ,CENTER) (stencil . ,ly:text-interface::print) + (vertical-skylines . ,ly:grob::vertical-skylines-from-stencil) (X-offset . ,ly:self-alignment-interface::x-aligned-on-self) (meta . ((class . Item) (interfaces . (font-interface @@ -1826,6 +1854,7 @@ (padding . 1.2) (side-axis . ,Y) (staff-padding . 1.0) + (vertical-skylines . ,ly:grob::vertical-skylines-from-element-stencils) (X-extent . ,ly:axis-group-interface::width) (Y-extent . ,ly:axis-group-interface::height) (Y-offset . ,ly:side-position-interface::y-aligned-side) @@ -2059,6 +2088,7 @@ (padding . 0.0) ;; padding relative to SustainPedalLineSpanner (self-alignment-X . ,CENTER) (stencil . ,ly:sustain-pedal::print) + (vertical-skylines . ,ly:grob::vertical-skylines-from-stencil) (X-offset . ,ly:self-alignment-interface::x-aligned-on-self) (meta . ((class . Item) (interfaces . (font-interface @@ -2076,6 +2106,7 @@ (padding . 1.2) (side-axis . ,Y) (staff-padding . 1.2) + (vertical-skylines . ,ly:grob::vertical-skylines-from-element-stencils) (X-extent . ,ly:axis-group-interface::width) (Y-extent . ,ly:axis-group-interface::height) (Y-offset . ,ly:side-position-interface::y-aligned-side) @@ -2090,6 +2121,7 @@ . ( (adjacent-pure-heights . ,ly:axis-group-interface::adjacent-pure-heights) (axes . (,X ,Y)) + (outside-staff-placement-directive . left-to-right-polite) (skyline-horizontal-padding . 0.5) (vertical-skylines . ,ly:axis-group-interface::calc-skylines) (X-extent . ,ly:axis-group-interface::width) @@ -2098,7 +2130,9 @@ (object-callbacks . ((footnotes-before-line-breaking . ,ly:system::footnotes-before-line-breaking) (footnotes-after-line-breaking . ,ly:system::footnotes-after-line-breaking) (pure-relevant-grobs . ,ly:system::calc-pure-relevant-grobs) - (pure-Y-common . ,ly:axis-group-interface::calc-pure-y-common))) + (pure-Y-common . ,ly:axis-group-interface::calc-pure-y-common) + (vertical-skyline-elements . ,ly:system::vertical-skyline-elements) + (vertical-alignment . ,ly:system::get-vertical-alignment))) (interfaces . (axis-group-interface system-interface)))))) @@ -2204,6 +2238,7 @@ (cross-staff . ,script-or-side-position-cross-staff) (direction . ,DOWN) (extra-spacing-width . (+inf.0 . -inf.0)) + (outside-staff-horizontal-padding . 0.12) (outside-staff-priority . 450) ;; sync with Fingering ? @@ -2214,6 +2249,7 @@ (slur-padding . 0.5) (staff-padding . 0.5) (stencil . ,ly:text-interface::print) + (vertical-skylines . ,ly:grob::vertical-skylines-from-stencil) ;; todo: add X self alignment? (X-offset . ,ly:self-alignment-interface::x-aligned-on-self) (Y-offset . ,ly:side-position-interface::y-aligned-side) @@ -2287,6 +2323,7 @@ (neutral-direction . ,UP) (springs-and-rods . ,ly:spanner::set-spacing-rods) (stencil . ,ly:tie::print) + (vertical-skylines . ,ly:grob::vertical-skylines-from-stencil) (thickness . 1.2) (meta . ((class . Spanner) (interfaces . (tie-interface)))))) @@ -2416,6 +2453,7 @@ (staff-padding . 0.25) (stencil . ,ly:tuplet-bracket::print) (thickness . 1.6) + (vertical-skylines . ,ly:grob::vertical-skylines-from-stencil) (X-positions . ,ly:tuplet-bracket::calc-x-positions) (meta . ((class . Spanner) @@ -2447,6 +2485,7 @@ (padding . 0.0) ;; padding relative to UnaCordaPedalLineSpanner (self-alignment-X . ,CENTER) (stencil . ,ly:text-interface::print) + (vertical-skylines . ,ly:grob::vertical-skylines-from-stencil) (X-offset . ,ly:self-alignment-interface::x-aligned-on-self) (meta . ((class . Item) (interfaces . (font-interface @@ -2463,6 +2502,7 @@ (padding . 1.2) (side-axis . ,Y) (staff-padding . 1.2) + (vertical-skylines . ,ly:grob::vertical-skylines-from-element-stencils) (X-extent . ,ly:axis-group-interface::width) (Y-extent . ,ly:axis-group-interface::height) (Y-offset . ,ly:side-position-interface::y-aligned-side) @@ -2507,8 +2547,10 @@ (minimum-distance . 8) (padding . 1))) (nonstaff-unrelatedstaff-spacing . ((padding . 0.5))) + (outside-staff-placement-directive . left-to-right-polite) (staff-staff-spacing . ,ly:axis-group-interface::calc-staff-staff-spacing) (stencil . ,ly:axis-group-interface::print) + (skyline-horizontal-padding . 0.1) (vertical-skylines . ,ly:hara-kiri-group-spanner::calc-skylines) (X-extent . ,ly:axis-group-interface::width) (Y-extent . ,ly:hara-kiri-group-spanner::y-extent) @@ -2532,6 +2574,7 @@ (padding . 1.5) )) )) + (cross-staff . #t) (gap . 0.5) (left-bound-info . ,ly:line-spanner::calc-left-bound-info) (non-musical . #t) @@ -2553,6 +2596,7 @@ (stencil . ,ly:volta-bracket-interface::print) (thickness . 1.6) ;; line-thickness (word-space . 0.6) + (vertical-skylines . ,ly:grob::vertical-skylines-from-stencil) (meta . ((class . Spanner) (interfaces . (font-interface horizontal-bracket-interface @@ -2571,9 +2615,10 @@ (outside-staff-priority . 600) (padding . 1) (side-axis . ,Y) + (vertical-skylines . ,ly:grob::vertical-skylines-from-element-stencils) (X-extent . ,ly:axis-group-interface::width) (Y-extent . ,ly:axis-group-interface::height) - (Y-offset . ,ly:side-position-interface::y-aligned-side) + (Y-offset . ,ly:side-position-interface::y-aligned-side) (meta . ((class . Spanner) (object-callbacks . ((pure-Y-common . ,ly:axis-group-interface::calc-pure-y-common) (pure-relevant-grobs . ,ly:axis-group-interface::calc-pure-relevant-grobs))) diff --git a/scm/harp-pedals.scm b/scm/harp-pedals.scm index 8fa02fb5a0..ce756ddfe2 100644 --- a/scm/harp-pedals.scm +++ b/scm/harp-pedals.scm @@ -121,10 +121,13 @@ divider) and @code{space-after-divider} (box spacing after the divider). (final-x (car result)) (stencils (cdr result))) ; Add the horizontal line and combine all stencils: - (apply ly:stencil-add - (cons - (make-line-stencil line-width 0 0 final-x 0) - stencils)))) + (box-stencil + (apply ly:stencil-add + (cons + (make-line-stencil line-width 0 0 final-x 0) + stencils)) + 0.0 + 0.0))) ;; Parse the harp pedal definition string into list of directions (-1/0/1), #\o and #\| (define (harp-pedals-parse-string definition-string) diff --git a/scm/lily.scm b/scm/lily.scm index 070ba758d2..35a16019a1 100644 --- a/scm/lily.scm +++ b/scm/lily.scm @@ -289,7 +289,6 @@ messages into errors.") (if (memq (ly:get-option 'backend) music-string-to-path-backends) (ly:set-option 'music-strings-to-paths #t)) - (define-public (ly:load x) (let* ((file-name (%search-load-path x))) (ly:debug "[~A" file-name) diff --git a/scm/output-lib.scm b/scm/output-lib.scm index af55cc8fde..5b7d441952 100644 --- a/scm/output-lib.scm +++ b/scm/output-lib.scm @@ -574,6 +574,10 @@ and duration-log @var{log}." (define-public (accidental-interface::calc-alteration grob) (ly:pitch-alteration (ly:event-property (event-cause grob) 'pitch))) +(define-public (accidental-interface::glyph-name grob) + (assoc-get (ly:grob-property grob 'alteration) + standard-alteration-glyph-name-alist)) + (define-public cancellation-glyph-name-alist '((0 . "accidentals.natural"))) diff --git a/scm/output-ps.scm b/scm/output-ps.scm index 7c8a6ed394..497f197aeb 100644 --- a/scm/output-ps.scm +++ b/scm/output-ps.scm @@ -112,12 +112,13 @@ (define (embedded-ps string) string) -(define (glyph-string postscript-font-name +(define (glyph-string pango-font + postscript-font-name size cid? w-x-y-named-glyphs) - (define (glyph-spec w x y g) + (define (glyph-spec w h x y g) ; h not used (let ((prefix (if (string? g) "/" ""))) (ly:format "~4f ~4f ~4f ~a~a" w x y diff --git a/scm/output-svg.scm b/scm/output-svg.scm index 9f10629eac..a15a9d8ad0 100644 --- a/scm/output-svg.scm +++ b/scm/output-svg.scm @@ -244,7 +244,7 @@ (begin (set! path (apply dump-path d-attr-value font-scale - (list (cadr rest) (caddr rest)))) + (list (caddr rest) (cadddr rest)))) (set! next-horiz-adv (+ next-horiz-adv (car rest))) path)) @@ -263,7 +263,7 @@ "")))) (define (extract-glyph-info all-glyphs glyph size) - (let* ((offsets (list-head glyph 3)) + (let* ((offsets (list-head glyph 4)) (glyph-name (car (reverse glyph)))) (apply extract-glyph all-glyphs glyph-name size offsets))) @@ -428,7 +428,7 @@ (define (embedded-svg string) string) -(define (embedded-glyph-string font size cid glyphs) +(define (embedded-glyph-string pango-font font size cid glyphs) (define path "") (if (= 1 (length glyphs)) (set! path (music-string-to-path font size (car glyphs))) @@ -444,7 +444,7 @@ (set! next-horiz-adv 0.0) path) -(define (woff-glyph-string font-name size cid? w-x-y-named-glyphs) +(define (woff-glyph-string pango-font font-name size cid? w-h-x-y-named-glyphs) (let* ((name-style (font-name-style font-name)) (family-designsize (regexp-exec (make-regexp "(.*)-([0-9]*)") font-name)) @@ -458,7 +458,7 @@ (font (ly:paper-get-font paper `(((font-family . ,family) ,(if design-size `(design-size . design-size))))))) - (define (glyph-spec w x y g) + (define (glyph-spec w h x y g) ; h not used (let* ((charcode (ly:font-glyph-name-to-charcode font g)) (char-lookup (format #f "&#~S;" charcode)) (glyph-by-name (eoc 'altglyph `(glyphname . ,g))) @@ -477,7 +477,7 @@ (string-append glyph-by-name apparently-broken char-lookup))))) (string-join (map (lambda (x) (apply glyph-spec x)) - (reverse w-x-y-named-glyphs)) "\n"))) + (reverse w-h-x-y-named-glyphs)) "\n"))) (define glyph-string (if (not (ly:get-option 'svg-woff)) embedded-glyph-string woff-glyph-string)) diff --git a/scm/stencil.scm b/scm/stencil.scm index 0ecc9abe8e..9b0db9a3fd 100644 --- a/scm/stencil.scm +++ b/scm/stencil.scm @@ -324,55 +324,55 @@ defined by @code{fill}." (cons (min-max-crawler min cddr possible-extrema) (min-max-crawler max cddr possible-extrema))))) -(define (path-min-max origin pointlist) - - (define (line-part-min-max x1 x2) - (list (min x1 x2) (max x1 x2))) - - (define (bezier-part-min-max x1 x2 x3 x4) - ((lambda (x) (list (reduce min 10000 x) (reduce max -10000 x))) - (map - (lambda (x) - (+ (* x1 (expt (- 1 x) 3)) - (+ (* 3 (* x2 (* (expt (- 1 x) 2) x))) - (+ (* 3 (* x3 (* (- 1 x) (expt x 2)))) - (* x4 (expt x 3)))))) - (if (< (+ (expt x2 2) (+ (expt x3 2) (* x1 x4))) - (+ (* x1 x3) (+ (* x2 x4) (* x2 x3)))) - (list 0.0 1.0) - (filter - (lambda (x) (and (>= x 0) (<= x 1))) - (append - (list 0.0 1.0) - (map (lambda (op) - (if (not (eqv? 0.0 - (- (+ x1 (* 3 x3)) (+ x4 (* 3 x2))))) - ;; Zeros of the bezier curve - (/ (+ (- x1 (* 2 x2)) - (op x3 - (sqrt (- (+ (expt x2 2) - (+ (expt x3 2) (* x1 x4))) - (+ (* x1 x3) - (+ (* x2 x4) (* x2 x3))))))) - (- (+ x1 (* 3 x3)) (+ x4 (* 3 x2)))) - ;; Apply L'hopital's rule to get the zeros if 0/0 - (* (op 0 1) - (/ (/ (- x4 x3) 2) - (sqrt (- (+ (* x2 x2) - (+ (* x3 x3) (* x1 x4))) - (+ (* x1 x3) - (+ (* x2 x4) (* x2 x3))))))))) - (list + -)))))))) - - (define (bezier-min-max x1 y1 x2 y2 x3 y3 x4 y4) - (map (lambda (x) - (apply bezier-part-min-max x)) - `((,x1 ,x2 ,x3 ,x4) (,y1 ,y2 ,y3 ,y4)))) +(define (line-part-min-max x1 x2) + (list (min x1 x2) (max x1 x2))) + +(define (bezier-part-min-max x1 x2 x3 x4) + ((lambda (x) (list (reduce min 10000 x) (reduce max -10000 x))) + (map + (lambda (x) + (+ (* x1 (expt (- 1 x) 3)) + (+ (* 3 (* x2 (* (expt (- 1 x) 2) x))) + (+ (* 3 (* x3 (* (- 1 x) (expt x 2)))) + (* x4 (expt x 3)))))) + (if (< (+ (expt x2 2) (+ (expt x3 2) (* x1 x4))) + (+ (* x1 x3) (+ (* x2 x4) (* x2 x3)))) + (list 0.0 1.0) + (filter + (lambda (x) (and (>= x 0) (<= x 1))) + (append + (list 0.0 1.0) + (map (lambda (op) + (if (not (eqv? 0.0 + (exact->inexact (- (+ x1 (* 3 x3)) (+ x4 (* 3 x2)))))) + ;; Zeros of the bezier curve + (/ (+ (- x1 (* 2 x2)) + (op x3 + (sqrt (- (+ (expt x2 2) + (+ (expt x3 2) (* x1 x4))) + (+ (* x1 x3) + (+ (* x2 x4) (* x2 x3))))))) + (- (+ x1 (* 3 x3)) (+ x4 (* 3 x2)))) + ;; Apply L'hopital's rule to get the zeros if 0/0 + (* (op 0 1) + (/ (/ (- x4 x3) 2) + (sqrt (- (+ (* x2 x2) + (+ (* x3 x3) (* x1 x4))) + (+ (* x1 x3) + (+ (* x2 x4) (* x2 x3))))))))) + (list + -)))))))) + +(define (bezier-min-max x1 y1 x2 y2 x3 y3 x4 y4) + (map (lambda (x) + (apply bezier-part-min-max x)) + `((,x1 ,x2 ,x3 ,x4) (,y1 ,y2 ,y3 ,y4)))) + +(define (line-min-max x1 y1 x2 y2) + (map (lambda (x) + (apply line-part-min-max x)) + `((,x1 ,x2) (,y1 ,y2)))) - (define (line-min-max x1 y1 x2 y2) - (map (lambda (x) - (apply line-part-min-max x)) - `((,x1 ,x2) (,y1 ,y2)))) +(define (path-min-max origin pointlist) ((lambda (x) (list diff --git a/scripts/auxiliar/show_skyline_command.py b/scripts/auxiliar/show_skyline_command.py new file mode 100644 index 0000000000..6fc63143c9 --- /dev/null +++ b/scripts/auxiliar/show_skyline_command.py @@ -0,0 +1,156 @@ +# This file is part of LilyPond, the GNU music typesetter. +# +# Copyright (C) 2012 Joe Neeman <joeneeman@gmail.com> +# +# LilyPond is free software: you can redistribute it and/or modify +# it under the terms of the GNU General Public License as published by +# the Free Software Foundation, either version 3 of the License, or +# (at your option) any later version. +# +# LilyPond is distributed in the hope that it will be useful, +# but WITHOUT ANY WARRANTY; without even the implied warranty of +# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +# GNU General Public License for more details. +# +# You should have received a copy of the GNU General Public License +# along with LilyPond. If not, see <http://www.gnu.org/licenses/>. + +# A gdb plugin debugging skylines. To use the plugin, make sure that +# skyline_viewer.py is in your PATH, then add +# source /path/to/show_skyline_command.py +# to your .gdbinit file. The 'vsky' and 'hsky' commands for +# drawing skylines will then be available in gdb. + +import gdb +from subprocess import Popen, PIPE +from math import isinf + +SKYLINE_VIEWER = 'skyline_viewer.py' + +# Function taken from GCC +def find_type(orig, name): + typ = orig.strip_typedefs() + while True: + search = str(typ) + '::' + name + try: + return gdb.lookup_type(search) + except RuntimeError: + pass + # The type was not found, so try the superclass. We only need + # to check the first superclass, so we don't bother with + # anything fancier here. + field = typ.fields()[0] + if not field.is_base_class: + raise ValueError, "Cannot find type %s::%s" % (str(orig), name) + typ = field.type + +# Class adapted from GCC +class ListIterator: + def __init__ (self, val): + self.val = val + self.nodetype = find_type (val.type, '_Node') + self.nodetype = self.nodetype.strip_typedefs ().pointer () + + head = val['_M_impl']['_M_node'] + self.base = head['_M_next'] + self.head = head.address + + def __iter__ (self): + return self + + def next (self): + if self.base == self.head: + raise StopIteration + elt = self.base.cast (self.nodetype).dereference () + self.base = elt['_M_next'] + return elt['_M_data'] + +def to_list (list_val): + return list (ListIterator (list_val)) + +def skyline_to_lines (sky_value): + """Turns a gdb.Value into a list of line segments.""" + sky_d = int (sky_value['sky_']) + buildings = to_list (sky_value['buildings_']) + + def bld_to_line (bld): + y_intercept = float (bld['y_intercept_']) * sky_d + slope = float (bld['slope_']) * sky_d + x1 = float (bld['start_']) + x2 = float (bld['end_']) + + if isinf (y_intercept) or isinf (x1) or isinf (x2): + return None + return (x1, y_intercept + slope * x1, x2, y_intercept + slope * x2) + + ret = map (bld_to_line, buildings) + return [r for r in ret if r is not None] + +viewer = Popen(SKYLINE_VIEWER, stdin=PIPE) +def add_skyline(lines): + global viewer + try: + for line in lines: + x1, y1, x2, y2 = line + viewer.stdin.write('(%f,%f) (%f,%f)\n' % (x1, y1, x2, y2)) + viewer.stdin.write('\n') + except IOError: + # If the pipe is broken, it probably means that someone closed + # the viewer window. Open another one. + viewer = Popen(SKYLINE_VIEWER, stdin=PIPE) + add_skyline(lines) + +class ShowSkylineCommand (gdb.Command): + "Show a skyline graphically." + + def __init__ (self, command_name): + super (ShowSkylineCommand, self).__init__ (command_name, + gdb.COMMAND_DATA, + gdb.COMPLETE_SYMBOL, False) + + def to_lines (self, skyline): + pass + + def invoke (self, arg, from_tty): + global plot + + val = gdb.parse_and_eval (arg) + typ = val.type + + # If they passed in a reference or pointer to a skyline, + # dereference it. + if typ.code == gdb.TYPE_CODE_PTR or typ.code == gdb.TYPE_CODE_REF: + val = val.referenced_value () + typ = val.type + + if typ.tag == 'Skyline_pair': + sky = val['skylines_'] + arr = sky['array_'] + add_skyline (self.to_lines (arr[0])) + add_skyline (self.to_lines (arr[1])) + + elif typ.tag == 'Skyline': + add_skyline (self.to_lines (val)) + +class ShowVSkylineCommand (ShowSkylineCommand): + "Show a vertical skyline." + + def __init__ (self): + super (ShowVSkylineCommand, self).__init__ ("vsky") + + def to_lines (self, skyline): + return skyline_to_lines (skyline) + +class ShowHSkylineCommand (ShowSkylineCommand): + "Show a horizontal skyline." + + def __init__ (self): + super (ShowHSkylineCommand, self).__init__ ("hsky") + + def to_lines (self, skyline): + lines = skyline_to_lines (skyline) + # Because it is a horizontal skyline, reflect around the line y=x. + return [(y1, x1, y2, x2) for (x1, y1, x2, y2) in lines] + +ShowHSkylineCommand() +ShowVSkylineCommand() diff --git a/scripts/auxiliar/skyline_viewer.py b/scripts/auxiliar/skyline_viewer.py new file mode 100755 index 0000000000..83e45f80f7 --- /dev/null +++ b/scripts/auxiliar/skyline_viewer.py @@ -0,0 +1,159 @@ +#!/usr/bin/env python + +# This file is part of LilyPond, the GNU music typesetter. +# +# Copyright (C) 2012 Joe Neeman <joeneeman@gmail.com> +# +# LilyPond is free software: you can redistribute it and/or modify +# it under the terms of the GNU General Public License as published by +# the Free Software Foundation, either version 3 of the License, or +# (at your option) any later version. +# +# LilyPond is distributed in the hope that it will be useful, +# but WITHOUT ANY WARRANTY; without even the implied warranty of +# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +# GNU General Public License for more details. +# +# You should have received a copy of the GNU General Public License +# along with LilyPond. If not, see <http://www.gnu.org/licenses/>. + +# A GTK+ program for debugging skylines. The program reads a sequence +# of line segments from stdin (one line segment per line of stdin, in the format +# '(x1, y1) (x2, y2)'). A skyline is terminated by an empty line, which +# causes the skyline to be displayed on the screen. + +from threading import Thread +from math import isinf +import gtk +import gobject +import goocanvas +import sys +import re + +class GtkSkylineCanvas (goocanvas.Canvas): + """A Canvas for displaying skylines.""" + def __init__ (self): + super (GtkSkylineCanvas, self).__init__ () + self.connect ('size-allocate', GtkSkylineCanvas.rescale) + self.x_min = float ('inf') + self.x_max = float ('-inf') + self.y_min = float ('inf') + self.y_max = float ('-inf') + + self.colors = ('black', 'red', 'green', 'blue', 'maroon', 'olive', 'teal') + self.cur_color_index = 0 + + def rescale (self, allocation): + width = (self.x_max - self.x_min + 1) * 1.1 + height = (self.y_max - self.y_min + 1) * 1.1 + if width <= 0 or height <= 0: + return + + scale_x = allocation.width / width + scale_y = allocation.height / height + scale = min (scale_x, scale_y) + self.set_scale (scale) + + center_x = (self.x_max + self.x_min) / 2 + center_y = (self.y_max + self.y_min) / 2 + actual_width = allocation.width / scale + actual_height = allocation.height / scale + actual_min_x = center_x - actual_width / 2 + actual_max_x = center_x + actual_width / 2 + actual_min_y = center_y - actual_height / 2 + actual_max_y = center_y + actual_height / 2 + + self.set_bounds (actual_min_x, actual_min_y, actual_max_x, actual_max_y) + self.scroll_to (actual_min_x, actual_min_y) + + def add_skyline (self, lines): + """Adds a skyline to the current canvas, in a new color. + + The canvas will be rescaled, if necessary, to make room for the + new skyline.""" + # Flip vertically, because goocanvas thinks higher numbers are + # further down, while lilypond thinks they're further up. + lines = [(x1, -y1, x2, -y2) for (x1, y1, x2, y2) in lines] + + color = self.colors[self.cur_color_index] + self.cur_color_index = (self.cur_color_index + 1) % len (self.colors) + + # Update the bounding box of the skylines. + x_vals = [s[0] for s in lines] + [s[2] for s in lines] + y_vals = [s[1] for s in lines] + [s[3] for s in lines] + self.x_min = min ([self.x_min] + x_vals) + self.x_max = max ([self.x_max] + x_vals) + self.y_min = min ([self.y_min] + y_vals) + self.y_max = max ([self.y_max] + y_vals) + + # Add the lines to the canvas. + root = self.get_root_item () + for (x1, y1, x2, y2) in lines: + goocanvas.polyline_new_line (root, x1, y1, x2, y2, + stroke_color=color, + line_width=0.05) + self.rescale (self.get_allocation ()) + +# We want to run the gtk main loop in a separate thread so that +# the main thread can be responsible for reading stdin. +class SkylineWindowThread (Thread): + """A thread that runs a Gtk.Window displaying a skyline.""" + + def run (self): + gtk.gdk.threads_init () + self.window = None + self.canvas = None + gtk.main () + + # This should only be called from the Gtk main loop. + def _destroy_window (self, window): + sys.exit (0) + + # This should only be called from the Gtk main loop. + def _setup_window (self): + if self.window is None: + self.window = gtk.Window () + self.canvas = GtkSkylineCanvas () + self.window.add (self.canvas) + self.window.connect ("destroy", self._destroy_window) + self.window.show_all () + + # This should only be called from the Gtk main loop. + def _add_skyline (self, lines): + self._setup_window () + self.canvas.add_skyline (lines) + + def add_skyline (self, lines): + # Copy the lines, just in case someone modifies them. + gobject.idle_add (self._add_skyline, list (lines)) + +thread = SkylineWindowThread () +thread.setDaemon (True) +thread.start () + +def lines(infile): + line = infile.readline() + while len(line) > 0: + yield line[:-1] + line = infile.readline() + +point_re_str = r'\(([a-z.0-9-]*) *,([a-z0-9.-]*)\)' +line_re_str = point_re_str + r' +' + point_re_str +line_re = re.compile (line_re_str) + +# The main loop just reads lines from stdin and feeds them to the +# display. +current_skyline = [] +for line in lines(sys.stdin): + if not line: + thread.add_skyline(current_skyline) + current_skyline = [] + continue + + m = re.search (line_re, line) + if m is None: + print('line did not match') + else: + pts = map(float, m.groups()) + if not any(map(isinf, pts)): + current_skyline.append(pts) |