Incendium – Making fractal animations


Udklip

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):

naming_regex_tri_noname

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:

naming_regex_tri

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:

naming_regex_tri_only1

Where do we draw them?

single-polygon

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

Advertisements

One thought on “Incendium – Making fractal animations

Comment on this article

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s