Bresenham Implementation of the Euclidean Rhythm Algorithm in SuperCollider

[Iannis_Zannos]

Hello,

The Euclidean Rhythm Algorithm by G. Toussaint is an interesting way to create rhythmic patterns, some of which coincide with well known rhythms in various cultures. (https://en.wikipedia.org/wiki/Euclidean_rhythm). Out of the 3 versions of the algorithm known to me, the Bresenham algorithm is the simplest one. Here is an implementation of that algorithm in SuperCollider, in a single statement. I submit this as an example of the expressive power of sclang and a demo of some useful aspects of coding with numerical arrays (instead of explicit iteration).

Cheers,
Iannis Zannos

Attached: (a) Inline code in message, (b) link to jist.

/* Sources: 
See: https://codepen.io/Dafuseder/pen/WEqOVw
https://gist.github.com/crashingbooth/e9f0b7dbec8aecabf13db3663d28480f
https://medium.com/code-music-noise/euclidean-rhythms-391d879494df
*/
//:Implementation 1 (plain)
(
~br = { | o = 1, p = 4 |
	(o / p * (0..p - 1)).floor.differentiate.asInteger.put(0, 1);
};
// test: 
(0..12) do: { | i | postf("bresenham plain. i: %, rhythm: %\n", i, ~br.(i, 8)) };
)
/* // RESULT 1: 
bresenham plain. i: 0, rhythm: [ 1, 0, 0, 0, 0, 0, 0, 0 ] // error
bresenham plain. i: 1, rhythm: [ 1, 0, 0, 0, 0, 0, 0, 0 ]
bresenham plain. i: 2, rhythm: [ 1, 0, 0, 0, 1, 0, 0, 0 ]
bresenham plain. i: 3, rhythm: [ 1, 0, 0, 1, 0, 0, 1, 0 ]
bresenham plain. i: 4, rhythm: [ 1, 0, 1, 0, 1, 0, 1, 0 ]
bresenham plain. i: 5, rhythm: [ 1, 0, 1, 0, 1, 1, 0, 1 ]
bresenham plain. i: 6, rhythm: [ 1, 0, 1, 1, 1, 0, 1, 1 ]
bresenham plain. i: 7, rhythm: [ 1, 0, 1, 1, 1, 1, 1, 1 ]
bresenham plain. i: 8, rhythm: [ 1, 1, 1, 1, 1, 1, 1, 1 ]
bresenham plain. i: 9, rhythm: [ 1, 1, 1, 1, 1, 1, 1, 1 ]
bresenham plain. i: 10, rhythm: [ 1, 1, 1, 1, 2, 1, 1, 1 ]
bresenham plain. i: 11, rhythm: [ 1, 1, 1, 2, 1, 1, 2, 1 ]
bresenham plain. i: 12, rhythm: [ 1, 1, 2, 1, 2, 1, 2, 1 ]
*/
//:Implementation 2 (allow o == 0, o > p)
(
~br1 = { | o = 1, p = 4 |
	(o / p * (0..p - 1)).floor.differentiate.asInteger.min(1)[0] = if (o <= 0) { 0 } { 1 };
	// Note: the if (o <= 0) statement covers the case when we want 0 beats
	// in the pattern
};
//
(0..12) do: { | i | postf("bresenham improved. i: %, rhythm: %\n", i, ~br1.(i, 8)) };
)
/* // RESULT 2: 
bresenham improved. i: 0, rhythm: [ 0, 0, 0, 0, 0, 0, 0, 0 ]
bresenham improved. i: 1, rhythm: [ 1, 0, 0, 0, 0, 0, 0, 0 ]
bresenham improved. i: 2, rhythm: [ 1, 0, 0, 0, 1, 0, 0, 0 ]
bresenham improved. i: 3, rhythm: [ 1, 0, 0, 1, 0, 0, 1, 0 ]
bresenham improved. i: 4, rhythm: [ 1, 0, 1, 0, 1, 0, 1, 0 ]
bresenham improved. i: 5, rhythm: [ 1, 0, 1, 0, 1, 1, 0, 1 ]
bresenham improved. i: 6, rhythm: [ 1, 0, 1, 1, 1, 0, 1, 1 ]
bresenham improved. i: 7, rhythm: [ 1, 0, 1, 1, 1, 1, 1, 1 ]
bresenham improved. i: 8, rhythm: [ 1, 1, 1, 1, 1, 1, 1, 1 ]
bresenham improved. i: 9, rhythm: [ 1, 1, 1, 1, 1, 1, 1, 1 ]
bresenham improved. i: 10, rhythm: [ 1, 1, 1, 1, 1, 1, 1, 1 ]
bresenham improved. i: 11, rhythm: [ 1, 1, 1, 1, 1, 1, 1, 1 ]
bresenham improved. i: 12, rhythm: [ 1, 1, 1, 1, 1, 1, 1, 1 ]
*/

https://gist.github.com/iani/f88b12bcf0d97f8a41f60ab3fe4f3d42

[kflak]

Thanks a lot for this! Extremely useful for my current rhythmical explorations

[Sem_16161d]

Thanks for sharing, I was just looking for that!

[dietcv]

i have implemented the Bresenham algorithm as presented in the gen~ book in SC for creating Euclidean patterns:

the cool thing is you can reverse the pattern by using negative integers for n or k and additionally you can create ratchets by using an integer for k which is bigger then n:

(
var rampToTrig = { |phase|
	var history = Delay1.ar(phase);
	var delta = (phase - history);
	var sum = (phase + history);
	var trig = (delta / sum).abs > 0.5;
	Trig1.ar(trig, SampleDur.ir);
};

{
	var rate = 100;
	var measurePhase = (Phasor.ar(DC.ar(0), rate * SampleDur.ir) - SampleDur.ir).wrap(0, 1);
	var stepsPerMeasure = 8;

	var stepPhase = (measurePhase * stepsPerMeasure).wrap(0, 1);
	var stepTrigger = rampToTrig.(stepPhase);

	var numSize = \numSize.ar(8);
	var numHits = \numHits.ar(9);
	var offset = \offset.ar(0);

	var ratio = Latch.ar(numHits.floor / numSize.floor, stepTrigger);
	var ratioAbs = ratio.abs;
	var rampDirection = ratio.sign;
	var ratchetLevel = ratioAbs.ceil;
	var ratchets = 2 ** (ratchetLevel - 1);

	var stepPhaseRotated = ((measurePhase * stepsPerMeasure) - Latch.ar(offset.floor, stepTrigger) * rampDirection).wrap(0, numSize);
	var stepIndex = stepPhaseRotated.floor;

	var lastEvent = (stepIndex * ratioAbs).floor;
	var currentEvent = (lastEvent / ratioAbs).ceil;
	var nextEvent = ((lastEvent + ratchetLevel) / ratio.abs).ceil;

	var stepDuration = nextEvent - currentEvent;

	var eventPhase = (stepPhaseRotated - currentEvent / stepDuration * ratchets).wrap(0, 1);

	[measurePhase, eventPhase];
}.plot(0.011);
)

ratchets:

n and k both are 8

n = 8, k is 9:

n = 8, k is 10:

n= 8, k is 11:

n=8, k is 12:

etc. up to:

n=8, k is 16:

and beyond…

Here is one example of n = 24, k=11 running at 120 bpm at 4/4 with 16 steps per measure deriving triggers from the ramps:

(
var rampRotate = { |phase, offset|
	(phase - offset).wrap(0, 1);
};

var rampFromBPM = { |bpm, beatsPerMeasure, reset|
	var beatsPerSec = bpm / 60;
	var measureRate = beatsPerSec / beatsPerMeasure;
	var measurePhase = Phasor.ar(reset, measureRate * SampleDur.ir);
	rampRotate.(measurePhase, SampleDur.ir);
};

var rampToTrig = { |phase|
	var history = Delay1.ar(phase);
	var delta = (phase - history);
	var sum = (phase + history);
	var trig = (delta / sum).abs > 0.5;
	Trig1.ar(trig, SampleDur.ir);
};

var rampToEuclidean = { |measurePhase, stepsPerMeasure, numSize, numHits, offset|

	var measurePhaseScaled = measurePhase * stepsPerMeasure;
	var stepPhase = measurePhaseScaled.wrap(0, 1);
	var stepTrigger = rampToTrig.(stepPhase);

	var ratio = Latch.ar(numHits.floor / numSize.floor, stepTrigger);
	var ratioAbs = ratio.abs;
	var rampDirection = ratio.sign;
	var ratchetLevel = ratioAbs.ceil;
	var ratchets = 2 ** (ratchetLevel - 1);

	var stepPhaseRotated = (measurePhaseScaled - Latch.ar(offset.floor, stepTrigger) * rampDirection).wrap(0, numSize);
	var stepIndex = stepPhaseRotated.floor;

	var lastEvent = (stepIndex * ratioAbs).floor;
	var currentEvent = (lastEvent / ratioAbs).ceil;
	var nextEvent = ((lastEvent + ratchetLevel) / ratio.abs).ceil;

	var stepDuration = nextEvent - currentEvent;

	(stepPhaseRotated - currentEvent / stepDuration * ratchets).wrap(0, 1);
};

SynthDef(\test, {

	var reset = \reset.tr(0);
	var measurePhase = rampFromBPM.(\bpm.kr(120), \beatsPerMeasure.kr(4), reset);
	var stepsPerMeasure = 16;

	var numSize = \numSize.ar(24);//K2A.ar(MouseY.kr(8, 32)).poll(label: \numSize);
	var numHits = \numHits.ar(11);//K2A.ar(MouseX.kr(5, 32)).poll(label: \numHits);
	var offset = \offset.ar(0);

	var eventPhase = rampToEuclidean.(measurePhase, stepsPerMeasure, numSize, numHits, offset);
	var eventTrigger = rampToTrig.(eventPhase);

	var sig = eventTrigger!2 * 0.5;

	Out.ar(\out.kr(0), sig);
}).add;
)

Synth(\test);

[Iannis_Zannos]

Wow!

Thank you very much for sharing this.

Just yesterday I came across the euclidean rhythm pattern generator
in TidalCycles, and so I tried to find my own implementation here.
I failed, but then your email brought me back to it. It is encouraging
to see the feedback to this post.
Now I am trying to build bridges to the TidalCycles approach in
my own library, (sc-hacks-redux), and I believe there is a lot of
interesting musical ground to discover by exploring the ground
beyond the cycle approach and combining it with other approaches.

Also, your implementation of this as a synthdef is great.
Building a generalized cycles engine on the server is a
very promising approach in this context.

I hope we can exchange more on this topic and meet in person some time.
In the meanwhile, waiting to see what you make with your implementation.

Best regards,

Iannis Zannos