# Trees

First, lets ask ourselves: "What is a tree?" Well, go outside and have a look at one. You will see that most trees have the same basic structure:

Trees are made up from a big trunk of wood with stuff at the top. OK, thats very nice. Stuff. Well What is stuff? Look at your tree a little bit closer. The trunk has these things sticking out of the top of it. These things have a similar structure:

Aah, cunning. Notice that the stuff has the same structure as the main bit of the trunk, but there are more of them, and they are all smaller. That's exactly what a tree is. It is a trunk which branches off into a couple of smaller trunks which themselves branch off into smaller branches. This process could go on forever, but then there would be no leaves. The branching stops eventually, terminating with leaves.

There you see it's starting to look much more like a tree. As you keep adding on more and more branches, it gets more tree like. Notice here that the number of branches doubles every time. It first branches twice, then the two branch twice each, thats four. Then those four branch to produce eight and so on. Making trees can be a very memory consuming business. But how do you actually produce them? how do u actually write some code? . . . lets find out . . .

## Recursive functions

Right, now you may or may not have heard of these. I'll have to assume you have not. If you have, then is should be pretty obvious how the tree will be constructed.

A recursive function can call itself. WHAT!? But how? Won't that just go on forever?
Alright, calm down already. I'll tell you:

A recursive function needn't call itself forever, It will call itself if it needs to. What you do is to have a procedure called BRANCH or something. You call it once, telling it to produce a trunk of a certain size angle, and position. It produces the trunk (ie draws it, or makes a 3 dimensional model of it), then it calls itself twice telling itself to produce 2 branches a bit smaller at the end of the trunk and at some angle. It goes something like this:

PROCEDURE branch(position, size, angle)
Construct the trunk
If we want another branch then:
{
call branch(at_the_end_of_the_trunk, smaller_size, angle + a_bit)
call branch(at_the_end_of_the_trunk, smaller_size, angle - a_bit)
}
END OF PROCEDURE

So when we run this procedure, we get a tree which looks something like this. This thing which looks more like an anorexic broccoli than a tree. This is because this is exactly how God makes broccoli. By recursively sub-dividing branches, until they get to a certain size, then sticks some lump of green stuff on the end.

First thing you might want to do is to add some thickness to the branches. Still looks like a broccoli, but at least it's got some body.
Right. All trees are different. I haven't actually checked this. I have better things to do than go around comparing all the trees in the world to see if there are any two exactly alike. I'm just guessing. So to make the tree looks more realistic, add some randomness to the angle that the branches branch at. Dunno about you, but I reckon that looks much more like a tree.
Next thing to do is to break out of the constant branching by two every time. In this tree, the branches split once at the end, and sprout one branch from the middle.
This time the size of the branches is not always the same. If you have a close look at a branch, you might notice that the main bit of the branch stays straightish, and occasionally sprouts a little branch. The main branch bends away from the sprout and gets a little bit smaller. The bigger the sprout, the smaller the main branch gets and the more it bends. I modeled this by branching by two each time, and keeping the angle between the two branches the same. However the angle they make with the main branch can vary. The size of the new branches depends on the cosine of the angle between it and the main branch. Um, is that confusing? I'll do a picture.
You can see that the new branches are always 90 decrees apart, but they can both rotate relative to the trunk. The one that is most parallel to the trunk is biggest.

OK, so lets see what the pseudo code looks like with all that stuff above added in.

PROCEDURE branch(position, size, angle)
Construct the trunk
If we want another branch then:
{
branch_angle = random number betwen -1 and 1
branch1_angle = branch_angle + 45 degrees
branch2_angle = branch_angle - 45 degrees

branch1_size = size * cos (branch1_angle)
branch2_size = size * cos (branch2_angle)

call branch(at_the_end_of_the_trunk, branch1_size, branch1_angle)
call branch(at_the_end_of_the_trunk, branch2_size, branch2_angle)
}
END OF PROCEDURE

As you may have guessed, this is rather an over-simplification of a tree. There are a lot more things going on in a tree that require a slightly more complicated model. Each species of tree also needs a slightly different model.

Firstly you might notice that the branches in the last tree up there seem to go in whatever direction they like. If you look at a real tree, you will see that often the branches are inclined to point upwards. In some trees, the branches near the top of the trunk tend to point skyward, whereas the ones near the bottom stick out sideways. Weeping Willows however, tend to droop a lot. I will try to explain how to make droopy trees, and trees that can sway and bend in the wind later, but for now there is the very difficult task of making trees in 3D.

There are two ways that I can think of describing trees in 3D. Polar and Vector.