Category: Fractals

Multi-Fractal Explorer

paul

One program to rule them all…

The obvious code similarity between most of my fractal sketches prompted me to write a generic fractal explorer, using a simplified version of my recently finished ESP32 framework for self-replicating cellular automata.

Unlike the more complicated functions for self-replicating automata, most fractal-specific functions only take a few lines of code, so rather than being a template for separate fractal sketches, it’s a single program that can browse and zoom-in on multiple fractal types (Mandelbrot, Julia, Newton etc.) by calling their corresponding fractal functions.

 

The video shows the ‘renormalized’ Mandelbrot fractal on a 320×240 display, with a fixed zoom factor per click. The clicked position of the fractal stays mapped to the clicked pixel. If the accumulated zoom level exceeds a threshold value, the algorithm will switch to double precision calculations for better resolution.

I may add a simple web server for switching fractal type, setting zoom factor or changing color palette over WiFi, but the real fun here was to write a generic sketch that gets maximum speed from the ESP32 microcontroller by using both cores, as well as a couple of techniques and tricks developed for earlier projects.

 

Strange attraction

paul

fractals again…

If chaos theory applies to this blog, then fractals are definitely among its strange attractors… Reading an article about ‘renormalizing’ iteration escape values persuaded me to focus on colorizing fractals once more. The article presents a simple method for calculating real iteration escape values (i.e. C++ floats instead of integers).

With integer escape values, the number of available colors is limited by the algorithm’s  maximum number of iterations (maxIter), whereas the escape values from the descibed method are real numbers in the [0, maxIter) range, so if you want to color a fractal using n*maxIter colors, you can just muliply all escape values by n and use their integer part as an index for your color array. In exchange for just two extra iterations per pixel, fractal images will often look better, especially for small maxIter values.

The pictures show both methods, applied to the Mandelbrot fractal on a 480×320 display.

Integer escape values (maxIter = 128; 128 colors):

 

Renormalized float escape values (maxIter = 128; 256 colors):

[zooming-in caused some frequency interference between display and camera]

 

And this picture shows Julia in her new ‘renormalized’ dress:

 

Here’s the relevant function taken from my ‘Mandelzoom’ sketch that now uses 256 colors, although maxIter is still set to 128.

 

Turbocharged TFT display

paul

Here are some first results of the (speed) progress that I’ve made since my previous post about using PSRAM as display buffer.

The first video shows a 200×150 pixels animation generated by looping over 61 frames (ripped from an animated gif). The partial refresh of the relevant display area is so fast that I had to include delays between the frames.

 

 

The next video shows my dual core/ dual buffer Julia Fractal Zoomer sketch in action. The two ESP32 cores cooperate in writing Julia Fractals with ever increasing zoom levels to a (double) buffer in PSRAM. When a fractal is finished, the loop function takes care of writing its pixel values from the last completed buffer to the display.

Zooming in on Julia fractal (c = -0.79 -0.15i) ; max iterations: 128

 

This spinning globe was my first sketch that used PSRAM as a display buffer, written to test the concept and measure its speed. It is generated by looping over 21 frames.

 

 

The above videos show a LOLIN TFT-2.4 Shield, driven by a LOLIN D32 Pro with 8MB PSRAM. Sketches will follow after I’ve implemented a new idea that may further increase the zoom speed.

 

 

PSRAM Display Buffer

paul

One possible application of ESP32 WROVER’s PSRAM memory is using it as a (double) display buffer. I thought this could be useful for fractal-based animations on a TFT display, as these sketches often require a considerable amount of calculations for each pixel, followed by an update of that single pixel on the display, This way, a full refresh of the display can take a lot of time, but by writing calculated color values to a PSRAM buffer instead, the actual refresh can be done much faster by pushing the entire buffer to the display after all pixel colors have been calculated in a background process (even simultaneously on a different core, using a double buffering technique).

As a proof of concept, I converted one of my Julia Fractal sketches to a version that continuously draws a specific Julia Set Jc with an incrementing zoom level. The first result is satisfying enough, even though my pixel-by-pixel approach is probably not the most efficient way to interact with PSRAM. I may post a video in due course, but for now you can find the prototype sketch for a 320×240 display at the end of this post. It uses both fast cores and a double buffering technique: while one buffer is being filled by a core 1 task, the other one can be read by a core 0 task for filling the display.

Perhaps this display buffer concept can finally make aircraft position updates in my ‘What’s Up’ Flight Radar sketch completely flicker free. Instead of always having to save clean map tiles from the diplay (with readPixel) before drawing updated aircraft sprites on them, it will allow me to restore the appropriate tiles directly from the full map image stored  in PSRAM. That will circumvent my long time problem with the only fast library for the HX8357D display (Bodmer’s TFT_eSPI library): it’s readPixel() function doesn’t work on that display, so until now I couldn’t use it for my Flight Radar sketches. No longer having to use readPixel allows me to drive this nice 480×320 display in that library’s parallel mode, which is very fast! With the maximum of 12 aircraft on display, updating all positions will take < 80 milliseconds. So my next post may be ‘What’s Up – final version‘.

Here’s a quick and dirty dual core ‘Julia Fractal Zoomer’ sketch. For some reason, omitting the vTaskDelay command in loop() makes it run slower! Leaving out these commands from the task functions will crash the ESP32. Make sure to enable PSRAM before compiling the sketch on a WROVER based ESP32 (option will appear under ‘Tools’ in the Arduino IDE or can be set with make menuconfig if you use Espressif’s ESP-IDF).

[UPDATE] the prototype sketch below ran much faster after dividing calculations for the new display buffer over both cores and, as expected, by replacing the individual drawPixel commands by pushing the entire display buffer in one single SPI transaction.

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 in visualisations of IFS fractals, where I made each pixel keep track of the number of times it was ‘hit’ by the iteration process, and then color it 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 without PSRAM. 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 extent 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’d better 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, the part 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 fascination 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 excited 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. Update: the TFT_eSPI library now supports driving the HX8457 in parallel mode and the results are impressive.

 

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 make sense for my 480×320 display anyway, 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. The sketch is for iteration depth 4 on a 320×240 display.