Lomse Hacking Guide
Layouting a score is a very complex task. When I started with Lenmus project I had no experience on anything related to music. I wasn’t able to find academic papers on the subject as all academic knowledge is not free but paywalled and quite expensive. As, normally, you have to read many papers before having a clear picture and finding something usefull, it was totally out of my budget. So, I decided to reinvent the wheel: being optimistic I decided to see it as a great opportunity to learn first hand about the problems involved.
Important
Be awared: all score layouting discusion is based on my own ideas, without any knowledge of academic papers on the subject, appart from GUIDO thesis [1] that is available for free on internet. Probably, many ideas presented here are naif and there are better, documented ways of doing things.
Before starting the description of the scores layouting process, just a few words about the approaches followed and the main problems found:
Initially (LenMus 1.x & 2.x) no knowledge at all. My layouting approach was that of a text processor: layout symbols in sequence as if they were charaters in a sentence. No graphical model: all info in the internal model. Two single pass phases: layout and drawing. During layout phase (single pass), positions for objects were computed and stored in the internal model (problems to have two views of the same score). Drawing was just redering symbols at computed possitions. Discovering that time was the key concept for deciding on position.
Soon it was clear the need of do layouting in two phases: the final positions of some objects (i.e. beams) can not be computed until all notes positions are definitly computed and systems are justified. For layouing, notes and rest are the key symbols that should be layouted first and determines the coarse layout. All remainder symbols are just “decoration” but they can affect to notes/rest positions, although in small degree.
System justification based on measures (bars). Problems for layouting multi-metric music.
LenMus 3.x & 4.x. GUIDO thesis found. I started to isolate rendering information: first steps towards a graphical model. But: no boxes, only shapes objects created, and shapes stored in the internal model. Again, problems for supporting multiple views. Layout was still the same algorithm in two passes. And system justification was still based on measures, so layouting multi-metric music was not possible. Monolitic, complex code, difficult to understand, maintain and improve was refactored by starting to use a test driven approach (TDD). Starting to separate responsibilities, and have better understanding of staep, task and responsibilities during layouting.
LenMus 5.x (Lomse library). New layouting algorithm. Clear separation between internal model and graphical model (multiple views now supported). System justification no longer based on measures but re-designed for supporting multi-metric and no-metric music. Full TDD develpment of the layouting algorithms, nearly from scratch.
In this paper I will document current Lomse ideas and implementation but. when appropriate, I will also describe the drawbacks of previous abandoned approaches.
When layouting a score the available information will greately vary from only the musical aspects (i.e. a MIDI file without any information about layouting) to a full description for printing (i.e. a detailed LDP or MusicXML file with all details, including positioning information for every symbol).
The most simple approach (full layouting information present in the score file) would imply giving full responsibility to the user: do not add anything not enterd by the user. It is the same situation in traditional engraving with pen and paper. The scores editor becomes just a drawing program. As an improvement, the program could have knowledge about music engraving, but oriented to check for problems and errors. When the user has finished engraving the score and drawing all details, the user could click on a button to validate the engraving and, perhaps, fix some minor issues.
Once the engraved score is saved in a file, including all positioning information (even system and page breaks) no future needs for user intervention when having to render again the score.
But this simple approach is not enough for Lomse. The Lomse library should be able to produce acceptable results with any input, ranging from the two previously described extremes:
Lomse first objective is supporting the LenMus program. This implies two needs:
As my objective is, mainly, an interactive editor for music students and simple scores, pragmatic solutions and ad hoc methods will be preferred, even if they do not solve all cases. High quality automatic engraving is not the main objective but:
Lomse will consider high quality engraving as a manual process:
Initially, three requirements were established:
In following paragraphs I elaborate more on these requirements and comment on current Lomse achievement level.
Quoting from GUIDO (p.95):
Three essential tasks must be performed when setting music:
- Deciding where to break the lines of a score. This is called line breaking.
- Distributing the space between graphical elements of a single line of music. This is called spacing.
- Connected to line breaking is the task of distributing the lines of a score in such a way that all printed pages are full. A traditional score usually ends at the end of the last page. The problem of finding line breaks so that all pages are full is called page filling.
Current Lomse algorithms only deal with line breaking and page breaking, but not with page filling. Nevertheless, the algorithms are ready to take page filling into account and it is mainly improving the page break algorithm to take page filling into account.
It should be possible to split a long measure in two or more systems. Scores without barlines (no-metric music), such as many from Eric Satie, should be layouted without problems with no need for the user to do special actions, such as having to insert hidden barlines.
Multi-metric music, that is scores with several instruments in with two or more time signatures are used simultaneusly (i.e. Don Giovanni opera, from Mozart, in the minuet in the first act Finale, No.13) should be also automatically layouted by Lomse without requiring tricks such as inserting hidden barlines.
Current Lomse algorithms fully support multi-metric and no-metric music.
When the score is updated it should be posible to re-layout only the affected measures, without having to re-layout the whole score.
Current Lomse algorithms are not fully incremental. Some mechanisms are in place but are not fully developed.
Before describing the approach let me define some concepts and terminology I will use in this document and in code:
Segment is a concept that I will use when refering to one staff and column is the same idea but in reference to a system. The concept of column/segment, as replacement for measure, is the basis for layouting multi-metric music. But do not worry too much, think of column/segment as if it was a measure.
To design the layouting algorithm I started considering the following theoretical approach:
As commented, the idea is to start layouting only relevant staff objects (all ImoStaffObj objects) and engrave details once columns has been created and systems are justified. I will justify here this idea.
In previous versions of the layouting algorithm (LenMus version lower than 5.0), all objects where initially engraved (shapes created) and, later, during vertical alignment of notes and rests and systems justification, all shapes had to be re-positioned or even re-computed. Consider, for instance, the problem of having to split a tie at a system break. If the tie shape is created when the note shape is created, there will be not enough information to decide if the tie must be splitted, because system breaks are not yeet computed. Therefore, the approach of creating all shapes at begining required a lot of work for re-considering shapes and repositioning them. To improve performance, two mechanisms were implemented:
Both approaches were costly and required to place a lot of engraving knowledge on the shapes, which is contrary to the single responsibility design principle [2]. So these mechanisms were abandoned in Lomse algorithms.
In current Lomse algorithm, during column creation only ImoStaffObj objects are taken into account. Current algorithm first creates shapes for ImoStaffObj objects. Later, when the columns are created and systems are justified, the process of engraving all remaining objects (the ImoAuxObj objects) takes place.
But engraving ImoAuxObj objects representing relationships between two or more ImoStaffObj objects (i.e. an slur, it relates several notes/rests) can not be done until the last ImoStaffObj of the relationship (i.e. the last note of the slur) is in a system. For instance, a slur across two or more systems can only be engraved only when all affected systems are created. Therefore, engraving ImoAuxObj objects representing relationships between two or more ImoStaffObj objects must be further delayed until the last object of the relation is included in a system.
The algorithm for layouting scores is, conceptually, a five steps process:
To implement the sketched process the implementation follows the layout architecture described in section Layouting a document: the algorithm. An specialized object, ScoreLayouter, takes the responsibility for layouting a score. As with any other layouter, the whole algorithm is driven by two methods: prepare_to_start_layout() and layout_in_box().
The first two previously commented steps (create the columns and layout each column) are performed in the preparation phase (prepare_to_start_layout() method). The other three steps (create the systems; fill pages; and engrave the details) are done in the page filling phase (layout_in_box() method).
Here is the algorithm at high level. I will explain later, in detail, each step:
LenMusPreparation [prepare_to_start_layout()]:
* Score layouter creates instrument engravers [create_instrument_engravers()]
* instrument engravers decide systems indentation [decide_systems_indentation()]
* instrument engravers are requested to assign height for system
and position for staves.
* Score layouter creates column layouters
* Score layouter asks ColumsBuilder to create the columns.
* To create a column:
* create_column_boxes():
* create_slice_box()
* for each instrument, create a slice:
* find_and_save_context_info_for_this_column();
* collect_content_for_this_column():
* explore staff objs collection and engrave column
staff objects (but they are not added to any box)
* Layout column (only staff objects) [layout_column()]
Page filling [layout_in_box()]:
* When score layouter is asked to fill one page:
* If it is first page, apply the line break algorithm to decide on
line breaks. Break points are stored.
* Enter in a loop to create systems until the page is full.
* To create a system:
* create and save a system layouter
* create a system box [create_system_box()]
* fill system with columns until next break point
* justify_current_system();
* engrave_system_details();
* Score layouter engraves Aux Objs for current system
* instrument engraver is requested to engrave staff lines, name/abbrev
and brace/bracket.
* add_initial_line_joining_all_staves_in_system
This algorithm (algorithm-2) is in use in Lomse since SVN rev.25 included. The initial approach for line breaking (see Algorithm 1 for score layouting) was a first-fit: line breaks were decided as systems are set, by filling a line until no more columns could be added. Algorithm 1 was the algorithm used in LenMus (until version 4.3 included) and in Lomse (up to SVN rev.23 included). It was modified and transformed in the described algorithm (algorithm-2) because algorithm-1 did not justify the last system: breaking a line when no more columns can be added doesn’t allow for any optimization, and there are great chances that last system is too short to be justifiable. In current algorithm-2, all columns are measured before deciding where to introduce the line breaks. By knowing in advance all columns’ sizes, line breaks can be optimized for ensuring that the last system is of similar size than all others.
(To be continued ...)
| [TODO8] | In current code, the linking mechanism between shapes is still in place but it is not used. I’ve decided not to remove it until confirming that it is not really necessary for score edition (although I already have strong fillings about it). It should be removed when finally confirmed. See Delayed engraving of auxiliary objects. |
| [1] | Kai Renz, “Algorithms and Data Structures for a Music Notation System based on GUIDO Music Notation”, PhD Thesis, Darmstadt University of Technology, 2002. Available online from http://www.noteserver.org/diss_kai_final/diss_final.pdf. |
| [2] | Robert C. Martin, “Agile Software Development: Principles, Patterns, and Practices”, 2002. Chapter 9, “The Single Responsibility Principle”. This chapter is available online from http://www.objectmentor.com/resources/articles/srp.pdf. |