Category: Fractals

Visual memory

paul

Soon after my start with Arduino, I bought an external 32KB EEPROM, just in case a future project would need more memory than the board’s modest SRAM. But when I finally needed it for a sketch, I realized that the 300 KByte RAM of my 480×320 TFT display could be used for this purpose as well.

I had used pixels as memory before, but only in visualisations of IFS fractals, where each pixel keeps track of the number of times it has been ‘hit’ by the iteration process, and is colored accordingly. Recent examples are this autumn inspired version of Barnsley’s Fern and this conifer-like fractal, based on an example on Ken Brakke’s IFS page. Both fractals were produced by an esp8266 on a 320×240 TFT display (ili9341).

Using a display as external memory for projects brings memory intensive algorithms, like the A* path search algorithm for my 15-Puzzle project, within reach of Arduino and ESP boards. The only prerequisite is that your display library lets you read single pixel values. Bonus: leaving the display’s backlight on will show a ‘brain scan’ of the sketch in progress.

 

Buddhabrot – the last fractal?

paul

Writing sketches for posts in the Fractals category of this blog made me realize that for many fractals (e.g. Mandelbrot, Julia, Newton etc.), visual appeal depends to a large extend on color mapping. In other words: mathematics may have blessed these fractals with a potentially beautiful complexity, but it still takes a programmer to visualize it as such.

Another thought that crossed my mind was whether the (perceived) infinite complexity of fractals couldn’t be just revealing the incompleteness of the mathematical system that produces and observes them (in which case we should name them Gödel fractals).

The above observations became manifest again when I was looking for a way to color the inside of the Mandelbrot set, that’s usually left uncolored. After a couple of very unappealing attemps, I discovered someone’s method for producing the so called Buddhabrot fractal.

 

However, as you can see, the result on my small 480×320 pixel display doesn’t even come close to some of the beautiful images that pop up in Google. Actually, it looks more like one of Marie Curie’s early X-ray images. On the other hand, I suspect that many beautiful realizations of the Buddhabrot fractal have been enhanced with the same post-processing techniques that are used for beautifying pictures of galaxies and nebulae. That feels a bit like cheating to me, because I could probably make my Buddhabrot look like Donald Trump that way… (would that still be called beautifying?)

 

Now that this somewhat demystifying idea of ‘artificial beauty’ has tempered my facination for fractals a bit, it’s time to return to the challenge of creating fast and memory-friendly algorithms for IFS-generated shapes, like space filling curves.

Newton fractal

paul

Here’s another famous fractal that I wanted to try on Arduino: the Newton fractal. It’s named after Isaac Newton’s iterative method for finding roots of functions. The classic example applies the method to function f(z) = z3 – 1 , where z is a complex number. This function has three roots in the complex plane.

classic newton fractal

The sketch that produced this picture loops over the pixels of a 480×320 display, mapping each of them to a complex number z0, that will serve as the initial value for Newton’s iteration process:

zn+1 = zn – f(zn) / f'(zn)

The basic color of a pixel (red, green or blue) depends on to which of the three roots the process converges. Its color intensity depends on the number of iterations that were needed to reach that root within a pre-defined precision. It’s just that simple!

Apart from playing with different color mappings (always essential for producing visually appealing fractals), I wanted to use modified versions of Newton’s method, as well as to apply them to different functions. The Arduino core has no support for complex calculus, and a library that I found didn’t even compile. So I wrote a couple of basic complex functions and put them in a functions.h file. There must better ways, but it works for me.

Once you have a basic sketch, the canvas of complexity is all yours!

 

 

f(z) = z4 – 1

 

This is my functions.h file. It must be in the same folder as the fractal sketch.

 

And here’s the Newton fractal sketch. Note the #include “functions.h” on the first line.

 

 

Snowflakes & Clouds

paul

I haven’t been working on larger projects for a while, so here’s a couple of recent chips from the workbench.

In my ongoing quest for a faster HX8357D display driver, I was exited to read that the fast TFT_eSPI library now claims to support this beautiful but rather slow display. Unfortunately, the results were disappointing (unstable, readPixel freezes the screen). However, a nice bycatch of my experiments was the discovery that display updates become noticeably faster when the esp8266’s runs at 160MHz. Very useful for my fractal sketches, and for faster aircraft position updates on the Flight Radar‘s map.

Then I wondered how fast an esp8266 could actually drive my ili9341 driven 320×240 display. So I used my fast ‘offset-modulo’ Koch Snowflake algorithm for a snowflake animation speed test.

The result: an esp8266 at 160MHz can draw more than 100 (iteration depth 3) snowflakes per second on an ili9341 display, using the TFT_eSPI library. That’s about 5x faster than Adafruit’s HX8357 library can achieve on my 480×320 display. Hopefully, there will be a fast and reliable library for that display some day.

 

 

My renewed attention to the Koch Snowflake led to the discovery of a fractal that was new to me: the Plasma fractal. A commonly used algorithm to produce it is the Diamond-square algorithm. It’s apparently being used to generate nature-like backgrounds for video games.

I wrote a small demo sketch that produces random clouds (well, sort of…), but it can also be used to produce (non-musical) rock formations or landscapes.

6 samples of randomly generated clouds

(picture quality suffers from camera pixel interference with the TFT display)

 

The Diamond-square algorithm assigns initial values to the four corners of a (2n+1)x(2n+1) grid. Then it starts a process of calculating the remaining elements of the grid, based on neighbour values and a random noise of decreasing magnitude. The visual result depends on the four initial corner values, the random noise and the chosen color mapping.

The name Plasma fractal becomes clear when we show consecutive results in a loop. While still using random noise, the trick is to initialize the random generator with the same seed value for every new loop cycle. By slightly changing the initial corner values for each new cycle, the results will also be slightly different from the previous one, which is exactly what we want for a smooth animation.

The general formula that I used for initializing corner k with value h[k] is:

h[k] = d[k] + a[k]*sin( t*f[k] )   where t is a loop counter.

So the value of corner k will periodically swing around value d[k] with amplitude a[k]. The period of the swing is determined by f[k].

Now we can play with the d, a and f values for each corner, as well as with the color mapping, in order to find visually appealing animations. Here’s a first impression (esp8266 & ili9341 320×240 display). The sketch uses a 65×65 grid, with every point filling a corresponding 3×4 rectangle on the display with it’s color value. Since grid values are stored in 4-byte float variables, a 129×129 grid would become too large for the esp8266.

 

Used values:

Assignment:

Color mapping:

 

 

More fractals…

paul

At the end of my exploration of the fractal-universe, I had my tireless Arduino Uno create a couple of ‘classics’. The video shows the growth of the famous Barnsley Fern.

This is a special IFS fractal: each iteration step transforms just one single pixel (instead of the usual geometric shape), using one out of four possible transformations. By changing the parameters and/or the probabilities of the transformations, different kinds of fern patterns will appear.

After I’d finished the sketch (the simplest of all my fractal sketches), I could hardly believe that it could generate such a beautiful image (after 50,000 iterations).

And then, of course, there is the mother of all fractals, named after the (disputed) father of all fractalists: Mandelbrot. The sketch to produce it is much simpler than most backtracking sketches, but it may take up to 256 iterative function calls for every pixel to calculate its color. With 153,600 pixels, it took the Uno a couple of minutes to finish the picture.

The black area is a 2D representation of the actual Mandelbrot Set, but the fascinating stuff is happening at its border. By changing the coordinates and zoom level inside the sketch, you can zoom in at any area. Key factors for getting spectacular results are: selection of the area, maximum number of iterations and color mapping.

 

This short exploration wouldn’t be complete without mentioning the elegant Julia fractals. Like Mandelbrot fractals, they are created by iteration of the function f(z) = z² + c  (in the complex plane). For Julia fractals, c is fixed and we examine the function’s behaviour for all z values within our range of interest. So there’s a Julia set Jc for every c in the complex plane, but the most visually appealing Julia fractals will arise from c values at the border of the Mandelbrot set.

Julia fractal (c = -0.79 -0.15i) produced by an esp8266 on a 480×320 TFT display

IFS fractals

paul

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.

Pythagorean Tree

paul

This fractal was first drawn by Albert Bosman, a Dutch mathematics teacher.

It takes its name from the right-angled triangles between the generated squares, illustrating the Pythagorean theorem. The choice of the remaining angles determines the skewness of the tree.

The sketch runs on an Arduino Uno and draws the tree for 3 different angles on a 480×320 TFT display. The color of the squares depends on their size, trying to simulate trunks and leafs.

The algorithm uses backtracking, very similar to the maze generator & solver in my previous post. Recursion depth was limited to 10 levels deep, in order to prevent the smallest squares from becoming single pixels.

To speed up drawing, I use the display’s symmetry when the tree is generated from an isosceles triangle. The rest is just basic goniometry.

[Comments are in Dutch. Sorry…]