# Sierpinksi on a 16x16 matrix

I wanted to see how well antialiasing and the persistence of vision on HDR SK9822s would give the impression of a higher-resolution thingy. So, here’s a spinning zooming wobbling Sierpinski gasket!

See if you can spot the 1-character change between the video and the code below.

Sierpinski gasket drawn with Wu antialiasing

``````// Made for fun. Share and enjoy.

// This pattern creates a rectangular framebuffer
// and does its own integer coordinate mapping
// and draws a moving Sierpinski triangle
// using Xiaolin Wu's antialiased line algorithm.

var blur = 0
export function sliderMotion_Blur(v) {
blur = v * 3/5
}

// export var hour, minute, second, hx, hy, mx, my, sx, sy

// Duplicate PixelBlaze 'Mapper' functionality without normalizing

var width = 16
var height = width
var mid = width/2 - 0.5
var midm1 = mid - 1
var midm2 = mid - 2
var hlen = midm2 * 2/3

var coordmap = array(pixelCount)

for (index=0; index<pixelCount; index++) {
x = floor(index / height)
y = index % height
y = x % 2 == 1 ? height - 1 - y : y // I have a zigzag LED matrix
coords = array(2)
coords[0] = x
coords[1] = y
coordmap[index] = coords
}

// HSV to RGB using global variables

var r, g, b // filled by HSVtoRGB

function HSVtoRGB(h, s, v) {
var i, f, p, q, t;
i = floor(h * 6);
f = h * 6 - i;
p = v * (1 - s);
q = v * (1 - f * s);
t = v * (1 - (1 - f) * s);
im6 = i % 6
if (im6 == 0) {
r = v; g = t; b = p;
} else { if (im6 == 1) {
r = q; g = v; b = p;
} else { if (im6 == 2) {
r = p; g = v; b = t;
} else { if (im6 == 3) {
r = p; g = q; b = v;
} else { if (im6 == 4) {
r = t; g = p; b = v;
} else {if (im6 == 5) {
r = v; g = p; b = q;
}}}}}}
}

// RGB framebuffer
// ... Storage

var Pr = array(width); for (i=0; i<width; i++) Pr[i] = array(height)
var Pg = array(width); for (i=0; i<width; i++) Pg[i] = array(height)
var Pb = array(width); for (i=0; i<width; i++) Pb[i] = array(height)

// ... Render a pixel
//  - Only used by WuLine, so we do 'alpha' here to keep WuLine readable
//  - Uses max() so overlapping line pixels don't make bright spots

function PixelMax(x,y,a,h,s,v) {
if (x >= 0 && x < width && y >= 0 && y < height) {
HSVtoRGB(h,s,v*a*a*a)
Pr[x][y] = max(Pr[x][y], r)
Pg[x][y] = max(Pg[x][y], g)
Pb[x][y] = max(Pb[x][y], b)
}
}

// just attenuate the existing pixel data by a
function PixelMultiply(x,y,a,h,s,v) {
if (x >= 0 && x < width && y >= 0 && y < height) {
Pr[x][y] = clamp(Pr[x][y] * a, 0, 1)
Pg[x][y] = clamp(Pg[x][y] * a, 0, 1)
Pb[x][y] = clamp(Pb[x][y] * a, 0, 1)
}
}

// Xiaolin Wu's antialiased line algorithm
// (replaced utility functions with PixelBlaze built-ins)

function WuLine(pfn, x0, y0, x1, y1, h, s, v) {
if (x0 == x1 && y0 == y1) return

steep = abs(y1 - y0) > abs(x1 - x0);

if (steep) {
tmp = y0; y0 = x0; x0 = tmp;
tmp = y1; y1 = x1; x1 = tmp;
}

if (x0 > x1) {
tmp = x0; x0 = x1; x1 = tmp;
tmp = y0; y0 = y1; y1 = tmp;
}

dx = x1 - x0;
dy = y1 - y0;

xEnd = round(x0);
yEnd = y0 + gradient * (xEnd - x0);
xGap = 1 - frac(x0 + 0.5);
xPx1 = xEnd;
yPx1 = trunc(yEnd);

if (steep) {
pfn(yPx1, xPx1, 1 - frac(yEnd) * xGap, h, s, v )
pfn(yPx1 + 1, xPx1, frac(yEnd) * xGap, h, s, v )
} else {
pfn(xPx1, yPx1, 1 - frac(yEnd) * xGap, h, s, v )
pfn(xPx1, yPx1 + 1, frac(yEnd) * xGap, h, s, v )
}

xEnd = round(x1);
yEnd = y1 + gradient * (xEnd - x1);
xGap = frac(x1 + 0.5);

xPx2 = xEnd;
yPx2 = trunc(yEnd);

if (steep) {
pfn(yPx2, xPx2, 1 - frac(yEnd) * xGap, h, s, v )
pfn(yPx2 + 1, xPx2, frac(yEnd) * xGap, h, s, v )
} else {
pfn(xPx2, yPx2, 1 - frac(yEnd) * xGap, h, s, v )
pfn(xPx2, yPx2 + 1, frac(yEnd) * xGap, h, s, v )
}

if (steep) {
for (x = xPx1 + 1; x <= xPx2 - 1; x++) {
pfn(trunc(intery), x, 1 - frac(intery), h, s, v )
pfn(trunc(intery) + 1, x, frac(intery), h, s, v )
}
} else {
for (x = xPx1 + 1; x <= xPx2 - 1; x++) {
pfn(x, trunc(intery), 1 - frac(intery), h, s, v )
pfn(x, trunc(intery) + 1, frac(intery), h, s, v )
}
}
}

function Triangle(pfn,value,hrot,ax,ay,bx,by,cx,cy) {
WuLine(pfn,ax,ay,bx,by,hrot,0.75,value)
WuLine(pfn,bx,by,cx,cy,hrot+1/3,0.75,value)
WuLine(pfn,cx,cy,ax,ay,hrot+2/3,0.75,value)
}

function Sierpinski(pfn,depth,value,hrot,ax,ay,bx,by,cx,cy) {
Triangle(pfn,value,hrot,ax,ay,bx,by,cx,cy)

if(depth > 0) {
Triangle(pfn,value,hrot+1/6,(ax+bx)/2,(ay+by)/2,(ax+cx)/2,(ay+cy)/2,(bx+cx)/2,(by+cy)/2)

if(depth > 1) {
nd = depth-1
nv = value/2
nr = hrot+1/3
Sierpinski(pfn,nd,nv,nr,
(3*ax+cx)/4,
(3*ay+cy)/4,
(3*ax+bx)/4,
(3*ay+by)/4,
(2*ax+bx+cx)/4,
(2*ay+by+cy)/4,
)
Sierpinski(pfn,nd,nv,nr,
(3*cx+ax)/4,
(3*cy+ay)/4,
(3*cx+bx)/4,
(3*cy+by)/4,
(2*cx+bx+ax)/4,
(2*cy+by+ay)/4,
)
Sierpinski(pfn,nd,nv,nr,
(3*bx+ax)/4,
(3*by+ay)/4,
(3*bx+cx)/4,
(3*by+cy)/4,
(2*bx+cx+ax)/4,
(2*by+cy+ay)/4,
)
}
}
}

// constants
var pi23 = PI2/3
var pi43 = 2 * PI2/3
var midp = 7.5

// Clear (or fade if blur enabled) framebuffer
// and render the current time

export function beforeRender(delta) {
for (i=0; i<width; i++) {
for (j=0; j<height; j++) {
Pr[i][j] = blur * Pr[i][j]
Pg[i][j] = blur * Pg[i][j]
Pb[i][j] = blur * Pb[i][j]
}
}

rotation = time(0.05) * PI2
hrot = time(0.025)

midx = midp + 2.5 * sin(time(0.087) * PI2)
midy = midp + 2 * cos(time(0.043) * PI2)

Sierpinski(PixelMax,2,1,hrot,ax,ay,bx,by,cx,cy)
}

// Draw from the framebuffer

export function render(index) {
coords = coordmap[index]
x = coords[0]
y = coords[1]

rgb(Pr[x][y], Pg[x][y], Pb[x][y])
}
[details="Summary"]
This text will be hidden
[/details]

``````
3 Likes

Oh, and I’m not entirely happy with how the recursion works. I wanted to make sure that the edges of the big triangle were drawn as one line, instead of recursing by drawing 3 smaller triangles. As usual I stopped once I got it working!

Hey, it looks great on my new (2nd) V3, but I get this message as well

Maybe you have configured more than 256 pixels, so the `coordmap[index]` calculation generates a y value which is > 15, but framebuffer arrays only go up to 15.

These are the hazards of skipping the pixel mapper so I can have integer pixel coordinates.

Ok, I’m super happy with this now. (At least, I’m marking it as ‘done’ on my todo list )

Most importantly the framebuffer is now FB[pixelCount][3] so each Pixel can be retrieved and modified as a single 3-element array. I could have done FB[width][height][3] but sometimes we don’t care about the x,y: calculating motion blur is just `FB.forEach((Pixel) => { Pixel.mutate((v) => { return blur * v } )})`. Super cool is that the “mapper” is IndexPixel[pixelCount]{reference to pixel in FB[]} which makes the render function trivial.

• I fixed the recursion process by drawing the outer triangle separately; the Sierpinski function draws an inner triangle and (when depth > 0) the 3 smaller triangles around it.
• The recursion level is dynamically selected using log2(zoom level) to avoid drawing tiny triangles.
• There are sliders for blur, recursive brightness (each recursion level gets darker), hue-spinning-on recursion, and global saturation. There could always be more knobs, for the various wobbling speeds.
• It should work with any square matrix, though 8x8 is definitely a bit small, and the zigzagging is still hardcoded.
• Dead code removed and minor bugs fixed, as usual.
• Array iteration is done with forEach and mutate for extra speed.
``````// Made for fun. Share and enjoy.

// This pattern creates a rectangular framebuffer
// and does its own integer coordinate mapping
// and draws a moving Sierpinski triangle
// using Xiaolin Wu's antialiased line algorithm.

var blur = 0.5
export function sliderMotionBlur(v) { blur = v * 4/5 }

var darken = 0.5
export function sliderRecursiveBrightness(v) { darken = v }

var huespin = 0
export function sliderHueSpin(v) { huespin = v }

var saturation = 0
export function sliderSaturation(v) { saturation = v }

// Duplicate PixelBlaze 'Mapper' functionality without normalizing

var width = floor(sqrt(pixelCount)) // this had better be square!
var height = width

// RGB framebuffer
// ... Storage

var FB = array(pixelCount)
FB.mutate(()=>{return array(3)})

// ... direct references to pixel by index
var IndexPixel = array(pixelCount)
IndexPixel.mutate((foo,index)=>{
x = floor(index / height)
y = index % height
y = x % 2 == 1 ? height - 1 - y : y // I have a zigzag LED matrix
return FB[x + y * height]
})

// HSV to RGB using global variables

var r, g, b // filled by HSVtoRGB

function HSVtoRGB(h, s, v) {
var i, f, p, q, t;
i = floor(h * 6);
f = h * 6 - i;
p = v * (1 - s);
q = v * (1 - f * s);
t = v * (1 - (1 - f) * s);
im6 = i % 6
if (im6 == 0) {
r = v; g = t; b = p;
} else { if (im6 == 1) {
r = q; g = v; b = p;
} else { if (im6 == 2) {
r = p; g = v; b = t;
} else { if (im6 == 3) {
r = p; g = q; b = v;
} else { if (im6 == 4) {
r = t; g = p; b = v;
} else {if (im6 == 5) {
r = v; g = p; b = q;
}}}}}}
}

// ... Render a pixel
//  - Only used by WuLine, so we do 'alpha' here to keep WuLine readable
//  - Uses max() so overlapping line pixels don't make bright spots

function PixelMax(x,y,a,h,s,v) {
if (x >= 0 && y >= 0 && x < width && y < height) {
HSVtoRGB((h%1),s,v*a*a*a)
Pixel = FB[x + y*height]
Pixel[0] = max(Pixel[0], r)
Pixel[1] = max(Pixel[1], g)
Pixel[2] = max(Pixel[2], b)
}
}

// Xiaolin Wu's antialiased line algorithm
// (replaced utility functions with PixelBlaze built-ins)

function WuLine(pfn, x0, y0, x1, y1, h, s, v) {
if (x0 == x1 && y0 == y1) return

steep = abs(y1 - y0) > abs(x1 - x0);

if (steep) {
tmp = y0; y0 = x0; x0 = tmp;
tmp = y1; y1 = x1; x1 = tmp;
}

if (x0 > x1) {
tmp = x0; x0 = x1; x1 = tmp;
tmp = y0; y0 = y1; y1 = tmp;
}

dx = x1 - x0;
dy = y1 - y0;

xEnd = round(x0);
yEnd = y0 + gradient * (xEnd - x0);
xGap = 1 - frac(x0 + 0.5);
xPx1 = xEnd;
yPx1 = trunc(yEnd);

if (steep) {
pfn(yPx1, xPx1, 1 - frac(yEnd) * xGap, h, s, v )
pfn(yPx1 + 1, xPx1, frac(yEnd) * xGap, h, s, v )
} else {
pfn(xPx1, yPx1, 1 - frac(yEnd) * xGap, h, s, v )
pfn(xPx1, yPx1 + 1, frac(yEnd) * xGap, h, s, v )
}

xEnd = round(x1);
yEnd = y1 + gradient * (xEnd - x1);
xGap = frac(x1 + 0.5);

xPx2 = xEnd;
yPx2 = trunc(yEnd);

if (steep) {
pfn(yPx2, xPx2, 1 - frac(yEnd) * xGap, h, s, v )
pfn(yPx2 + 1, xPx2, frac(yEnd) * xGap, h, s, v )
} else {
pfn(xPx2, yPx2, 1 - frac(yEnd) * xGap, h, s, v )
pfn(xPx2, yPx2 + 1, frac(yEnd) * xGap, h, s, v )
}

if (steep) {
for (x = xPx1 + 1; x <= xPx2 - 1; x++) {
pfn(trunc(intery), x, 1 - frac(intery), h, s, v )
pfn(trunc(intery) + 1, x, frac(intery), h, s, v )
}
} else {
for (x = xPx1 + 1; x <= xPx2 - 1; x++) {
pfn(x, trunc(intery), 1 - frac(intery), h, s, v )
pfn(x, trunc(intery) + 1, frac(intery), h, s, v )
}
}
}

// Draws a Triangle via WuLine

function Triangle(pfn,hue,value,ax,ay,bx,by,cx,cy) {
WuLine(pfn,ax,ay,bx,by,hue,saturation,value)
WuLine(pfn,bx,by,cx,cy,hue+0.333333,saturation,value)
WuLine(pfn,cx,cy,ax,ay,hue+0.666666,saturation,value)
}

//

function Sierpinski(pfn,depth,hue,value,ax,ay,bx,by,cx,cy) {
Triangle(pfn,hue,value,ax,ay,bx,by,cx,cy)

if(depth > 0) {
var nd = depth - 1
var nv = value * darken
var nh = hue + huespin

var ax3 = ax*3
var ay3 = ay*3
var bx3 = bx*3
var by3 = by*3
var cx3 = cx*3
var cy3 = cy*3

var tx = (ax+bx) * 0.5
var ty = (ay+by) * 0.5
var qx = (tx-cx) * 0.5
var qy = (ty-cy) * 0.5
Sierpinski(pfn,nd,nh,nv,
tx,ty,
(ax3+bx) * 0.25 + qx,
(ay3+by) * 0.25 + qy,
(bx3+ax) * 0.25 + qx,
(by3+ay) * 0.25 + qy
)

tx = (bx+cx) * 0.5
ty = (by+cy) * 0.5
qx = (tx-ax) * 0.5
qy = (ty-ay) * 0.5
Sierpinski(pfn,nd,nh,nv,
tx,ty,
(bx3+cx) * 0.25 + qx,
(by3+cy) * 0.25 + qy,
(cx3+bx) * 0.25 + qx,
(cy3+by) * 0.25 + qy
)

tx = (cx+ax) * 0.5
ty = (cy+ay) * 0.5
qx = (tx-bx) * 0.5
qy = (ty-by) * 0.5
Sierpinski(pfn,nd,nh,nv,
tx,ty,
(cx3+ax) * 0.25 + qx,
(cy3+ay) * 0.25 + qy,
(ax3+cx) * 0.25 + qx,
(ay3+cy) * 0.25 + qy
)
}
}

// constants
var pi23 = PI2/3
var pi43 = 2 * pi23
var midp = (width-1)/2

// Clear (or fade if blur enabled) framebuffer
// and render a Sierpinski

export function beforeRender(delta) {
FB.forEach((Pixel) => { Pixel.mutate((v) => { return blur * v } )})

var rotation = time(0.06) * PI2
var hrot = time(0.067)

var midx = midp + 7 * sin(time(0.047) * PI2)
var midy = midp + 7 * cos(time(0.091) * PI2)

var ax = midx + radz*sin(rotation)
var ay = midy + radz*cos(rotation)
var bx = midx + radz*sin(rotation+pi23)
var by = midy + radz*cos(rotation+pi23)
var cx = midx + radz*sin(rotation+pi43)
var cy = midy + radz*cos(rotation+pi43)

Triangle(PixelMax,hrot,1,ax,ay,bx,by,cx,cy)
Sierpinski(PixelMax,depth,hrot+huespin,1,(ax+bx) * 0.5,(ay+by) * 0.5,(ax+cx) * 0.5,(ay+cy) * 0.5,(bx+cx) * 0.5,(by+cy) * 0.5)
}

// Draw from the framebuffer

export function render(index) {
Pixel = IndexPixel[index]
rgb(Pixel[0], Pixel[1], Pixel[2])
}
``````
2 Likes

Last night while trying to sleep after burning my retinas by watching this, I remembered that I hadn’t applied the “no division by constants” trick. Also, “less multiplication in general”… so I updated the code in the post above.

Now `/2` is `* 0.5`, `/4` is `* 0.25` and in the recursive call where I use `3*{a,b,c}{x,y}` twice, I store them in a variable instead. At 12MHz it now only drops below 30fps at the full zoom level!

(oh, and I made it go back and forth a bit more and zoom in further to show another level of recursion, and now it drops to 20fps!)

2 Likes