Bresenham Implementation of the Euclidean Rhythm Algorithm in SuperCollider

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 ]
*/

8 Likes

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

Thanks for sharing, I was just looking for that!

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

grafik

n = 8, k is 9:
grafik

n = 8, k is 10:
grafik

n= 8, k is 11:
grafik

n=8, k is 12:
grafik

etc. up to:

n=8, k is 16:
grafik

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);
2 Likes

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