Bresenham's Line Algorithm suggests 4 step sizes for rank-3 MOS

Keenan described MOS's as fundamentally resulting from a periodicity
block in octave-explicit space that you're shearing so as to draw a
pixelated line from 1/1 to 2/1. Or, in other words, MOS's are
fundamentally what you get if you set up a generalized keyboard with
two axes of your choice, and draw a line from 1/1 to 2/1.

I noted that this is Bresenham's line algorithm:
http://en.wikipedia.org/wiki/File:Bresenham.svg (hey, look it's
orwell! No, wait, it's semaphore!)

If you load up a Bosanquet keyboard and play an octave of 5L2s, you'll
note that you've just traced out a Bresenham line from 1/1 to 2/1.
More precisely, if you start with the meantone lattice, set one of the
axes to <5 8 14| and the other to <7 11 16| (meaning your generators
are 9/8 and 16/15), the 5L2s MOS will be a Bresenham line from1/1 to
2/1.

Bresenham lines end up moving by one of two fundamental directions -
up or up-right (or some rotation of this). Bresenham's algorithm
attempts to make the line as smooth as possible, evenly distributing
these motions, so that the line doesn't look lumpy. The way it evenly
distributes them is related to Euclid's algorithm:
http://www.cs.tau.ac.il/~nachum/calendar-book/papers/bresenham.pdf

So what about rank-3 MOS's? They'll require a 3d generalized keyboard.
If you do this whole thing out again in 3d, and apply Bresenham's
algorithm, you do sometimes indeed get four step sizes, not three. For
example, here's the points Bresenham's algorithm suggests for the line
going from the point (0, 0, 0) to (11, 4, 3):

x y z
0 0 0
1 0 0
2 1 1
3 1 1
4 1 1
5 2 1
6 2 2
7 3 2
8 3 2
9 3 2
10 4 3
11 4 3

By treating this as a matrix and taking the difference of successive
rows, hence telling us what differential direction we move into get
each successive pixel, we get this:

1 0 0
1 1 1
1 0 0
1 0 0
1 1 0
1 0 1
1 1 0
1 0 0
1 0 0
1 1 1
1 0 0

There are only four unique row entries in this matrix, and they are:

1 0 0
1 1 0
1 0 1
1 1 1

Or, in other words, we can move by (1, 0, 0), (1, 1, 0), (1, 0, 1), or
(1, 1, 1). These points form a square on the lattice, and represent
the four step sizes in our rank-3 MOS. If we take the set of
differences of these points, which yields our chromata for step sizes,
you get

+/- (0, 1, 0): +/- uv1
+/- (0, 0, 1): +/- uv2
+/- (0, 1, 1): +/- (uv1+uv2)
+/- (0, 1, -1): +/- (uv1-uv2)

There's the magic parallelogram.

As a final caveat, I used the MATLAB code here to generate the line:
http://www.mathworks.com/matlabcentral/fileexchange/21057

It's possible that the code has some bug in it, but I've also double
checked here: http://translate.google.com/translate?js=y&prev=_t&hl=es&ie=UTF-8&layout=1&eotf=1&u=http://sites.google.com/site/proyectosroboticos/bresenham-3d&sl=es&tl=en

You can see in the examples posted on the latter site that you end up
getting 4 step sizes as well.

-Mike

--- In tuning-math@yahoogroups.com, Mike Battaglia <battaglia01@...> wrote:

For
> example, here's the points Bresenham's algorithm suggests for the line
> going from the point (0, 0, 0) to (11, 4, 3):

You could try this sort of thing to generate comma pumps also; going from 1/1 to 4375/4374 is going from |* 0 0 0> to |* -7 4 1>, and a Bresenham line would produce pitch classes going from one to the other.

On Wed, Sep 28, 2011 at 11:52 AM, genewardsmith
<genewardsmith@sbcglobal.net> wrote:
>
> --- In tuning-math@yahoogroups.com, Mike Battaglia <battaglia01@...> wrote:
>
> For
> > example, here's the points Bresenham's algorithm suggests for the line
> > going from the point (0, 0, 0) to (11, 4, 3):
>
> You could try this sort of thing to generate comma pumps also; going from 1/1 to 4375/4374 is going from |* 0 0 0> to |* -7 4 1>, and a Bresenham line would produce pitch classes going from one to the other.

Do it with a triangular lattice and you got yerself a winner!

-Mike

On Wed, Sep 28, 2011 at 11:57 AM, Mike Battaglia <battaglia01@gmail.com> wrote:
> On Wed, Sep 28, 2011 at 11:52 AM, genewardsmith
> <genewardsmith@sbcglobal.net> wrote:
>>
>> --- In tuning-math@yahoogroups.com, Mike Battaglia <battaglia01@...> wrote:
>>
>> For
>> > example, here's the points Bresenham's algorithm suggests for the line
>> > going from the point (0, 0, 0) to (11, 4, 3):
>>
>> You could try this sort of thing to generate comma pumps also; going from 1/1 to 4375/4374 is going from |* 0 0 0> to |* -7 4 1>, and a Bresenham line would produce pitch classes going from one to the other.

NM, I was too hasty with the triangular thing, looks like Bresenham
takes care of that for you. But I just realized, this is similar to
something I was thinking of myself the other day - you can generate
MOS's by just creating Bresenham lines from 1/1 to the comma you're
tempering out, not just comma pumps.

You suggested 4375/4374. So here's the ragisma comma pump you ordered:

|* 0 0 0>
|* -1 1 0>
|* -2 1 0>
|* -3 2 0>
|* -4 2 1>
|* -5 3 1>
|* -6 3 1>
|* -7 4 1>

This means you get only 3 step sizes, which are

|* -1 0 0> - 4/3
|* -1 1 0> - 5/3
|* -1 0 1> - 7/6

Beautiful and triangularized! On the other hand, if you only want
steps of 3/2, 5/4, and 7/4, you can generate a "superline" instead -
this guy's algorithm is an example (but not perfect for our purposes):
http://lifc.univ-fcomte.fr/~ededu/projects/bresenham/

Maybe you can synthesize a MIDI example of what the above pump sounds like?

-Mike

--- In tuning-math@yahoogroups.com, Mike Battaglia <battaglia01@...> wrote:
>
> Keenan described MOS's as fundamentally resulting from a periodicity
> block in octave-explicit space that you're shearing so as to draw a
> pixelated line from 1/1 to 2/1. Or, in other words, MOS's are
> fundamentally what you get if you set up a generalized keyboard with
> two axes of your choice, and draw a line from 1/1 to 2/1.
>
> I noted that this is Bresenham's line algorithm:
> http://en.wikipedia.org/wiki/File:Bresenham.svg (hey, look it's
> orwell! No, wait, it's semaphore!)

Bresenham's line algorithm is one specific way to compute 0-connected (that is, pixels that touch corners are considered connected) discrete lines in 2D.

I had in mind discrete lines that are (d-1)-connected (that is, only pixels with Euclidean distance 1 are considered connected).

In 2D, there is a simple relationship between 0-connected and 1-connected discrete lines: just add the appropriate "corners" to a 0-connected line and you get a 1-connected line. But in 3D there is no such simple relationship between 0-connected and 2-connected discrete lines.

> Bresenham lines end up moving by one of two fundamental directions -
> up or up-right (or some rotation of this). Bresenham's algorithm
> attempts to make the line as smooth as possible, evenly distributing
> these motions, so that the line doesn't look lumpy. The way it evenly
> distributes them is related to Euclid's algorithm:
> http://www.cs.tau.ac.il/~nachum/calendar-book/papers/bresenham.pdf

In the 0-connected case the two directions are indeed up and up-right. In the 1-connected case they're simply up and right.

In 3D, in the 0-connected case you have four possible directions: (0,0,1), (1,0,1), (0,1,1), and (1,1,1). In the 2-connected case there are only three possible directions: (1,0,0), (0,1,0), and (0,0,1).

> There are only four unique row entries in this matrix, and they are:
>
> 1 0 0
> 1 1 0
> 1 0 1
> 1 1 1

Right, this is what you get for 0-connected.

> Or, in other words, we can move by (1, 0, 0), (1, 1, 0), (1, 0, 1), or
> (1, 1, 1). These points form a square on the lattice, and represent
> the four step sizes in our rank-3 MOS. If we take the set of
> differences of these points, which yields our chromata for step sizes,
> you get
>
> +/- (0, 1, 0): +/- uv1
> +/- (0, 0, 1): +/- uv2
> +/- (0, 1, 1): +/- (uv1+uv2)
> +/- (0, 1, -1): +/- (uv1-uv2)
>
> There's the magic parallelogram.

I think this whole process, with 0-connected lines, is equivalent to the definition for Fokker blocks given here: http://xenharmonic.wikispaces.com/Fokker+blocks . So this is simply an alternate definition for Fokker blocks.

Another way to see this is that the projections of your 3D 0-connected line in the y and z directions (the two axes perpendicular to the main direction of the line) are 2D 0-connected lines, a.k.a. MOSes. So you get a scale such that if you temper out either of two chromata, you get a MOS. This is the defining property of a free Fokker block.

However, I think that 2-connected 3D discrete lines will define a different kind of scale. They will have 3 steps, because there are only 3 possible directions for a 2-connected discrete line. And all 3 projections are 1-connected 2D discrete lines, but instead of tempering out chromata, this corresponds to tempering out scale *steps*, making smaller scales.

Keenan

This is it right here: http://dx.doi.org/dx.doi.org/10.1007/978-3-642-19867-0_4

These French guys already have it all figured out.

Here's the same stuff in the form of a slideshow: http://dgci2011.loria.fr/Presentations/Talks/Berthe+Labbe-talk-DGCI2011.pdf

(BTW, if anyone would like copies of any papers I post, I can email to people individually. I have access through UC Berkeley.)

Keenan

--- In tuning-math@yahoogroups.com, "Keenan Pepper" <keenanpepper@...> wrote:
>
> This is it right here: http://dx.doi.org/dx.doi.org/10.1007/978-3-642-19867-0_4

Whoops, obviously this is supposed to be

http://dx.doi.org/10.1007/978-3-642-19867-0_4

Keenan

It looks like these lines are generated by applying Euclid's algorithm
to 3-tuples of integers. So I guess that brings us back to a
definition of MOS that necessitates a step size of N=3, with the step
sizes distributed as far apart as possible.

(You mentioned rational beatty sequences as being one way to
distribute them, but I'm not sure if they're the same as or different
from what Euclid's algorithm gives you, not being too familiar with
either).

My vote is that this is too restrictive to be an all-encompassing
definition for MOS; I don't see any reason why a step size of N=4
wouldn't work.

Maybe I should just lay out exactly what I, personally, want, in
regular terms. Then, anyone else can lay out what they like about MOS
as well, and we'll see if there's a unique set of features that they
share.

I like to switch between things like C ionian to C dorian to C lydian
dominant and such, and when I studied jazz at UM much of the theory
revolved around becoming fluent in that sort of modal harmony. To do
all of that stuff, the most important thing is seeing how the MOS lays
out against the backdrop of a larger, "chromatic" MOS. Also, what's
important is seeing how the MOS is actually made up of a chain of
generators, so I know that Lydian lies "adjacent" to Ionian in the
"minor" direction. What this all means is that I'm really interested
in the MOS scale tree, because that's ultimately what makes all of
this stuff possible.

Rank-3 MOS's have the potential to lead to the most insanely awesome
modal harmonies the world has ever heard, because there's more
chromata and hence no one unique chromatic extension. There's also not
one unique chain of generators - there are two generator chains which
form a "field" of notes, perhaps triangular or parallelogramar (?) or
hexagonal in shape. So the full exploration of rank-3 modal harmony
will entail that there are two orthogonal directions to shift
everything in, which synesthetically speaking will be able to purify
men's souls on the spot as well as resurrect the dead.

So basically, I'm mainly concerned with figuring out what the rank-3
MOS scale tree looks like. I can't believe that it's going to be a DAG
- I think it's more likely that it'll end up being in some way
analogous to the rank-2 scale tree. I'm going to suggest that the
scale tree for rank-3 will be 3-dimensional, e.g. entries will be of
the form #L#m#n#s, and that for scales with N=3 step sizes, one of
those numbers will simply be zero. We can limit the "MOS" term to the
N=3 step size case, but then we need a name for the larger structure.

-Mike

On Wed, Sep 28, 2011 at 3:23 PM, Keenan Pepper <keenanpepper@gmail.com> wrote:
>
> This is it right here: http://dx.doi.org/dx.doi.org/10.1007/978-3-642-19867-0_4
>
> These French guys already have it all figured out.
>
> Here's the same stuff in the form of a slideshow: http://dgci2011.loria.fr/Presentations/Talks/Berthe+Labbe-talk-DGCI2011.pdf
>
> (BTW, if anyone would like copies of any papers I post, I can email to people individually. I have access through UC Berkeley.)
>
> Keenan

--- In tuning-math@yahoogroups.com, Mike Battaglia <battaglia01@...> wrote:
>
> It looks like these lines are generated by applying Euclid's algorithm
> to 3-tuples of integers. So I guess that brings us back to a
> definition of MOS that necessitates a step size of N=3, with the step
> sizes distributed as far apart as possible.

Yeah, that's what I'm currently going for.

> (You mentioned rational beatty sequences as being one way to
> distribute them, but I'm not sure if they're the same as or different
> from what Euclid's algorithm gives you, not being too familiar with
> either).

They are different. For example, no DCSRBS exists with 3 'a's, 2 'b's, and 1 'c', but most of the different Euclidean algorithms are guaranteed to give you a sequence for any numbers of steps.

And do keep in mind that there's no single 3D generalization of Euclid's algorithm. There are at least 4 different ones.

> My vote is that this is too restrictive to be an all-encompassing
> definition for MOS; I don't see any reason why a step size of N=4
> wouldn't work.

Depends what you mean by "work", of course.

> Maybe I should just lay out exactly what I, personally, want, in
> regular terms. Then, anyone else can lay out what they like about MOS
> as well, and we'll see if there's a unique set of features that they
> share.
>
> I like to switch between things like C ionian to C dorian to C lydian
> dominant and such, and when I studied jazz at UM much of the theory
> revolved around becoming fluent in that sort of modal harmony. To do
> all of that stuff, the most important thing is seeing how the MOS lays
> out against the backdrop of a larger, "chromatic" MOS. Also, what's
> important is seeing how the MOS is actually made up of a chain of
> generators, so I know that Lydian lies "adjacent" to Ionian in the
> "minor" direction. What this all means is that I'm really interested
> in the MOS scale tree, because that's ultimately what makes all of
> this stuff possible.
>
> Rank-3 MOS's have the potential to lead to the most insanely awesome
> modal harmonies the world has ever heard, because there's more
> chromata and hence no one unique chromatic extension. There's also not
> one unique chain of generators - there are two generator chains which
> form a "field" of notes, perhaps triangular or parallelogramar (?) or
> hexagonal in shape. So the full exploration of rank-3 modal harmony
> will entail that there are two orthogonal directions to shift
> everything in, which synesthetically speaking will be able to purify
> men's souls on the spot as well as resurrect the dead.

Haha, I'm glad someone is so excited, er... I'm glad someone sees the true potential of this.

> So basically, I'm mainly concerned with figuring out what the rank-3
> MOS scale tree looks like. I can't believe that it's going to be a DAG
> - I think it's more likely that it'll end up being in some way
> analogous to the rank-2 scale tree. I'm going to suggest that the
> scale tree for rank-3 will be 3-dimensional, e.g. entries will be of
> the form #L#m#n#s, and that for scales with N=3 step sizes, one of
> those numbers will simply be zero. We can limit the "MOS" term to the
> N=3 step size case, but then we need a name for the larger structure.

I'm interested to see what you come up with.

Personally I'm against using the term "MOS" for anything other than rank 2, to avoid confusion. Even if I found what was surely the One True MOS Analogue, I wouldn't just call it a "MOS", I'd call it something else.

Keenan

http://diwww.epfl.ch/w3lsp/publications/discretegeo/nratddl.html

This paper defines 26-connected discrete lines in a way that makes them identical to free Fokker block scales.

In particular it shows there are c^2 different versions of the line with vector (a,b,c) (c>b>a), which fall into c combinatorially distinct classes, which is something we already knew about Fokker block scales with c notes in their, shall we say, "irreducible" block, which is the block you get if you divide each UV by the gcd of its entries.

So a Figueiredo discrete line is a Fokker block scale, but other discrete line definitions will lead to different kinds of scales.

Keenan

Keenan wrote:
> http://dx.doi.org/dx.doi.org/10.1007/978-3-642-19867-0_4

I think you meant http://dx.doi.org/10.1007/978-3-642-19867-0_4

-Carl

Keenan wrote:

>Haha, I'm glad someone is so excited, er... I'm glad someone sees the
>true potential of this.

I'll weigh in to say I think it's of theoretical interest only.
Rank 2 scales other than meantone already have complexity problems.

>Personally I'm against using the term "MOS" for anything other than
>rank 2, to avoid confusion. Even if I found what was surely the One
>True MOS Analogue, I wouldn't just call it a "MOS", I'd call it
>something else.

Good idea.

-Carl