2 simple-spacer.cc -- implement Simple_spacer
4 source file of the GNU LilyPond music typesetter
6 (c) 1999--2004 Han-Wen Nienhuys <hanwen@cs.uu.nl>
9 - add support for different stretch/shrink constants?
14 #include <libc-extension.hh> // isinf
16 #include "simple-spacer.hh"
17 #include "paper-column.hh"
21 #include "column-x-positions.hh"
22 #include "spaceable-grob.hh"
23 #include "dimensions.hh"
27 A simple spacing constraint solver. The approach:
29 Stretch the line uniformly until none of the constraints (rods)
30 block. It then is very wide.
32 Compress until the next constraint blocks,
34 Mark the springs over the constrained part to be non-active.
36 Repeat with the smaller set of non-active constraints, until all
37 constraints blocked, or until the line is as short as desired.
39 This is much simpler, and much much faster than full scale
40 Constrained QP. On the other hand, a situation like this will not
41 be typeset as dense as possible, because
44 veryveryverylongsyllable2 veryveryverylongsyllable2
45 " "4 veryveryverylongsyllable2 syllable4
48 can be further compressed to
52 veryveryverylongsyllable2 veryveryverylongsyllable2
53 " "4 veryveryverylongsyllable2 syllable4
56 Perhaps this is not a bad thing, because the 1st looks better anyway. */
59 Simple_spacer::Simple_spacer ()
62 Give an extra penalty for compression. Needed to avoid compressing
68 default_space_ = 20 PT;
72 Simple_spacer::add_rod (int l, int r, Real dist)
74 if (isinf (dist) || isnan (dist))
76 programming_error ("Weird minimum distance. Ignoring");
80 Real c = range_stiffness (l,r);
84 If a spring is fixed, we have to do something here:
85 we let the rod override the spring.
88 for (int i = l ; i < r; i++)
89 total_dist += springs_[i].ideal_;
91 if (total_dist < dist)
92 for (int i = l ; i < r; i++)
93 springs_[i].ideal_ *= dist/total_dist;
98 Real d = range_ideal_len (l,r);
99 Real block_stretch = dist - d;
101 Real block_force = c * block_stretch;
102 force_ = force_ >? block_force;
104 for (int i=l; i < r; i++)
105 springs_[i].block_force_ = block_force >?
106 springs_[i].block_force_ ;
110 Simple_spacer::range_ideal_len (int l, int r) const
113 for (int i=l; i < r; i++)
114 d += springs_[i].ideal_;
119 Simple_spacer::range_stiffness (int l, int r) const
122 for (int i=l; i < r; i++)
124 if (springs_[i].is_active_)
125 den += 1 / springs_[i].hooke_;
132 Simple_spacer::active_blocking_force () const
134 Real bf = - infinity_f;
135 for (int i=0; i < springs_.size (); i++)
136 if (springs_[i].is_active_)
138 bf = bf >? springs_[i].block_force_;
144 Simple_spacer::active_springs_stiffness () const
146 Real stiff = range_stiffness (0, springs_.size ());
150 all springs are inactive. Take the stiffness of the
151 latest spring to block.
154 Real max_block_force = -infinity_f;
156 for (int i=0; i < springs_.size (); i++)
158 if (springs_[i].block_force_ > max_block_force)
161 max_block_force = springs_[i].block_force_;
165 stiff = springs_[max_i].hooke_;
171 Simple_spacer::set_active_states ()
173 /* float comparison is safe, since force is only copied. */
174 for (int i=0 ; i <springs_.size (); i++)
175 if (springs_[i].is_active_
176 && springs_[i].block_force_ >= force_)
178 springs_[i].is_active_ = false;
184 Simple_spacer::configuration_length () const
187 for (int i=0; i < springs_.size (); i++)
188 l += springs_[i].length (force_);
194 Simple_spacer::is_active () const
196 return active_count_;
200 Simple_spacer::my_solve_linelen ()
204 force_ = active_blocking_force ();
205 Real conf = configuration_length ();
207 if (conf < line_len_)
209 force_ += (line_len_ - conf) * active_springs_stiffness ();
213 set_active_states ();
219 Simple_spacer::my_solve_natural_len ()
221 Real line_len_force = 0.0;
225 force_ = active_blocking_force () >? 0.0;
226 Real conf = configuration_length ();
228 if (conf < line_len_)
230 line_len_force = force_
232 * active_springs_stiffness();
235 if (force_ < 1e-8) // ugh.,
238 set_active_states ();
241 force_ = line_len_force;
244 LY_DEFINE(ly_solve_spring_rod_problem, "ly:solve-spring-rod-problem",
245 4, 1, 0, (SCM springs, SCM rods, SCM length, SCM ragged),
246 "Solve a spring and rod problem for @var{count} objects, that "
247 "are connected by @var{count-1} springs, and an arbitrary number of rods "
248 "Springs have the format (ideal, hooke) and rods (idx1, idx2, distance) "
249 "@var{length} is a number, @var{ragged} a boolean "
250 "Return: a list containing the force (#f for non-satisfied constraints) "
251 "followed by the @var{spring-count}+1 positions of the objects. "
254 int len = scm_ilength (springs);
256 return scm_list_2 (scm_from_double (0.0), scm_from_double (0.0));
258 SCM_ASSERT_TYPE (len >= 0, springs, SCM_ARG1, __FUNCTION__, "list of springs");
259 SCM_ASSERT_TYPE (scm_ilength (rods) >= 0, rods, SCM_ARG2, __FUNCTION__, "list of rods");
260 SCM_ASSERT_TYPE (scm_is_number (length) || length == SCM_BOOL_F,
261 length, SCM_ARG3, __FUNCTION__, "number or #f");
264 bool is_ragged = ragged == SCM_BOOL_T;
265 Simple_spacer spacer;
266 for (SCM s = springs; ly_c_pair_p (s); s = ly_cdr (s))
268 Real ideal = scm_to_double (ly_caar (s));
269 Real hooke = scm_to_double (ly_cadar (s));
271 spacer.add_spring (ideal, hooke);
274 for (SCM s = rods; ly_c_pair_p (s); s = ly_cdr (s))
276 SCM entry = ly_car (s);
277 int l = scm_to_int (ly_car (entry));
278 int r = scm_to_int (ly_cadr (entry));
279 entry = ly_cddr (entry);
281 Real distance = scm_to_double (ly_car (entry));
282 spacer.add_rod (l, r, distance);
285 spacer.line_len_ = scm_to_double (length);
288 spacer.my_solve_natural_len ();
290 spacer.my_solve_linelen ();
294 for (int i = 0; i < spacer.springs_.size(); i++)
296 Real l = spacer.springs_[i].length ((is_ragged) ? 0.0 : spacer.force_);
297 posns.push (posns.top() + l);
300 SCM force_return = SCM_BOOL_F;
301 if (!isinf (spacer.force_)
302 && spacer.is_active ())
304 force_return = scm_from_double (spacer.force_);
308 for (int i = posns.size(); i--;)
310 retval = scm_cons (scm_from_double (posns[i]), retval);
313 retval = scm_cons (force_return, retval);
318 /****************************************************************/
320 Spring_description::Spring_description ()
330 Spring_description::is_sane () const
334 && !isinf (ideal_) && !isnan (ideal_);
338 Spring_description::length (Real f) const
342 return ideal_ + f / hooke_ ;
344 /****************************************************************/
349 TODO: should a add penalty for widely varying spring forces (caused
358 The ## forces the notes apart; we shouldn't allow the O's to touch
363 Simple_spacer_wrapper::solve (Column_x_positions *positions, bool ragged)
366 spacer_->my_solve_natural_len ();
368 spacer_->my_solve_linelen ();
370 positions->force_ = spacer_->force_;
373 We used to have a penalty for compression, no matter what, but that
374 fucked up wtk1-fugue2 (taking 3 full pages.)
376 positions->config_.push (spacer_->indent_);
377 for (int i=0; i < spacer_->springs_.size (); i++)
379 Real l = spacer_->springs_[i].length ((ragged) ? 0.0 : spacer_->force_);
380 positions->config_.push (positions->config_.top () + l);
382 we have l>= 0 here, up to rounding errors
387 For raggedright, we must have a measure of music density: this is
388 to prevent lots of short lines (which all have force = 0).
392 positions->satisfies_constraints_ =
393 positions->config_.top () < spacer_->line_len_ ;
397 positions->cols_ = spaced_cols_;
398 positions->loose_cols_ = loose_cols_;
399 positions->satisfies_constraints_ =
400 positions->satisfies_constraints_ && spacer_->is_active ();
403 Check if breaking constraints are met.
405 bool break_satisfy = true;
406 int sz = positions->cols_.size ();
407 for (int i = sz; i--; )
409 SCM p = positions->cols_[i]->get_property ( "penalty");
410 if (scm_is_number (p))
412 if (scm_to_double (p) < -9999)
413 break_satisfy = break_satisfy && (i == 0 || i == sz -1);
414 if (scm_to_double (p) > 9999)
415 break_satisfy = break_satisfy && !(i == 0 || i == sz -1);
420 positions->satisfies_constraints_ =
421 positions->satisfies_constraints_ && break_satisfy;
425 Simple_spacer::add_spring (Real ideal, Real hooke)
427 Spring_description desc;
431 if (!desc.is_sane ())
433 programming_error ("Insane spring found. Setting to unit spring.");
441 desc.is_active_ = false;
448 desc.block_force_ = - desc.hooke_ * desc.ideal_; // block at distance 0
452 springs_.push (desc);
456 Simple_spacer_wrapper::add_columns (Link_array<Grob> const &icols)
458 Link_array<Grob> cols (icols);
460 for (int i = cols.size (); i--;)
461 if (ly_c_pair_p (cols[i]->get_property ("between-cols")))
463 loose_cols_.push (cols[i]);
468 for (int i=0; i < cols.size () - 1; i++)
470 Spring_smob *spring = 0;
472 for (SCM s = cols[i]->get_property ("ideal-distances");
473 !spring && ly_c_pair_p (s);
476 Spring_smob *sp = unsmob_spring (ly_car (s));
479 if (sp->other_ == cols[i+1])
484 programming_error (_f ("No spring between column %d and next one",
485 Paper_column::get_rank (cols[i])
488 Real ideal = (spring) ? spring->distance_ : spacer_->default_space_;
489 Real hooke = (spring) ? spring->strength_ : 1.0;
491 spacer_->add_spring (ideal, hooke);
494 for (int i=0; i < cols.size () - 1; i++)
496 for (SCM s = Spaceable_grob::get_minimum_distances (cols[i]);
497 ly_c_pair_p (s); s = ly_cdr (s))
499 Grob * other = unsmob_grob (ly_caar (s));
500 int oi = cols.find_index (other);
503 spacer_->add_rod (i, oi, scm_to_double (ly_cdar (s)));
509 Simple_spacer_wrapper::Simple_spacer_wrapper ()
511 spacer_ = new Simple_spacer ();
514 Simple_spacer_wrapper::~Simple_spacer_wrapper ()
520 Simple_spacer_wrapper::Simple_spacer_wrapper (Simple_spacer_wrapper const&)