IFS fractals

The use of backtracking in my Pythagorean tree sketch made me realize that it can be useful for creating other IFS fractals as well (fractals produced by Iterated Function Systems). These fractals are very ‘geometric’ by nature (and can actually be found in nature). Classic examples are the Sierpinski Gasket and the Koch Snowflake.

Memory usage for backtracking is O(d), where d is the chosen recursion depth. For my purpose (displaying contractive fractals on a 480×320 display), d will usually be quite small (<15) in order to prevent objects from becoming single pixels. That means that most sketches will run fine on an Arduino Uno.

The above video shows a (slightly randomized) Binary Tree fractal

Generating Binary Tree fractals resembles the growth of a plant. Starting with a vertical trunk, branches recursively split into two new branches, growing in directions determined by θ (0°<θ<180°) while their length is reduced by a factor r (0<r<1).

In symmetric binary trees, θ and r are fixed. In order to produce more naturally looking ‘plants’, I applied some randomization to both θ and r for every new branch. The drawing order of splitting branches is randomized as well. As a finishing touch, branches with lengths smaller than a treshold value will be drawn in red.

 

 

Another famous IFS fractal is the Sierpinski Carpet. The largest square in the picture is 243×243 pixels wide. Iteration depth is 5, so the smallest black squares become single pixels (you may have to zoom in to see them).

 

 

 

 

And this is the Sierpinski Gasket (or Triangle) with iteration depth 6. It’s interesting that the same pattern can also be generated by elementary cellular automaton Rule 30, by a Lindenmayer system or by a Chaos game method.

 

 

 

Next is the Koch Snowflake (actually a triangle of three Koch curves) with iteration depth 4.

After writing a familiar backtracking based algorithm, I also wrote a far more compact sketch for drawing a Koch curve. It’s the second sketch at the bottom of this page.

 

 

My last example is the space-filling (pseudo) Hilbert curve. It took me some time to understand why a backtracking approach is less suitable in this case. Each level consists of more than just four transformations of its parent’s pattern, because these transformations have to be interconnected as well. Moreover, since levels don’t share any lines with previous levels (see video below), you can’t use the display to preserve lines.

So I went for a solution that iteratively builds an array of drawing instructions. This results in a very simple algorithm, but the size of the instructions array is equal to  4n – 1, where n is the desired iteration depth. With some bitwise tricks, an Arduino Uno can draw the Hilbert curve for up to n=6, which happens to be the maximum for my 480×320 display, because line distances would become smaller than a pixel for n>6.

 

 

This is the sketch that generated the fractal in the Binary Tree video:

 

And here’s my newest sketch for drawing a Koch Snowflake. It superimposes the same pattern of rotation instructions with a different offset and periodicity for each level. I like the elegance of this algorithm. It kind of generates and processes the final string of an L-system on the fly, without any rewriting or intermediate data storage.