I am still totally into fractal geometry. I was all about fractals before they were cool, I was all about them when everyone on the planet (including me!) had a fractal tie-dye T-shirt, and I'm still all about them. It's the order, the disorder, and the beauty. This is also why I'm marrying Kim.
Back in High School, I was in need of a science fair project. My Dad turned me on to an article in a 1985 Scientific American magazine, from A.K. Dewdney's (best name ever) column Computer Recreations. It's hard to believe now, but back then, 1985 was the near past. The article was on the Mandelbrot set. With this article, and lessons from Dad on complex numbers, I was able to make a rudimentary program in QuickBASIC that drew the Mandelbrot set. It was slow.
To this day, I still re-write this program whenever I'm trying to learn a new programming language. It gets a little fancier every time. The one I wrote last year for the Mac in Objective-C with the Cocoa API is the fanciest. It uses separate scaling and computation threads to take advantage of modern multi-core processors. Kim and I talked about using images from this one to do the save-the-date cards. But, it was, like, weird. It didn't go at all with the obviously fall-themed wedding.
But trees would! I had always wanted to try my hand at some fractally trees. Thankfully, Kim was patient with me.
Early experiments with L-system trees produced rigid, super-regular results (example from processing.org.) Not at all what we wanted.
So, I struck out on my own. I looked at a lot of real trees. I looked at a lot of pictures of trees on flickr. I read a lot of papers about how trees grow, and about forestry management(!), and pruning.
Kim and I were going for a tree silhouette. I thought I could get away with an entirely two-dimensional simulation. My first crack at this is a frizzy little number. His branches taper as 1/sqrt(x) towards their tips, and the distance between branches drops the same way too. It's better than the L-system one, but still, this is not what a tree looks like. The branches happen in about the same place every time. The limb taper is OK, but the branches aren't right. It's not real.
From the get-go, even this tree had some of the fundamentals: The trunk and branches turn and twist as they're growing. Where they're thicker, their movement is limited. At the tips, they're free to move quite a bit. And, branches get closer together the nearer they are to the tips of the branch where they came from.
Shooting for a quick win, I developed a tree that at each branching interval would decide whether it would branch left, right, or both. The result was striking. For a long time, my algorithm could do only worse than what you can see to the right. The good part about this is that it really looks like a tree. The bad part is that the more you stare at it, the more the problems become evident. The angles were too constrained, and way too two-dimensional. Branches clearly sprouted to the left and to the right; never to the front and behind.
I knew I had to migrate to three dimensions to get all this right. Before going whole hog, I tinkered. We knew we wanted leaves, so I tried one that had a kind of leaf skeleton, or a star at the end of each branch. The colors were chosen randomly from a range in the oranges and yellows. From a distance, interesting, but it didn't hold up to scrutiny.
One day, I printed out an outline of a large maple leaf. I sat down with paper, pencil, and a protractor (seriously), and drew up the smallest set of vectors that I could use to represent the leaf. I jammed one of these at the end of every branch, and it wasn't too bad. Rigid, but getting there.
The transition to 3D was not simple. I was doing everything in polar coordinates in 2D. Going to 3D with spherical coordinates was brain hurty. To ease my frustrations, I ended up developing a test application with rotatable axes so I could visualize what I was trying to do.
The result? A mess! But... an organic-looking mess!
The worst part of the conversion to 3D was getting the branching angle right. I ended up with two parameters: once a location is selected for a branch, it can sprout randomly anywhere on the circumference of its trunk. And, it leaves the trunk at a random angle uniformly distributed between 30 and 70 degrees. This area is shown with the green dots in the test program screen shot above. Note the hole in the middle of the distribution between 30 and 0 degrees; this keeps the branch from getting all up in the trunk's junk.
Also, for these trees, the distance between branches drops off faster towards its end. After staring at lots of trees, and trying various functions, I settled on L = sqrt(A-Bx^2). The actual distance to the next branch is chosen randomly from Gaussian distributed numbers centered around L, with a standard deviation of 1/3 L.
When a branch forks off, it can be between 25% and 75% of the diameter of the larger branch it left behind. One paper I read had this figure at 25% to 50%.
When a branch leaves, the diameter of the branch it left behind is reduced going forward such that the cross-sectional area is conserved. In other words, if you have a branch, and then it forks like a "Y", the cross sectional areas of the two tines add up to the cross sectional area of the branch leading up to the fork. Incredibly, this observation comes from one of Leonardo Da Vinci's notebooks!
If a branch off of the trunk takes too much of the area, it can become a co-dominant leader. This makes a weaker tree that doesn't grow as tall. But, it'll definitely look funkier!
I made the discovery that branches affect the trunks where they leave. When a branch forks off, it pushes the trunk where it left away from it, altering the angle that the trunk grows. There's a lot of fudginess applied to how much it pushes. Too much, and there are branches going everywhere. Too little, and the tree looks very artificial.
There's one key hack for on branches that come from the main trunk. It remembers where the last few branches came off, and avoids putting a new branch on top of an existing one. This simulates how real trees grow, with each branch fighting for sunlight. It helps balance the tree, and spread it out. Before I did this, I'd frequently get trees that were crazily imbalanced, with all the branches coming out of the left side.
I came up with a simple way of faking phototropism (how plants grow towards the sun). The edges of the tree bend up more than the parts near the trunk. Only, Kim and I found we almost preferred the droopier trees we got when the phototropism vector pointed down towards the ground!
These trees are also the first to have leaves with actual stems! Each leaf hangs from the tip of a branch by a stem that curves slightly downwards. I made the curve by applying a little gravity to each of three segments of the stem.
Don't tell anyone, but the leaf transformations are all 2D hacks. It's just enough to make the leaves look different, so you don't see them all face on.
Finally, here's the tree we used for the save-the-date invitations. Sure, it's not really a maple, but it's interesting!
The applet at the top of this page (and on the splash screen) starts out in a "demo mode". If you turn off the demo, you can interact with the applet and change most of its crazy parameters. To start this, click on the applet to bring it into focus. Type the character 'd' to leave demo mode, and then 'h' to bring up the help menu with the list of keys. If you can't remember the commands, you can launch the keys in a separate window.
|Controlling the tree applet|
|g and G||control the number of generations that the tree grows. Make it bigger with "G", and smaller with "g". When you increase the generation, the tree gets more complex.|
|w and W||control the width of the tree at the base.|
|l and L||control the base length of each generation. Making it bigger makes the tree grow more each time. This is different than "generation" which makes the tree get more complex.|
|n or space or mouse click||grow a different tree: choose a new random seed|
|p and P||Set the phototropism vector. Positive numbers point down (don't ask). Stuff in the range of 0.2 to -0.2 seems best.|
|u and U||Sets how hard the branches pull away from the trunk. 0.1 is probably the most reasonable setting for this.|
|y and Y||When a branch happens, other branches might happen right around the same point. This controls the likeliness that it'll happen.|
|e and E||Set the base distance between branches. It'll shrink as you get to the end of a branch. This is the maximum.|
|f and F||control the size of the leaves.|
|r and R||set how red the leaves are.|
|a and A||This control sets how high up the trunk the first branch comes off.|
|m and M||Use this to set the maximum ratio of a branch's diameter to its trunk. 1.0 means that the branch can have the same diameter as its trunk.|
|v||toggle leaves on and off.|
|&||reset to default settings. (turns demo mode back on too)|
|h||toggle the help text on and off.|
|delete or backspace||go back to the prior tree's random seed.|
1985. A computer microscope zooms in for a close look at the most complicated object in mathematics, A.K. Dewdney, Computer Recreations, Scientific American, Aug: pp.16-24
Stem Length and Diameter Taper Limits Coder, Kim D. Tree Biomechanics Series, University of Georgia, September, 2000.
Size-dependent Allometry of Tree Height, Diameter and Trunk-Taper. Niklas, Karl J., Annals of Botany 75: 217-227, 1995.
Tree Structure Presenation. Gilman, Edward F., Department of Environmental Horticulture, University of Florida.
Search for "tree silhouette" on flickr.com.
L-system tree applet from processing.org.