struct Accidental_placement_entry
{
- vector<Skyline_entry> left_skyline_;
- vector<Skyline_entry> right_skyline_;
+ Skyline left_skyline_;
+ Skyline right_skyline_;
Interval vertical_extent_;
vector<Box> extents_;
vector<Grob*> grobs_;
for (vsize i = apes.size (); i--;)
{
Accidental_placement_entry *ape = apes[i];
- ape->left_skyline_ = empty_skyline (LEFT);
- ape->right_skyline_ = empty_skyline (RIGHT);
for (vsize j = apes[i]->grobs_.size (); j--;)
{
Grob *a = apes[i]->grobs_[j];
-
vector<Box> boxes = Accidental_interface::accurate_boxes (a, common);
ape->extents_.insert (ape->extents_.end (), boxes.begin (), boxes.end ());
- for (vsize j = boxes.size (); j--;)
- {
- insert_extent_into_skyline (&ape->left_skyline_, boxes[j], Y_AXIS, LEFT);
- insert_extent_into_skyline (&ape->right_skyline_, boxes[j], Y_AXIS, RIGHT);
- }
}
+ ape->left_skyline_ = Skyline (ape->extents_, Y_AXIS, LEFT);
+ ape->right_skyline_ = Skyline (ape->extents_, Y_AXIS, RIGHT);
}
Interval total;
Accidental_placement_entry *head_ape = new Accidental_placement_entry;
common[X_AXIS] = common_refpoint_of_array (heads, common[X_AXIS], X_AXIS);
- vector<Skyline_entry> head_skyline (empty_skyline (LEFT));
vector<Box> head_extents;
for (vsize i = heads.size (); i--;)
- {
- Box b (heads[i]->extent (common[X_AXIS], X_AXIS),
- heads[i]->extent (common[Y_AXIS], Y_AXIS));
-
- insert_extent_into_skyline (&head_skyline, b, Y_AXIS, LEFT);
- }
+ head_extents.push_back (Box (heads[i]->extent (common[X_AXIS], X_AXIS),
+ heads[i]->extent (common[Y_AXIS], Y_AXIS)));
vector<Grob *> stems;
for (vsize i = 0; i < heads.size (); i++)
{
int very_large = INT_MAX;
- Box b (heads[i]->extent (common[X_AXIS], X_AXIS),
- heads[i]->pure_height (common[Y_AXIS], 0, very_large));
-
- insert_extent_into_skyline (&head_skyline, b, Y_AXIS, LEFT);
+ head_extents.push_back (Box (heads[i]->extent (common[X_AXIS], X_AXIS),
+ heads[i]->pure_height (common[Y_AXIS], 0, very_large)));
}
-
- head_ape->left_skyline_ = head_skyline;
+
+ head_ape->left_skyline_ = Skyline (head_extents, Y_AXIS, LEFT);
head_ape->offset_ = 0.0;
Real padding = robust_scm2double (me->get_property ("padding"), 0.2);
- vector<Skyline_entry> left_skyline = head_ape->left_skyline_;
- heighten_skyline (&left_skyline,
- -robust_scm2double (me->get_property ("right-padding"), 0));
+ Skyline left_skyline = head_ape->left_skyline_;
+ left_skyline.raise (-robust_scm2double (me->get_property ("right-padding"), 0))
+;
/*
Add accs entries right-to-left.
*/
for (vsize i = apes.size (); i-- > 0;)
{
- Real offset
- = -skyline_meshing_distance (apes[i]->right_skyline_, left_skyline);
+ Real offset = -apes[i]->right_skyline_.distance (left_skyline);
if (isinf (offset))
offset = (i < apes.size () - 1) ? apes[i + 1]->offset_ : 0.0;
else
apes[i]->offset_ = offset;
- vector<Skyline_entry> new_left_skyline = apes[i]->left_skyline_;
- heighten_skyline (&new_left_skyline, apes[i]->offset_);
- merge_skyline (&new_left_skyline, left_skyline, LEFT);
+ Skyline new_left_skyline = apes[i]->left_skyline_;
+ new_left_skyline.raise (apes[i]->offset_);
+ new_left_skyline.merge (left_skyline);
left_skyline = new_left_skyline;
}
#include "axis-group-interface.hh"
#include "align-interface.hh"
+#include "directional-element-interface.hh"
#include "pointer-group-interface.hh"
#include "grob.hh"
#include "grob-array.hh"
#include "item.hh"
#include "paper-column.hh"
#include "paper-score.hh"
+#include "std-vector.hh"
#include "system.hh"
#include "warn.hh"
Axis_group_interface::generic_group_extent (Grob *me, Axis a)
{
extract_grob_set (me, "elements", elts);
+ if (a == Y_AXIS && to_boolean (me->get_property ("skyline-spacing")))
+ skyline_spacing (me, elts);
Grob *common = common_refpoint_of_array (elts, me, a);
Real my_coord = me->relative_coordinate (common, a);
}
}
+bool
+staff_priority_less (Grob * const &g1, Grob * const &g2)
+{
+ int priority_1 = robust_scm2int (g1->get_property ("outside-staff-priority"), INT_MIN);
+ int priority_2 = robust_scm2int (g2->get_property ("outside-staff-priority"), INT_MIN);
+
+ if (priority_1 < priority_2)
+ return true;
+ else if (priority_1 > priority_2)
+ return false;
+
+ /* if there is no preference in staff priority, choose the one with the lower rank */
+ int rank_1 = g1->spanned_rank_iv ()[LEFT];
+ int rank_2 = g2->spanned_rank_iv ()[LEFT];
+ return rank_1 < rank_2;
+}
+
+void
+Axis_group_interface::skyline_spacing (Grob *me, vector<Grob*> elements)
+{
+ vector_sort (elements, staff_priority_less);
+ Grob *x_common = common_refpoint_of_array (elements, me, X_AXIS);
+ Grob *y_common = common_refpoint_of_array (elements, me, Y_AXIS);
+
+ vsize i = 0;
+ vector<Box> boxes;
+
+ for (i = 0; i < elements.size ()
+ && !scm_is_number (elements[i]->get_property ("outside-staff-priority")); i++)
+ boxes.push_back (Box (elements[i]->extent (x_common, X_AXIS),
+ elements[i]->extent (y_common, Y_AXIS)));
+
+
+ Drul_array<Skyline> skylines (Skyline (boxes, X_AXIS, DOWN),
+ Skyline (boxes, X_AXIS, UP));
+ for (; i < elements.size (); i++)
+ {
+ Direction dir = get_grob_direction (elements[i]);
+ if (dir == CENTER)
+ {
+ warning (_ ("an outside-staff object should have a direction"));
+ continue;
+ }
+
+ Box b (elements[i]->extent (x_common, X_AXIS),
+ elements[i]->extent (y_common, Y_AXIS));
+ boxes.clear ();
+ boxes.push_back (b);
+ Skyline other = Skyline (boxes, X_AXIS, -dir);
+ Real dist = skylines[dir].distance (other);
+
+ if (dist > 0)
+ {
+ b.translate (Offset (0, dir*dist));
+ elements[i]->translate_axis (dir*dist, Y_AXIS);
+ }
+ skylines[dir].insert (b, X_AXIS);
+ }
+}
+
ADD_INTERFACE (Axis_group_interface, "axis-group-interface",
"An object that groups other layout objects.",
"elements "
"common-refpoint-of-elements "
"pure-relevant-elements "
+ "skyline-spacing "
"cached-pure-extents "
);
vector<Beam_segment>
Beam::get_beam_segments (Grob *me_grob, Grob **common)
{
+ /* ugh, this has a side-effect that we need to ensure that
+ Stem #'beaming is correct */
+ (void) me_grob->get_property ("quantized-positions");
+
Spanner *me = dynamic_cast<Spanner*> (me_grob);
extract_grob_set (me, "stems", stems);
"meta "
"minimum-X-extent "
"minimum-Y-extent "
+ "outside-staff-priority "
"rotation "
"springs-and-rods "
"staff-symbol "
static Interval cached_pure_height (Grob *me, vector<Grob*> const &list,
Grob *common, int, int);
+ static void skyline_spacing (Grob *me, vector<Grob*> elements);
static void add_element (Grob *me, Grob *);
static void set_axes (Grob *, Axis, Axis);
static bool has_axis (Grob *, Axis);
#ifndef GROB_HH
#define GROB_HH
+#include "box.hh"
#include "virtual-methods.hh"
#include "dimension-cache.hh"
#include "grob-interface.hh"
/*
display and print newline.
*/
-extern "C" {
- void ly_display_scm (SCM s);
-}
+void ly_display_scm (void *s);
void read_lily_scm_file (string);
void ly_c_init_guile ();
/*
- skyline.hh -- declare Skyline_entry and funcbs.
+ skyline.hh -- declare Skyline class.
source file of the GNU LilyPond music typesetter
- (c) 2002--2006 Han-Wen Nienhuys <hanwen@xs4all.nl>
+ (c) 2006 Joe Neeman <joeneeman@gmail.com>
*/
#ifndef SKYLINE_HH
#define SKYLINE_HH
-#include "std-vector.hh"
+#include <list>
+#include "axis.hh"
#include "box.hh"
+#include "interval.hh"
+#include "direction.hh"
+#include "std-vector.hh"
+#include "stencil.hh"
-struct Skyline_entry
+struct Building
{
- Interval width_;
- Real height_;
- Skyline_entry ();
- Skyline_entry (Interval, Real);
+ Interval iv_;
+ Real start_height_;
+ Real end_height_;
+ Real m_;
+ Real b_;
+
+ Building (Real start, Real start_height, Real end_height, Real end, Real max_slope);
+
+ Real height (Real x) const;
+ Real intersection (Building const &other) const;
+ void leading_part (Real chop, Real h);
+ bool obstructs (Building const &other) const;
};
-void
-merge_skyline (vector<Skyline_entry> *a1, vector<Skyline_entry> const &a2,
- Direction);
-void insert_extent_into_skyline (vector<Skyline_entry> *line, Box b, Axis line_axis,
- Direction d);
-vector<Skyline_entry>
-extents_to_skyline (vector<Box> const &extents, Axis a, Direction d);
-vector<Skyline_entry> empty_skyline (Direction d);
-void heighten_skyline (vector<Skyline_entry> *buildings, Real ground);
-Real
-skyline_meshing_distance (vector<Skyline_entry> const &buildings,
- vector<Skyline_entry> const &clouds);
-
-Real
-skyline_height (vector<Skyline_entry> const &buildings,
- Real airplane, Direction sky_dir);
+class Skyline
+{
+private:
+ list<Building> buildings_;
+ Direction sky_;
+ Real max_slope_;
+ void internal_merge_skyline (list<Building>*, list<Building>*,
+ list<Building> *const result);
+ void internal_build_skyline (list<Building>*,
+ list<Building> *const result);
+ bool is_legal_skyline () const;
+
+public:
+ Skyline ();
+ Skyline (Direction sky);
+ Skyline (vector<Box> const &bldgs, Axis a, Direction sky);
+
+ void merge (Skyline const &);
+ void insert (Box const &, Axis);
+ void raise (Real);
+ Real distance (Skyline const &) const;
+ Real height (Real airplane) const;
+ Real max_height () const;
+ void set_minimum_height (Real height);
+ Stencil stencil ();
+};
#endif /* SKYLINE_HH */
#include "column-x-positions.hh"
#include "spanner.hh"
#include "grob-array.hh"
+#include "skyline.hh"
/*
If you keep following offset reference points, you will always end
{
int rank_;
Grob_array *all_elements_;
+ Drul_array<Skyline> skylines_;
+ void build_skylines ();
void init_elements ();
friend class Paper_score; // ugh.
Paper_score *pscore_; // ugh.
#include "lily-proto.hh"
#include "tie-configuration.hh"
-void set_chord_outline (vector<Skyline_entry> *skyline,
+void set_chord_outline (Skyline *skyline,
vector<Item*> bounds,
Grob *common,
Direction d);
Tie_formatting_problem const&,
Grob *staff_referencer);
void
-set_chord_outlines (Drul_array< vector<Skyline_entry> > *skyline_drul,
+set_chord_outlines (Drul_array<Skyline> *skyline_drul,
vector<Grob*> ties,
Grob *common);
Tie_configuration_variation ();
};
-typedef map < Tuple<int, 2>, vector<Skyline_entry> > Chord_outline_map;
+typedef map < Tuple<int, 2>, Skyline> Chord_outline_map;
typedef map < Tuple<int, 2>, Box> Column_extent_map;
class Tie_formatting_problem
{
text_spanner_->set_bound (LEFT, col);
text_spanner_->set_property ("text", short_text_);
text_spanner_->set_property ("long-text", long_text_);
+
+ /*
+ UGH, should handle this in Score_engraver.
+ */
+ Grob *system = unsmob_grob (get_property ("rootSystem"));
+ if (system)
+ Axis_group_interface::add_element (system, text_spanner_);
+ else
+ text_spanner_->programming_error ("can't find root system");
}
Pointer_group_interface::set_ordered (text_spanner_, ly_symbol2scm ("elements"), false);
- System *system = get_root_system (text_spanner_);
-
- /*
- UGH, should handle this in Score_engraver.
- */
- if (system)
- Axis_group_interface::add_element (system, text_spanner_);
- else
- text_spanner_->programming_error ("can't find root system");
-
text_spanner_ = 0;
}
return result;
}
-extern "C" {
- // maybe gdb 5.0 becomes quicker if it doesn't do fancy C++ typing?
- void
- ly_display_scm (SCM s)
- {
- scm_display (s, scm_current_output_port ());
- scm_newline (scm_current_output_port ());
- }
-};
+void
+ly_display_scm (void *s)
+{
+ scm_display ((SCM)s, scm_current_output_port ());
+ scm_newline (scm_current_output_port ());
+}
string
ly_scm2string (SCM str)
/* Only reachable if GUILE exits. That is an error. */
return 1;
}
+
+SCM atexit_list = SCM_EOL;
+
+LY_DEFINE (ly_atexit, "ly:atexit",
+ 2, 0, 0, (SCM proc, SCM args),
+ "Just before exiting, call the procedure given. "
+"If this is called multiple times, the procedures are called "
+"in LIFO order.")
+{
+ atexit_list = scm_cons (scm_cons (proc, args), atexit_list);
+ scm_gc_protect_object (atexit_list);
+ return SCM_UNSPECIFIED;
+}
+
+LY_DEFINE (ly_do_atexit, "ly:do-atexit",
+ 0, 0, 0, (),
+ "Call the atexit procedures.")
+{
+ for (SCM s = atexit_list; scm_is_pair (s); s = scm_cdr (s))
+ scm_apply_0 (scm_caar (s), scm_cdar (s));
+ return SCM_UNSPECIFIED;
+}
/* Write midi as formatted ascii stream? */
bool do_midi_debugging_global;
bool use_object_keys;
+bool debug_skylines;
/*
Backwards compatibility.
strict_infinity_checking = to_boolean (val);
val = scm_from_bool (to_boolean (val));
}
+ else if (var == ly_symbol2scm ("debug-skylines"))
+ {
+ debug_skylines = to_boolean (val);
+ val = scm_from_bool (to_boolean (val));
+ }
}
ssize const HELP_INDENT = 30;
-/*
- skyline.cc -- implement Skyline_entry and funcs.
+/* skyline.cc -- implement the Skyline class
- source file of the GNU LilyPond music typesetter
-
- (c) 2002--2006 Han-Wen Nienhuys <hanwen@xs4all.nl>
+ source file of the GNU LilyPond music typesetter
+
+ (c) 2006 Joe Neeman <joeneeman@gmail.com>
*/
#include "skyline.hh"
-/*
- A skyline is a shape of the form:
-
-
- * ----
- * | |
- * ---------| |
- * | |
- * | |
- * | |______
- * --------| |___
- *
-
- This file deals with building such skyline structure, and computing
- the minimum distance between two opposing skylines.
-
- Invariants for a skyline:
-
- skyline[...].width_ forms a partition of the real interval, where
- the segments are adjacent, and ascending. Hence we have
-
- skyline.back ().width_[RIGHT] = inf
- skyline[0].width_[LEFT] = -inf
+#include "line-interface.hh"
+
+/* A skyline is a sequence of non-overlapping buildings: something like
+ this:
+ _______
+ / \ ________
+ / \ ________/ \
+ /\ / \ / \
+ / -----/ \ / \
+ / \ / \
+ / ------------/ ----
+ --
+ Each building has a starting position, and ending position, a starting
+ height and an ending height.
+
+ The following invariants are observed:
+ - the start of the first building is at -infinity
+ - the end of the last building is at infinity
+ - if a building has infinite length (ie. the first and last buildings),
+ then its starting height and ending height are equal
+ - the end of one building is the same as the beginning of the next
+ building
+
+ We also allow skylines to point down (the structure is exactly the same,
+ but we think of the part above the line as being filled with mass and the
+ part below as being empty). ::distance finds the minimum distance between
+ an UP skyline and a DOWN skyline.
+
+ Note that we store DOWN skylines upside-down. That is, in order to compare
+ a DOWN skyline with an UP skyline, we need to flip the DOWN skyline first.
+ This means that the merging routine doesn't need to be aware of direction,
+ but the distance routine does.
*/
-const Real EPS = 1e-12;
-
-/*
- TODO: avoid unnecessary fragmentation.
+#define EPS 1e-10
- This is O (n^2), searching and insertion. Could be O (n log n) with
- binsearch.
-*/
-void
-insert_extent_into_skyline (vector<Skyline_entry> *line, Box b, Axis line_axis,
- Direction d)
+static inline bool
+equal (Real x, Real y)
{
- Interval extent = b[line_axis];
- if (extent.is_empty ())
- return;
+ return abs (x - y) < EPS || (isinf (x) && isinf (y) && ((x > 0) == (y > 0)));
+}
- Real stick_out = b[other_axis (line_axis)][d];
+bool
+Skyline::is_legal_skyline () const
+{
+ list<Building>::const_iterator i;
+ Real last_x = -infinity_f;
+ Real last_h = -infinity_f;
+ for (i = buildings_.begin (); i != buildings_.end (); i++)
+ {
+ if (i->iv_[LEFT] != last_x)
+ return false;
+ if (i != buildings_.begin () && !equal (i->start_height_, last_h))
+ return false;
+ last_x = i->iv_[RIGHT];
+ last_h = i->end_height_;
+ }
+ return last_x == infinity_f;
+}
- /*
- Intersect each segment of LINE with EXTENT, and if non-empty, insert relevant segments.
- */
- for (vsize i = line->size (); i--;)
+Building::Building (Real start, Real start_height, Real end_height, Real end, Real max_slope)
+ : iv_ (start, end)
+{
+ start_height_ = start_height;
+ end_height_ = end_height;
+
+ if (isinf (start))
+ assert (isinf (start_height) || start_height == end_height);
+ if (isinf (end))
+ assert (isinf (end_height) || start_height == end_height);
+
+ m_ = (end_height - start_height) / (end - start);
+ if (start_height == end_height)
+ m_ = 0;
+ if (isinf (m_) || isnan (m_))
+ m_ = max_slope * (start_height < end_height ? 1 : -1);
+ assert (abs (m_) <= max_slope);
+
+ if (isinf (start))
{
- Interval w = line->at (i).width_;
- w.intersect (extent);
+ if (isinf (end))
+ b_ = start_height;
+ else
+ b_ = end_height - m_*end;
+ }
+ else
+ b_ = start_height - m_*start;
+}
- if (extent[LEFT] >= w[RIGHT])
- break;
+Real
+Building::height (Real x) const
+{
+ if (isinf (x))
+ return (x > 0) ? end_height_ : start_height_;
+ return m_*x + b_;
+}
- Real my_height = line->at (i).height_;
+Real
+Building::intersection (Building const &other) const
+{
+ return (b_ - other.b_) / (other.m_ - m_);
+}
- if (!w.is_empty ()
- && w.length () > EPS
- && d * (my_height - stick_out) < 0)
- {
- Interval e1 (line->at (i).width_[LEFT], extent[LEFT]);
- Interval e3 (extent[RIGHT], line->at (i).width_[RIGHT]);
+void
+Building::leading_part (Real chop, Real h)
+{
+ assert (chop > iv_[LEFT] && chop <= iv_[RIGHT] && !equal (chop, iv_[LEFT]));
+ assert (equal (h, height (chop)));
+ iv_[RIGHT] = chop;
+ end_height_ = h;
+}
- if (!e3.is_empty () && e3.length () > EPS)
- line->insert (line->begin () + i + 1, Skyline_entry (e3, my_height));
+static void
+skyline_trailing_part (list<Building> *sky, Real x)
+{
+ if (equal (x, sky->front ().iv_[RIGHT]))
+ sky->pop_front ();
+ else
+ assert (x < sky->front ().iv_[RIGHT]);
- line->at (i).height_ = stick_out;
- line->at (i).width_ = w;
- if (!e1.is_empty () && e1.length () > EPS)
- line->insert (line->begin () + i, Skyline_entry (e1, my_height));
- }
+ if (!sky->empty ())
+ {
+ sky->front ().iv_[LEFT] = x;
+ sky->front ().start_height_ = sky->front ().height (x);
}
}
+bool
+Building::obstructs (Building const &other) const
+{
+ if (equal (intersection (other), iv_[LEFT]) || equal (start_height_, other.start_height_))
+ return m_ > other.m_ || (m_ == other.m_ && b_ > other.b_);
+ return start_height_ > other.start_height_;
+}
+
void
-merge_skyline (vector<Skyline_entry> *a1,
- vector<Skyline_entry> const &a2,
- Direction dir)
+Skyline::internal_merge_skyline (list<Building> *s1, list<Building> *s2,
+ list<Building> *const result)
{
- for (vsize i = 0; i < a2.size (); i++)
+ while (!s1->empty ())
{
- Box b;
- b[X_AXIS] = a2[i].width_;
- b[Y_AXIS][dir] = a2[i].height_;
- b[Y_AXIS][-dir] = dir * infinity_f;
-
- insert_extent_into_skyline (a1, b, X_AXIS, dir);
+ if (s2->front ().obstructs (s1->front ()))
+ swap (s1, s2);
+
+ Building b = s1->front ();
+ while (s2->front ().iv_[RIGHT] < b.iv_[RIGHT]
+ && s2->front ().end_height_ <= b.height (s2->front ().iv_[RIGHT]) + EPS)
+ s2->pop_front ();
+
+ /* the front of s2 either intersects with b or it ends after b */
+ Real end = infinity_f;
+ Real s2_end_height = s2->front ().end_height_;
+ Real s1_end_height = b.height (s2->front ().iv_[RIGHT]);
+ if (s2_end_height > s1_end_height + EPS)
+ end = b.intersection (s2->front ());
+ end = min (end, b.iv_[RIGHT]);
+ Real height = b.height (end);
+
+ b.leading_part (end, height);
+ result->push_front (b);
+
+ skyline_trailing_part (s1, end);
+ if (!s1->empty ())
+ s1->front ().start_height_ = height;
+ skyline_trailing_part (s2, end);
}
+ result->reverse ();
}
-vector<Skyline_entry>
-empty_skyline (Direction d)
+static void
+empty_skyline (list<Building> *const ret)
{
- vector<Skyline_entry> skyline;
+ ret->push_front (Building (-infinity_f, -infinity_f, -infinity_f, infinity_f, 0));
+}
- Interval i;
- i.set_empty ();
- i.swap ();
- Skyline_entry e;
- e.width_ = i;
- e.height_ = -d * infinity_f;
- skyline.push_back (e);
- return skyline;
+static void
+single_skyline (Building const &b, list<Building> *const ret, Real max_slope)
+{
+ if (!isinf (b.iv_[RIGHT]))
+ ret->push_front (Building (b.iv_[RIGHT], b.end_height_, -infinity_f, infinity_f, max_slope));
+ ret->push_front (b);
+ if (!isinf (b.iv_[LEFT]))
+ ret->push_front (Building (-infinity_f, -infinity_f, b.start_height_, b.iv_[LEFT], max_slope));
}
-vector<Skyline_entry>
-extents_to_skyline (vector<Box> const &extents, Axis a, Direction d)
+void
+Skyline::internal_build_skyline (list<Building> *buildings, list<Building> *const result)
{
+ vsize size = buildings->size ();
- vector<Skyline_entry> skyline = empty_skyline (d);
+ if (size == 0)
+ {
+ empty_skyline (result);
+ return;
+ }
+ else if (size == 1)
+ {
+ single_skyline (buildings->front (), result, max_slope_);
+ return;
+ }
- /*
- This makes a cubic algorithm (array insertion is O (n),
- searching the array dumbly is O (n), and for n items, we get O (n^3).)
+ list<Building> right_half;
+ list<Building>::iterator i = buildings->begin ();
- We could do a lot better (n log (n), using a balanced tree) but
- that seems overkill for now.
- */
- for (vsize j = extents.size (); j--;)
- insert_extent_into_skyline (&skyline, extents[j], a, d);
+ for (vsize s = 0; s < size/2; s++)
+ i++;
+ right_half.splice (right_half.end (), *buildings, i, buildings->end ());
- return skyline;
+ list<Building> right;
+ list<Building> left;
+ internal_build_skyline (&right_half, &right);
+ internal_build_skyline (buildings, &left);
+ internal_merge_skyline (&right, &left, result);
}
-/*
- minimum distance that can be achieved between baselines. "Clouds" is
- a skyline pointing down.
+Skyline::Skyline ()
+{
+ max_slope_ = 2;
+ sky_ = UP;
+ empty_skyline (&buildings_);
+}
- This is an O (n) algorithm.
-*/
-Real
-skyline_meshing_distance (vector<Skyline_entry> const &buildings,
- vector<Skyline_entry> const &clouds)
+Skyline::Skyline (Direction sky)
{
- int i = buildings.size () -1;
- int j = clouds.size () -1;
+ max_slope_ = 2;
+ sky_ = sky;
+ empty_skyline (&buildings_);
+}
- Real distance = -infinity_f;
+Skyline::Skyline (vector<Box> const &boxes, Axis a, Direction sky)
+{
+ list<Building> bldgs;
+ sky_ = sky;
+ max_slope_ = 2;
- while (i > 0 || j > 0)
+ for (vsize i = 0; i < boxes.size (); i++)
{
- Interval w = buildings[i].width_;
- w.intersect (clouds[j].width_);
+ Interval iv = boxes[i][a];
+ Real height = sky * boxes[i][other_axis (a)][sky];
+ if (!iv.is_empty () && !isinf (height) && !equal (iv[LEFT], iv[RIGHT]))
+ bldgs.push_front (Building (iv[LEFT], height, height, iv[RIGHT], max_slope_));
+ }
+ internal_build_skyline (&bldgs, &buildings_);
+ assert (is_legal_skyline ());
+}
- if (!w.is_empty ())
- distance = max (distance, (buildings[i].height_ - clouds[j].height_));
+void
+Skyline::merge (Skyline const &other)
+{
+ assert (sky_ == other.sky_);
- if (i > 0 && buildings[i].width_[LEFT] >= clouds[j].width_[LEFT])
- i--;
- else if (j > 0 && buildings[i].width_[LEFT] <= clouds[j].width_[LEFT])
- j--;
- }
+ 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_);
+ assert (is_legal_skyline ());
+}
- return distance;
+void
+Skyline::insert (Box const &b, Axis a)
+{
+ list<Building> other_bld;
+ list<Building> my_bld;
+ Interval iv = b[a];
+ Real height = sky_ * b[other_axis (a)][sky_];
+
+ my_bld.splice (my_bld.begin (), buildings_);
+ single_skyline (Building (iv[LEFT], height, height, iv[RIGHT], max_slope_), &other_bld, max_slope_);
+ internal_merge_skyline (&other_bld, &my_bld, &buildings_);
+ assert (is_legal_skyline ());
}
-Skyline_entry::Skyline_entry ()
+void
+Skyline::raise (Real r)
{
- height_ = 0.0;
+ list<Building>::iterator end = buildings_.end ();
+ for (list<Building>::iterator i = buildings_.begin (); i != end; i++)
+ {
+ i->start_height_ += sky_ * r;
+ i->end_height_ += sky_ * r;
+ i->b_ += sky_ * r;
+ }
+ assert (is_legal_skyline ());
}
-Skyline_entry::Skyline_entry (Interval i, Real r)
+Real
+Skyline::distance (Skyline const &other) const
{
- width_ = i;
- height_ = r;
+ assert (sky_ == -other.sky_);
+ list<Building>::const_iterator i = buildings_.begin ();
+ list<Building>::const_iterator j = other.buildings_.begin ();
+
+ Real dist = -infinity_f;
+ while (i != buildings_.end () && j != other.buildings_.end ())
+ {
+ Interval iv = intersection (i->iv_, j->iv_);
+ dist = max (dist, max (i->height (iv[LEFT]) + j->height (iv[LEFT]),
+ i->height (iv[RIGHT]) + j->height (iv[RIGHT])));
+ if (i->iv_[RIGHT] <= j->iv_[RIGHT])
+ i++;
+ else
+ j++;
+ }
+ return dist;
}
-void
-heighten_skyline (vector<Skyline_entry> *buildings, Real ground)
+Real
+Skyline::height (Real airplane) const
{
- for (vsize i = 0; i < buildings->size (); i++)
- buildings->at (i).height_ += ground;
+ assert (!isinf (airplane));
+
+ list<Building>::const_iterator i;
+ for (i = buildings_.begin (); i != buildings_.end (); i++)
+ {
+ if (i->iv_[RIGHT] >= airplane)
+ return sky_ * i->height (airplane);
+ }
+ assert (0);
+ return 0;
}
Real
-skyline_height (vector<Skyline_entry> const &buildings,
- Real airplane,
- Direction sky_dir)
+Skyline::max_height () const
{
- Real h = - sky_dir * infinity_f;
+ Skyline s (-sky_);
+ s.set_minimum_height (0);
+ return sky_ * distance (s);
+}
- /*
- Ugh! linear, should be O(log n).
- */
- for (vsize i = 0; i < buildings.size (); i++)
- if (buildings[i].width_.contains (airplane))
- h = sky_dir * max (sky_dir * h,
- sky_dir * buildings[i].height_);
-
- return h;
+void
+Skyline::set_minimum_height (Real h)
+{
+ Skyline s (sky_);
+ s.buildings_.front ().start_height_ = h*sky_;
+ s.buildings_.front ().end_height_ = h*sky_;
+ s.buildings_.front ().b_ = h*sky_;
+ merge (s);
}
+Stencil
+Skyline::stencil ()
+{
+ Stencil ret;
+ for (list<Building>::iterator i = buildings_.begin (); i != buildings_.end (); i++)
+ {
+ if (!isinf (i->iv_.length ()))
+ {
+ Stencil line = Line_interface::make_line (0.1,
+ Offset (i->iv_[LEFT], sky_*i->start_height_),
+ Offset (i->iv_[RIGHT], sky_*i->end_height_));
+ ret.add_stencil (line);
+ }
+ }
+ return ret;
+}
#include "tweak-registration.hh"
#include "warn.hh"
+extern bool debug_skylines;
+
System::System (System const &src, int count)
: Spanner (src, count)
{
System *system = dynamic_cast<System *> (broken_intos_[i]);
system->post_processing ();
+ system->build_skylines ();
+ if (i > 0)
+ {
+ System *prev = dynamic_cast<System*> (broken_intos_[i-1]);
+ Real r = prev->skylines_[DOWN].distance (system->skylines_[UP]);
+ system->set_property ("skyline-distance", scm_from_double (r));
+ }
scm_vector_set_x (lines, scm_from_int (i),
system->get_paper_system ());
Stencil sys_stencil (Box (x, y),
scm_cons (ly_symbol2scm ("combine-stencil"),
exprs));
+ if (debug_skylines)
+ {
+ sys_stencil.add_stencil (skylines_[UP].stencil ().in_color (255, 0, 0));
+ sys_stencil.add_stencil (skylines_[DOWN].stencil ().in_color (0, 255, 0));
+ }
Grob *left_bound = this->get_bound (LEFT);
SCM prop_init = left_bound->get_property ("line-break-system-details");
/* information that the page breaker might need */
Grob *right_bound = this->get_bound (RIGHT);
+ pl->set_property ("skyline-distance", get_property ("skyline-distance"));
pl->set_property ("page-break-permission", right_bound->get_property ("page-break-permission"));
pl->set_property ("page-turn-permission", right_bound->get_property ("page-turn-permission"));
pl->set_property ("page-break-penalty", right_bound->get_property ("page-break-penalty"));
return dynamic_cast<System*> (system_grob);
}
+void
+System::build_skylines ()
+{
+ vector<Box> boxes;
+ for (vsize i = 0; i < all_elements_->size (); i++)
+ {
+ Grob *g = all_elements_->grob (i);
+ if (!unsmob_stencil (g->get_property ("stencil")))
+ continue;
+
+ Interval xiv = g->extent (this, X_AXIS);
+ Interval yiv = g->extent (this, Y_AXIS);
+ if (!xiv.is_empty () && !yiv.is_empty ())
+ boxes.push_back (Box (xiv, yiv));
+ }
+
+ skylines_[UP] = Skyline (boxes, X_AXIS, UP);
+ skylines_[DOWN] = Skyline (boxes, X_AXIS, DOWN);
+}
ADD_INTERFACE (System, "system-interface",
"columns "
"pure-Y-extent "
"spaceable-staves "
+ "skyline-distance "
)
if (i == chord_outlines_.end ())
programming_error ("Can't find chord outline");
else
- attachments[d] = skyline_height ((*i).second, y, -d);
+ attachments[d] = i->second.height (y);
}
while (flip (&d) != LEFT);
}
Tuple2<int> key (column_rank, int (dir));
-
- chord_outlines_[key] = empty_skyline (-dir);
-
- if (bounds[0]->break_status_dir ())
- {
- Real x = robust_relative_extent (bounds[0], x_refpoint_, X_AXIS)[-dir];
- chord_outlines_[key].at (0).height_ = x;
- }
- else
- {
- Interval x;
- for (vsize j = 0; j < head_boxes.size (); j++)
- {
- x.unite (head_boxes[j][X_AXIS]);
- }
-
- chord_outlines_[key].at (0).height_ = x[dir];
- }
-
- for (vsize i = 0; i < boxes.size (); i++)
- insert_extent_into_skyline (&chord_outlines_[key] ,
- boxes[i], Y_AXIS, -dir);
if (stem
&& !Stem::is_invisible (stem))
Direction stemdir = get_grob_direction (stem);
y.add_point (Stem::head_positions (stem)[-stemdir]
* staff_space * .5);
-
- insert_extent_into_skyline (&chord_outlines_[key], Box (x,y), Y_AXIS, -dir);
+
+ boxes.push_back (Box (x, y));
stem_extents_[key].unite (Box (x,y));
{
Box flag_box = Stem::get_translated_flag (stem).extent_box ();
flag_box.translate( Offset (x[RIGHT], X_AXIS));
- insert_extent_into_skyline (&chord_outlines_[key], flag_box,
- Y_AXIS, -dir);
+ boxes.push_back (flag_box);
}
}
else if (stem)
Interval y_ext;
for (vsize j = 0; j < head_boxes.size (); j++)
y_ext.unite (head_boxes[j][Y_AXIS]);
-
- insert_extent_into_skyline (&chord_outlines_[key],
- Box (x_ext, y_ext),
- Y_AXIS, -dir);
+
+ boxes.push_back (Box (x_ext, y_ext));
}
Direction updowndir = DOWN;
}
if (!x.is_empty ())
- insert_extent_into_skyline (&chord_outlines_[key],
- Box (x,y),
- Y_AXIS, -dir);
+ boxes.push_back (Box (x, y));
}
while (flip (&updowndir) != DOWN);
+ chord_outlines_[key] = Skyline (boxes, Y_AXIS, -dir);
+ if (bounds[0]->break_status_dir ())
+ {
+ Real x = robust_relative_extent (bounds[0], x_refpoint_, X_AXIS)[-dir];
+ chord_outlines_[key].set_minimum_height (x);
+ }
+ else
+ {
+ Interval x;
+ for (vsize j = 0; j < head_boxes.size (); j++)
+ {
+ x.unite (head_boxes[j][X_AXIS]);
+ }
+
+ chord_outlines_[key].set_minimum_height (x[dir]);
+ }
+
head_extents_[key].set_empty ();
for (vsize i = 0; i < head_boxes.size (); i++)
{
set_chord_outline (heads, head_dir);
- Real extremal = head_dir * infinity_f;
-
Tuple2<int> head_key (column_rank, head_dir);
Tuple2<int> open_key (column_rank, -head_dir);
-
- for (vsize i = 0; i < chord_outlines_[head_key].size (); i++)
- {
- extremal = head_dir * min (head_dir * extremal,
- head_dir * chord_outlines_[head_key][i].height_);
- }
+ Real extremal = chord_outlines_[head_key].max_height ();
- Skyline_entry right_entry;
- right_entry.width_.set_full ();
- right_entry.height_ = extremal - head_dir * 1.5;
-
- chord_outlines_[open_key].push_back (right_entry);
+ chord_outlines_[open_key] = Skyline (head_dir);
+ chord_outlines_[open_key].set_minimum_height (extremal - head_dir * 1.5);
}
(non-musical ,boolean? "True if the grob belongs in a NonMusicalPaperColumn.")
(number-type ,symbol? "Type of numbers to use in label. Choices
include @code{roman-lower}, @code{roman-upper}, and @code{arabic}.")
+ (outside-staff-priority ,number? "When set, the grob will be positioned outside the staff
+in such a way as to avoid all collisions. In case of a potential collision, the grob with
+the smaller outside-staff-priority will be closer to the staff.")
(packed-spacing ,boolean? "If set, the notes are spaced as
tightly as possible.")
(padding ,ly:dimension? "Add this much extra space between
(spaceable-staves ,ly:grob-array? "Objects to be spaced during page layout.")
+ (skyline-distance ,number? "The distance between this staff and the next one, as determined by a skyline algorithm.")
+ (skyline-spacing ,boolean? "When true, this axis-group will vertically space its children
+using a skyline algorithm.")
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(axes . (0 1))
(X-extent . ,ly:axis-group-interface::width)
(Y-extent . ,ly:axis-group-interface::height)
+ (skyline-spacing . #t)
(meta . ((class . System)
(interfaces . (system-interface
axis-group-interface))))))
(Y-offset . ,ly:hara-kiri-group-spanner::force-hara-kiri-callback)
(Y-extent . ,ly:hara-kiri-group-spanner::y-extent)
(X-extent . ,ly:axis-group-interface::width)
+ (skyline-spacing . #t)
(meta . ((class . Spanner)
(interfaces . (axis-group-interface
hara-kiri-group-interface
--- /dev/null
+(define-module (scm graphviz)
+ #:use-module (lily)
+ #:export (make-graph add-node add-edge))
+
+(define (make-graph filename)
+ (let ((empty-graph (list->vector (list filename '() '() '()))))
+ (ly:atexit write-graph (list empty-graph))
+ empty-graph))
+
+(define (filename g) (vector-ref g 0))
+(define (nodes g) (vector-ref g 1))
+(define (edges g) (vector-ref g 2))
+(define (clusters g) (vector-ref g 3))
+
+(define (add-node graph label)
+ (let ((ns (nodes graph)))
+ (vector-set! graph 1 (cons `(,(length ns) . ,label) ns))
+ (length ns)))
+
+(define (add-edge graph node1 node2)
+ (vector-set! graph 2 (cons `(,node1 . ,node2) (edges graph))))
+
+(define (write-graph graph)
+ (let ((out (open-file (filename graph) "w"))
+ (ns (nodes graph))
+ (es (edges graph))
+ (cc (clusters graph)))
+ (ly:message (format "writing graph ~s..." (filename graph)))
+ (display "digraph G {\nrankdir=\"LR\"\nnode [shape=rectangle]\n" out)
+ (map (lambda (n) (display (format "~a [label=\"~a\"]\n" (car n) (cdr n)) out))
+ ns)
+ (map (lambda (e) (display (format "~a -> ~a\n" (car e) (cdr e)) out))
+ es)
+ (display "}" out)))
+
\ No newline at end of file
"Minimum distance between `line' reference position and `next-line'
reference position. If next-line is #f, return #f."
(and next-line
- (max 0 (- (+ (interval-end (paper-system-extent next-line Y))
- (if ignore-padding 0 (line-next-padding line next-line layout)))
- (interval-start (paper-system-extent line Y))))))
+ (let ((non-skyline-distance (- (interval-end (paper-system-extent next-line Y))
+ (interval-start (paper-system-extent line Y)))))
+ (max 0 (+ (ly:prob-property next-line 'skyline-distance non-skyline-distance)
+ (if ignore-padding 0 (line-next-padding line next-line layout)))))))
(define (line-ideal-distance line next-line layout ignore-padding)
"Ideal distance between `line' reference position and `next-line'
(debug-lexer #f "debug the flex lexer")
(debug-midi #f "generate human readable MIDI")
(debug-parser #f "debug the bison parser")
+ (debug-skylines #f "debug skylines")
(delete-intermediate-files #f
"delete unusable PostScript files")
(dump-signatures #f "dump output signatures of each system")
(ly:error (_ "failed files: ~S") (string-join failed))
(exit 1))
(begin
+ (ly:do-atexit)
;; HACK: be sure to exit with single newline
(ly:message "")
(exit 0)))))
projects / lilypond.git / commitdiff