Pure Math 370 - Chaos & Fractals Final Project
Infinite Binary and Trinary Fractal Trees and Leaves
Erika Harrison
A final course project for PM 370 - Chaos & Fractals visualizing binary and trinary trees derived from recursive, and fractal-based deviations.
Infinite Binary Fractal Trees
Basic Idea: One stem has two branches extending from one end at varying angles, and varying scaling factors, as compared to the original stem.
Binary Fractal Trees can generate the binary tree as often described in Computer Science theory, and display visual representations. If there is a finite set of iterations, then then a complete tree is formed (ie. the number of branches from the root to any node is the same for all nodes). As demonstrated by the above images, Binary Fractal Trees can generate common fractal-like images, including the notorious Sierpinski's triangle, and a fairly interesting fill-in graph (given an infinite number of iterations, a rectangular shape will be filled in, as shown in class).
Given the extensive experience in binary tree structures from other courses, binary trees are fairly straightforward to implement.
A tree consists of it's own branch, and pointers to it's two child trees. The tree stores the angles and scaling factors for each of the child trees, and creates the branch for each child tree (at least in this implementation).
The most complex part is actually determining where what the two child branches look like. ie. How they're positioned based on the scaling and rotation. With a little bit of adjustments, this too is fairly straightforward.
After recognizing that the most common numeric-representations of a vector considers the vector to be positioned at the orgin, one can transform the parent branch to the origin, rotate and scale it by the rotation matrix:
and then translate it away from the origin to where it should be positioned.
Infinite Trinary Fractal Trees
Basic Idea: One stem has three branches extending from one end at varying angles, and varying scaling factors, as compared to the original stem.
You'll perhaps immediately notice that a trinary - three- branched tree - is as flexible as a binary tree. If the scaling factor on one of the branches is set to 0, then it has no effect on the iterative function, and therefore becomes a binary fractal tree, as described above.
The added flexibility - or third arm - of the trinary fractal trees allows for more leaf-like structures. In nature, the stem extends past the first two branches in many instances. Rarely does one walk down the tree to see all trees split exactly in two once branching occurs. Instead the trunk extends up to the top of the tree, or leaf. As displayed in the images, this creates a more natural leaf-like function. (The basic branching image in the binary images is more common to cauliflower, or parsley, where the stem discontinues at branching).
Modification to the actual application is minimal though, since it just requires an additional sub tree in the tree implementation.
As a quick aside, the grid pattern can be created through a binary tree, but the ability to generate the grid through a trinary tree occurs in fewer iterations than that needed by a binary equivalent.
Leaves
Basic Idea: Given that the basic structure of a leaf can be formed from binary and trinary fractal trees, it isn't too much of a stretch to add a boundary to the iterations and generate actual leaves, or at least their outlines.
From CS370 - Numeric Computation - I was introduced to spline- producing methods. ie. How to produce smooth lines given a number of points. In a graph, a line of best fit is often generated. An expansion from a linear line of best fit is various smooth-line constructs. Here, we use a bezier curve.
With the end points given, and various constraining interior points to get close to, but not necessarily go throough, we can generate (although I use the help of OpenGL) a smooth bezier curve. The end points in the leaves are the different node/leaf- end points. An additional end point would normally be the bottom of the stem, however as a leaf surface doesn't usually start at the base of the stem, I've chosen to start the outline half- way up the stem. The control points, or interior points are those situated, through an ordered tree traversal (the self node being counted both before and after the subnodes are calculated), between two end points.
In English, take a look at one of the leaf images. There is a smooth line between the inital point on the stem, and the first end-point node. Similarly, there's a smooth line between it and the next end point node, going clock-wise around the leaf, and finally getting back to the starting stem node.
Through random trial and mucking about, some additinally outlined images were generated, which appeared kinda neat.
December 9, 2005