|
The paper is here. 'Optimal Line Breaking in Music', by Wael A. Hegazy and John S. Gourlay of the Ohio State University, 1987: fifteen typed pages, scanned from somebody's reading copy, complete with underlinings and a few pencilled notes in the margins. It's out of print and it isn't online, and I'd been looking for it far and wide. In the end Ulrik Bodén, owner of Musikboden and one of Ooloi's sponsors, tracked down a copy and sent it to me. Once again the small circle of friends around this project has done what searching couldn't, and I'm very grateful. Under the last post, Magnus Johansson asked whether I'd had the chance to study it yet. I have, and this is what I found. First, a word about how I look at other programs, since several of them appear below. I don't run Dorico, MuseScore or LilyPond, and I don't intend to. That isn't disdain. I read what can be read: source code where it's open, development diaries where their authors have published them, forum posts where a decision has been explained. I read them as I read the source of gRPC or the JVM, to understand how something was built and, above all, why. What I don't do is examine the latest release to see what I'm up against, because I'm not up against anything. Ooloi isn't a feature race. I'm trying to build an engine for music notation in which the difficult parts are dealt with underneath, once and properly, so that whoever builds on it doesn't have to. If it works, it'll be because of what Ooloi is rather than what it does. Casting off and horizontal spacing are where reading other programs is most illuminating. Casting off is the engraver's term for deciding where each system ends; horizontal spacing is how the notes within a system share out its width. Between them they decide whether a page reads evenly or lurches, and whether the last system of a movement is full or holds two forlorn bars. A player takes all of that in before reading a single note. Every notation program has to answer the question, the answers differ, and the reasons for the differences say a great deal about the architectures behind them. The Other Ninety Per CentIn September 1985 Jon Bentley's Programming Pearls column in Communications of the ACM collected a page of programmers' aphorisms. One of them, credited to Tom Cargill of Bell Labs, has outlived most of the others: 'The first 90 percent of the code accounts for the first 90 percent of the development time. The remaining 10 percent of the code accounts for the other 90 percent of the development time.' Engravers have their own version. Notation software handles about 95% of engraving well, and engravers spend about 95% of their time on the remaining 5%. Those figures are practitioners' experience rather than measurements, but anyone who has prepared parts for a performance will recognise the shape. The afternoon goes on forcing system breaks, prising collisions apart, and recasting a part so that the page turns fall in rests. The two rules describe the same remainder from opposite ends. The cases a developer leaves unfinished, because they belong to the last 10% that would take the other 90% of the time, are precisely the cases the engraver then finishes by hand. Shipping at the 90% mark doesn't make the remaining work go away. It passes it on to the users, multiplied by every user and every score. That's a tax, and like most taxes it's paid continuously by people who never voted for it. Ooloi is in large part an attempt to abolish taxes of this kind wherever the architecture allows, from undo to collaboration. The engraver's 5% is the largest of them. I should be fair here, because it matters. Doing 95% well might genuinely be good enough for most people's music. In December 2016 Daniel Spreadbury wrote that Dorico's casting off, tested against the Gourlay method, 'produced very similar results a lot of the time'. That's the 95% working exactly as designed. The 5% is where it doesn't, and that's where the engraver's afternoons go. Knuth & Plass, BrieflyI wrote about the algorithm in 'Boxes & Glue', so a reminder will do. In 1981 Donald Knuth and Michael Plass published the line breaker that TeX still uses. A paragraph is a row of boxes (the words, which are rigid) with glue between them (the spaces, each with a natural width and a given capacity to stretch and shrink). Any choice of breaks gives each line an adjustment ratio r: the stretch or shrink the line needs, divided by the stretch or shrink its glue can supply. So r = 0 is a line at its natural width, r = 1 is a line stretched as far as its glue is meant to go, and r = −1 is the tightest line TeX will set. Knuth turns r into badness, roughly 100 × |r|³, and badness into demerits, (l + b)² + p², where l is a small charge for every line and p the penalty attached to the break. Then he finds the set of breaks with the smallest total for the whole paragraph. The cubes and squares mean that one very bad line is punished far more than several slightly imperfect ones, which is exactly the judgement a good compositor makes. What makes it fast is dynamic programming. The program walks through the paragraph once and, at each possible break, remembers only the best way of getting there. If the cost of a line depends on that line alone, nothing more is needed: when the walk reaches the end, the best layout of the whole paragraph is recovered by following the remembered steps backwards. The result is exact, meaning provably the minimum of its cost rather than a good guess, and the work grows with the number of possible breaks times the number of words that can share a line. The alternative, and still the usual one, is greedy filling: put bars on a system until the next one won't fit, move on, and never look back. It's quick and it's local, and the bill arrives at the end of the piece. What Hegazy and Gourlay Actually WroteAs far as I can tell, nobody has described this paper in public. LilyPond's source names it as the origin of its first line breaker, and Daniel Spreadbury has said it informed Dorico's casting off, but I've found no account of what it actually contains. ADR-0037, which specifies Ooloi's breaker, cited it while admitting that it described none of its contents. That ADR has now been updated with a description along these lines. The paper opens by explaining why music isn't text. The last system of a piece is always full, so a copyist has to be prepared to revise early breaks that don't lead to a full last line, and a program must be able to do the same or it'll stretch the last system grotesquely. Long works should also fill their last page, which sometimes means forcing a particular number of systems. Clefs and key signatures repeat at the start of every system, and they change, in content and in width. Most important of all, notes don't move linearly when a system is stretched or squeezed. The state of the art, they note, offered little help. Byrd's 1984 thesis program did first-fit breaking, which is greedy filling by another name, and expected users to choose their own breaks. Ross's engraving manual advised avoiding bad breaks and keeping the spacing uniform. 'There appears to be no published algorithm', they write, that attempts to deal with these problems at all. Their claim is that Knuth's model already handles the first three. A paragraph with no fill glue at its end gets a full last line automatically. Penalties encourage or discourage particular breaks, which is how a performer's awkward page turn can be avoided. TeX can be told to use a set number of lines. And TeX's discretionary breaks, the mechanism behind hyphenation, can change what's printed at the end of one line and the start of the next. Only the fourth problem needs new theory. That theory is the paper's real contribution, and it's lovely. Think of the space between two notes as a spring. In text the springs join the outsides of rigid boxes. Hegazy and Gourlay pass the springs through the boxes and attach them to the left edges of the noteheads, because what the eye measures is the distance from one note to the next, not the white space between their shapes. The boxes still can't pass through each other, though. A note and the accidentals of the note after it take up room, and when those shapes touch, the spring between them can shrink no further. So each gap carries four numbers: an ideal width w, a stretchability y, a shrinkability z, and a blocking width b, the width at which the shapes on either side collide. Under a force f, which is Knuth's adjustment ratio under another name, positive to stretch and negative to compress, the gap's width is the larger of two quantities: width = max(b, w + f·k), where k is y when stretching and z when compressing. Read as a musician: the spring tries to be its ideal width plus whatever the force asks of it, but never narrower than the collision allows. Read as a mathematician: each gap is a piecewise-linear function of the force, and therefore so is the whole system. The interesting case is the one where b exceeds w, which they call 'prestretched'. Their Figure 1 shows it: a note preceded by two flats so wide that the gap before it is already larger than its duration warrants. That gap doesn't move at any line length until the force on the rest of the system has caught up with it; only then does it begin to grow with the others. The accidental takes the room it needs and not a hair more, and once the system is loose enough it costs nothing at all. That's exactly how an engraver treats an accidental. The consequence for breaking is that the force needed to fit a system is no longer a single division, as it is in TeX. It's the solution of a piecewise-linear equation whose kinks lie wherever an individual gap collides or begins to stretch. The search around it is Knuth's, which they say 'does not differ in any significant way' from TeX's: remember the best predecessor for each barline, discard lines whose force falls outside a permitted window, and trace the optimum backwards from the end. Their efficiency section is the most telling part of the paper, because they never treat the dynamic programming as the expensive part. The expense lies in working out the force for each candidate system, and they attack it twice. First comes a cheap lower bound on the force, built from running totals: 'the sums are computed from the beginning of the piece to the current place, and two such sums are subtracted to obtain the sum for what lies between them'. Programmers call these prefix sums. The bound is designed so that it can never wrongly reject a system that would fit. Second comes a fast path for the common case, in which the force stays on the first straight segment of the curve, before any gap has collided. They test for that with minima precomputed for each bar. Their evidence is modest and well chosen. They broke a 48-bar piece on a single stave, Dean K. Roush's 'Lacrimosa', into systems. The breaks matched those chosen by a professional musician, who had spent a few hours on it. The program took a few seconds on a personal computer of 1987. So is it Knuth–Plass? Not purely. The search is Knuth's without his fitness classes, which TeX uses to stop a tight line from sitting next to a loose one, at the price of extra bookkeeping. The cost is shaped like TeX's but never written down as a formula. And the model of a line is a strict generalisation of boxes and glue: TeX's glue is the special case in which nothing ever collides. But it isn't approximate either. The cost of each system depends only on that system, the pruning is sound, and the cheap bound never discards a line that would fit, so the result is the exact optimum of its own cost. Nor do the modifications reduce the efficiency of the algorithm. The dynamic programming is untouched; what grows is the arithmetic inside the evaluation of a single system. What Hegazy and Gourlay did to Knuth and Plass was extend them. The DescendantsThree documented lines of descent made three different choices, and in each case the authors have said why. LilyPond's first line breaker, gourlay-breaking.cc, says in its source that it was 'adapted from the OSU Tech report on breaking lines'. It was a straightforward dynamic program until October 1999 (release 1.2.14), when a term comparing each system with its predecessor was added for the sake of evenness. With only one predecessor stored per breakpoint, that made the result an approximation of its own cost, and the term survives in LilyPond's current breaker. LilyPond's spacing, which I'll come back to, is solved afresh for every candidate line. Han-Wen Nienhuys, who wrote the original breaker, commented in 2015 that he'd first run it on a 386 at about 40 MHz, where 'it was somewhat expensive'; that computers had since become a hundred times faster; and that you have to solve 'O(#bars * #bars-per-system) spacing problems'. He thought it could be used for interactive scores too. Dorico's team evaluated the Gourlay method early on. In 2015 Spreadbury set out the reasoning in his development diary. A program that compiles its output from text input needn't respond in real time, but for an interactive one 'a compromise is needed in order to balance the quality of the result against the time taken to compute it', and Dorico's principle was to 'always do only the minimal amount of recalculation to respond to an edit'. In December 2016 he wrote that the method's performance characteristics weren't suitable for Dorico's real-time use, and that Dorico's own algorithm 'basically runs only one way, from the start of the layout to the end'. In April this year he confirmed that the paper had informed Dorico's casting off, which is greedy, with a separate remainder-distribution step at the end of each flow. That remainder step deals with the full last system, the first of the four problems Hegazy and Gourlay listed in 1987. Others claim the full prize. Christof Schardt, the author of PriMus, wrote in 2015 that PriMus had used TeX's total-fit algorithm, 'modified for scores instead of text', interactively for over ten years, taking collisions into account 'by an equivalent linear operation'. Basil Crow's open-source Neanes editor does optimal line breaking for Byzantine neume notation. I haven't checked either at source. None of this is a league table. Each choice was rational under the constraints its makers had, and Spreadbury's 2013 statement of Dorico's ethos, that the application should do 'automatically what an experienced engraver or copyist would do anyway', is one I'd sign without changing a word. The goal is shared. The constraints aren't. Speed was Never the ObstaclePut the dates side by side. In 1987 an exact optimum over a nonlinear spring model ran in seconds on a personal computer. In 2015 the author of LilyPond's first breaker, who had run it on a 386, reckoned that machines a hundred times faster could manage it interactively. Processor speed hasn't been the obstacle for a very long time. What costs something is evaluating each candidate system, and everyone who has looked closely puts the cost there: Hegazy and Gourlay in 1987, Han-Wen in 2015. Hegazy and Gourlay's remedies, the running totals and the per-bar minima, rest on an assumption so basic they never needed to state it, which is that each bar's numbers are fixed before breaking begins. They could assume it because their input was a single stave, handed to the program as a ready-made sequence of springs. A notation program has to manufacture that input from a full score, and this is where architecture comes in. Suppose a candidate system's width depends on which bars share it, or on something settled only after the breaks are chosen: the courtesy accidentals at a system start, an accidental decision that changes when a tie crosses a break, spacing that's adjusted and then fed back. Then every candidate needs its own spacing calculation. In a mutable, incremental program, every moved break also invalidates whatever was computed downstream of it. A global optimum, where one edit can move breaks anywhere in the score, then becomes the most expensive thing you could possibly ask for, and greedy filling is the sensible choice. I can't see inside anyone else's program, so take this as my reading of the problem rather than a finding about any product. But it's consistent with everything their authors have said, and it puts the obstacle where the 1987 paper already implied it was: in the data, not in the processor. Vestigia Nulla RetrorsumOoloi lays out a score in six stages, and information moves through them in one direction only. Stage 1 works on every bar in parallel. It forms the atoms (a note or chord with its accidentals, dots and articulations, handled as one unit) and traces their outlines from the font, the shape each presents to its neighbours. Stage 2 lines the staves up vertically and works out, for every gap, both its ideal width, which comes from the durations, and its minimum, where neighbouring outlines would touch, so that each measure stack (one bar across all the staves) leaves it as a handful of numbers. Stage 3 breaks the systems. Stage 4 positions the atoms. Stage 5 draws what connects them, the ties, slurs, hairpins and beams, and works out how tall each system is. Stage 6 breaks the pages. Nothing flows back. Stage 5 can't ask Stage 3 for more room, and Stage 3 can't reopen a decision made in Stage 1. The musical questions, such as which accidentals a note needs, are closed before layout begins, so layout can't change them. Everything Stage 3 needs is known before it starts, including what each bar would require at the start of a system and at the end of one. The pipeline has a motto, borrowed from Horace. In the first of his Epistles (I.1.73–75) a fox declines the sick lion's invitation into its den and explains why: 'quia me vestigia terrent, omnia te adversum spectantia, nulla retrorsum'. The footprints frighten me: they all lead towards you, and none lead back. In the fable that's a warning; in a layout pipeline it's the design. Every footprint points forward, and that single property is what turns casting off from a negotiation into arithmetic. Arriving at the Same PlaceOoloi’s breaker, specified in ADR-0037, was written from Knuth and Plass directly, before I’d read a line of Hegazy and Gourlay. Reading them now is a curious experience, because the search is the same. Both remember one best predecessor per barline, with no fitness classes. Both subtract running totals between barlines, and both stop extending a candidate system as soon as more bars can’t possibly fit. Their per-bar minima, used to test whether a line has reached its first collision, correspond to a number every Ooloi measure stack carried until now: its tightest gap’s ratio of minimum to ideal width, tracked as a running maximum while the candidate system grew. The correspondence goes deeper than I expected. Until now, Ooloi’s baseline let every gap stretch and shrink in proportion to its ideal width, so each system had a single scale factor. It also calibrated the adjustment ratio so that r = −1 fell exactly where the tightest gap in the system reached its minimum, and allowed nothing beyond that point. In Hegazy and Gourlay’s terms, that was their model restricted to the first straight segment, before any gap has collided, with the force rescaled so that the first collision sits at −1. I got there independently, but I don't think the convergence is remarkable. Both designs start from TeX, and both discover that the cost lies in evaluating a line; from there the problem pushes you towards the same answers. I find that reassuring rather than surprising. Where Ooloi goes further, most of the reasons lead back to the direction of flow. The first concerns system starts and ends. Hegazy and Gourlay pointed at TeX's discretionary breaks for the clefs and keys at each system start, and left it there. A discretionary has three parts: what's printed before the break, what's printed after it, and what's printed if no break happens. Ooloi's breaker has all three. A postamble holds what a system's end needs, which is the cautionary key and time signatures; a preamble and a gutter hold what the next system's start needs: clef and key, courtesy accidentals for tied notes, a start repeat. Everything else at a barline belongs to a bar, wherever that bar falls: the barline itself, as it looks at the end of a system, and a clef change drawn in front of it belong to the bar they close, and a new key or time signature to the bar it begins. The third part holds what exists only mid-system: the start half of a repeat barline, which at a break moves to the start of the next system, and the cancellation naturals of a key change, if the house style drops them at a system start because the previous system's cautionary has already shown them. Each is a fixed width at its barline, and the breaker subtracts those inside a candidate system with a single subtraction of running totals, so the result stays exact. All of it is known before breaking, because nothing downstream can change it. This also matters for exactness. Hegazy and Gourlay's pruning is only safe because their systems carry no such material. Give each system start a width that varies from bar to bar and their pruning can wrongly discard systems that would have fitted. ADR-0037 prunes against the full system width instead, which stays exact. The second concerns editing. A global optimum means that one edit can move breaks anywhere, which is why interactive programs avoid it. In Ooloi every stack's numbers are immutable and cached, so after an edit nothing upstream is recomputed except what the edit actually touched, which is usually the bar that changed. The new optimum is then found exactly from two stored tables, holding the best layouts of everything before the edit and of everything after it, in roughly K² evaluations, where K is the number of bars that fit on a system. That's a couple of hundred cheap evaluations, not a re-layout. Keeping breaks where they were while you work is a separate problem, and the ADR specifies mechanisms for it that are anchored to the identity of bars rather than to luck. The third is determinism. Layout is computed once, by the authoritative backend, not separately by each client; but it still matters that the same music always produces the same layout. Everything is computed in exact rational arithmetic, and when two layouts cost exactly the same, which under exact arithmetic happens whenever bars are identical, the tie is broken by a rule that depends only on the layout itself, never on the order in which the program happened to meet the candidates. Re-optimising after an edit therefore gives the same answer as starting from scratch, undo brings back the identical layout, and a score opened on another machine looks the same there. Nothing on the page moves unless the music has given it a reason to, which removes a whole class of jitter at its source. One further difference has nothing to do with immutability: Ooloi's cost is written down. It uses Knuth's badness and demerits with TeX's own constants as the starting point. That only works because the adjustment ratio is calibrated so that −1 means collision and +1 means a stated amount of stretch; without the calibration, TeX's numbers would mean something quite different for music. That one is simply care. What Gourlay has that Ooloi Doesn'tThe other direction is the more interesting one. Until now, ADR-0037 allowed four fitting rules, which are ways of deciding how each gap gives way when a system is looser or tighter than ideal. All four were linear glue: each gap stretches and shrinks in fixed proportion, and a system’s force is a single division. None of them could represent a gap that blocks while its neighbours carry on, and none could represent a prestretched gap at all. The ADR’s contract with Stages 1 and 2 actually forbade it, since every gap’s minimum had to be at or below its ideal. And the case isn’t rare. The engraver’s principle is that everything belonging to a note, accidentals included, should fit within its proportional allocation: accidentals don’t add space. But a sixteenth’s allocation is around one and a half stave spaces, and a notehead plus a sharp plus clearance needs more than two. In any chromatic passage in sixteenths, a good share of the gaps have a minimum larger than their ideal. That’s Gourlay’s prestretched spring, and it’s what the decision below turns on. All of this is easiest to picture on a single stave, but Ooloi doesn't space just single staves. Stage 2 aligns every stave in a measure stack on a shared vertical raster: one column for each rhythmic position that occurs in any stave, so that notes sounding together line up from the top of the system to the bottom. A gap in Gourlay's sense is the distance between two columns, and its blocking width is set by whichever stave needs the most room there. A sharp in the violas widens that column for the flutes as well. What I Have to DecideThere are three ways to go, and each of them shows on the page. Take a bar of chromatic sixteenths, half of them carrying accidentals, as the running example.
I have decided that Ooloi will adopt Gourlay’s springs, and ADR-0037 has been revised to specify them. Will it make Ooloi slower? As with Hegazy and Gourlay, the dynamic programming itself doesn’t change at all: the same states, the same number of candidate systems, the same tables for re-optimising after an edit. What changes is the arithmetic inside the evaluation of a single candidate system, and only for the systems that need it. Compression is always a single division, exactly as before. So is stretching, until a gap held open by an accidental starts to stretch. Only then does the candidate take the slower path, in which those gaps’ kinks are kept in sorted order as the candidate grows and the force is found by walking them. That costs a handful of extra operations per kink passed, not a spacing calculation. Those are precisely the systems the linear baseline spaced wrongly. The ones it rejected outright, frozen by a single gap that couldn’t shrink, now cost nothing extra at all. Stages 1 and 2 already compute every gap’s ideal and minimum, so nothing new is asked of them; each stack simply keeps a few sums and a short list of its accidental-held gaps. The result stays exact and identical on every machine, and nothing flows backwards. I’ll know the real cost when there’s a benchmark on chromatic material. Until then, that’s reasoning rather than measurement. As I've decided to go with the springs, more questions follow. The first is what r = −1 should mean. If each gap’s shrinkability is set to its room above collision, every gap reaches collision at the same moment, at −1, and TeX’s constants keep their meaning. But wherever long notes have more room than short ones, they give up more of it, and the rhythmic hierarchy flattens under pressure. If shrinkability is weighted by duration instead, short values compress and collide first while longer ones keep giving. That’s nearer to the way engravers describe their own practice, but −1 then needs another definition. The choice decides whether a tight system still reads as rhythm. I’m starting with the first, which is also LilyPond’s default and keeps compression a single division; duration weighting stays a candidate for the plates to decide. The second is minimum distances that span more than one gap: a long syllable sung across a melisma, or material that crosses between staves. Gourlay’s blocking works between neighbours, so such constraints have to be reduced to minimums on adjacent gaps before breaking. LilyPond’s spacer shows how: a minimum distance spanning several notes becomes a blocking force on every spring beneath it, at a small cost in density that a comment in its source considers acceptable. Since that force depends only on the springs inside the span, it can be worked out before any break is chosen, and that’s the reduction ADR-0037 now specifies, in Stage 2. So Ooloi doesn’t need the per-candidate spacing calculation that LilyPond chose to pay for. The third is what the raster should do with the room. Take two staves of sixteenths in the same stack, some notes carrying accidentals and some not, in different places in each stave. One answer is that every sixteenth in the bar sits at the same distance from the next, so the rhythm reads as a regular grid and every column gets as much room as the most demanding one. Another is that each column takes only what it needs, so a column with an accidental in any stave is a little wider and the rest a little narrower: more economical, less regular. Gourlay's springs give a third answer that moves between the two. Under pressure the columns differ; as the system loosens, the columns held open by accidentals stop growing while the others catch up, until at some point the grid is even again. Which of these an engraver would choose, and at what degree of tightness, is a question for the plate. A related case shows what's at stake. Take a bar that opens with a half note, continues with eight thirty-second notes and ends on a quarter. Logarithmic spacing already gives the thirty-seconds far more room than strict proportion would, and with their beams, stems and perhaps an accidental or two they may need more still. The half note and the quarter, on the other hand, are mostly air. An engraver lets them pay: the run of thirty-seconds gets the room it needs, and the long notes give some of theirs back. Proportional scaling can’t do that. Every gap shrinks by the same factor, so the thirty-seconds reach their minimum first and the whole system stops compressing while the half note still has room to spare. Shrinkability bounded by each gap’s own room, the second option above, does let the long notes give way, and Gourlay’s springs do it as a matter of course: the thirty-seconds, with little or no room above their minimum, give up little or nothing, and the half note and the quarter absorb the rest. This is also where the weighting question gets interesting. ‘Shorter values compress first’ sounds right until the shorter values have nowhere left to go; beyond that point the blocking decides, not the weighting. What none of this decides is who pays. Gourlay's force is one number for the whole system, so the cost of the thirty-seconds is spread over every gap in it, including a half note three bars away. An engraver might prefer the half note in the same bar to pay, and leave the rest of the system alone. That's a choice between consistency, where the same duration gets the same space across the system, and locality, where each bar settles its own debts. It belongs to the setting of ideal widths within a bar, before any fitting begins. In a full score it's subtler still: if the half note sounds against thirty-seconds in another stave, the raster has no half-note gap to shrink at all. All of this sits beside two questions ADR-0037 already left open. One was whether to add a term for evenness between neighbouring systems, as TeX does with its fitness classes. I’ve decided against it. The cubic badness already punishes an extreme system out of all proportion, so under an exact optimum a cramped system survives next to a loose one only when every alternative costs more. And a comment in LilyPond’s source warns that such a term can make cramped lines more cramped where the music grows gradually denser. Music changes density for reasons of its own, and the layout shouldn’t pretend otherwise. The other question, how page breaking and with it the page turns in parts should be costed, remains open. How the Others AnswerEach of the programs I've read has answered these questions definitely, and since I read rather than run them, what follows comes from their source and their documentation. It describes how they work, not how their pages look. LilyPond's answer is the closest to Gourlay's, more literally than I'd realised. A spring in its spring.cc has an ideal length, a stretch, a compression and a minimum, and its length under a force is the larger of the minimum and the ideal plus the force times the flexibility: Hegazy and Gourlay's formula, prestretched springs included. By default a spring compresses by exactly its room above its minimum, which is the second option above, and a note's stretch is proportional to the space between bare noteheads, so the air stretches and the ink doesn't. In the bar with the half note and the thirty-seconds, the half note therefore takes most of any stretching and most of any compression, because it has most of the air. Durations are spaced from the most common shortest duration, each doubling adding a fixed increment of about a notehead's width, and each column takes the shortest duration sounding in it. MuseScore, in its current source, derives each note's natural width from its duration on a logarithmic curve: every doubling multiplies the space by a factor, 1.5 by default, starting from 3.5 stave spaces for a quarter. Where a collision demands more room, the extra is spread over the preceding notes rather than piled into one gap. When a system is justified, its notes act as springs whose stiffness comes from their durations, and a note already widened by a collision doesn't stretch until the force reaches it, which is the stretching half of Gourlay's model. Compression works differently: a system that is too wide is re-spaced with paddings and duration spacing reduced in steps, and as a last resort collisions are accepted. Bars are added to a system until the next one no longer fits at its natural width, and the system is then stretched to the margin, as its handbook also describes. Dorico's documentation says less about mechanism, but two things are on record. In 2015 Spreadbury described forming a column for every onset across all staves and giving it the value of the shortest note sounding there, the same raster as Ooloi's, and spreading surplus space as 'a tiny fraction of a space to each column', in contrast to the hand engraver's habit of giving it to the longest notes first. Its current layout options include a minimum space for short notes, which is the thirty-seconds' case, and a choice, when justifying, between 'actual widths', which count accidentals and dots, and 'ideal widths only', which count the notes. That last option is, in effect, the question of whether accidentals add space, offered to the user as a setting. None of it will be settled by argument. Ooloi's Vorbilder, the models it measures itself against, are printed pages from the great engraving houses, made by people who did this by hand for a living, and that's where the questions will be settled: on material chosen for where the 5% lives, such as chromatic passages, vocal scores heavy with lyrics, tight orchestral pages and parts with page turns. The measure is how many interventions it takes to reach the layout an engraver produced by hand. That number is the tax. And when I start showing pages from Ooloi, I'll set them beside printed music, never beside another program's output, however anonymised. Coda'Boxes & Glue' ended on a thought I hadn't finished: that the space after a whole note and the space after a sixteenth want different things, that each might have its own idea of how far it will stretch and how far it will give, and that this seemed very close to how a human engraver reasons about whitespace.
The thought is thirty-nine years old. Hegazy and Gourlay had it in 1987. They passed the springs through the boxes, gave each one a point beyond which it won't give, and solved the result exactly on a machine any modern thermostat would outrun. What they didn't have was a full score reduced to numbers that couldn't change underneath them. But that's exactly what I've spent the last two years building, mostly without realising that this was one of the things it was for.
5 Comments
Magnus Johansson
11/10/2026 11:16:54
Great, that Ulrik assisted with the paper by Hegazy and Gourlay!
Reply
Peter Bengtson
11/10/2026 11:26:37
Thanks, Magnus, and yes, Ulrik’s find made this post possible.
Reply
Magnus Johansson
11/10/2026 16:37:42
Thank *you*, Peter, for your fascinating effort dealing with these complicated things.
Reply
Peter Bengtson
11/10/2026 19:31:09
Oh, absolutely! They are exactly the same thing from the perspective of the algorithm.
Peter Bengtson
12/10/2026 16:56:40
And I've just realised that these decisions actually put Ooloi closer to the LilyPond tradition than the Dorico one, at least where spacing and casting off are concerned.
Reply
Leave a Reply. |
AuthorPeter Bengtson – SearchArchives
November 2026
Categories
All
|
|
|
Ooloi is an open-source desktop music notation system for musicians who need stable, precise engraving and the freedom to notate complex music without workarounds. Scores and parts are handled consistently, remain responsive at scale, and support collaborative work without semantic compromise. They are not tied to proprietary formats or licensing.
Ooloi is currently under development. No release date has been announced.
|
RSS Feed