# 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();.

# Recursively Generating Gradient Images from Regular Expressions

I’ve decided to write yet another blog post on this blog post (first post, second post), because I’ve found another algorithm which is far superior to the other algorithms. I’ve almost completely rewritten the source code (which can be found at this project’s GitHub page). Using this approach I’ve been able to generate a 16.384px x 16.384px image (right click > save as, my browser crashes trying to render the image).

## The Problem

The greatest problem with the old algorithm was that we had to enumerate all strings, check if they’re part of the regular language and then compute their Hamming distances using @nya’s $O(n)$ algorithm, which works much better than the modified $O(n^2)$ algorithm for Levenshtein distance previously used. But since there are $4^d$ strings for some depth $d$ this whole procedure quickly becomes infeasible as especially testing for membership in the regular language is expensive. This makes rendering the images very slow.

Another fatal problem with the old algorithm was its memory usage. For instance, for $d=13$ (images of size 8192px x 8192px) we need to save 67 million strings and equally many pixels. To calculate how much memory that many strings will take up on the heap, we can refer to the article on Javamex (since I’ve written the program in Java, results may be different for C++, Pascal, etc.), which states that the minimum number bytes $B$ a single string of length $n$ takes up on the heap is:

$B = 8 \cdot \left \lceil \dfrac{n \cdot 2 + 45}{8} \right \rceil$

Which for d=13 gives 5.0 GB of heap usage. Similarily, a BufferedImage uses 4 bytes of information per pixel and has $4^{13}$ pixels in total, resulting in a heap usage of 256 MB. This is all very inefficient and is a huge, unnecessary drag on the system. It also sets a strict upper bound on the size of the images as all this memory allocation quickly becomes too much for the size of the RAM in the computer. For my computer (which has 8 GB of RAM) this strict upper bound is $d=14$, as it would require 21 GB of memory to store both the image and the strings.

Fortunately, there is a way around most of this, and that is what we’ll be discussing in this article. Essentially, what we do is enumerate the strings one by one and add them to the image immediately, rather than generate all of them. We also circumvent the problem of testing for membership using a clever construction.

## The Algorithm

To fully understand how this algorithm works, it’s essential to have some preliminary knowledge of finite automata and regular languages. A regular expression defines a regular language $L$, and so do finite automata. We can therefore construct a finite automaton from a regular expression. To do so, we employ the help of the dk.brics.automaton package written by Anders Moeller from Aarhus University. The reason we use finite automata is that they have a lot of nice features – there are efficient algorithms to minimize automata and determine language membership of strings.

What we want, however, is not the language that is defined by the regular expression – we want to restrict the strings to have a length $d$ given some depth. Therefore we can compute the intersection of the automaton that accepts strings of length $d$ and the automaton which defines $L$. Next up, we’ll enumerate all strings in $L \cap \Sigma^d$ and store them in an array $M$.

Other than having an automaton $A_1$ which recognizes strings of length $d$ in $L$, we also want an automaton $A_2$ that recognizes all strings of length $d$ which aren’t in $L$ – this is just $L^c \cap \Sigma^d$. Because now that we have $M$, we want to assign the remaining strings recognized by $A_2$ distances and save the associated pixel information in our raster.

To do this, we perform a depth-first search of $A_2$, starting at some initial state $S$. This can be written in Java-like pseudo-code as:

process(State s, String currentString, int depth){
//Stop at end nodes
if(depth == max && s.isAccepted()){
int dist = getHammingDistance(s);
paintPixel(currentString, dist);
return;
}

//Otherwise, get all transitions and process them as well
for(Transition t : s.getTransitions()){
process(t.getDestination(), currentString+t.getChar(), depth+1);
}
}

The most obvious speed-up with this approach is that s.isAccepted(); is a cheap operation, whereas testing for membership of a string in a regular language has a worst-case time complexity of $O(e^n)$. The other advantage is that there is no reason to save all the Strings in an array, making it possible to make much larger images. To view the algorithm in further detail I encourage you to go read the source code for this project (there is decent documentation, so the code shouldn’t be too difficult to read).

## Gallery

While there are plenty of these images in the previous posts, I thought it’d be fun to share a few more of them.

# Faster Gradient Images from Regular Expressions

After releasing my last post, I got some amazing feedback. The user @nya had tried replicating my algorithm in c++ and got some amazing results! Not only did he get just as beautiful images as I did, he was able to do it *much faster*. The code I wrote was able to generate a 512px x 512px image in just about one hour – and @nya was able to generate a 1024px x 1024px image in roughly five seconds.

While I wasn’t able to replicate his results, I got some fantastic feedback from @j2kun who made me realize that my approach was wasteful. Generating all strings to find the edit distance between two strings generates a lot of overlap and wasted CPU cycles. Instead, inspired by his post on word metrics, I decided to rewrite my algorithm.

## The New Algorithm

For some depth $d$ (string length), first generate all $4^d$ strings and save them in some set $\mathcal{S}$. Then find all the strings that match the regular expression and save them in some set $\mathcal{M}$. Then compute the set difference between $\mathcal{M}$ and $\mathcal{S}$ to find the set of all strings that don’t match the regular expression $\mathcal{D} = \mathcal{S} \backslash \mathcal{M}$.

Then, for every string in $\mathcal{D}$ compute the minimum edit distance to any string in $\mathcal{M}$ (iterate through the array) and store this value in a table. Obviously, the minimum edit distance any string in $\mathcal{D}$ can have is 1, so when we find a string with a distance of 1, we break and give the string a distance of 1. We can write this is Java-like pseudocode as:

for(String s : D){

int dist = depth

for(String t : M){
if(levenshtein(s,t) < d)
dist = levenshtein(s,t)

if(dist == 1)
break
}

table.put(s, dist)
}

To find the actual source code used to generate the images, check out this project’s GitHub page.

For some depth $d$, note that this algorithm has time-complexity $O(e^d)$ as we have $4^d$ strings. This is extremely slow for large $d$ – but fortunately, we don’t need very large $d$, as $d=10$ gives an image with a size of 1024px x 1024px.

Although the apparent time complexity is very slow, it has much, much better performance than the old algorithm. While the old algorithm took an hour to produce a 512px x 512px image, this new algorithm can generate a 1024px x 1024px in less than a minute (varies depending on the size of $\mathcal{M}$ and the complexity of the regex). It still doesn’t match the performance of @nya’s algorithm, but it is still an impressive speed-up.

Just to show that the performance of this algorithm dwarfs that of the old one, here are some 1024px x 1024px images that took anywhere from 10 seconds to 5 minutes to produce:

# Gradient Images from Regular Expressions

The source code for this project can be found at its GitHub-page: https://github.com/SSODelta/GradientRegexImages

## Gradient Images from Regular Expressions

In one of my posts from last year, I detailed an algorithm for creating pretty fractal images based on regular expressions. While this idea wasn’t novel, it was still very interesting, and it was a challenge for me to code it. However, the other day I got a great idea – I had figured out a way to generalize this concept to (I presumed) create even more pretty images.

The problem with the old method was that it was binary whether or not a given pixel belonged to the regular language. This makes excellent sense from a computer science theoretical perspective, but when making pretty images it’s nice to have some variation. So instead of the binary approach, I’m going to allow pixels to have a certain distance to being a member of the regular language. We define that d=0 means that a pixel belongs to the regular language, and d=1 means that it has an edit distance of 1 to belonging to the language. We only use substitution as a transformation in this example, however, because we want all strings to have the same length

As an example, let’s consider the regular language 3*, and consider of strings of length 2. Obviously, the only string of length 2 that belongs to this language (and thus has d=0) is “33”. The strings of distance d=1 are the strings that can result in “33” after only 1 substitution. An example of this is the string “32”, which after changing the 2 to a 3 suddenly belongs to the regular expression. Likewise, an example of a string with d=2 is “11”, where both characters need to be changed for it to belong to the language.

## Determining the Distance of Every String

Like in the old post, we need to generate all strings of length n, check if they belong to the language, and then paint the image based on this information. In the old post, however, it was pretty straight forward checking if the strings belonged to the language or not. But in this approach, we’re faced with a far more complicated problem – how do we determine the edit distance of any one string?

To do so, we first generate all strings of length and then we check which of these strings belong to the language (we first find all d=0 strings) and remember them in a HashMap. Then we generate all variations of these strings. Obviously, any string which is a variation of a d=0 string must be at most a d=1 – so, using this set of variations we mark all the strings not previously marked with d=0 with d=1. We continue doing so until we’ve exhausted the list of strings (which must happen eventually, as any two strings of length are at most edits apart).

At each step, we remove all strings for which we’ve already determined its edit distance as keeping it would only generate copies. Also, we stop after d=n-1 and mark the remaining strings as d=n (again, because the maximum edit distance is n).

### Coloring the Pixels

After finding the edit distance of every string, we have an integer $d \in [0; n]$. We map this unto the interval $[0; 1]$ by dividing each edit distance with n. Next up, we associate some color 0xRRGGBB with 0, and another color 0xRRGGBB with 1 and give each pixel a color in this gradient.

### Performance

This algorithm is very, very slow though. I’ve not been able to generate any larger than 512×512 images on my laptop (my patience lasts about 1 hour), and I fear a 1024×1024 is impossible due to the time complexity of the algorithm. I’m sure there are many ways to improve the algorithm’s performance (dynamic programming, probably), but I’ve yet to find them. But if you find an improvement (or a mistake), feel free to leave a comment.

## Gallery

Here is a list of all images I’ve yet to render on my machine. It’s very difficult to generate massive amounts of images due to the complexity of the algorithm (as opposed to my post on Newton’s Fractals, where I have a gallery of 100+ images)

# How to Model the Wheels of a Slot Machine

Recently, in my IT class we had to create our own simple games as an exercise in programming. What I chose to make was a casino with a lot of slot machines in Unity. It was mainly an exercise in using Unity as I have little experience working with it. To demonstrate what I’m talking about, I made a small video showcasing the slow machines:

Now, what I want to talk about in this post is how to make the wheels of the slot machine stop at the right entries, so that we can easily program the slot machines to do what we want. Which means we can have a function:

rotateAndStopAtAngles(ANGLE_1, ANGLE_2, ANGLE_3);

Let’s assume that the wheels are already in motion and are travelling with an angle velocity of $\omega$. Let’s also assume that the wheels are affected by a constant acceleration when they’re stopping. This means that their time dependent angle velocity can be described as:

$\omega(t) = \omega_0 - \alpha \cdot t$

Where $\omega_0$ is the initial velocity of the wheel and $\alpha$ is the deceleration. Obviously we want the wheels to stop spinning, so we want to find the time $t_a$ which satisfies:

$\omega(t_a) = 0$

Which means we get the following expression for $t_a$:

$t_a = \dfrac{\omega_0}{\alpha}$

Now, what we want to find now is the angle $\theta_{start}$ where we start the deceleration of the wheel. Let $\theta_{goal}$ be the angle we want to wheel to stop on. Obviously, the total angle breadth travelled $\Delta \theta$ when decelerating is:

$\Delta \theta = \displaystyle \int_{0}^{t_a} \! \omega(t) ~ \mathrm{d}t$

Now, obviously we want $\theta_{start}$ to satisfy:

$\theta_{start} + \Delta \theta = \theta_{goal}$

Or written out in full:

$\theta_{start} + \displaystyle \int_{0}^{\frac{\omega_0}{\alpha}} \! \omega_0 - \alpha \cdot t$ $\mathrm{d}t$ $= \theta_{goal}$

Which allows us to get the following expression for $\theta_{start}$:

$\theta_{start} = \dfrac{1}{2} \cdot \dfrac{2 \cdot \alpha \cdot \theta_{goal} + \omega_0^2}{\alpha}$

And as you can see in the above video, it works! This is what I love about math – it’s such a powerful language for describing the world. Although, due to technical issues (*cough cough* floats) and due to the fact that computers work with discrete units rather than continuous units it doesn’t stop at exactly the right angle, but this is easily mitigated as you can see in the above video by sliding in at low speed to get it to stop just right.

# Storing the Images of Surveillance Cameras in Constant Space Using Infinite Geometric Series

I was recently in London – it’s a fantastic city and I loved my time there. However, I was completely baffled by the large amount of surveillance cameras in the city. Almost everywhere you go the Queen’s watching you.

While I won’t go into a debate on whether or not surveillance is a good thing, I do want to discuss the sheer amount of data these cameras must pick up on a daily basis. I mean, several cameras on every street recording video non-stop – that must be super expensive in storage. Is there any way we can circumvent this?

## The Naïve Solution

An often used solution to the storage problem is to delete all images older than X days. This keeps the storage space needed constant and ensures that the most recent (and most relevant) photo information is readily available to check if needed. The most obvious disadvantage here is that the old images get deleted completely, making forensics difficult if the crime was committedso early that the camera has deleted all the relevant images. In this post we’ll detail an algorithm which keeps track of all images the surveillance camera has saved, yet accomplishes it in constant space.

# Storing the Images of Surveillance Cameras in Constant Space using Infinite Series

For the sake of this post, let’s assume the surveillance cameras take still photos every X minutes. The reason for this is that this algorithm probably doesn’t work well with existing video codecs (or at least, I wouldn’t know where to start). Now, obviously we can’t just store an indefinite amount of high-quality images on a drive with a limited storage space, so what we’re going to do is let the old images degrade over time. That is, the older the images is, the worse quality it has.

This makes sense – we assume that the most relevant images are the most recent images. After all, why would the police need to look at 3 year old surveillance photos of a random gas station? (There certainly could be incentive to look at old images, but we assume it’s the recent photos that we need to have in the best quality).

## The algorithm

We’ll let the images degrade with a constant factor $r \in [0, 1]$ for every constant amount of images. That is, the first $n$ images are saved in quality $Q = 1$ where $Q$ represents how large a percentage of the data we’re keeping for the image, so $Q=0.5$ means that we have reduced the space by 50%. The next $n$ images are saved in quality $Q = r$, and the next $n$ images after these are saved in quality $Q=r^2$.

We’ll call the first $n$ images for the priority 1 images, the next $n$ images for the priority 2 images etc. If we assume all images require a maximum disk space of $S$, then obviously the total disk space $D$ for all priority 1 images is $D_1 = n \cdot S$. Likewise, the total disk space for all priority 2 images is $D_2 = r \cdot n \cdot S$. And in general for priority $p$ images, we get:

$D_p = r^{p-1} \cdot n \cdot S$

And for the first $k$ priorities we get the total disk space $T$:

$T_k = D_1 + D_2 + D_3 + ... + D_k$

Which can be written using sigma-notation:

$T_k = \displaystyle \sum_{i=1}^{k} D_i$

Expanding this, we get:

$T_k = \displaystyle \sum_{i=1}^{k} r^{i-1} \cdot n \cdot S$

Switching our terms, we get:

$T_k = n \cdot S \cdot \displaystyle \sum_{i=0}^k r^i$

To show that the total disk space is constant no matter how long we let our surveillance cameras run, we need to show that no matter how many priorities we sum up we’ll always remain bounded below some finite constant. That is, we look at the limit as we increase $k$:

$T_\infty = n \cdot S \cdot \displaystyle \sum_{i=0}^\infty r^i$

And since this is a geometric series, we get the following expression:

$T_\infty = \dfrac{n \cdot S}{1 - r}$

Which is finite for $n,S,r \in \mathbb{R}$ proving that the disk space required is constant with this approach.

## An example

Let’s say each surveillance camera has a total disk space of $T = 2 ~ \textrm{Gb}$ (2,147,483,648 bytes), and that each image is stored in the JPEG file format with size 480p (720 x 480). According to Wikipedia, a $Q=1$ image requires about 8.25 bits per color pixel, which means that each photo takes up $S = 348 ~ \textrm{Kb}$.

Assuming we take one image every minute from our surveillance cameras, and that we want the images to degrade on a daily basis (all images taken the same day are of the same quality), then $n = 1440$ images.

Finally, we can easily derive:

$r = 1 - \dfrac{n \cdot S}{T}$

Which means that  $r = 0.768$, which means that the images degrade roughly 23% in quality every day given this setup (obviously the parameters can vary, but this was just one example). Notice that this formula gives $r \notin [0,1]$ if $n \cdot S > T$. This makes sense because it implies that the priority 1 images themselves take up more disk space than the surveillance cameras (which is of course impossible).

I’m not sure how practical this would be to implement, but I found the thought interesting at least.