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

Newton’s Fractals – Generating Images from Roots


img1

Fractals have always amazed me. Every time I see a fractal, I can get just as excited as the first time I saw the mandelbrot set. In this post, we’ll go through a method, which can generate beautiful structures from simple functions.

Link to the source code for this project: https://github.com/SSODelta/newtons-fractals

For a real-valued function f(x), a root is any x, which satisfies f(x) = 0. A trivial case might be x=0 for the function f(x) = x^2. Roots are also what is found with the famous solution \frac{-b \pm \sqrt{D}}{4\cdot a \cdot c} to the quadratic equation f(x) = a \cdot x^2 + b \cdot x + c.

Sometimes however, a second degree equation does not have any real solutions. That is when D < 0. A quadratic equation will, however always have two solutions in the complex plane.

The complex plane is an extension of the real number line to a plane. The major new addition is the introduction of the imaginary unit i, which is the unique number satisfying i^2 = -1. This allows us to find solutions to equations such as x^2 = -1, which otherwise wouldn’t have any real solutions. In the complex plane every single point has a unique complex number associated with it. A complex number consists of two parts, a real part and an imaginary part. This is usually stylized a + b \cdot i, where a is the real part and b is the imaginary part.

What does all this have to do with fractals?

To make a fractal, we need to assign a color code to each point in a plane, in this case the complex plane as discussed above. We decide on an initial size (w, h) and a resolution r. The size is the width w and height h of an image measured in pixels. The resolution r is the “zoom-factor”, if you will. If r=1, then we’ll deal with complex numbers a + b \cdot i in the range a,b \in [-1, 1]. And in general a,b \in [-r, r]. To make it clear how to combine roots and points in the complex plane to make fractals, we need to introduce a very important method.

Introducing, Newton’s approximation for finding roots to a real-valued function (although it extends nicely to the complex plane, fortunately). For a function f(x) and an initial “guess” x_0, a better guess will be x_1 = x_0 - \frac{f(x_0)}{f'(x_0)}, where f'(x) is the derivative of f(x). In fact, this can be generalized to the recursive formula x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}. So how do we make fractals?

  • Have a function f(x), a size (w, h) and a resolution r.
  • Assign a unique color to each root to f(x).
  • For every point P(x, y) in the image, make an inital guess x_0 = (-r + (\frac{x}{w}) \cdot 2r, (-r + \frac{y}{h}) \cdot 2r).
  • Use Newton’s approximation method to approximate a root as long as x_{n+1} - x_n > \epsilon.
  • Color the pixel P(x, y) the color which is assigned to the root which has just been approximated.

In practice, we’ll only deal with polynomials, though, because they’re easy to calculate and to calculate the derivative of.

Using this method gives us some stunning images:

fractal_6 fractals_38 fractals_43 hd_6 hd_12

Link to an album with more than 100 HD fractals: http://imgur.com/a/xOFyF#0

As a little extra feature I have also colored the points which converge faster darker as to create some variation in the images.

Inspiration for this post: http://www.reddit.com/r/math/comments/25nhy8/beautiful_symmetry_in_solving_x310_with_newtons/

Creating Colored Images from Regular Expressions


Note: This post creates some cool colors, but to see something truly stunning, check out dln385’s images, inspired by these posts.

In my last post, I detailed an algorithm for generating images using regular expressions. However, I found them a tad boring and mundane, so in this post I’m going to add colors to the images.

We follow exactly the same algorithm for choosing where to color the pixels, but we need a method to decide what color to paint. To accomplish this, we introduce three colors channels C, M, Y which are basically a long string, composed of the same alphabet as the areas (0, 1, 2, 3).

For each string S (area) do the following:

  • If S matches the regular expression, mark it as painted.
  • Define a blank color CMY(0, 0, 0).
  • For each color channel, xor the string accompanying the channel, and if it matches the regular expression, change the color channel from 0.0 to 1.0.

Let’s do an example. Let R be the regular expression (1+2+3)*0(1+3)*0(0+1+2+3)*.

Let the following be the color channels C,M,Y:

  • C – 032102
  • M – 033122
  • Y – 132212

If we test the string S = 330100, we find it matches, so we must paint it.

Calculate S XOR C = 330100 XOR 032102 = 302002, which matches the regular expression, so the cyan color channel is 1.0.

Calculate S XOR M = 330100 XOR 033122 = 303022, which also matches the regular expression, so the magenta color channel is also 1.0.

Calculate S XOR Y = 330100 XOR 132212 = 202321, which does not match the regular expression, so the yellow color channel is 0.0.

This means we paint the area, marked by the string 330100 with the CMY-color (1, 1, 0).

Here is a visual example to showcase this new method:

test

You can also do AND instead of XOR, it produces images like the following:

test2

It’s obviously less visually stunning, but still interesting. Here is OR instead:

test2

It’s also less visually diverse, but still cool to look at.

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:

img1

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.

img2

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:

img3

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

test

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

really_large_triangle_fractal

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:

also-cool-fractal bars  dots pik

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/