midisort: sonification & visualization of sorting algorithms using MIDI note number (for Mac OSX)

Music 256: Music | Computing | Design (Autumn 2008-2009)

Final Project by Jieun Oh

project motivation & vision

My goal for the Music 256 final project is to sonify and visualize elementary sorting algorithms-- because programming (and learning about programming concepts) is fun, especially with auditory and visual interactions!

Depending on the success of this mini-project, I’d like to consider the greater vision of sonifying andvisualizing concepts in programming and discrete math, such as sorting and searching algorithms; recursive functions; path finding in graphs/ trees and coloring of their nodes. It would also be interesting to be able to evaluate data structure choices—arrays, linked lists, map, trees, etc—given a context of tasks to perform.

 

specifications

minimal essential system (implemented, as of 12/12/2008)

1. Input a sequence of midi-notes: Live input using a MIDI keyboard or other MIDI devices
2. Display the original input based on pitch information
3. Sort the pitch using a selected sorting algorithm, visualizing and sonifying the process
4. Display the resulting sorted pitch information
5. Display algorithm evaluation: track timing, swap, comparisons statistics

beyond minimal: other desirable features (in progress and not yet incorporated, as of 12/12/2008)

1. Do all of the above preserving the rhythm information associated with each note: makes it more musical and fun
2. Add an option to read input from an existing MIDI file
3. Have an interface to compare algorithms
4. Be able to specify the comparison function to define the “ascending order" (i.e. using not necessarily MIDI key number; other obvious possibilities are rhythmic and velocity information in ascending or descending order)

milestones (as planned on 11/21/2008; this schedule was modified in various ways in practice!)

1. figure out various sorting algorithms (import from somewhere…) – over Thanksgiving
2. setup MIDI input to correctly read and save pitch data – over Thanksgiving
3. visualize and sonify the original array of pitches – over Thanksgiving
4. visualize and sonify the sorted outcome – over Thanksgiving
5. visualize and sonify the sorting process – by 12/4
6. work on displaying algorithm evaluation – by 12/7
7. work on “other desirable features” – post 256, possibly over winter break!

software design overview

1. approx. 30% from HW 2 (MIDI input played through Karplus-Strong algorithm implementation)
2. approx. 30% from HW3 (modified OpenGL "waterfall" code from sndpeek)
3. approx. 40% "new": applying sonification and visualization techniques to various sorting algorithms

 

implementation (designed for Mac OSX)

download .zip file --or -- page with individual files

documentation

README (also downloadable from above):

[1] How to run

You will need the following files:

(download from http://ccrma.stanford.edu/~jieun5/256/midisort.zip)

1. midisort.cpp: main file for the program
2. RtAudio.h, RtAudio.cpp, RtError.h: for real time audio capabilities
3. RtMidi.h, RtMidi.cpp: for MIDI input
4. Karplus.h, Karplus.cpp: implementation of the Karplus-Strong algorithm used in RtAudio callback
5. makefile

To run:

1. connect an MIDI input and test port with the optional midiprobe file
2. type "make" followed by ./midisort (optional addition: -bubble -selection -insertion -shell to specify algorithm)
3. input MIDI notes. once done, press enter
4. graphics window will show up. click on the window to make it active.
5. enter appropriate keyboard command to manipulate
6. press 'h' anytime for keyboard controls help menu
7. press 'q' to quit

Note:

To manually populate MIDI key numbers (instead of using an input device), set g_MIDIin (line 85) to be false. Then specify the desired key numbers in the setupMidiInput function (line 218).

[2] Functionality

• input options: MIDI device or manual note-number specification
• choice of sorting algorithms: bubble sort, insertion sort, selection sort, shell sort
  (these are popular sorting algorithms that can be easily implemented with array/ vector data structure;
  other algorithms, such as merge sort and quick sort was omitted because they require different structures
  and involve a different kind of analysis for statistics calculation.)
  
• play, repeat, or skip forward stages until the note-sequences are completely sorted (with keyboard inputs)
• plays the midi notes in plucked string sound, and visualizes the contour using a line graph for each stage visited
• rotate, tilt, and zoom z-axis for the graphics (using keyboard inputs)
  

[3] Bugs & Things to Improve on

• currently the program is fragile with occasional bus errors :(
• need to take care of memory cleanup
• feature to add #1: preserve the rhythm with which the notes were added when sorting and playing through stages
• feature to add #2: have an interface to easily compare two (or more) algorithms using the same input notes
• feature to add #3: have an option to read data from a midi file
• define comparison function to specify what to sort in what order

[4] Reflections

• keeping track of various threads running simultaneously was troublesome (I could not master mutex/ lock/ wait placements that would get rid of the unpredictable bus error.)
• still having a difficult time how the coordinate system works in OpenGL: the way it is done now is a result of trial-and-error, and by no means is done using the correct "logic" (as as result, changing a parameter may have unwanted side-effects on the positioning/ viewing of other features.)
• it was fun to be able to incorporate code used from the past (specifically HW2 and HW3) and re-use them constructively
• Sorting real-time as we step through vs. storing each stages of the sorting algorithm and accessing them after the fact: chose the latter option, but as a result had to use a fairly large vector of vectors.
• I like the outcome: it's quite fun to see and hear what the algorithm does to pitch pattern