X-Git-Url: https://git.donarmstrong.com/?a=blobdiff_plain;f=lily%2Fsimple-spacer.cc;h=a44e9f8d7546d8262d7a74af30fae5226a9f82c9;hb=5d7a663ab5450018118c99fc48263c18f2df52dc;hp=4910fd27de868d60814da505a9dc28a9c47e1c3a;hpb=28b274e6d311e56087794a973e82ebd1185f923e;p=lilypond.git diff --git a/lily/simple-spacer.cc b/lily/simple-spacer.cc index 4910fd27de..a44e9f8d75 100644 --- a/lily/simple-spacer.cc +++ b/lily/simple-spacer.cc @@ -3,16 +3,15 @@ source file of the GNU LilyPond music typesetter - (c) 1999 Han-Wen Nienhuys + (c) 1999--2003 Han-Wen Nienhuys TODO: - add support for different stretch/shrink constants? - - Use force as a minimizing function, and use it to discourage mixes of - wide and tight lines. */ - +#include #include +#include // isinf #include "simple-spacer.hh" #include "paper-column.hh" @@ -20,14 +19,54 @@ #include "rod.hh" #include "warn.hh" #include "column-x-positions.hh" +#include "spaceable-grob.hh" #include "dimensions.hh" + +/* + A simple spacing constraint solver. The approach: + + Stretch the line uniformly until none of the constraints (rods) + block. It then is very wide. + + Compress until the next constraint blocks, + + Mark the springs over the constrained part to be non-active. + + Repeat with the smaller set of non-active constraints, until all + constraints blocked, or until the line is as short as desired. + + This is much simpler, and much much faster than full scale + Constrained QP. On the other hand, a situation like this will not + be typeset as dense as possible, because + + c4 c4 c4 c4 + veryveryverylongsyllable2 veryveryverylongsyllable2 + " "4 veryveryverylongsyllable2 syllable4 + + + can be further compressed to + + + c4 c4 c4 c4 + veryveryverylongsyllable2 veryveryverylongsyllable2 + " "4 veryveryverylongsyllable2 syllable4 + + + Perhaps this is not a bad thing, because the 1st looks better anyway. */ + + Simple_spacer::Simple_spacer () { - force_f_ = 0.; - indent_f_ =0.0; - default_space_f_ = 20 PT; - compression_energy_factor_f_ = 3.0; + /* + Give an extra penalty for compression. Needed to avoid compressing + tightly spaced lines. + */ + compression_penalty_b_ = false; + active_count_ = 0; + force_ = 0.; + indent_ =0.0; + default_space_ = 20 PT; } void @@ -38,18 +77,34 @@ Simple_spacer::add_rod (int l, int r, Real dist) programming_error ("Weird minimum distance. Ignoring"); return; } - - + Real c = range_stiffness (l,r); + if (isinf (c)) + { + /* + If a spring is fixed, we have to do something here: + we let the rod override the spring. + */ + Real total_dist = 0.; + for (int i = l ; i < r; i++) + total_dist += springs_[i].ideal_; + + if (total_dist < dist) + for (int i = l ; i < r; i++) + springs_[i].ideal_ *= dist/total_dist; + + return; + } + Real d = range_ideal_len (l,r); Real block_stretch = dist - d; Real block_force = c * block_stretch; - force_f_ = force_f_ >? block_force; + force_ = force_ >? block_force; for (int i=l; i < r; i++) - springs_[i].block_force_f_ = block_force >? - springs_[i].block_force_f_ ; + springs_[i].block_force_ = block_force >? + springs_[i].block_force_ ; } Real @@ -57,7 +112,7 @@ Simple_spacer::range_ideal_len (int l, int r) const { Real d =0.; for (int i=l; i < r; i++) - d += springs_[i].ideal_f_; + d += springs_[i].ideal_; return d; } @@ -66,7 +121,10 @@ Simple_spacer::range_stiffness (int l, int r) const { Real den =0.0; for (int i=l; i < r; i++) - den += 1 / springs_[i].hooke_f_; + { + if (springs_[i].active_b_) + den += 1 / springs_[i].hooke_; + } return 1 / den; } @@ -78,7 +136,7 @@ Simple_spacer::active_blocking_force () const for (int i=0; i < springs_.size (); i++) if (springs_[i].active_b_) { - bf = bf >? springs_[i].block_force_f_; + bf = bf >? springs_[i].block_force_; } return bf; } @@ -86,23 +144,20 @@ Simple_spacer::active_blocking_force () const Real Simple_spacer::active_springs_stiffness () const { - Real den = 0.0; - for (int i=0; i < springs_.size (); i++) - if (springs_[i].active_b_) - { - den += 1 / springs_[i].hooke_f_; - } - return 1/den; + return range_stiffness (0, springs_.size ()); } void Simple_spacer::set_active_states () { - // safe, since - // force is only copied. + /* float comparison is safe, since force is only copied. */ for (int i=0 ; i = force_f_) - springs_[i].active_b_ = false; + if (springs_[i].active_b_ + && springs_[i].block_force_ >= force_) + { + springs_[i].active_b_ = false; + active_count_ --; + } } Real @@ -110,26 +165,15 @@ Simple_spacer::configuration_length () const { Real l =0.; for (int i=0; i < springs_.size (); i++) - l += springs_[i].length (force_f_); + l += springs_[i].length (force_); return l; } -Real -Spring_description::length (Real f) const -{ - if (!active_b_) - f = block_force_f_; - return ideal_f_ + f / hooke_f_ ; -} - bool Simple_spacer::active_b () const { - for (int i=0; i < springs_.size (); i++) - if (springs_[i].active_b_) - return true; - return false; + return active_count_; } void @@ -137,12 +181,12 @@ Simple_spacer::my_solve_linelen () { while (active_b ()) { - force_f_ = active_blocking_force (); + force_ = active_blocking_force (); Real conf = configuration_length (); - if (conf < line_len_f_) + if (conf < line_len_) { - force_f_ += (line_len_f_ - conf) * active_springs_stiffness (); + force_ += (line_len_ - conf) * active_springs_stiffness (); break; } else @@ -156,9 +200,9 @@ Simple_spacer::my_solve_natural_len () { while (active_b ()) { - force_f_ = active_blocking_force () >? 0.0; + force_ = active_blocking_force () >? 0.0; - if (force_f_ < 1e-8) // ugh., + if (force_ < 1e-8) // ugh., break; set_active_states (); @@ -166,114 +210,199 @@ Simple_spacer::my_solve_natural_len () } void -Simple_spacer::add_columns (Link_array cols) +Simple_spacer::add_columns (Link_array const &icols) { + Link_array cols(icols); + + for (int i = cols.size (); i--;) + if (gh_pair_p (cols[i]->get_grob_property ("between-cols"))) + { + loose_cols_.push (cols[i]); + cols.del (i); + } + + spaced_cols_ = cols; for (int i=0; i < cols.size () - 1; i++) { - Paper_column * c = cols [i]; - Column_spring *to_next = 0; - for (int j =0; !to_next && j < c->spring_arr_drul_[RIGHT].size( ); j++) - { - Column_spring &sp = c->spring_arr_drul_[RIGHT] [j]; - if (sp.other_l_ != cols[i+1]) - continue; + Spring_smob *spring = 0; - to_next = &sp; + for (SCM s = cols[i]->get_grob_property ("ideal-distances"); + !spring && gh_pair_p (s); + s = ly_cdr (s)) + { + Spring_smob *sp = unsmob_spring (ly_car (s)); + + + if (sp->other_ == cols[i+1]) + spring = sp; } Spring_description desc; - if (to_next) + if (spring) { - desc.hooke_f_ = to_next->strength_f_; - desc.ideal_f_ = to_next->distance_f_; + desc.ideal_ = spring->distance_; + desc.hooke_ = spring->strength_; } else { - desc.hooke_f_ = 1.0; - desc.ideal_f_ = default_space_f_; + programming_error (_f("No spring between column %d and next one", + Paper_column::get_rank (cols[i]) + )); + desc.hooke_ = 1.0; + desc.ideal_ = default_space_; + + continue; } if (!desc.sane_b ()) { - programming_error ("Insane spring."); - continue; + programming_error ("Insane spring found. Setting to unit spring."); + + desc.hooke_ = 1.0; + desc.ideal_ = 1.0; + } + + if (isinf (desc.hooke_)) + { + desc.active_b_ = false; + springs_.push (desc); + } + else + { + desc.block_force_ = - desc.hooke_ * desc.ideal_; // block at distance 0 + springs_.push (desc); + + active_count_ ++; + } + + if (spring->expand_only_b_) + { + compression_penalty_b_ = true; } - desc.block_force_f_ = - desc.hooke_f_ * desc.ideal_f_; // block at distance 0 - springs_.push (desc); } for (int i=0; i < cols.size () - 1; i++) { - Array * rods = &cols [i]->minimal_dists_arr_drul_[RIGHT]; - for (int j =0; j < rods->size( ); j++) + for (SCM s = Spaceable_grob::get_minimum_distances (cols[i]); + gh_pair_p (s); s = ly_cdr (s)) { - int oi = cols.find_i (rods->elem (j).other_l_ ); + Grob * other = unsmob_grob (ly_caar (s)); + int oi = cols.find_index (other); if (oi >= 0) { - add_rod (i, oi, rods->elem (j).distance_f_); + add_rod (i, oi, gh_scm2double (ly_cdar (s))); } } } - if (line_len_f_ < 0) - my_solve_natural_len (); - else - my_solve_linelen (); + } +/* + + TODO: should a add penalty for widely varying spring forces (caused + by constraints, eg. + + + ===== + | | + o|o| x ##x + + + The ## forces the notes apart; we shouldn't allow the O's to touch + this closely. + + */ void -Simple_spacer::solve (Column_x_positions *positions) const +Simple_spacer::solve (Column_x_positions *positions, bool ragged) { - positions->energy_f_ = energy_f (); // abs (force_f_); - positions->force_f_ = force_f_; + /* + TODO: should support natural length on only the last line. + */ + ragged = ragged || (line_len_ < 0) ; + if (ragged) + my_solve_natural_len (); + else + my_solve_linelen (); + + positions->force_ = force_; + /* + We used to have a penalty for compression, no matter what, but that + fucked up wtk1-fugue2 (taking 3 full pages.) + */ - positions->config_.push (indent_f_); + positions->config_.push (indent_); for (int i=0; i config_.push (positions->config_.top () + springs_[i].length (force_f_)); + Real l = springs_[i].length ((ragged) ? 0.0 : force_); + positions->config_.push (positions->config_.top () + l); + /* + we have l>= 0 here, up to rounding errors + */ } - positions->satisfies_constraints_b_ = (line_len_f_ < 0) || active_b (); -} + /* + For raggedright, we must have a measure of music density: this is + to prevent lots of short lines (which all have force = 0). + */ + if (ragged && line_len_ > 0) + { + Real len = positions->config_.top (); + positions->force_ = (line_len_ - len) * active_springs_stiffness (); + } + positions->cols_ = spaced_cols_; + positions->loose_cols_ = loose_cols_; + positions->satisfies_constraints_b_ = (line_len_ < 0) || active_b (); -Spring_description::Spring_description( ) -{ - ideal_f_ =0.0; - hooke_f_ =0.0; - active_b_ = true; - block_force_f_ = 0.0; + /* + Check if breaking constraints are met. + */ + bool break_satisfy = true; + int sz = positions->cols_.size (); + for (int i = sz; i--; ) + { + SCM p = positions->cols_[i]->get_grob_property( "penalty"); + if (gh_number_p (p)) + { + if (gh_scm2double (p) < -9999) + break_satisfy = break_satisfy && (i == 0 || i == sz -1); + if (gh_scm2double (p) > 9999) + break_satisfy = break_satisfy && !(i == 0 || i == sz -1); + } + + } + + positions->satisfies_constraints_b_ = + positions->satisfies_constraints_b_ && break_satisfy; + + if (ragged && force_ < 0) + positions->satisfies_constraints_b_ = false; } -Real -Spring_description::energy_f (Real force) const +/****************************************************************/ + +Spring_description::Spring_description () { - Real stretch = (force >? block_force_f_) / hooke_f_; - Real e = 0.5 * stretch * stretch * hooke_f_; - return e; + ideal_ =0.0; + hooke_ =0.0; + active_b_ = true; + block_force_ = 0.0; } + bool Spring_description::sane_b () const { - return (hooke_f_ > 0) && ! isinf (ideal_f_) && !isnan (ideal_f_); + return (hooke_ > 0) && !isinf (ideal_) && !isnan (ideal_); } - Real -Simple_spacer::energy_f () const +Spring_description::length (Real f) const { - Real e =0.; - - for (int i=0; i