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 -gon (called depth ) drawn with its center at the origin , and from each of its vertices, we draw another regular n-gon (it does not need to be the same for every depth). These new polygons have center at the vertices of the old polygon and have depth , and in general a polygon at depth will have children of depth . We continue doing this process until we’ve reached the specified fractal depth, giving us images such as (shown from depth to ):
Note that this image uses triangles, rather than the more general -gon. This is because the math is pretty much the same for any , 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 -gon the empty string . Its children will be appended the characters , meaning that the children of the root node are called . The children of the polygon represented by the string will likewise be appended these characters, and thus be called . Adding these labels to the above drawing yields:
Note that the length of the string is directly related to the depth of the polygon represented by that string, that is for some fractal depth . For a constant polygon degree throughout the fractal, we will have a polygon for every possible string . Thus we’ve reduced the problem of determining which polygon to draw to choosing a language and drawing all the polygons represented by the strings in . Please note that since the polygon degree isn’t necessarily constant, we can’t be sure that all such strings 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 we draw all polygons represented by all the strings in . Shown here is the regular expression 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 , 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” and rotation . 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:
And in general,
Where is the -th vertex.
Now, assume we have some polygon at depth represented by some regular expression , and we want to know the position of its vertices. We know the origin of this polygon is given by the polygon at depth . This other polygon is naturally represented by the regular expression , so its position is . We know the character represents which vertex we have (0 being the first vertex, 1 being the next vertex etc.). Therefore, we can write the following recursive relation:
Where is the radius for the polygon represented by , and is the angle – these will be investigated later. This recursive relation has the base-case 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 to denote the radius of the polygon represented by the regular expression , 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 to be larger than . Therefore, we can assume that the argument for is a number, so we have . Obviously, we want to be the largest radius (for the root polygon), and we label this , so . We also want this function to be strictly decreasing as , so for every . Finally, we want to structure we’re designing to be a fractal – it should converge towards the same points as .
Note that the maximum distance from the origin that the first polygon can get is , and therefore the maximum distance any polygon at depth can get from the origin is and so on… Therefore the maximum distance any polygon at an arbitrary depth can get is . And since we want our fractal to be finite we require this sum to be finite, that is:
For some finite constant . This looks an awful lot like infinite geometric series. While it’s not the exclusive solution for , it is a possible one giving us the following expression for :
For some constant . 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 and now we’ll do the same for . Using a similar argument as in the previous section, we want the argument of to be the length of the regular expression . 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 :
Where 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 of a polygon represented by the regular expression :
I’ve split it into two lines for x and y 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();.