# Incendium – Making fractal animations

I’ve recently created a piece of software for creating fractal animations. The full source code and a description of its features can be found at the project’s GitHub page. On this page, however, I’ll explain the technical details behind the algorithm used by the core engine of Incendium to generate its fractals. If you want a non-technical overview, please check out the GitHub page. In essense, the program works by drawing a bunch of polygons unto an empty frame. There are two central problems here, how to choose which polygons to draw, and to figure out where to draw them.

We start with a regular $n$-gon (called depth $d=0$) drawn with its center at the origin $(0,0)$, and from each of its vertices, we draw another regular n-gon (it does not need to be the same $n$ for every depth). These new polygons have center at the vertices of the old polygon and have depth $d=1$, and in general a polygon at depth $d=n$ will have children of depth $d=n+1$. We continue doing this process until we’ve reached the specified fractal depth, giving us images such as (shown from depth $d=0$ to $d=2$):

Note that this image uses triangles, rather than the more general $n$-gon. This is because the math is pretty much the same for any $n$, and triangles are easier to visualize. Note that we’ve drawn all triangles here – what is a good method to choose which of these triangles to choose?

## Choosing which polygons to draw

First of all, let’s label the polygons accordingly in a systematic fashion. Let’s label the very first $n$-gon the empty string $\epsilon$. Its $n$ children will be appended the characters $\Sigma = \{0,1,2,...,n-1\}$, meaning that the children of the root node are called $0,1,2,...,n-1$. The children of the polygon represented by the string $0$ will likewise be appended these characters, and thus be called $00, 01, 02, ..., 0n$. Adding these labels to the above drawing yields:

Note that the length of the string $s$ is directly related to the depth of the polygon represented by that string, that is $|s|=fd$ for some fractal depth $fd$. For a constant polygon degree throughout the fractal, we will have a polygon for every possible string $s \in \Sigma^* : |s| \leq fd$. Thus we’ve reduced the problem of determining which polygon to draw to choosing a language $L \subset \Sigma^*$ and drawing all the polygons represented by the strings in $L$. Please note that since the polygon degree isn’t necessarily constant, we can’t be sure that all such strings $s$ actually exist in the fractal, but there is a relatively simple workaround.

To do this, we employ the help of regular expressions. While this technically limits the class of possible languages, it is a very simple approach, so we’re sticking with it. So, given some regular expression $R$ we draw all polygons represented by all the strings in $L(R)$. Shown here is the regular expression $.^*1.^*$ which only accepts all regular expressions that contain a 1:

## Where do we draw them?

Still, it’s not enough to just know which polygons to draw, we also need to know where to draw them. The root polygon is by definition placed at $(0,0)$, so its location is trivial. It’s children are drawn with their centers at the vertices of the root polygon, which seems to suggest we need the position of these. Assume we have some polygon with “radius” $r$ and rotation $\theta$. We know that all the vertices of the polygon lie on the graph for the circumscribed circle of the polygon. Therefore, we can easily derive the following formulas for the position of the vertices using trigonometry:

$P_0 =$ $( r \cdot \cos(\theta),$ $r \cdot \sin(\theta) )$

$P_1 = \left ( r \cdot \cos( \theta + \frac{1}{n} \cdot 2 \pi), r \cdot \sin( \theta + \frac{1}{n} \cdot 2 \pi) \right )$

$P_2 = \left ( r \cdot \cos( \theta + \frac{2}{n} \cdot 2 \pi), r \cdot \sin( \theta + \frac{2}{n} \cdot 2 \pi) \right )$

And in general,

$P_k = \left ( r \cdot \cos( \theta + \frac{k}{n} \cdot 2 \pi), r \cdot \sin( \theta + \frac{k}{n} \cdot 2 \pi) \right )$

Where $P_k$ is the $k$-th vertex.

Now, assume we have some polygon at depth $d$ represented by some regular expression $R=a_0 a_1 a_2 ... a_k$, and we want to know the position of its vertices. We know the origin of this polygon is given by the polygon at depth $d-1$. This other polygon is naturally represented by the regular expression $R' = a_0 a_1 a_2 ... a_{k-1}$, so its position is $P_{R'}$. We know the character $a_n$ represents which vertex we have (0 being the first vertex, 1 being the next vertex etc.). Therefore, we can write the following recursive relation:

$P_{a_0 a_1 a_2 ... a_k} = P_{a_0 a_1 a_2 ... a_{k-1}} +$ $\left ( r(R) \cdot \cos( \theta(R) + \frac{a_k}{n} \cdot 2 \pi), r(R) \cdot \sin( \theta(R) + \frac{a_k}{n} \cdot 2 \pi) \right )$

Where $r(R)$ is the radius for the polygon represented by $R$, and $\theta(R)$ is the angle – these will be investigated later. This recursive relation has the base-case $P_\epsilon = (0,0)$ and implementing it is straight-forward (shown here in pseudo-code):

function positionFromRegex(R)
if len(R) == 0: return (0,0)

return positionFromRegex(R')
+ ( r(R) * cos(theta(R) + a_k/n * 2pi),
r(R) * sin(theta(R) + a_k/n * 2pi) )

## It’s the size that matters

In the previous section, we just used $r(R)$ to denote the radius of the polygon represented by the regular expression $R$, we’ll now derive an expression for this function. First note that the size should only be dependent on the depth. Strings of the same depth should have the same size – we don’t want $0210$ to be larger than $1203$. Therefore, we can assume that the argument for $r$ is a number, so we have $r(d) : d \in \mathbb{N}$. Obviously, we want $r(0)$ to be the largest radius (for the root polygon), and we label this $r_0$, so $r(0) = r_0$. We also want this function to be strictly decreasing as $n \rightarrow \infty$, so $r(d) > r(k)$ for every $d > k$. Finally, we want to structure we’re designing to be a fractal – it should converge towards the same points as $n \rightarrow \infty$.

Note that the maximum distance from the origin that the first polygon can get is $r(0)$, and therefore the maximum distance any polygon at depth $d=1$ can get from the origin is $r(1)$ and so on… Therefore the maximum distance any polygon at an arbitrary depth $d$ can get is $r(0) + r(1) + ... r(d)$. And since we want our fractal to be finite we require this sum to be finite, that is:

$\displaystyle \sum_{d=0}^{\infty}$ $r(d) = K$

For some finite constant $K \in \mathbb{R}$. This looks an awful lot like infinite geometric series. While it’s not the exclusive solution for $r$, it is a possible one giving us the following expression for $r(d)$:

$r(d) = r_0 \cdot \rho^d$

For some constant $\rho \in [0,1]$. We call this constant the size decay of the fractal.

## You spin my head right round…

We’ve just derived the expression for the function $r(R)$ and now we’ll do the same for $\theta(R)$. Using a similar argument as in the previous section, we want the argument of $\theta$ to be the length of the regular expression $R$. We also want the rotation to not be very chaotic, as the assumption is that this won’t create beautiful fractals. Therefore we want the fractals to rotate a constant amount at every subsequent depth. This means we can derive the following expression for $\theta(n)$:

$\theta(n) = \theta_0 \cdot n$

Where $\theta_0 \in [0, 2\pi]$ is a constant. We call this constant the rotation of the fractal.

## Putting it all together

Now we’ve derived expressions for the two unknown functions and we get the following final recursive relation for the position $P$ of a polygon represented by the regular expression $R= a_0 a_1 a_2 ... a_k$:

$P_{a_0 a_1 a_2 ... a_k}[x] = P_{a_0 a_1 a_2 ... a_{k-1}}[x] +$ $r_0 \cdot \rho^k \cdot \cos( \theta_0 \cdot k + \frac{a_k}{n} \cdot 2 \pi)$

$P_{a_0 a_1 a_2 ... a_k}[y] = P_{a_0 a_1 a_2 ... a_{k-1}}[y] +$ $r_0 \cdot \rho^k \cdot \sin( \theta_0 \cdot k + \frac{a_k}{n} \cdot 2 \pi)$

$P_\epsilon = (0,0)$

I’ve split it into two lines for and to make it more comprehensible. We can also write this in pseudo-code:

function positionFromRegex(R)
k = len(R)
if k == 0: return (0,0)

return positionFromRegex(R')
+ ( r_0 * rho^k * cos(theta_0 * k + a_k/n * 2pi),
r_0 * rho^k * sin(theta_0 * k + a_k/n * 2pi) )

This has been implemented in the source code in the function called getPositionFromString();.

# Generating Images from Regular Expressions

There is an update to this post, which includes colors: https://ssodelta.wordpress.com/2014/03/25/creating-colored-images-from-regular-expressions/

Source code complete with Javadoc can be found at: http://pastebin.com/ccRK75aq

This post will detail a method for using regular expressions to generate images.

A regular expression is an array of characters, which represents a series of instructions, which for any input either matches or doesn’t match. For a simple example, the regular expression

ssodelta

Only matches the string ssodelta. This makes sense, but we can do pretty nice things with regular expressions. If we for example write

ssodelta|delta

Then the regular expression either matches ssodelta or the string delta. This is because the vertical bar | represents the symbol or. We also have so called quantifiers, the most important of which is the kleene star *.

sso(delta)*

The parentheses group strings together, like regular parentheses in mathematical expressions (2+4)*3, for example. The kleene star * means zero or more, meaning that there can be zero or more delta and it will still match the regular expression. A few matches include ssodelta, ssodeltadelta, ssodeltadeltadelta and so on…

I won’t completely detail regular expression, but if want to read up on it, I suggest close-reading the wikipedia article on the matter, but the bottom line is that regular expressions are really cool. But how can they be used to generate images?

Consider a completely square image, which is divided into 4 quadrants:

We can refer to each of these four quadrants by their numbers 0,1,2,3, and we can further divide these quadrants into four numbers, and label them accordingly.

But what does this have to do with regular expresssions? Well, we can have a regular expression, which only uses the characters 0,1,2,3 and every string adresses an area in this area. For example, the string 022 represents the area marked with red:

We can decide on a resolution n, and generate all strings of length n, parse them through a regular expression, and if it matches, paint it black. For example, the regular expression (0|2)(0+1+2+3)* generates the following image (for any resolution >= 2):

This is because the regular expression only matches if the cell begins with a 0 or a 2, which is why the 0th and the 2nd quadrants are painted black, and the rest aren’t.

We aren’t limited to boring checkers though, if we feed the generator the regular expression (1+2+3)*0(1+3)*0(0+1+2+3)*:

Notice the self-similarity in the image, that’s because this image is actually a fractal.

Here is a gallery of other images generated using this technique:

Notice how often triangles appear in these images.

Although the .java file has an included Javadoc, here’s how you use it to generate images:

Generator g = new Generator(RESOLUTION, IMAGE_SIZE);
g.generateAndExport("REGULAR_EXPRESSION", "EXPORTED_FILE_PATH.png"); //Must be a .png file

If you prefer Python code, check out Jack Morris’ post on the same subject, where he implements it in Python: http://jackm.co.uk/posts/2014/03/25/Using-Regular-Expressions-To-Generate-Images/