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:
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:
It can also be used to generate interesting animations such as this:
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
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).
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.
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)
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).