Development diary, part six

An accidental, yesterday. Courtesy starrise on flickr.In the last update, we started discussing some of the individual engines that are under development to handle atomic notation and engraving tasks, and I described the engines for note and rest grouping, and positioning rests in multiple voices. Let's take a look at another couple of little engines that could.

Accidental duration

Most scoring programs implement what might be termed the "common practice" rule for when accidentals should appear: an accidental is shown on a note of a given staff position whose pitch differs either from its unmodified pitch determined by the key signature, if any; the accidental applies only to the octave in which it appears; and the accidental lasts until the end of the bar, unless it is contradicted by a further accidental in the meantime.

Some scoring programs also implement support for cautionary (or courtesy) accidentals, either as proper built-in features or by way of plug-ins that have to be run and re-run as the music is edited.

A couple of scoring programs (though neither of the two most mature commercial products) provide options that support a variety of different conventions for accidental durations, such as accidentals applying only to the note on which they appear, with naturals shown on all other notes, or sometimes with no other accidentals shown (in which case a note with no accidental shown is played as if it had an explicit natural shown), and so on.[1. These conventions can be achieved to greater and lesser extent in the most mature commercial applications with the aid of plug-ins, but these have to be run and re-run after the music is edited to ensure that the display of accidentals is always correct. In the leading open-source music engraving program, of course, accidentals are calculated when the whole input file is processed, so changing the rules for accidental duration necessitates the re-processing of the whole input file, just like any other change to the input.]

By now it should not surprise you to hear that our goal is to handle accidentals more powerfully and more flexibly than any other scoring program, though specific details will have to wait for another day. The engine for calculating the required accidentals feeds its output into another engine for calculating the order in which accidentals should appear before a note or chord, via a minor detour.

Stem side calculation

The engine for stacking accidentals needs to know not only which accidentals should appear for a given note or chord, and other fundamental information like the staff position of each note, but also what the arrangement of notes in a chord will be: specifically, it needs to know on which side of the stem each note will appear.

When a chord includes notes on adjacent lines and spaces (i.e. intervals of a second of some kind), noteheads have to be positioned on opposite sides of the stem. A notehead that is positioned on the opposite side of the stem to the majority of noteheads in a chord is known as a back-note. It's very important that the majority of noteheads appear on the correct side of the stem (i.e. on the left for an up-stem chord, and on the right for a down-stem chord), with the back-note (or back-notes) positioned on the opposite side of the stem.

The engine to calculate the correct arrangement of notes around the stem of a chord takes as its input the staff position of each note in the chord, and its stem direction, each of which is worked out by other engines. Each engine keeps all of its information up to date for the whole span of music, so that it is readily available to other engines that need it, and great care is being taken to ensure that only the minimum required recalculation is being carried out when the musical content changes due to edits, new music being entered, and so on, so that the performance of the application as a whole is as good as possible, despite the complexity of the calculations being performed.

Accidental stacking

Accidental stacking is another deceptively simple aspect of music engraving: in general terms, the aim is to arrange accidentals such that they appear to the left of a chord in notional "columns"[2. Think of each vertical slice containing one or more accidentals to the left of a chord as an individual column: a two-note chord describing an interval of a second, each note with its own accidental, would require two columns, because one accidental has to be positioned to the left of the other to avoid overprinting.] in as compact an arrangement as possible, taking into consideration various conventional practices, such as aligning accidentals on notes an octave apart in the same column (except when you don't) and aligning accidentals on intervals of a second such that the accidental for the higher of the two notes is positioned immediately to the right of the accidental for the lower of the two notes (except when you don't), and so on.

Each of the major texts on the finer points of engraving cover accidental stacking to some extent; Elaine Gould's book Behind Bars is probably the most explicit and detailed in terms of both the general approach that should be taken and some key exceptions. However, as with more or less any aspect of engraving, a set of simple rules and some exceptions to those rules do not account for every possible case, and the job of deriving algorithms to produce pleasing accidental stacks in every case is by no means trivial.

For simple chords of up to three or four accidentals, there is generally little argument among music engravers about what the correct stacking arrangement should be. Once chords get more dense, then there is substantially less agreement, and a perusal of a variety of published editions from the age predating computer engraving shows just how much variety there can be. As with many complex problems of geometry, there are many possible solutions for each case, and the correct arrangement is as much a matter of taste as it is anything else. There is no thought that our accidental stacking algorithm – or indeed any of our other engraving algorithms – should replace the judgement of an experienced engraver, but our aim is to produce a satisfactory result that a musician will accept automatically, so that users who do not have years of experience in manually stacking accidentals against complex chords can have confidence in the default appearance it produces.

Since a picture paints a thousand words, let's take a look at a few examples. These chords are drawn from the first few bars of Max Reger's Introduction, Passacaglia and Fugue in B minor (Op. 96) for four hands, two pianos; it's an interesting test case for accidental stacking because it's a thickly-textured work largely consisting of chords in all four hands.

Here's the result produced by one of the two leading commercial scoring products, which we will call Product A:

The other leading commercial scoring product, Product B:

The open-source music engraving program, which we'll call Product C:

Interestingly, all three programs come up with different stacking arrangements for three of the five chords, all three agree for the third chord, Product B and Product C agree for the fourth chord, and Product A and Product B agree for the fifth chord.

The basic rule for stacking accidentals can be described as a zig-zag: start with the highest accidental in the chord and position it in the first column (immediately to the left of the chord), then the lowest in the second column, then the next highest in the third column, the next lowest in the fourth column, and so on, until you run out of accidentals. At each stage, if you find an accidental on the same note name in another octave, position that in the same column, so that accidentals on octaves are aligned. This is something of a simplification, of course, but it's enough for you to get a general idea of how accidental stacking works.

Now look at the first chord, and in particular Product A's default rendering: it positions the sharp on F#3 (assuming middle C is C4), the third lowest accidental, in the first column. It does this because it can be tucked underneath the leger line on D4, though this isn't entirely successful: the other accidentals end up too far away from the chord, and the result from either Product B or Product C would be preferable.[3. Product A has an option that prioritises the placement of the highest accidental in the first column, which produces an identical appearance to Product B and Product C for the first chord, but it has disadvantageous side-effects in other chords, and in any case this option is not enabled by default.]

Product A's strategy for tucking accidentals in for back-notes and leger lines is more successful in the case of the fourth chord, where it produces the most compact result, positioning the sharp on G#4 in the first column, while Product B and Product C position this in the outermost third column. However, many engravers would find the placement of the sharp sign so close to the D5 immediately above it that they would choose not to tuck it in here.

For the second chord, Product C's default rendering is the most conventional (and perhaps therefore the most desirable): the highest sharp, on D#4, is positioned in the first column, with the octave D#3 aligned in the same column; the lowest remaining accidental, the sharp on F#3, is positioned in the second column; and the remaining natural on A3 is positioned in the fourth column. Product A would presumably produce the same result if it did not attempt to tuck the natural in under the leger line, again an unconventional choice.

It's a similar story for the fifth chord, where Product B unconventionally chooses to place the next highest accidental (the natural on A4) in the second column after correctly aligning the octave on C5 and C4 in the first column; Product C instead chooses the sharp on D#4 for the second column, which follows the standard convention more closely. Notice how the naturals on the octave C5-C4 are aligned precisely in Product B and Product C, but not quite in Product A: Product C subtly shortens the leger line on C4 to allow the natural to be positioned as closely as possible, while Product B moves the naturals on both C4 and C5 a little to the left to clear the normal-length leger line; Product A, on the other hand, only adjusts the position of the natural on C4, producing a sub-optimal result where the accidentals separated by an octave are not precisely aligned.[4. As ever, it seems only fair to point out that it is relatively quick and easy to adjust the position of individual accidentals in both of the most mature commercial scoring programs, while it is somewhat more involved in the text input-based Product C, and cannot be done in a graphical fashion at all, except perhaps with a separate graphical front-end, instead requiring tweaks to the input file and re-compilation to see the result of each attempted improvement. Fortunately, for these five chords at least, there is little to complain about in Product C's default stacking arrangements.]

The arrangement for the third chord is pretty uncontroversial: although there is an interval of a second in this chord, and it's usually best to stack accidentals for seconds such that the accidental for the higher of the two notes is positioned immediately to the right of the accidental for the lower of the two notes, if there are other accidentals in the chord it's often preferable to use the more standard zig-zag arrangement, as it occupies marginally less horizontal space.

You might well be asking how our in-development application handles these chords. It happens to produce the same results as Product B:

The above examples illustrate just how much variation there is in stacking accidentals even for quite straightforward chords. When things get more complicated, there is even greater possible variation in the arrangement of accidentals.

To test this out, we generated hundreds of random chords of increasing complexity using the music21 toolkit and exported them as MusicXML. The resulting MusicXML file was then imported into our own test harness and a variety of other commercial scoring products, and the default accidental arrangements were exported as PDF, with no editing. We examined the results by eye, and recorded a number of interesting characteristics. You can check out a subset of the results (32 chords, ranging from three to 12 notes) using a simple interactive tool[5. Although the results have been manipulated in an illustration program in order to ensure that the notes and staves line up exactly, none of the accidentals have been moved relative to their corresponding notes, so they present an accurate depiction of how those chords are laid out by each application.]:

Click this image to view the interactive comparison tool.

By now you are familiar with Product A, Product B and Product C. Product D is a commercial scoring product no longer under development or indeed widely used, but still used by some top publishers; Product E is a popular open source scoring program with a graphical user interface; and Product F is a browser-based social composition product.

Using the comparison tool, you can zoom in to get a closer look at each chord, and then switch between the default results produced by each program. Click Show annotations to see various sub-optimal characteristics called out with coloured highlights (refer to the legend for the meaning of each different colour).

The point of this comparison is not to be critical of the results produced by different scoring programs, but instead to illustrate just how non-trivial the job of designing a fully general algorithm for accidental stacking is, even for mature and well-regarded applications.[6. Indeed Product E also demonstrates that it's hard to do the stem side calculation – described above and performed in our application as a prerequisite of the accidental stacking – for arbitrarily complex chords, as there are quite a few examples of back-notes on the wrong side of the stem, with subtle but discomfiting results.] Experienced engravers would undoubtedly find much to disagree with in all of the results. However, we have worked hard to produce results that exhibit as few undesirable traits as possible.

The job of our accidental stacking engine, then, is to determine which accidentals should go in each column, and specify whether any of the columns can be tucked in to share the same space as a back-note elsewhere in the chord. It doesn't concern itself with how those accidentals should actually be drawn and spaced relative to the note or chord and each other, so the rendering from our test application is rudimentary with regard to spacing. Its job is to pass the resulting columns on to the next engine in the chain, which can determine how best to lay out those columns in as compact a form as possible while maintaining legibility.

More to come

That's probably (more than!) enough detail about the little engines at the heart of our application's musical brain for the time being. In the next instalment of this series, I'll describe some of the other things that have been going on, including an update on our music font, Bravura, and the standardisation effort for music fonts we're leading, plus details on our progress in designing key parts of the application's user experience.