For just a bit of fun, I’ve been working on a repeating pattern generator which can generate fractal-like-structures. Currently the generator begins with one node, generates two children attached to the first, and then two children attached to those nodes, and on and on; it creates a tree like structure. The process looks like this:

4 levels generated using default settings

This can be continued forever, however, I’ve created an input that limits the number of layers or levels of the tree. This generates quite interesting patterns like:

Interesting Rendering

or

Interesting Rendering 2

It can also be used to generate interesting animations such as this:

Simple Animation

Implementation

The implementation for this is fairly straight forward if done recursively; in pseudo-code:

func processNode(inputNode)
    drawLine
    drawCircle
    if (inputNode.level < MaxLevel)
        child1 = new Node(child1Location, inputNode.level + 1)
        processNode(child1)
        child2 = new Node(child2Location, inputNode.level + 1)
        processNode(child2)
    endif
end

This code would execute fine, however, for large numbers of recursions, this will quickly fill up the available stack space and eventually crash the program. For this we can convert it to a more iterative approach. I chose to place all nodes in a queue as they are generated and to pull from the queue constantly. This provides an easy way to save the children nodes as well as removes the recursive nature.

Below is the core of the logic, you would add a first node to the queue at the beginning and then run processNodes continuously until all nodes are processed.

func processNodes()
    node = nodeQueue.dequeue()
    if (node.level < MaxLevel)
        DrawNode(node)
        children = GenerateChildren(node)
        nodeQueue.add(children)
    endif
end

Code Details

I originally chose javascript for portability reasons. I found javascript to be a pretty good language for this application, however, I wanted to try to make a faster program. I switched to WPF with C# to speed it up. However, the usual way of drawing things in WPF is to use FrameworkElements, which doesn’t work for large number of elements. Then I tried the DrawingVisual and DrawingContext which is the next best way to render images. This too was much too slow with large amounts of drawing calls. I considered Direct 2D but ultimately chose to draw directly to bitmaps because this seemed a little more straightforward.

I found a NuGet package called WriteableBitmapExtensions which adds a few very handy extensions to the WriteableBitmap class. I implemented the code close to the above pseudo-code. First, I executed the processing function on a timer interrupt. This wasn’t efficient enough, so I threw the processing into an infinite loop on a background thread, which uses the dispatcher to put any UI calls onto the UI thread. This resulted in much much better performance then Javascript, FrameworkElements, or DrawingVisuals implementations.

For more info on the performances: WriteableBitmap executes around 100x faster than when I used Javascript. Javascript performs about 10x better than DrawingVisuals. DrawingVisuals performs about 2x better than FrameworkElements. This makes a certain amount of sense since DrawingVisuals and FrameworkElements draw at a very high level with low optimizations.

TL;DR start here:

After finding a speedy way of drawing (with writable bitmaps in C# WPF), I moved onto putting the work into more than one background thread. This wasn’t too difficult, but required moving a lot of the global variables to local variables that are passed into other functions. The program uses nearly 100% of all my 8 CPUs on my desktop with around 95% of the program’s computations going to the drawing calls. I was able to render 2^26 nodes in only a minute or two (that’s over 67 million nodes).

Conclusion

This isn’t as good as I would expect with say Direct2D or another more optimized solution. However, this was a lot of fun and was a good way to practice optimization and multi-threading. I’ve found myself spending quite a while messing with the settings finding interesting patterns.

Source Code

I’ve included the source code below. As this is not a large project, I was willing to break some best practices to speed up development; very little “proper” design patterns were used. Feel free to use and modify the code.

Fractals.zip (Click link, look for download button on the top right)

Future?

If I work more on this, I’m would like to create an automated way to generate large numbers of frames. Something to the effect of having a start frame with certain settings, an end frame with certain settings, and an option for the number of in-between frames (n). The program would generate n frames and save them to a specified folder. Long animations could be created quickly and easily (the above animation took absolutely forever).

Another possible next step would be to use/make a more optimized way to draw shapes and lines as the draw calls do not seem to be as efficient as they could be (and they aren’t using the GPU).