Recursive Sierpinski triangle (just a bit of fun)

Nothing special, just a bit of fun.

Plotting the good old Sierpinski triangle.

The pattern is made from basically one simple rule: Go halfway towards a vertex, plot a point, repeat. Starting point doesn’t matter (or not much, but if outside the triangle you’d get a trail of sorts towards it).

There’s basically two methods to do that:

  • Randomly pick one vertex
  • Use all of them. And then use all of the new points towards all of the vertices again, etc. It adds up quickly.

I’ve been looking a bit into recursion lately and it occurred to me that’s one simple solution to use the latter method. Previously I’ve always used the “random choice” method (apparently it’s called Chaos Game. But these type of fractals are not chaotic though).

Sierpinski

/** Sierpinski test 3

    All paths method (with recursion)

    2020.08.29 raron
*/

int depth = 8;  // recursion depth
color c = color( 192 );
PVector startPoint;
PVector [] coord = new PVector[3];


void setup()
{
  size(400,400);
  background(32);  

  // Sierpinski triangle vertices
  coord[0] = new PVector( 0, 0 );
  coord[1] = new PVector( 150, 300 );
  coord[2] = new PVector( 300, 0 );
  
  // random start point
  startPoint = new PVector( 150, 150 );

  sierpinski(startPoint, depth);
  
  noLoop();
}


void draw(){}


void sierpinski(PVector currentPoint, int currentDepth)
{
  if (currentDepth == 0) return;
  PVector temp = currentPoint.get();
  for (PVector sVertice : coord)
  {
    currentPoint.set((currentPoint.x+sVertice.x)/2, (currentPoint.y+sVertice.y)/2);
    set(50+int(currentPoint.x), (height-50)-int(currentPoint.y), c);
    sierpinski(currentPoint, currentDepth-1);
    currentPoint = temp.get();
  }
}
5 Likes

Nice!
I was working on an animated version to post on the rosetta code page, but stopped because I would like you to join the rosetta tasks
Please consider to join the club here You can start by uploading this sketch at the rosetta page (first link).
Thanks.

4 Likes

I‘d like to see a 3D version of this…

3 Likes

Lazydog took the sierpinski triangle a bit further with his ball of confusion which I’ve since translated for JRubyArt.

5 Likes

monkstone’s last link has a (sort of) really nice example. I just tried it.

Once more an excellent link.I should be making a list of interesting Processing related links. By chance you have posted one somewhere?

I was contemplating how to do an animated one too, while it is being generated I mean. I don’t have the method down to do that (yet), but I will look into it.

You had to mention that :stuck_out_tongue: Now I want it too!

I used to have a blog similar to lazydogs but I deleted it (I’m pretty sure at one stage I created a solid Sierpinski triangle). The sierpinski triangle can be created in several ways such as an lsystems or by context free art, much fun to be had.

1 Like

Forgot to say thanks for the tip! I’ve never edited Wiki’s before though, feels a bit daunting!

Whatever difficulty, feel free to send me a message.

2 Likes

Or as an IFS (Iterated Function System - might be the same as the Isystems you mentioned?). It makes for a more general approach. Years ago I saw an excellent article about that in the August 1990 edition of the magazine Electronics & Wireless World. I wanted a refresher on it but lost the magazine (last year even!). Luckily they’ve scanned all issues from 1911 to 2005 (the link above!). Btw the article is on pdf page 57 of that issue, if interested.

1 Like

@Chrisir I’ve been developing a ruby-processing equivalent of Shadertoy2processing on github so I used the shadertoy 3D sierpinski as a test:-
sierpinski

Runs at 60 fps for me linux box as before.

attr_reader :last_mouse_position, :mouse_click_state, :mouse_dragged
attr_reader :previous_time, :wrapper, :start

def settings
  size(640, 360, P2D)
end

def setup
  sketch_title '3D Sierpinski'
  @previous_time = 0.0
  @mouse_dragged = false
  @mouse_click_state = 0.0
  # Load the shader file from the "data" folder
  @wrapper = load_shader(data_path('sierpinski.glsl'))
  # Assume the dimension of the window will not change over time
  wrapper.set('iResolution', width.to_f, height.to_f, 0.0)
  @last_mouse_position = Vec2D.new(mouse_x.to_f, mouse_y.to_f)
  @start = java.lang.System.current_time_millis
end

def draw
  puts frame_rate if (frame_count % 300).zero?
  # shader playback time (in seconds)
  current_time = (java.lang.System.current_time_millis - start) / 1000.0
  wrapper.set('iTime', current_time)
  # mouse pixel coords. xy: current (if MLB down), zw: click
  if mouse_pressed?
    @last_mouse_position = Vec2D.new(mouse_x.to_f, mouse_y.to_f)
    @mouse_click_state = 1.0
  else
    @mouse_click_state = 0.0
  end
  wrapper.set('iMouse', last_mouse_position.x, last_mouse_position.y, mouse_click_state, mouse_click_state)
  shader(wrapper)
  # Draw the output of the shader onto a rectangle that covers the whole viewport.
  rect(0, 0, width, height)
end

Shader:-

// The MIT License
// Copyright © 2013 Inigo Quilez
// Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions: The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software. THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.


#ifdef GL_ES
precision mediump float;
precision mediump int;
#endif

// ----------------------
// SHADERTOY UNIFORMS  -
// ----------------------

uniform vec3      iResolution;           // viewport resolution (in pixels)
uniform float     iTime;                 // shader playback time (in seconds)
uniform vec4      iMouse;                // mouse pixel coords. xy: current (if MLB down), zw: click

void mainImage( out vec4 fragColor, in vec2 fragCoord );

void main() {
    mainImage(gl_FragColor,gl_FragCoord.xy);
}

const vec3 va = vec3(  0.0,  0.57735,  0.0 );
const vec3 vb = vec3(  0.0, -1.0,  1.15470 );
const vec3 vc = vec3(  1.0, -1.0, -0.57735 );
const vec3 vd = vec3( -1.0, -1.0, -0.57735 );

// return distance and address
vec2 map( vec3 p )
{
	float a = 0.0;
    float s = 1.0;
    float r = 1.0;
    float dm;
    vec3 v;
    for( int i=0; i<8; i++ )
	{
	    float d, t;
		d = dot(p-va,p-va);              v=va; dm=d; t=0.0;
        d = dot(p-vb,p-vb); if( d<dm ) { v=vb; dm=d; t=1.0; }
        d = dot(p-vc,p-vc); if( d<dm ) { v=vc; dm=d; t=2.0; }
        d = dot(p-vd,p-vd); if( d<dm ) { v=vd; dm=d; t=3.0; }
		p = v + 2.0*(p - v); r*= 2.0;
		a = t + 4.0*a; s*= 4.0;
	}

	return vec2( (sqrt(dm)-1.0)/r, a/s );
}

const float precis = 0.0002;

vec3 intersect( in vec3 ro, in vec3 rd )
{
	vec3 res = vec3( 1e20, 0.0, 0.0 );

	float maxd = 5.0;

	// sierpinski
    float h = 1.0;
    float t = 0.5;
	float m = 0.0;
    vec2 r;
	for( int i=0; i<100; i++ )
    {
	    r = map( ro+rd*t );
        if( r.x<precis || t>maxd ) break;
		m = r.y;
        t += r.x;
    }

    if( t<maxd && r.x<precis )
		res = vec3( t, 2.0, m );

	return res;
}

vec3 calcNormal( in vec3 pos )
{
    vec3 eps = vec3(precis,0.0,0.0);
	return normalize( vec3(
           map(pos+eps.xyy).x - map(pos-eps.xyy).x,
           map(pos+eps.yxy).x - map(pos-eps.yxy).x,
           map(pos+eps.yyx).x - map(pos-eps.yyx).x ) );
}

float calcOcclusion( in vec3 pos, in vec3 nor )
{
	float ao = 0.0;
    float sca = 1.0;
    for( int i=0; i<8; i++ )
    {
        float h = 0.001 + 0.5*pow(float(i)/7.0,1.5);
        float d = map( pos + h*nor ).x;
        ao += -(d-h)*sca;
        sca *= 0.95;
    }
    return clamp( 1.0 - 0.8*ao, 0.0, 1.0 );
}

vec3 lig = normalize(vec3(1.0,0.7,0.9));

vec3 render( in vec3 ro, in vec3 rd )
{
    vec3 col = vec3(0.0);

	// raymarch
    vec3 tm = intersect(ro,rd);
    if( tm.y>0.5 )
    {
        // geometry
        vec3 pos = ro + tm.x*rd;
		vec3 nor = calcNormal( pos );
		vec3 maa = vec3( 0.0 );

        maa = 0.5 + 0.5*cos( 6.2831*tm.z + vec3(0.0,1.0,2.0) );

		float occ = calcOcclusion( pos, nor );

		// lighting
		float amb = (0.5 + 0.5*nor.y);
		float dif = max(dot(nor,lig),0.0);

        // lights
		vec3 lin = 1.5*amb*vec3(1.0) * occ;

		// surface-light interacion
		col = maa * lin;

	}

    // gamma
	col = pow( clamp(col,0.0,1.0), vec3(0.45) );

    return col;
}
void mainImage( out vec4 fragColor, in vec2 fragCoord )
{
	vec2 q = fragCoord.xy / iResolution.xy;
    vec2 p = -1.0 + 2.0 * q;
    p.x *= iResolution.x/iResolution.y;
    vec2 m = vec2(0.5);
	if( iMouse.z>0.0 ) m = iMouse.xy/iResolution.xy;

    //-----------------------------------------------------
    // camera
    //-----------------------------------------------------

	float an = 3.2 + 0.5*iTime - 6.2831*(m.x-0.5);

	vec3 ro = vec3(2.5*sin(an),0.0,2.5*cos(an));
    vec3 ta = vec3(0.0,-0.5,0.0);
    vec3 ww = normalize( ta - ro );
    vec3 uu = normalize( cross(ww,vec3(0.0,1.0,0.0) ) );
    vec3 vv = normalize( cross(uu,ww));
	vec3 rd = normalize( p.x*uu + p.y*vv + 5.0*ww*m.y );

    vec3 col = render( ro, rd );

    fragColor = vec4( col, 1.0 );
}

void mainVR( out vec4 fragColor, in vec2 fragCoord, in vec3 fragRayOri, in vec3 fragRayDir )
{
    vec3 col = render( fragRayOri + vec3(0.0,-0.1,2.0), fragRayDir );

    fragColor = vec4( col, 1.0 );
}
// ----------------------------
//  SHADERTOY CODE ENDS HERE  -
// ----------------------------

The beauty of JRubyArt is that you can develop ruby code and shader code in atom, and test without leaving atom.

5 Likes

Quick 3D-ification of the other Sierpinski (Except for a pesky NPE, I forgot to increase the index of the new point for the 3D version!). Nothing fancy, no rotation etc, just a quick’n’dirty viewpoint change when holding down a mouse button. Scrollwheel zooms.

And yes the triangles are made of boxes, for the lack of 3D points… :slight_smile:

Recursion depth of 5 gives me ~60 FPS, 6 is ~30, and 7 is below 10 on my machine.

/** Sierpinski test 4 - 3D

    All paths method (with recursion)

    2020.08.29 raron
*/

int depth = 6;  // recursion depth

int dWidth  = 600;
int dHeight = 600;
int scrollWheel = 0;

PVector eye;
PVector startPoint;

int verts = 4;
PVector [] coord = new PVector[verts];


void settings()
{
  size(dWidth, dHeight, P3D);
}

void setup()
{
  //background(32);  
  
  eye = new PVector(width/2.0, height/2.0, (height/2.0) / tan(PI*30.0 / 180.0));

  // 3D Sierpinski triangle vertices
  coord[0] = new PVector(   0,   0,   0 );
  coord[1] = new PVector( 300,   0,   0 );
  coord[2] = new PVector( 150,   0, 260 );
  coord[3] = new PVector( 150, 245, 130 );
  
  // random start point
  startPoint = new PVector( 150, 122, 130 );
}


void draw()
{
  background(32);  
  stroke(color(255,70,70));
  noFill();
  //text(frameRate, 50, 50);
  
  // Quick'n'dirty viewpoint change
  if(mousePressed)
  {
    eye.x = dWidth-mouseX;
    eye.y = dHeight-mouseY;
  }
  eye.z = eye.z + scrollWheel * 20;
  scrollWheel = 0;

  sierpinski(startPoint, depth);

  camera(eye.x, eye.y, eye.z, width/2.0, height/2.0, 0, 0, 1, 0);
}


void sierpinski(PVector currentPoint, int currentDepth)
{
  if (currentDepth == 0) return;
  PVector temp = currentPoint.get();
  for (PVector sVertice : coord)
  {
    currentPoint.set((currentPoint.x+sVertice.x)/2, (currentPoint.y+sVertice.y)/2, (currentPoint.z+sVertice.z)/2);
    pushMatrix();
    translate(width/4+currentPoint.x, height*3/4-currentPoint.y, currentPoint.z);
    box(1);
    popMatrix();
    sierpinski(currentPoint, currentDepth-1);
    currentPoint = temp.get();
  }
}


void mouseWheel(MouseEvent event)
{
  scrollWheel = event.getCount();
}
5 Likes

Very nice! I took @Chrisir 's challenge as well.
I’m trying to do it with tetrahedrons. Since I feel a little more confortable with P5.java, I’m starting to code in P5.js.
This is actually my first posted sketch in P5.js.
Here my first attempt.
https://editor.p5js.org/noelpil/present/L8q2xBZtM

3 Likes

Just found it I submitted a Sierpinski3D as an open processing sketch here. Needs modifying to run on Processing4.

2 Likes

That’s why I’m starting to learn P5.js. Processing java is very limited now on OpenProcessing. :grin:

1 Like

Thanks guys! Excellent!

Monocolor is boring.
Messed a bit more with the 3D version. Added PeasyCam.

Click to (un) expand
/** Sierpinski test 6 - 3D

    All paths method (using recursion)

    2020.08.30 raron
*/
import peasy.*; 

int depth = 6;  // recursion depth

// 3D Sierpinski triangle vertices
PVector [] coord = 
{
  new PVector(  0,   0,   0),
  new PVector(300,   0,   0),
  new PVector(150,   0, 260),
  new PVector(150, 245, 130)
};

color[] vertexColor =
{
  color(255,   0,   0),
  color(  0, 255,   0),
  color(  0,   0, 255),
  color(255, 255, 255)
};

int verts = coord.length;
PeasyCam cam;

// random start point
PVector startPoint = new PVector(150, 122, 130);


void setup()
{
  size(600, 600, P3D);
  cam = new PeasyCam(this, startPoint.x, startPoint.y, startPoint.z, 400);
  cam.setMinimumDistance(200);
  cam.setMaximumDistance(600);
}


void draw()
{
  background(32);  
  noFill();
  sierpinski(startPoint, depth);
}


void sierpinski(PVector currentPoint, int currentDepth)
{
  if (currentDepth == 0) return;
  PVector temp = currentPoint.get();
  for (PVector sVertice : coord)
  {
    currentPoint.set((currentPoint.x+sVertice.x)/2, (currentPoint.y+sVertice.y)/2, (currentPoint.z+sVertice.z)/2);
    stroke(colorSpace(currentPoint));
    pushMatrix();
    translate(currentPoint.x, 245-currentPoint.y, 260-currentPoint.z);
    box(1);
    popMatrix();
    sierpinski(currentPoint, currentDepth-1);
    currentPoint = temp.get();
  }
}

// Return a color depending on distances from vertices
color colorSpace(PVector spacePos)
{
  float temp;
  color tempCol = color(0, 0, 0);
  for (int i=0; i<verts; i++)
  {
    temp    = 1-(spacePos.dist(coord[i])/300.0);
    //temp    = pow(temp, 2);
    //temp    = abs(log(temp)/log(2));
    tempCol = lerpColor(tempCol, vertexColor[i], temp);
  }
  return tempCol;
}

my version…

I think I made the recursive function better and tried to make pyramids

but VERY unhappy with it…

lights() and avoidClipping() are a must have when using PeasyCam imho

Chrisir

/** Sierpinski test 6 - 3D
 
 All paths method (using recursion)
 
 2020.08.30 raron
 */
import peasy.*; 

int depth = 6;  // recursion depth - try 6

// 3D Sierpinski triangle vertices
PVector [] coord = 
  {
  new PVector(  0, 0, 0), 
  new PVector(300, 0, 0), 
  new PVector(150, 0, 260), 
  new PVector(150, -245, 130)
};

color[] vertexColor =
  {
  color(255, 0, 0), 
  color(  0, 255, 0), 
  color(  0, 0, 255), 
  color(255, 255, 255)
};

int verts = coord.length;
PeasyCam cam;

// random start point
PVector startPoint = new PVector(150, 122, 130);

PShape ps; 

//------------------------------------------------------------------------------
// Two core functions 

void setup() {
  size(600, 600, P3D);

  avoidClipping();

  cam = new PeasyCam(this, startPoint.x, startPoint.y, startPoint.z, 400);
  //cam.setMinimumDistance(200);
  cam.setMaximumDistance(600);

  PVector startPoint = new PVector(0, 0, 0);

  PVector currentPoint=new PVector(0, 0, 0);

  ps = createShape(); 
  ps.beginShape(TRIANGLE_STRIP);
  PVector sVertice; 
  //for (PVector sVertice : coord) {
  // currentPoint.set((startPoint.x+sVertice.x)/2, (startPoint.y+sVertice.y)/2, (startPoint.z+sVertice.z)/2);
  float f = 66;
  // base 1
  sVertice = coord[0].copy();
  ps.vertex(sVertice.x/f, sVertice.y/f, sVertice.z/f);
  // top
  sVertice = coord[3].copy();
  ps.vertex(sVertice.x/f, sVertice.y/f, sVertice.z/f);
  // base 2
  sVertice = coord[1].copy();
  ps.vertex(sVertice.x/f, sVertice.y/f, sVertice.z/f);
  // top
  sVertice = coord[3].copy();
  ps.vertex(sVertice.x/f, sVertice.y/f, sVertice.z/f);
  // base 3
  sVertice = coord[2].copy();
  ps.vertex(sVertice.x/f, sVertice.y/f, sVertice.z/f);
  // base 1
  sVertice = coord[0].copy();
  ps.vertex(sVertice.x/f, sVertice.y/f, sVertice.z/f);

  // }//for
  ps.endShape();
}

void draw() {
  background(32);  
  lights(); 
  sierpinski(startPoint, depth);
}

//------------------------------------------------------------------------------
// Other functions 

void sierpinski(PVector currentPoint, int currentDepth) {

  if (currentDepth == 0) {
    stroke(colorSpace(currentPoint));
    pushMatrix();
    translate(currentPoint.x, 
      245+currentPoint.y, 
      260-currentPoint.z);
    //box(1);
    ps.setFill(colorSpace(currentPoint));
    rotateY(PI/3);
    shape(ps, 0, 0);
    popMatrix();
    return; // Leave
  }//if

  PVector temp = currentPoint.copy();

  for (PVector sVertice : coord) {
    currentPoint.set((currentPoint.x+sVertice.x)/2, (currentPoint.y+sVertice.y)/2, (currentPoint.z+sVertice.z)/2);
    sierpinski(currentPoint, currentDepth-1);
    currentPoint = temp.copy();
  }//for
}

// Return a color depending on distances from vertices
color colorSpace(PVector spacePos) {
  float temp;
  color tempCol = color(0, 0, 0);
  for (int i=0; i<verts; i++)
  {
    temp    = 1-(spacePos.dist(coord[i])/300.0);
    //temp    = pow(temp, 2);
    //temp    = abs(log(temp)/log(2));
    tempCol = lerpColor(tempCol, vertexColor[i], temp);
  }
  return tempCol;
}

void avoidClipping() {
  // avoid clipping (at camera): 
  // https : // 
  // forum.processing.org/two/discussion/4128/quick-q-how-close-is-too-close-why-when-do-3d-objects-disappear
  perspective(PI/3.0, (float) width/height, 1, 1000000);
}//func 
//
2 Likes